ECO290E: Game Theory
Lecture 7: Dynamic Games and Backward Induction
Information on Midterm
The coverage of the midterm exam is what we have
covered in Lectures 1 - 6.
The exam is take-home, which will be posted on
March 9 (Sun) morning via gateway.
You have to bring your answer at the beginning of the
morning lecture on March 11 (Tue).
If you cannot attend the lecture on 11th, please let me
know in advance. Otherwise, I will NOT accept ANY late submission.
The midterm counts about 1/3 of the entire grade.
Review of Lecture 5
Indifference property in mixed strategy NE.
If a player chooses more than one strategy with positive
probability, she must be indifferent among such pure strategies: choosing any of them generate same expected payoff.
Pure strategy is a special case of mixed strategy:
assigning a strategy probability 1.
Any finite game has a Nash equilibrium, possibly in
mixed strategies.
Dynamic Game
Each dynamic game can be described (in detail) by extensive-form.
Its formal definition will be given in Lecture 7.
Often expressed by a “game tree”.
Dynamic games can also be analyzed in normal form (or, strategic form).
A strategy in dynamic games is a complete action plan which prescribes how the player will act in each possible
contingencies in future.
Entry and Predation
There are two firms in the market game: a potential entrant and a monopoly incumbent.
First, the entrant decides whether or not to enter this monopoly market.
If the potential entrant stays out, then she gets 0 while the monopolist gets a large profit, say 4.
If the entrant enters the market, then the incumbent must choose whether or not to engage in a price war.
If he triggers a price war, then both firms suffer (receive -1).
If he accommodates the entrant, then both firms obtain modest profits, say 1 each.
Game Tree Analysis
(0,4)
(-1,-1)
(1,1)
Entrant
Monopolis
t
OUT
IN
WAR
ACC.
Normal (Strategic)-Form Analysis
Is (O, PW) a reasonable NE?
Monopolist Entrant
Price War Accommodate
In -1
-1
1 1
Out 4
0
4 0
Lessons
Dynamic games often have multiple Nash equilibria,
and some of them do not seem plausible since they
rely on non-credible threats.
By solving games from the back to forward, we can
erase those implausible equilibria.
⇒
Backward Induction
This idea will lead us to the refinement of NE, the
subgame perfect Nash equilibrium.
Formal definition will be given in Lecture 7.
Backward Induction Solution
( ,4)
(-1, )
( , )
Entrant
Monopolis
t
OUT
IN
WAR
ACC.
Sequential Battle of the Sexes
What happens if Wife makes decision first, and Husband decides after observing Wife’s action?
Husband Wife
Musical Soccer
Musical 1 3
0 0
Soccer 0 0
3 1
Normal-Form Analysis
There are three Nash equilibria:
(M, MM’), (M, MS’), (S, SS’) => Do they look reasonable?
Backward induction selects (M, MS’).
H
W
M, M’ M, S’ S, M’ S, S’
Musical 1
3
1
3
0
0
0
0
Soccer 0
0
3
1
0
0
3
1
Strategy and Outcome
Strategy in dynamic game = Complete plan of actions
What each player will do in every possible chance of move.
Even if some actions will not be taken in the actual play, players specify all contingent action plan.
Outcome = Combination of actions in the play
Actions that each player takes in the actual play.
Not specify contingent actions that will not be reached in the actual play.
To derive/understand rational (backward induction) play, we need to look at strategy, rather than outcome!
Centipede Game
1 P 2 P 1 P 2 P 1 P 2 P 25.60
6.40
T
T T T T T
0.40 0.20 1.60 0.80 6.40 3.20
12.80
0.10 0.80 0.40
3.201.60
Counting Game: Not 21
Two players count series of numbers (from 1 to 21)
in turn.
Each player must count at least one, but at most three numbers.
The player who ends up declaring 21 loses, and the other wins.
Does the first or the second player have a winning strategy?
If so, what does winning strategy look like?
How is the analysis changed if the last number is different from 21?
Zermelo’s Theorem
In any finite two-person game in which
1. players have strictly opposing interests,
2. the players move alternatively,
3. chance does not affect the decision making process,
4. the game cannot end in a draw,
one of the two players must have a winning strategy .
In these cases, one player is guaranteed “win” regardless of how her opponent will play, e.g., “Not 21.”
In principle, the complicated game such as chess has a winning strategy (or both players are guaranteed draw).
Further Exercises
Find the conditions under which backward induction works, i.e., pins down the unique outcome.
If this is too difficult, construct a counter example that backward induction does not work.
Consider the sequential version (one player moves first) of prisoner’s dilemma and coordination game, and solve them by backward induction.
Construct a dynamic game to which Zeomelo’s theorem can be applied, and derive the winning strategy.