Exercises: Game Theory

Chapter 10: Game Theory for Optimization and Multi-Agent Systems

Self-assessment guide: These exercises cover game theory from basic strategic reasoning to algorithmic applications in robotics and ML. They connect to LP duality, convex optimization, and multi-robot coordination. Complete them in order; later exercises build on earlier ones.

Difficulty key: ⭐ Foundational | ⭐⭐ Intermediate | ⭐⭐⭐ Advanced | ⭐⭐⭐⭐ Challenge

Section A — Normal Form Games and Dominance

A1. ⭐ Two OKS warehouse robots arrive at an intersection simultaneously. Each can Yield (wait) or Go (proceed). If both Go, they collide (cost −10 each). If both Yield, they waste time (−2 each). If one Goes and the other Yields, the goer gets 0 and the yielder gets −3.

1. Write the payoff matrix.
2. Does either player have a strictly dominated strategy?
3. Find all pure-strategy Nash equilibria.

A2. ⭐ Consider the 3-player game where each player chooses L or R. Player $i$'s payoff is 1 if they match the majority, 0 otherwise.

1. How many pure-strategy profiles exist?
2. Find all pure-strategy NE by checking each profile.

A3. ⭐⭐ Eliminate all strictly dominated strategies by iterated dominance (IESDS) in:

What strategy profile(s) survive?

A4. ⭐⭐ Given a two-player game, prove that a strategy that survives iterated elimination of strictly dominated strategies is never strictly dominated in the original game.

A5. ⭐⭐⭐ OKS connection. A fleet of $n$ robots must each choose a corridor (A or B) to reach the charging station. Corridor $i$ has capacity $c_i$ (robots/minute). If $k$ robots choose corridor $i$, each experiences delay $k / c_i$. Let $c_A = 2, c_B = 3, n = 5$.

1. Model this as a congestion game. What is each robot's strategy set and cost function?
2. Find the Nash equilibrium allocation $(k_A, k_B)$.
3. Find the social optimum (minimizes total delay). Is it different from NE?

Section B — Nash Equilibrium

B1. ⭐ Find all mixed-strategy Nash equilibria in the Matching Pennies game:

B2. ⭐⭐ In the Battle of the Sexes:

1. Find the two pure-strategy NE.
2. Find the mixed-strategy NE.
3. Which NE is Pareto dominant? Which is risk dominant?

B3. ⭐⭐⭐ Find all Nash equilibria (pure and mixed) of the 3×3 game:

Hint: The game is symmetric. Look for a symmetric mixed NE.

B4. ⭐⭐⭐ OKS connection. Two charging stations serve 4 robots. Station 1 charges at rate $\mu_1 = 2$ robots/hour, station 2 at $\mu_2 = 3$ robots/hour. Each robot independently chooses a station to minimize expected wait time (M/M/1 model: wait $\approx 1/(\mu_i - \lambda_i)$ where $\lambda_i$ is arrival rate at station $i$).

1. If each robot chooses station 1 with probability $p$, what is the expected wait for a robot choosing station $i$?
2. Find the symmetric mixed NE probability $p^*$.
3. Is this socially optimal? Compare to a centralized dispatcher.

B5. ⭐ State Nash's existence theorem. Why does it require mixed strategies? Give a 2×2 game with no pure NE to illustrate.

Section C — Zero-Sum Games and LP

C1. ⭐ Find the saddle point (if it exists) and the value of the game:

$$A = \begin{pmatrix} 3 & 1 & 4 \\ 2 & 5 & 2 \\ 6 & 0 & 3 \end{pmatrix}$$

C2. ⭐⭐ For the 2×2 zero-sum game with payoff matrix:

$$A = \begin{pmatrix} 4 & 1 \\ 2 & 3 \end{pmatrix}$$

1. Verify no saddle point exists.
2. Find the minimax mixed strategies and game value using the 2×2 formula.
3. Solve graphically.

C3. ⭐⭐⭐ Formulate the following zero-sum game as a linear program and its dual:

$$A = \begin{pmatrix} 3 & 0 \\ 1 & 4 \\ 2 & 2 \end{pmatrix}$$

Row player has 3 strategies, Column has 2. Write both LPs and explain the duality connection.

import numpy as np
from scipy.optimize import linprog

A = np.array([[3, 0], [1, 4], [2, 2]])

