Dynamic Games
2: Imperfect information
Universidad Carlos III de Madrid
Dynamic Games with Imperfect Information
• Games in which at least one of the following happens:
• A player does not know which action some other player has taken.
• Some players have different information over a result of a nature move.
• This translates into the fact that some players don’t know with
certainty in which one of their nodes actually are at some point in
the game.
• The nodes a player cannot tell apart are nodes in which the player
has the same information. Each set of nodes in which this occurs
is called an information set.
• Trivially, when a player knows that she is a node, that node is an
information set of one element.
• Graphically, we will join the nodes belonging in an information set
with a dotted line or a “cloud”.
Example: dynamic battle of the sexes
1.1 1.1
L R L R
2.1 2.2 2.1 2.2
L R l r L R l r
3 0 0 1 3 0 0 1
1 0 0 3 1 0 0 3
• Player 2 knows what player 1 • Player 2 does not know what
did. player 1 did.
• Nodes 2.1 y 2.2 belong in an
information set.
• There is no backward induction
equilibrium, but there are SPNE.
A complicated example
1.1
2.1 2.2 3.1
1.2 1.3 3.2 1.4 2.3 2.4 2.5
• Information sets:
• Player 1: {1.1}, {1.2, 1.3} y {1.4} .
• Player 2: {2.1}, {2.2}, {2.3, 2.4} y {2.5}.
• Player 3: {3.1} y {3.2}.
• Static and dynamic subgames:
• At 2.1 begins a static (sub)game.
• At 2.2 begins a dynamic (sub)game.
• At 3.1 begins a (sub)game with characteristics of both kinds of game.
Extensive form, normal form and
subgames
• We have to add or change the following in the extensive
form definition for games of imperfect information:
• Group the nodes of a player in information sets.
• Define actions in each information set (not in each node):
informally, an action implies choosing the same edge in each node
of a given information set.
• To obtain the normal form, it is enough to define a player’
strategy as a vector that defines an action in each
information set (rather than in each node).
• Subgames are defined as before, but with a new rule “do
not break information sets”.
A complicated example
1.1
I
C D
2.1 2.2 3.1
1.2 1.3 3.2 1.4 2.3 2.4 2.5
a b a b x z
• Which subgames are there?
• Those starting at 1.1, 2.1, 2.2, 3.1, 3.2, 1.4 and 2.5.
• Which is the set of strategies for Player 1?
• {(I,a,x), (I,a,z), (I,b,x), (I,b,z), (C,a,x), (C,a,z), (C,b,x), (C,b,z),
(D,a,x), (D,a,z), (D,b,x), (D,b,z)}.
• Example: (C,a,z) in red.
Complicated example 2
1.1
2.1 2.2 3.1
I D I D
1.2 1.3 3.2 1.4 2.3 2.4 2.5
a b a b r t
• Which subgames are there?
• Those starting at 1.1, 3.1, 3.2, 1.4 y 2.5.
• Which is the set of strategies for Player 2?
• {(I,a,r), (I,a,t), (I,b,r), (I,b,t), (D,a,r), (D,a,t), (D,b,r), (D,b,t)}.
• Example: (D,a,r) in red.
Example to find SPNEa
• Player 1 chooses between A and B.
• If he chooses A, he and Player 2 play the chicken game.
• If he chooses B, they play the battle of the sexes.
1.1
A B
1.2 1.3
K S F O
2.1 2.2
K S K S F O F O
0 4 1 2 3 0 0 1
0 1 4 2 1 0 0 3
• We have numbered the information sets (rather than the nodes).
• Which subgames are there?
Three, starting at 1.1, 1.2 and 1.3.
• Begin by solving 1.2 and 1.3.
Example to find SPNEa
• To simplify, we only consider pure strategies.
• The subgame starting at 1.2 is the chicken game with NE in pure strategies: (K, S)
and (S, K).
• The subgame starting at 1.3 is the battle of the sexes with NE in pure strategies:
(F, F) and (O, O).
• To find the equilibrium action at 1.1, we must consider four possibilities:
1.2: (K, S) 1.2: (K, S) 1.2: (S, K) 1.2: (S, K)
1.3: (F, F) 1.3: (O, O) 1.3: (F, F) 1.3: (O, O)
1.1 1.1 1.1 1.1
A B A B A B A B
4 3 4 1 1 3 1 1
1.1 prefers A 1.1 prefers A 1.1 prefers B 1.1 is indifferent
SPNE: SPNE: SPNE: SPNEa:
((A,K,F), (S,F)) ((A,K,O), (S,O)) ((B,S,F), (K,F)) ((A,S,O), (K,O)) and
((B,S,O), (K,O))
Two ways to write the SPNEa
• The canonic way: sort by players.
• The convenient way: sort by subgames.
• In the example before, the equilibrium ((A,K,F),
(S,F)) is written in the canonic way.
• The convenient way is: (A, (K,S), (F,F)).
By players: By subgames:
((1.1, 1,2, 1.3), (2.1, 2.2)) (1.1, (1,2, 2.1), (1.3, 2.2))
(( A , K , F ), ( S , F )) ( A , ( K , S ), ( F , F ))
Example 2 on how to find ENPS
Formula 1 Game
• Before deciding what type of tires to use, Al can make a strategic
maneuver that would prevent Ham from participating in the race.
• Thus, in a first stage, Al must decide whether to prevent or not
Ham’s participation in the race (decisions P and NP).
• If Al prevents the participation of Ham, Al will have 4 points at the
end of the race, and Ham will have none.
• If Al does not prevent Ham’s participation, both pilots must
choose simultaneously the type of tires (rain or dry), with the
results shown next.
Example 2 on how to find ENPS
Formula 1 Game
AL.1
P NP
AL.2
4 R D
0 HAM.1
Subgames: R D R D
starting at AL.1 and
starting at AL.2 1 2 5 0
2 3 4 3
Example 2 on how to find ENPS
Formula 1 Game
• Start by solving subgame at AL.2 after NP:
AL.2
The normal form is:
R D
HAM.1 HAM.1
R D
R D R D
R 1, 2 2, 3
AL.2
1 2 5 0 D 5, 4 0, 3
2 3 4 3
• NE = {(D, R), (R, D), (1/2[R]+1/2[D], 1/3[R]+2/3[D])}
• Payoffs in NE of subgame after NP for AL: 5, 2 and 5/3, respectively.
• If AL.1 plays P he will get 4. Thus, if at the subgame after NP the NE is (D, R), he will
choose NP. For any other NE he will choose P.
• Hence: SPNE : {((NP,D), R), (P,R), D), ((P,1/2), 1/3)}.
