IA168 — Problem set 2
Except for Problem 3, we consider only pure strategies.
Problem 1 [3 points]
Give a formal description of rock-paper-scissors as a two-player imperfect-information extensive-form game
(i.e., according to the deﬁnition from the lectures).
Problem 2 [6 points]
Bob has been hired by Maﬁa to steal some valuable top-secret documents. Now that Bob has done so, he has
two options: Either he delivers the documents to Maﬁa, or he flees to Europe and sells them for twice as much.
If Bob ﬂees, Maﬁa either decide to leave this business and concentrate on other deals, or they start searching
for Bob. In the latter case, with probability p, they eventually ﬁnd Bob and kill him.
We model this scenario as the two-player perfect-information extensive-form game depicted below.
B
(10, 10) M
(20, −5) p(−100, 5) + (1 − p)(20, −10)
d f
l s
In dependence on the parameter p, 0 ≤ p ≤ 1, enumerate all:
a) never-best-response strategies;
b) maxmin strategies;
c) Nash equilibria;
d) subgame-perfect equilibria.
Problem 3 [2 points]
Consider the one-player perfect-information extensive-form game depicted below.
z0 z1 z2 z3 z4 z5 z6
z7
h0
h1 h2
h3 h4 h5 h6
A B
C D E
F
G
H I J K L M N
In this game, consider a mixed strategy σ given as follows:
1
σ(ACEHJLM) = 4
15
σ(ACEIKLN) = 2
5
σ(BCFHKLM) = 1
8
σ(BDFHJLN) = 1
24
σ(BDGHJLN) = 1
6
Find a behavioral strategy β which is equivalent to σ. Is there a unique solution to this task? Justify your
answer.
Problem 4 [6 points]
Find a two-player perfect-information extensive-form game where all of the following conditions are satisﬁed:
• there is a strategy proﬁle whose outcome is for both players better than that of any Nash equilibrium;
• there is a Nash equilibrium whose outcome is for both players better than that of any subgame-perfect
equilibrium;
• there are exactly two subgame-perfect equilibria s, s , and the outcome of s is for both players better than
that of s .
Should you fail to ﬁnd such a game, try your best (for partial points) to ﬁnd a game which matches the
requirements as closely as you can.
Problem 5 [3 points]
Prove or disprove: In every zero-sum two-player perfect-information extensive-form game G, all subgameperfect
equilibria have the same outcome for player 1.
2