Algorithmic Game Theory Games in Strategic Form
Exercise Sheet 1: Games in Strategic Form
Due Date: November 6, 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 55 points out of 100 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. 25 points)
a) [5 points] Formalize the following scenario as a strategic form game involving two players:
There are two shepherds, Alfred and Bob. Alfred owns three cows, while Bob owns two. They
have the option to either graze their cows on a shared meadow or keep them on their respective
farms. If there are N cows grazing in the same location (whether the meadow, Alfred’s farm,
or Bob’s farm), each cow from that location generates the utility 2 − N
3
(in the form of milk)
for its owner. Both shepherds must decide how many of their cows (ranging from 0 to all) they
want to send to graze in the shared meadow.
b) [5 points] We define an IDC (I Don’t Care) strategy as one where a shepherd randomly sends
a uniformly distributed number of cows, ranging from 0 to the maximum possible, to graze
on the shared meadow. What is the expected utility for each player if both adopt the IDC
strategy?
c) [5 points] Identify all Alfred’s best responses if Bob adopts the IDC strategy?
d) [10 points] Identify all (mixed and pure) Nash equilibria of the game and justify there are no
others. (Hint: Use concepts from the lecture to find a simple and concise solution. Avoid long
explanations.)
Exercise 2: (max. 25 points)
a) [10 points] In this exercise, consider only pure strategies. Find a strategic form game with
two players, P0 and P1, where all the following conditions are satisfied:
• P0 has two strategies (S0 = {A, B}), and P1 has three strategies (S1 = {X, Y, Z}).
• There is exactly one Nash equilibrium.
• Every strategy profile is Pareto optimal.1
1
A profile s is Pareto optimal if there is no other profile s′
such that ui(s′
) ≥ ui(s) for all players i, and ui(s′
) > ui(s)
for at least one player i.
1
Algorithmic Game Theory Games in Strategic Form
• Neither player has a weakly dominant strategy.2
b) [8 points] Prove that any game meeting the conditions in part (a) must contain a weakly
dominated strategy3
.
c) [7 points] Characterize all games satisfying the conditions in part (a).
Exercise 3: (max. 25 points)
Consider a strategic form game of two players P0 and P1 such that P1 has two strategies. Prove
that a pure strategy of P0 is strictly dominated by a mixed strategy if and only if it is never a best
response.
Exercise 4: (max. 25 points)
a) [10 points] Determine whether IESDS with pure strategies can introduce new pure Nash
equilibria in a finite game.
b) [15 points] Determine whether IESDS with pure strategies can introduce new pure Nash
equilibria in an infinite game.
2
A strategy si of player i is weakly dominant if for every strategy s′
i of player i, ui(si, s1−i) ≥ ui(s′
i, s1−i) for all
s1−i ∈ S1−i, and ui(si, s1−i) > ui(s′
i, s1−i) for at least one s1−i.
3
A strategy si of player i is weakly dominated if there exists a strategy s′
i of player i such that ui(s′
i, s1−i) ≥
ui(si, s1−i) for all s1−i ∈ S1−i, and ui(s′
i, s1−i) > ui(si, s1−i) for at least one s1−i.
2
Algorithmic Game Theory Games in Strategic Form
Bonus Exercise: There is a well-known topological result called Brouwer’s Fixed-Point Theorem,
which asserts that every continuous function from a convex, closed, and bounded set (such as a ball,
simplex, or polyhedron) to itself has at least one fixed point. One way to prove this is through a
combinatorial argument known as Sperner’s Lemma.
Theorem 1 (Brouwer’s Fixed-Point Theorem). Let X be a non-empty, convex, closed, and bounded
set in Rn
. Then, every continuous function f : X → X has a fixed point, i.e., there exists x ∈ X
such that f(x) = x.
In our context, we use this theorem to prove the existence of mixed Nash equilibria in finite
games. For simplicity, we will focus on two-player strategic form games, though a similar argument
applies to any number of players. Prove the following theorem:
Theorem 2. Every finite two-player strategic form game has a mixed Nash equilibrium.
The proof should proceed as follows:
1. Observe that the set of strategy profiles can be represented as a subset of Rn
for a suitable n.
(How is n related to the game?)
2. For any fixed strategy profile x, show that the set of best-response profiles4
is non-empty,
compact, convex, and closed.
3. Use (2) to construct a continuous function f : X → X (where X is the set of all strategy
profiles) that assigns each x a best-response profile.
4. Apply Brouwer’s Fixed-Point Theorem to conclude the existence of a mixed Nash equilibrium.
4
We call a profile x′
a best-response profile for x if every strategy with non-zero probability in x is a best response
to x.
3