Game Slide 最近の更新履歴 yyasuda's website

Introduction to Game Theory

Advanced Microeconomics II

2 0 0 9 /0 6 /1 1 I nt roduc t ion t o Ga m e T he or y 1

What is Game Theory?

•

Game theory is a field of Mathematics, 

analyzing strategically inter‐dependent

situations in which the outcome of your 

actions depends also on the actions of others

actions depends also on the actions of others.

–Is strategic thinking really important?

2 0 0 9 /0 6 /1 1 I nt roduc t ion t o Ga m e T he or y 2

Is strategic thinking relevant?

• In price theory, the market outcome is derived by the  intersection of the demand curve and the supply  curve. (demand‐supply analysis)

• There is no strategic inter‐dependence in its  framework.

Q: What’s the underlying assumption? A: Each economic agent is a “price‐taker.”

The birth of Game Theory

Q: Are most of problems in Economics indeed 

mere applications of “constrained 

optimization”?

A: NO!

von Neumann and Morgenstern (1944)

“We need essentially new mathematical theory 

to solve variety of problems in social 

sciences.”

2 0 0 9 /0 6 /1 1 I nt roduc t ion t o Ga m e T he or y 4

Strategic Thinking: Example

Example: Nintendo vs. Sony

• Nintendo’s action depends on how Nintendo predicts  the Sony’s action.

• Nintendo’s action depends on how Nintendo predicts 

h S di h Ni d ’ i

how Sony predicts the Nintendo’s action.

• Nintendo’s action depends on how Nintendo predicts  how Sony predicts how Nintendo predicts the Sony’s  action.

and so on… (this is called “infinite regress”)

2 0 0 9 /0 6 /1 1 I nt roduc t ion t o Ga m e T he or y 5

Revolution by Game Theory

• Game theory can solve the problem of strategic  inter‐dependence by pinning down how to predict  other players’ action.

Th f h

Therefore, game theory

• Provides us tools for analyzing important economic  phenomena beyond market economy (with perfect  competition).

• Enables us to compare different resource allocation  mechanisms.

New Areas Pioneered by Game Theory

• How does economy function if market is immature or not  existing?

– Economic History, Development Economics

• How do governments behave? Political Economics

– Political Economics

• What’s going on inside private companies? – Organizational Economics

• How to compare different types of market economy? – Comparative Institutional Analysis

2 0 0 9 /0 6 /1 1 I nt roduc t ion t o Ga m e T he or y 7

Discovery by vNM

• Any social problem can be formalized as a “game,”  consisting of three elements:

Players: i=1,2,…,N i’s Strategy: gy s_i

_

Q: What’s the solution of games?

 They failed to establish a general solution concept…

i i

)

,...,