# Column player LP: min c^T y s.t. A^T y >= 1, y >= 0
# Negate for linprog (minimization, <= constraints)
c = -np.ones(2)  # maximize y1 + y2
A_ub = A  # Ay <= 1
b_ub = np.ones(3)
res = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=[(0, None)]*2)
v = 1 / (-res.fun)
q = res.x * v
print(f"Game value: {v:.4f}, Column strategy: {q}")

C4. ⭐⭐⭐ OKS connection. An adversary can inject one of 3 sensor noise patterns into an OKS robot's sensorbar. The robot's estimator can use one of 3 filtering strategies. The resulting localization error (in cm) is:

The robot wants to minimize worst-case error; the adversary maximizes it.

1. Does a saddle point exist?
2. Find the optimal mixed strategy for the robot (minimax).
3. What is the guaranteed worst-case error?

from scipy.optimize import linprog
import numpy as np

# Cost matrix (robot minimizes)
C = np.array([[2, 8, 5], [6, 3, 4], [7, 5, 1]])

# Robot's LP: min v s.t. C^T p <= v*1, sum(p)=1, p>=0
# Variables: [p1, p2, p3, v]
# Objective: min v
c = [0, 0, 0, 1]

# C^T p - v <= 0
A_ub = np.hstack([C.T, -np.ones((3,1))])
b_ub = np.zeros(3)

# sum(p) = 1
A_eq = [[1, 1, 1, 0]]
b_eq = [1]

bounds = [(0, None), (0, None), (0, None), (None, None)]
res = linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, bounds=bounds)
print(f"Optimal mix: {res.x[:3].round(4)}")
print(f"Guaranteed worst-case error: {res.x[3]:.4f} cm")

C5. ⭐ Prove that in a two-player zero-sum game, if $(p^*, q^*)$ and $(p^{**}, q^{**})$ are both NE, then $(p^*, q^{**})$ is also a NE. (This is the interchangeability property.)

Section D — Cooperative Games

D1. ⭐ Three OKS robots can complete tasks individually or in coalitions. The value function (tasks completed per hour):

$$v(\emptyset) = 0, \quad v(\{1\}) = 4, \quad v(\{2\}) = 3, \quad v(\{3\}) = 5$$ $$v(\{1,2\}) = 10, \quad v(\{1,3\}) = 11, \quad v(\{2,3\}) = 9, \quad v(\{1,2,3\}) = 18$$

1. Is the game superadditive? (Is $v(S \cup T) \geq v(S) + v(T)$ for disjoint $S, T$?)
2. Compute each robot's marginal contribution to the grand coalition.

D2. ⭐⭐ For the game in D1, compute the Shapley value $\phi_i$ for each robot.

D3. ⭐⭐⭐ For the game in D1, find the core — the set of allocations $(x_1, x_2, x_3)$ such that no coalition wants to deviate.

D4. ⭐⭐⭐⭐ SHAP connection. The Shapley value is the foundation of SHAP (SHapley Additive exPlanations) in machine learning. Given a model $f$ and input features $\{1, \ldots, d\}$, the "game" is:

$$v(S) = E[f(X) \mid X_S = x_S] - E[f(X)]$$

where $X_S$ are the features in set $S$ fixed to their observed values.

1. Show that the Shapley value satisfies the efficiency axiom: $\sum_i \phi_i = f(x) - E[f(X)]$.
2. For a linear model $f(x) = \beta_0 + \sum_i \beta_i x_i$ with independent features, show that $\phi_i = \beta_i(x_i - E[X_i])$.
3. Why is computing exact SHAP values NP-hard in general?

D5. ⭐⭐⭐⭐ Two players negotiate over splitting a surplus of 100 units. Player 1's disagreement payoff is $d_1 = 20$, player 2's is $d_2 = 30$. Their utility functions are $u_1(x) = x$ and $u_2(x) = \sqrt{x}$.

Find the Nash bargaining solution (NBS) — the split $(x_1, x_2)$ with $x_1 + x_2 = 100$ that maximizes:

$$\max_{x_1, x_2} (u_1(x_1) - u_1(d_1))(u_2(x_2) - u_2(d_2))$$

Section E — Dynamic Games

E1. ⭐ Draw the extensive form (game tree) for the following scenario:

Player 1 moves first, choosing L or R. If L, Player 2 chooses A or B. If R, Player 2 chooses C or D. Terminal payoffs: - L→A: (2, 1), L→B: (0, 0), R→C: (1, 3), R→D: (3, 2)

