Algorithmic Game Theory Extensive-Form Games
Exercise Sheet 2: Extensive-Form Games
Due Date: December 16, 2024
Instructions
• Submit your exercises as a PDF file through the file vault (odevzd´av´arna) in the IS.
• Solutions will be graded based on their correctness and the clarity of the arguments presented.
• You do not have to provide proofs and justifications if you are not explicitly instructed to do
so.
• Collaboration: While you may discuss the exercises with classmates, you must write down the
solutions on your own.
• The bonus exercise is optional and will not be graded (although feedback will be provided if
you submit a solution). Solving the exercise serves mainly your benefit.
• To pass the exercise sheet, you need to obtain at least 45 points out of 85 possible.
• If you do not meet the threshold for the minimum points, you may resubmit your solution after
the first trial is marked.
Exercises
Exercise 1: (max. 10 points)
Formalize rock-paper-scissors as a two-player zero-sum imperfect-information extensive-form game.
Exercise 2: (max. 25 points)
Find a two-player perfect-information extensive-form game where all of the following conditions are
satisfied:
• there is a strategy profile 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 subgameperfect
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 find such a game, try your best (for partial points) to find a game which matches
the requirements as closely as you can.
Exercise 3: (max. 25 points)
a) [10 points] Consider the one-player perfect-information extensive-form game depicted below.
In this game, consider a mixed strategy σ given as follows:
1
Algorithmic Game Theory Extensive-Form Games
h1
h2
h4
z8
G
z9
H
C
h5
z10
I
z11
J
D
A
h3
h6
z12
K
z13
L
z14
M
E
z7
F
B
σ(ACEHJK) = 1/15
σ(ACFHJL) = 1/15
σ(ADFGIL) = 3/15
σ(BCEGIL) = 1/4
σ(BCFHJL) = 1/18
σ(BDEGIM) = 1/4
σ(BDFGIL) = 2/18
Find an equivalent behavioral strategy β. Is it unique? Justify your answer.
b) [15 points] Prove or disprove: In every zero-sum two-player perfect-information extensive-form
game G, all subgame-perfect equilibria have the same outcome for player 1.
Exercise 4: (max. 25 points)
Consider the following two-player strategic-form game G:
X Y
A 5, 6 −1, 7
B 7, −1 2, 2
a) [10 points] Find a subgame-perfect equilibrium in Gavg
irep whose value is (3, 10/3).
b) [8 points] Determine infc∈SPE(Gavg
irep) u1(c).
c) [7 points] Determine supc∈SPE(Gavg
irep) u1(c).
Justify your answers.
2