(

i

^{s s}



2 0 0 9 /0 6 /1 1 I nt roduc t ion t o Ga m e T he or y 8

Nash Equilibrium

John Nash: “A Beautiful Mind” (movie) 

• The solution of games must satisfy the following  criterion.

Nash equilibrium(mathematical definition):

) , ( ) ( ,

) ,..., (

*

*

*

* 1

*

i i i i

i N

s s s

s i

s s s













Interpretations of NE.

•

No one can benefit if she unilaterally changes 

her action from the original Nash equilibrium.

–NE describes a stable situation.

•

Everyone correctly predicts other players’ 

actions and takes best‐response against them.

–NE serves as a rational prediction.

2 0 0 9 /0 6 /1 1 I nt roduc t ion t o Ga m e T he or y 1 0

Rationality Question

Q: Does NE heavily depend on rationality of players? A: Not necessarily so.

Example: NE in Evolutionary Biology

Strategy = “phenotype” : a character of each animal  determined by its gene

Payoff = “fitness” : a number of the offspring

• NE is a stable situation reached not by rationality but  by evolutionary dynamics.

2 0 0 9 /0 6 /1 1 I nt roduc t ion t o Ga m e T he or y 1 1

Existence Question

Q: Does NE always exist?

A: Yes (in almost every cases).

Theorem (Nash, 1950)

“There exists at least one Nash equilibrium in 

any finite games in which the numbers of 

players and strategies are both finite.”

Impact of Nash

“Soon after Nash’s work, game‐theoretic models  began to be used in economic theory and political  science, and psychologists began studying how  human subjects behave in experimental games. In  the 1970s game theory was first used as a tool in g y evolutionary biology. Subsequently, game‐ theoretic methods have come to dominate  microeconomic theory and are used also in many  other fields of economics and a wide range of  other social and behavioral sciences.” 

(from An Introduction to Game Theory by Osborne)

2 0 0 9 /0 6 /1 1 I nt roduc t ion t o Ga m e T he or y 1 3

Games in Two Forms

•

Static games

 The 

•

Dynamic games

 The 

representation

•

In principle, static (/ dynamic) games can also 

be analyzed in an extensive‐form (/a normal‐

form) representation.

2 0 0 9 /0 6 /1 1 I nt roduc t ion t o Ga m e T he or y 1 4

Normal‐form Games

The normal‐form (strategic‐form) representation 

of a game specifies:

1 h l i h

1. The players in the game.

2. The strategies available to each player.

3. The payoff received by each player (for each 

combination of strategies that could be 

chosen by the players).

Static Games

• In a normal‐form representation, each player  simultaneouslychooses a strategy, and the  combination of strategies chosen by the players  determines a payoff for each player.

• The players do NOT necessarily act simultaneously: it

• The players do NOT necessarily act simultaneously: it  suffices that each chooses her own action without  knowing others’ choices.

 We will also study dynamic games in an extensive‐ form representation later.

2 0 0 9 /0 6 /1 1 I nt roduc t ion t o Ga m e T he or y 1 6

Example: Prisoners’ Dilemma

• Two suspects are charged with a joint clime, and are  held separately by the police.

• Each prisoner is told the following:

–If one prisoner confesses and the other one does not, p , the former will be given a reward of 1 and the latter will  receive a fine equal to 2.

–If both confess, each will receive a fine equal to 1. –If neither confesses, both will be set free.

2 0 0 9 /0 6 /1 1 I nt roduc t ion t o Ga m e T he or y 1 7

Payoff Bi‐Matrix

Player 2 Player 1

Silent Confess

Silent 0

0

1 2

0 -2

Confess -2

1

-1 -1

How to Use Bi‐Matrices

• Any two players game (with finite number of  strategies) can be expressed as a bi‐matrix.

• The payoffs to the two players when a particular pair  of strategies is chosen are given in the appropriate  cell

cell.

• The payoff to the row player (player 1) is given first,  followed by the payoff to the column player (player  2).

 How can we solve this game?

2 0 0 9 /0 6 /1 1 I nt roduc t ion t o Ga m e T he or y 1 9

Definition of Nash Equilibrium

Nash equilibrium(mathematical definition)

• A strategy profile s* is called a Nash equilibrium if  and only if the following condition is satisfied:

• Nash equilibrium is defined over strategy profiles,  NOT over individual strategies.

) , ( ) ( ,

*

*

i i i i

i

s s s

s i











2 0 0 9 /0 6 /1 1 I nt roduc t ion t o Ga m e T he or y 2 0

Solving PD Game

• For each player, u(C,C)>u(S,C) holds. –(Confess, Confess) is a NE.

• There is no other equilibrium.

• Playing “Confess” is optimal no matter how thePlaying  Confess  is optimal no matter how the  opponent takes “Confess” or “Silent.”

–“Confess” is a dominant strategy.

• The NE is not (Pareto) efficient.

–Optimality for individuals does not necessary imply  optimality for a group (society).

Terminology

Dominant strategy:

• A strategy s is called a dominant strategy if playing s  is optimal for anycombination of other players’  strategies.

Pareto efficiency:

• An outcome of games is Pareto efficient if it is not  possible to make one person better off (through  moving to another outcome) without making  someone else worse off.

2 0 0 9 /0 6 /1 1 I nt roduc t ion t o Ga m e T he or y 2 2

Applications of PD

Examples Players “Silent” “Confess”

Arms races Countries Disarm Arm

International trade polic

Countries Lower trade barriers

No change

trade policy barriers

Marital cooperation

Couple Obedient Demanding

Provision of public goods

Citizen Contribute Free-ride

Deforestation Woodmen Restrain cutting Cut down maximum

2 0 0 9 /0 6 /1 1 I nt roduc t ion t o Ga m e T he or y 2 3

Example: Coordination Game

Player 2 Player 1

Windows Mac

Windows 1

1

0 0

1 0

Mac 0

0

2 2

Solving Coordination Game

• There are two equilibria, (W,W) and (M,M). –Games, in general, can have more than oneNash 

equilibrium.

• Everybody prefers one equilibrium (M,M) to the  other (W,W).

–Several equilibria can be Pareto‐ranked.

• However, bad equilibrium can be chosen. –This is called “coordination failure.”

2 0 0 9 /0 6 /1 1 I nt roduc t ion t o Ga m e T he or y 2 5

Other Examples

•

Battle of the sexes

•

Stag Hunt Game

“Mi i ” G

–“Migration” Game

•

Hawk‐Dove (Chicken) Game

(Chapter 2 in Games in Economic Development by Wydick)

2 0 0 9 /0 6 /1 1 I nt roduc t ion t o Ga m e T he or y 2 6

Two Frameworks of Games 

• Non‐cooperative Game Theory

– examine individual decision makingin strategic settings. – assume a person decides her action on her own. – does NOT rule out cooperative behaviors.

• Cooperative Game Theory

i d i i ki i i i

– examine group decision makingin strategic settings. – assume players can agree on their joint action, or can make 

binding contracts.

– simplifies strategic analysis by NOT modeling the negotiation  process explicitly.

 The two tools are complements to one another, but this  lecture focuses (almost) entirely on Non‐cooperative game.

Games in Different Settings

Complete Information

Incomplete Information Static Nash Equilibrium

(L t 3 5)

Bayesian NE (L t 9 10) (Lecture 3-5) (Lecture 9,10) Dynamic Subgame Perfect

Equilibrium (Lecture 6-8)

Perfect Bayesian Equilibrium (Lecture, 11,12)

2 0 0 9 /0 6 /1 1 I nt roduc t ion t o Ga m e T he or y 2 8