Find the subgame perfect equilibrium (SPE) using backward induction.

         Player 1
        /        \
       L          R
      /            \
   Player 2     Player 2
   /    \        /    \
  A      B      C      D
(2,1)  (0,0)  (1,3)  (3,2)

E2. ⭐⭐ Ultimatum game. Player 1 proposes a split $(s, 1-s)$ of \$1 where $s \in [0,1]$ is Player 1's share. Player 2 accepts (payoffs $(s, 1-s)$) or rejects (payoffs $(0, 0)$).

1. Find the SPE.
2. Why does the SPE prediction fail in experiments?
3. How would the result change in a two-round alternating offers game with discount factor $\delta$?

E3. ⭐⭐⭐ OKS connection. Consider a repeated interaction between an OKS robot and a Battery Exchange Controller (BEC). In each round, the robot can Trust (approach BEC without verification) or Verify (run diagnostics first, costing 5s). The BEC can Work (function correctly) or Fail (malfunction, costing 60s).

This stage game is repeated $T = 100$ times. The BEC fails with probability $\epsilon = 0.01$ per round (exogenous, not strategic).

1. What is the one-shot optimal strategy for the robot?
2. Design a trigger strategy for when the robot should switch from Trust to Verify.
3. What if the robot uses an exponentially weighted moving average (EWMA) of failures?

# Robot trust controller
class TrustController:
    def __init__(self, window=50, threshold=3, verify_duration=20):
        self.history = []
        self.window = window
        self.threshold = threshold
        self.verify_remaining = 0

    def decide(self, last_outcome):
        self.history.append(last_outcome)  # 1=fail, 0=ok
        if self.verify_remaining > 0:
            self.verify_remaining -= 1
            return "VERIFY"
        recent = self.history[-self.window:]
        if sum(recent) >= self.threshold:
            self.verify_remaining = 20
            return "VERIFY"
        return "TRUST"

E4. ⭐⭐⭐⭐ Vickrey (second-price) auction. $n$ bidders with private values $v_i$ drawn i.i.d. from $U[0, 1]$. Each submits a sealed bid $b_i$. Highest bidder wins and pays the second-highest bid.

1. Prove that bidding $b_i = v_i$ (truthful bidding) is a weakly dominant strategy.
2. What is the expected revenue to the seller with $n$ bidders?
3. How does this relate to the VCG mechanism for multi-item allocation?

E5. ⭐⭐ Consider the centipede game with 6 stages. Players alternate; at each stage the active player can Stop (S) or Continue (C). The pot grows: at stage $k$, stopping gives the active player $2k$ and the other player $2k - 1$.

1. Draw the game tree.
2. Find the SPE by backward induction.
3. What outcome do experiments typically show? What explains the discrepancy?

P1     P2     P1     P2     P1     P2
 |      |      |      |      |      |
 S      S      S      S      S      S
(2,1) (2,3)  (6,3) (4,7)  (10,5) (6,11)
 |      |      |      |      |      |
 C      C      C      C      C      C
 →      →      →      →      →   (12,12)

Section F — Algorithmic GT and Applications

F1. ⭐⭐ A game is a potential game if there exists a function $\Phi: S_1 \times \cdots \times S_n \to \mathbb{R}$ such that for every player $i$ and strategies $s_i, s_i'$:

$$u_i(s_i, s_{-i}) - u_i(s_i', s_{-i}) = \Phi(s_i, s_{-i}) - \Phi(s_i', s_{-i})$$

1. Prove that every potential game has a pure-strategy NE.
2. Show that the congestion game from A5 is a potential game. What is $\Phi$?

F2. ⭐⭐⭐ Braess's Paradox and Price of Anarchy. Consider a network with 4 nodes and 4000 drivers from $s$ to $t$:

     A
   ↗   ↘
  s      t
   ↘   ↗
     B

Edge costs (where $x$ = flow on edge): - $s \to A$: cost $= x/100$ - $A \to t$: cost $= 45$ - $s \to B$: cost $= 45$ - $B \to t$: cost $= x/100$

1. Find the Wardrop equilibrium (NE for routing).
2. Now add an edge $A \to B$ with cost 0. Find the new equilibrium.
3. Compute the Price of Anarchy (PoA = worst NE cost / optimal cost).

F3. ⭐⭐⭐ Implement fictitious play for the following game and report whether it converges:

Run for 1000 iterations. Plot the empirical frequency of Row playing T over time.

import numpy as np
import matplotlib.pyplot as plt

