Game Theory
Part 3
Dynamic games
PowerPoint Slides prepared by:
Andreea CHIRITESCU
Eastern Illinois University
© 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as
1
permitted in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use.
Sequential Games
• In some games, the order of moves
matters
– A player that can move later in the game
can see how others have played up to that
point
© 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as
2
permitted in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use.
Sequential Battle of the Sexes
• Suppose the wife chooses first
– And the husband observes her choice
before making his
– Her possible strategies haven’t changed
– His possible strategies have expanded
• For each of his wife’s actions, he can choose
one of two actions
© 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as
3
permitted in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use.
8.1
Husband’s contingent strategies
© 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed with a
certain product or service or otherwise on a password-protected website for classroom use.
4
8.9
Normal Form for the Sequential Battle of the Sexes
© 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed with a
certain product or service or otherwise on a password-protected website for classroom use.
5
8.10
Extensive Form for the Battle of the Sexes
In the sequential version (a), the husband moves second, after observing his wife’s move. In
the simultaneous version (b), he does not know her choice when he moves, so his decision
nodes must be connected in one information set.
© 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed with a
certain product or service or otherwise on a password-protected website for classroom use.
6
Sequential Battle of the Sexes
• There are three pure-strategy Nash
equilibria
1. Wife plays ballet, husband plays (ballet |
ballet, ballet | boxing)
2. Wife plays ballet, husband plays (ballet |
ballet, boxing | boxing)
3. Wife plays boxing, husband plays
(boxing | ballet, boxing | boxing)
© 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as
7
permitted in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use.
Subgame-Perfect Equilibrium
• A subgame
– A part of the extensive form beginning with
a decision node and including everything
to the right of it
• A proper subgame
– Starts at a decision node not connected to
another in an information set
© 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as
8
permitted in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use.
8.11
Equilibrium Path
In the third of the Nash equilibria listed for
the sequential Battle of the Sexes, the
wife plays boxing and the husband plays
(boxing | ballet, boxing | boxing), tracing
out the branches indicated with thick lines
(both solid and dashed). The dashed line
is the equilibrium path; the rest of the tree
is referred to as being ‘‘off the equilibrium
path.’’
© 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed with a
certain product or service or otherwise on a password-protected website for classroom use.
9
8.12
Proper Subgames in the Battle of the Sexes
The sequential
version in (a) has
three proper
subgames, labeled
A, B, and C. The
simultaneous version
in (b) has only one
proper subgame: the
whole game itself,
labeled D.
© 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed with a
certain product or service or otherwise on a password-protected website for classroom use.
10
Subgame-Perfect Equilibrium
• A subgame-perfect equilibrium
– A strategy profile (s*1,s*2,…,s*n) that
constitutes a Nash equilibrium for every
proper subgame
– Is always a Nash equilibrium
– Rules out any empty threat in a sequential
game
© 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as
11
permitted in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use.
Backward Induction
• Backward induction
– A shortcut for finding the perfect-subgame
equilibrium directly
– Working backwards from the end of the
game to the beginning
• Compute the Nash equilibria for the bottommost
subgames at the husband’s decision nodes
• Substitute his equilibrium strategies for the
subgames themselves
• The resulting game is a simple decision problem
for the wife
© 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as
12
permitted in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use.
8.13
Applying Backward Induction
The last subgames (where player 2 moves) are replaced by the Nash equilibria on these
subgames. The simple game that results at right can be solved for player 1’s equilibrium action.
© 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed with a
certain product or service or otherwise on a password-protected website for classroom use.
13
Repeated Games
• Stage game
– Simple constituent game that is played
repeatedly
• Repeated play
– Opens up the possibility of cooperation in
equilibrium
– Players can adopt trigger strategies
• Cooperate as long as everyone else does
© 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as
14
permitted in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use.
Finitely Repeated Games
• Repeat a stage game for a known, finite
number of times
– May not increase the possibility for
cooperation
• Selten’s theorem
– For any stage game with a unique Nash
equilibrium
– The unique subgame-perfect equilibrium of the
finitely repeated game involves playing Nash
equilibrium every period
© 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as
15
permitted in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use.
Finitely Repeated Games
• If the stage game has multiple Nash
equilibria
– It may be possible to achieve cooperation
in a finitely repeated game
– Players can use trigger strategies to
maintain cooperation
• Threaten to play the Nash equilibrium that
yields a worse outcome for the player who
deviates from cooperation
© 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as
16
permitted in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use.
Infinitely Repeated Games
• Players can sustain cooperation in
infinitely repeated games
– By using trigger strategies
– The trigger strategy must be severe
enough to deter deviation
© 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as
17
permitted in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use.
Infinitely Repeated Games
• Both players follow a trigger strategy in
the Prisoners’ Dilemma
– If both players are silent every period, the
payoff over time would be
Veq = 2 + 2 + 22 + … = 2/(1–)
– If a player deviates and then the other finks
every period, that player’s payoff is
Vdev = 3 + 1 + 12 + … = 3 + /(1–)
– Trigger strategies form a perfect-subgame
equilibrium: Veq Vdev, so 1/2
© 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as
18
permitted in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use.
Infinitely Repeated Games
• Grim strategy
– The trigger strategy in which players revert
to the harshest punishment possible
– Revert to the stage-game nash equilibrium
forever
– Elicits cooperation for the lowest value of
for any strategy
• A tit-for-tat strategy
• Involves only one round of punishment for
cheating
© 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as
19
permitted in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use.
Infinitely Repeated Games
• As approaches 1
– Grim-strategy punishments become
infinitely harsh
• Because they involve an unending stream of
undiscounted losses
– Infinite punishments can be used to
sustain a wide range of possible outcomes
© 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as
20
permitted in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use.
