Dynamic Games of Complete Information
Dynamic Games of Complete and Perfect Information
73-347 Game Theory--Lecture 13
Outline of dynamic games of complete information
Dynamic games of complete information
Extensive-form representation
Dynamic games of complete and perfect information
Game tree
Subgame-perfect Nash equilibrium
Backward induction
Applications
Dynamic games of complete and imperfect information
More applications
Repeated games
73-347 Game Theory--Lecture 13
Today’s Agenda
Review of previous class
Subgame
Subgame-perfect Nash equilibrium
Backward induction
Sequential bargaining ( of Gibbons)
73-347 Game Theory--Lecture 13
Dynamic (or sequential-move) games of complete information
A set of players
Who moves when and what action choices are available?
What do players know when they move?
Players’ payoffs are determined by their choices.
All these are common knowledge among the players.
73-347 Game Theory--Lecture 13
Dynamic games of complete and perfect information
Perfect information
All previous moves are observed before the next move is chosen.
A player knows Who has moved What before she makes a decision
73-347 Game Theory--Lecture 13
Entry game
An incumbent monopolist faces the possibility of entry by a challenger.
The challenger may choose to enter or stay out.
If the challenger enters, the incumbent can choose either to accommodate or to fight.
The payoffs are common knowledge.
Challenger
In
Out
Incumbent
A
F
1, 2
2, 1
0, 0
The first number is the payoff of the challenger. The second number is the payoff of the incumbent.
73-347 Game Theory--Lecture 13
Strategy and payoff
A strategy for a player is a complete plan of actions.
It specifies a feasible action for the player in every contingency in which the player might be called on to act.
It specifies what the player does at each of her nodes
Player 1
Player 2
H
T
-1, 1
1, -1
H
T
Player 2
H
T
1, -1
-1, 1
a strategy for player 1: H
a strategy for player 2: H if player 1 plays H, T if player 1 plays T (written as HT)
Player 1’s payoff is -1 and player 2’s payoff is 1 if player 1 plays H and player 2 plays HT
73-347 Game Theory--Lecture 13
Nash equilibrium in a dynamic game
We can also use normal-form to represent a dynamic game
The set of Nash equilibria in a dynamic game of complete information is the set of Nash equilibria of its normal-form
How to find the Nash equilibria in a dynamic game of complete information
Construct the normal-form of the dynamic game of complete information
Find the Nash equilibria in the normal-form
73-347 Game Theory--Lecture 13
Entry game
Challenger’s strategies
In
Out
Incumbent’s strategies
Accommodate
Fight
Payoffs
Normal-form representation
Incumbent
Fight
1 , 2
1 , 2
Out
Challenger
0 , 0
2 , 1
In
Accommodate
Challenger
In
Out
Incumbent
A
F
1, 2
2, 1
0, 0
73-347 Game Theory--Lecture 13
Nash equilibria in entry game
Two Nash equilibria
( In, Accommodate )
( Out, Fight )
Does the second Nash equilibrium make sense?
Non-creditable threats
Incumbent
Fight
1 , 2
1 , 2
Out
Challenger
0 , 0
2 , 1
In
Accommodate
Challenger
In
Out
Incumbent
A
F
1, 2
2, 1
0, 0
73-347 Game Theory--Lecture 13
Remove nonreasonable Nash equilibrium
Subgame perfect Nash equilibrium is a refinement of Nash equilibrium
It can rule out nonreasonable Nash equilibria or non-creditable threats
We first need to define subgame
73-347 Game Theory--Lecture 13
Game tree
A game tree has a set of nodes and a set of edges such that
each edge connects two nodes (these two nodes are said to be adjacent)
for any pair of nodes, there is a unique path that connects these two nodes
x0
x1
x2
x3
x4
x5
x6
x7
x8
a node
an edge connecting nodes x1 and x5
a path from x0 to x4
73-347 Game Theory--Lecture 13
Game tree
A path is a sequence of distinct nodes y1, y2, y3, ..., yn-1, yn such that yi and yi+1 are adjacent, for i=1, 2, ..., n-1. We say that this path is from y1 to yn.
We can also use the sequence of edges induced by these nodes to denote the path.
The length of a path is the number of edges contained in the path.
Example 1: x0, x2, x3, x7 is a path of length 3.
Example 2: x4, x1, x0, x2, x6 is a path of length 4
x0
x1
x2
x3
x4
x5
x6
x7
x8
a path from x0 to x4
73-347 Game Theory--Lecture 13
Game tree
There is a special node x0 called the root of the tree which is the beginning of the game
The nodes adjacent to x0 are successors of x0. The successors of x0 are x1, x2
For any two adjacent nodes, the node that is connected to the root by a longer path is a successor of the other node.
Example 3: x7 is a successor of x3 because they are adjacent and the path from x7 to x0 is longer than the path from x3 to x0
x0
x1
x2
x3
x4
x5
x6
x7
x8
73-347 Game Theory--Lecture 13
Game tree
If a node x is a successor of another node y then y is called a predecessor of x.
In a game tree, any node other than the root has a unique predecessor.
Any node that has no successor is called a terminal node which is a possible end of the game
Example 4: x4, x5, x6, x7, x8 are terminal nodes
x0
x1
x2
x3
x4
x5
x6
x7
x8
73-347 Game Theory--Lecture 13
Game tree
Any node other than a terminal node represents some player.
For a node other than a terminal node, the edges that connect it with its successors represent the actions available to the player represented by the node
Player 1
Player 2
H
T
-1, 1
1, -1
H
T
Player 2
H
T
1, -1
-1, 1
73-347 Game Theory--Lecture 13
Game tree
A path from the root to a terminal node represents a complete sequence of moves which determines the payoff at the terminal node
Player 1
Player 2
H
T
-1, 1
1, -1
H
T
Player 2
H
T
1, -1
-1, 1
73-347 Game Theory--Lecture 13
Subgame
A subgame of a game tree begins at a nonterminal node and includes all the nodes and edges following the nonterminal node
A subgame beginning at a nonterminal node x can be obtained as follows:
remove the edge connecting x and its predecessor
the connected part containing x is the subgame
-1, 1
Player 1
Player 2
H
T
1, -1
H
T
Player 2
H
T
1, -1
-1, 1
a subgame
73-347 Game Theory--Lecture 13
Subgame: example
Player 2
E
F
Player 1
G
H
3, 1
1, 2
0, 0
Player 1
C
D
2, 0
Player 2
E
F
Player 1
G
H
3, 1
1, 2
0, 0
Player 1
G
H
1, 2
0, 0
73-347 Game Theory--Lecture 13
Subgame-perfect Nash equilibrium
A Nash equilibrium of a dynamic game is subgame-perfect if the strategies of the Nash equilibrium constitute a Nash equilibrium in every subgame of the game.
Subgame-perfect Nash equilibrium is a Nash equilibrium.
73-347 Game Theory--Lecture 13
Entry game
Two Nash equilibria
( In, Accommodate ) is subgame-perfect.
( Out, Fight ) is not subgame-perfect because it does not induce a Nash equilibrium in the subgame beginning at Incumbent.
Challenger
In
Out
Incumbent
A
F
1, 2
2, 1
0, 0
Incumbent
A
F
2, 1
0, 0
Accommodate is the Nash equilibrium in this subgame.
73-347 Game Theory--Lecture 13
Find subgame perfect Nash equilibria: backward induction
Starting with those smallest subgames
Then move backward until the root is reached
Challenger
In
Out
Incumbent
A
F
1, 2
2, 1
0, 0
The first number is the payoff of the challenger. The second number is the payoff of the incumbent.
73-347 Game Theory--Lecture 13
Find subgame perfect Nash equilibria: backward induction
Subgame perfect Nash equilibrium (DG, E)
Player 1 plays D, and plays G if player 2 plays E
Player 2 plays E if player 1 plays C
Player 2
E
F
Player 1
G
H
3, 1
1, 2
0, 0
Player 1
C
D
2, 0
73-347 Game Theory--Lecture 13
Existence of subgame-perfect Nash equilibrium
Every finite dynamic game of complete and perfect information has a subgame-perfect Nash equilibrium that can be found by backward induction.
73-347 Game Theory--Lecture 13
Sequential bargaining ( of Gibbons)
Player 1 and 2 are bargaining over one dollar. The timing is as follows:
At the beginning of the first period, player 1 proposes to take a share s1 of the dollar, leaving 1-s1 to player 2.
Player 2 either accepts the offer or rejects the offer (in which case play continues to the second period)
At the beginning of the second period, player 2 proposes that player 1 take a share s2 of the dollar, leaving 1-s2 to player 2.
Player 1 either accepts the offer or rejects the offer (in which case play continues to the third period)
At the beginning of third period, player 1 receives a share s of the dollar, leaving 1-s for player 2, where 0<s <1.
The players are impatient. They discount the payoff by a fact , where 0< <1
73-347 Game Theory--Lecture 13
Sequential bargaining ( of Gibbons)
Player 2
accept
reject
propose an offer ( s2 , 1-s2 )
Period 1
Player 1
accept
propose an offer ( s1 , 1-s1 )
s1 , 1-s1
Player 1
s2 , 1-s2
s , 1-s
Period 2
Period 3
reject
Player 2
73-347 Game Theory--Lecture 13
Solve sequential bargaining by backward induction
Period 2:
Player 1 accepts s2 if and only if s2 s. (We assume that each player will accept an offer if indifferent between accepting and rejecting)
Player 2 faces the following two options: (1) offers s2 = s to player 1, leaving 1-s2 = 1-s for herself at this period, or (2) offers s2 < s to player 1 (player 1 will reject it), and receives 1-s next period. Its discounted value is (1-s)
Since (1-s)<1-s, player 2 should propose an offer (s2* , 1-s2* ), where s2* = s. Player 1 will accept it.
73-347 Game Theory--Lecture 13
Sequential bargaining ( of Gibbons)
Player 2
accept
reject
propose an offer ( s2 , 1-s2 )
Period 1
Player 1
accept
propose an offer ( s1 , 1-s1 )
s1 , 1-s1
Player 1
s2 , 1-s2
s , 1-s
Period 2
Period 3
reject
Player 2
s , 1- s
73-347 Game Theory--Lecture 13
Solve sequential bargaining by backward induction
Period 1:
Player 2 accepts 1-s1 if and only if 1-s1 (1-s2*)= (1- s) or s1 1-(1-s2*), where s2* = s.
Player 1 faces the following two options: (1) offers 1-s1 = (1-s2*)=(1- s) to player 2, leaving s1 = 1-(1-s2*)=1-+s for herself at this period, or (2) offers 1-s1 < (1-s2*) to player 2 (player 2 will reject it), and receives s2* = s next period. Its discounted value is s
Since s < 1-+s, player 1 should propose an offer (s1* , 1-s1* ), where s1* = 1-+s
73-347 Game Theory--Lecture 13
Summary
Subgame perfect Nash equilibrium
Backward induction
Next time
Stackelberg Model of duopoly
Wages and employment in a unionized firm
Reading lists
Sec -C of Gibbons
Sec of Osborne
73-347 Game Theory--Lecture 13
Lecture 13
Lecture 13