# Payoff matrices
A = np.array([[2, 0], [0, 1]])  # Row player
B = np.array([[1, 0], [0, 2]])  # Column player

T = 1000
row_counts = np.array([0.0, 0.0])  # counts of T, B
col_counts = np.array([0.0, 0.0])  # counts of L, R
row_freq_history = []

for t in range(T):
    # Column's empirical frequency
    if t == 0:
        col_freq = np.array([0.5, 0.5])
    else:
        col_freq = col_counts / col_counts.sum()

    # Row's empirical frequency
    if t == 0:
        row_freq = np.array([0.5, 0.5])
    else:
        row_freq = row_counts / row_counts.sum()

    # Row best-responds to column's empirical freq
    row_payoffs = A @ col_freq  # [E[T], E[B]]
    row_action = np.argmax(row_payoffs)

    # Column best-responds to row's empirical freq
    col_payoffs = B.T @ row_freq  # [E[L], E[R]]
    col_action = np.argmax(col_payoffs)

    row_counts[row_action] += 1
    col_counts[col_action] += 1
    row_freq_history.append(row_counts[0] / row_counts.sum())

plt.figure(figsize=(10, 4))
plt.plot(row_freq_history)
plt.xlabel("Iteration")
plt.ylabel("Freq(Row plays T)")
plt.title("Fictitious Play — Battle of the Sexes variant")
plt.axhline(y=2/3, color='r', linestyle='--', label='Mixed NE: p=2/3')
plt.legend()
plt.tight_layout()
plt.savefig("fictitious_play.png", dpi=100)
plt.show()

F4. ⭐⭐⭐⭐ OKS multi-robot task allocation as auction. A fleet of 4 OKS robots must be assigned to 4 tasks. Robot $i$'s cost for task $j$ is $c_{ij}$:

$$C = \begin{pmatrix} 10 & 15 & 9 & 12 \\ 12 & 8 & 14 & 11 \\ 14 & 12 & 10 & 8 \\ 11 & 9 & 13 & 15 \end{pmatrix}$$

1. Find the socially optimal assignment (minimum total cost) using the Hungarian algorithm.
2. Design a sequential auction mechanism where robots bid on tasks. Show that truthful bidding leads to the optimal assignment.
3. Compute each robot's VCG payment and verify individual rationality.

import numpy as np
from scipy.optimize import linear_sum_assignment

C = np.array([
    [10, 15, 9, 12],
    [12, 8, 14, 11],
    [12, 12, 10, 8],
    [11, 9, 13, 15]
])

row_ind, col_ind = linear_sum_assignment(C)
assignment = list(zip(row_ind, col_ind))
total_cost = C[row_ind, col_ind].sum()
print(f"Assignment: {assignment}")
print(f"Total cost: {total_cost}")
for r, t in assignment:
    print(f"  Robot {r+1} → Task {t+1} (cost {C[r,t]})")

     T1  T2  T3  T4
R2: [12,  8, 14, 11]
R3: [14, 12, 10,  8]
R4: [11,  9, 13, 15]

F5. ⭐⭐⭐⭐ Adversarial robustness as minimax. A neural network classifier $f_\theta$ faces an adversary who adds perturbation $\delta$ (with $\|\delta\|_\infty \leq \epsilon$) to inputs.

1. Formulate adversarial training as a minimax optimization problem.
2. Show the connection to zero-sum game theory.
3. Derive the PGD (Projected Gradient Descent) inner-loop update for the adversary.
4. Why is this problem harder than standard training? Discuss computational and statistical implications.

for epoch in range(num_epochs):
    for x, y in dataloader:
        # Inner loop: find worst-case delta
        delta = torch.zeros_like(x).uniform_(-eps, eps)
        delta.requires_grad_(True)
        for k in range(K):
            loss = criterion(model(x + delta), y)
            loss.backward()
            delta.data += alpha * delta.grad.sign()
            delta.data = delta.data.clamp(-eps, eps)
            delta.data = (x + delta.data).clamp(0, 1) - x
            delta.grad.zero_()

        # Outer loop: update model
        optimizer.zero_grad()
        loss = criterion(model(x + delta.detach()), y)
        loss.backward()
        optimizer.step()

Summary

OKS robotics exercises: A1 (intersection coordination), A5 (corridor congestion), B4 (charging station), C4 (adversarial filtering), E3 (BEC trust strategy), F2 (fleet routing paradox), F4 (multi-robot task auction).