Phase VII — Game Theory for Optimization & Robotics | Week 14 | 2.5 hours Every strategic interaction can be encoded as a matrix — then solved with the tools you already know.
Two OKS robots approaching the same intersection must decide: yield or proceed. Each robot's best action depends on the other's choice. This is a coordination game in normal form. Understanding dominance lets the fleet controller prune clearly bad strategies before computing equilibria — reducing the dimension of the decision space for real-time dispatch.
A normal-form game is a tuple $\Gamma = (N, \{S_i\}_{i \in N}, \{u_i\}_{i \in N})$ where: - $N = \{1, 2, \ldots, n\}$ is the set of players. - $S_i$ is the finite set of strategies for player $i$. - $u_i : S_1 \times \cdots \times S_n \to \mathbb{R}$ is the payoff function.
A strategy profile $s = (s_1, \ldots, s_n) \in S_1 \times \cdots \times S_n$ specifies one strategy per player. We write $s_{-i}$ for the profile of all players except $i$.
For two-player games, payoffs are encoded in bimatrices $(A, B)$ where $A_{ij} = u_1(i,j)$ and $B_{ij} = u_2(i,j)$.
Prisoner's Dilemma — each player prefers to defect regardless of the other:
$$A = \begin{pmatrix} -1 & -3 \\ 0 & -2 \end{pmatrix}, \quad B = \begin{pmatrix} -1 & 0 \\ -3 & -2 \end{pmatrix}$$
Stag Hunt — coordination with risk:
$$A = \begin{pmatrix} 4 & 0 \\ 3 & 2 \end{pmatrix}, \quad B = \begin{pmatrix} 4 & 3 \\ 0 & 2 \end{pmatrix}$$
Chicken (Hawk-Dove) — anti-coordination:
$$A = \begin{pmatrix} 0 & -1 \\ 1 & -5 \end{pmatrix}, \quad B = \begin{pmatrix} 0 & 1 \\ -1 & -5 \end{pmatrix}$$
Strategy $s_i$ is strictly dominated by $s_i'$ if: $$u_i(s_i', s_{-i}) > u_i(s_i, s_{-i}) \quad \forall s_{-i} \in S_{-i}$$
Strategy $s_i$ is weakly dominated by $s_i'$ if $\geq$ holds everywhere and $>$ holds for at least one $s_{-i}$.
A rational player never plays a strictly dominated strategy. This lets us simplify games.
Key property: IESDS order does not matter — the result is unique. If IESDS reduces to a single profile, the game is dominance solvable.
import numpy as np
# --- Build classic games ---
def prisoners_dilemma():
"""Prisoner's Dilemma: (C)ooperate, (D)efect."""
A = np.array([[-1, -3],
[ 0, -2]])
B = np.array([[-1, 0],
[-3, -2]])
return NormalFormGame(A, B)
def stag_hunt():
A = np.array([[4, 0],
[3, 2]])
B = np.array([[4, 3],
[0, 2]])
return NormalFormGame(A, B)
# --- IESDS implementation ---
def iesds(payoff1, payoff2, strict=True):
"""Iterated elimination of (strictly) dominated strategies.
Returns masks of surviving strategies for each player.
"""
A, B = payoff1.copy(), payoff2.copy()
rows = list(range(A.shape[0]))
cols = list(range(A.shape[1]))
changed = True
while changed:
changed = False
# Check row player
to_remove = []
for i in rows:
for i2 in rows:
if i == i2:
continue
col_idx = [cols.index(c) for c in cols]
vals_i = A[i, cols]
vals_i2 = A[i2, cols]
if strict and np.all(vals_i2 > vals_i):
to_remove.append(i); break
elif not strict and np.all(vals_i2 >= vals_i) and np.any(vals_i2 > vals_i):
to_remove.append(i); break
for r in set(to_remove):
rows.remove(r); changed = True
# Check column player
to_remove = []
for j in cols:
for j2 in cols:
if j == j2:
continue
vals_j = B[np.ix_(rows, [j])].flatten()
vals_j2 = B[np.ix_(rows, [j2])].flatten()
if strict and np.all(vals_j2 > vals_j):
to_remove.append(j); break
elif not strict and np.all(vals_j2 >= vals_j) and np.any(vals_j2 > vals_j):
to_remove.append(j); break
for c in set(to_remove):
cols.remove(c); changed = True
return rows, cols
# --- Demo ---
game = prisoners_dilemma()
print("=== Prisoner's Dilemma ===")
print("Payoff1:\n", game.payoff1)
print("Payoff2:\n", game.payoff2)
rows, cols = iesds(game.payoff1, game.payoff2)
print(f"IESDS surviving strategies: Player1={rows}, Player2={cols}")
# Expected: [1], [1] — both defect
# 3×3 game where IESDS reduces fully
A3 = np.array([[3, 0, 1],
[1, 2, 0],
[0, 1, 3]])
B3 = np.array([[1, 0, 2],
[0, 3, 1],
[2, 1, 0]])
rows3, cols3 = iesds(A3, B3)
print(f"\n3×3 game IESDS survivors: P1={rows3}, P2={cols3}")
Expected output:
=== Prisoner's Dilemma ===
Payoff1: [[-1 -3] [ 0 -2]]
Payoff2: [[-1 0] [-3 -2]]
IESDS surviving strategies: Player1=[1], Player2=[1]
3×3 game IESDS survivors: P1=[0], P2=[2]
P1. Construct the payoff bimatrix for: two firms choose High or Low price. If both pick High, each earns 5. If both pick Low, each earns 2. If one picks High and the other Low, the High-price firm earns 0, the Low-price firm earns 7. Is this a Prisoner's Dilemma?
P2. Apply IESDS to the game $A = \begin{pmatrix} 4 & 3 & 2 \\ 5 & 4 & 1 \\ 1 & 0 & 0 \end{pmatrix}$, $B = \begin{pmatrix} 2 & 1 & 4 \\ 3 & 2 & 0 \\ 1 & 3 & 1 \end{pmatrix}$. Show each elimination step.
P3. In the Stag Hunt, is strategy Stag weakly dominated? Strictly dominated?
E1. Prove that the order of elimination does not matter for strict dominance (sketch the key argument using the irrelevance of eliminated strategies to the remaining comparisons).
E2. Construct a symmetric 3×3 game that is not dominance solvable but has a unique pure Nash equilibrium.
E3. Implement a function that checks whether a game is dominance solvable and, if so, returns the unique surviving profile in ≤ 10 lines.
def is_dominance_solvable(A, B):
rows, cols = iesds(A, B, strict=True)
if len(rows) == 1 and len(cols) == 1:
return True, (rows[0], cols[0])
return False, None
print(is_dominance_solvable(*[prisoners_dilemma().payoff1, prisoners_dilemma().payoff2]))
# (True, (1, 1))