8. Game Theory

The decision models of Chapter 7 treat the uncertain outcome as a move by an indifferent "nature". Game theory studies decisions whose outcome depends on the choices of other rational agents, who optimize against you or alongside you. The chapter starts with two-person zero-sum games, which linear programming duality solves completely, then moves to non-zero-sum and cooperative games. These model price competition, market entry, standards wars and the fair sharing of joint costs, and they underpin security patrol planning, robust optimization and cost allocation in logistics alliances.

<a id="81-two-person-zero-sum-games"></a>

8.1 Two-Person Zero-Sum Games

In a two-person zero-sum game, one player's gain is exactly the other's loss, so cooperation is pointless and each player may assume the worst about the other. This subchapter builds the theory from the payoff matrix up to von Neumann's minimax theorem, and shows that solving such a game is the same as solving a pair of dual linear programs.

Payoff Matrices

Why it matters. Before any solution method can be applied, a conflict has to be written down precisely. The payoff matrix plays the same role for games that $(A, b, c)$ plays for linear programs: once a situation is expressed as one, a whole library of solution methods applies. Building it also forces the modeler to list every option each side has and to agree on a single measure of success.

Theory. A game in normal form (or strategic form) has three ingredients:

• a set of players,
• for each player, a set of pure strategies: the complete plans of action available to that player,
• for each player, a payoff function giving what the player receives for every combination of strategies.

The players choose simultaneously, or at least without seeing each other's choice. Both know the whole game (complete information), both are rational, and each knows that the other is rational.

With two players, call them the row player (with $m$ pure strategies) and the column player (with $n$). The game is zero-sum if the payoffs always add up to zero: whatever one wins, the other loses. A single $m \times n$ matrix $A = (a_{ij})$ then describes the whole game. By convention

• $a_{ij}$ is the payoff to the row player, paid by the column player, when row $i$ meets column $j$,
• the row player maximizes $a_{ij}$ and the column player minimizes it, since $-a_{ij}$ is the column player's payoff.

A constant-sum game, where payoffs always add up to the same $k$ (market shares adding to 100%, or a fixed prize), is strategically identical to a zero-sum game: subtract $k/2$ from every entry. More generally, adding a constant to every entry or multiplying every entry by a positive number changes the value of the game in the same way but never changes the optimal strategies.

A mixed strategy is a probability distribution over pure strategies: $x \in \Delta_m = {x \ge 0, \sum_i x_i = 1}$ for the row player, and $y \in \Delta_n$ for the column player. When the two mix independently, the row player's expected payoff is

$$ E(x, y) = x^\top A y = \sum_{i=1}^{m} \sum_{j=1}^{n} x_i , a_{ij} , y_j. $$

Mixed strategies are developed in detail two topics below. Here, note only that $Ay$ is the vector of expected payoffs of each pure row against $y$, and $x^\top A$ is the vector of expected payoffs of $x$ against each pure column.

The difference from the decision tables of Section 7.2 is the opponent:

	Game against nature (Section 7.2)	Two-person zero-sum game
Who picks the column	an indifferent state of the world	a rational adversary
Does the column react to your choice?	no	yes, to hurt you as much as possible
Sensible criterion	expected value, Hurwicz, regret, ...	maximin, justified by the opponent's goal
Table	payoff table $v_{ij}$	payoff matrix $a_{ij}$

Against nature, maximin is a pessimistic attitude. Against an opponent whose gain is your loss, assuming the worst is simply correct reasoning. An everyday analogy is a fixed pie split between two people: every slice one of them takes is a slice the other loses, so neither has any reason to help the other.

Zero-sum models appear in OR wherever there is a genuine adversary or a worst case: military planning (where von Neumann and Morgenstern's 1944 theory found its first users), security and inspection games (defender against attacker), competition for a fixed market, sports, and robust optimization, where "nature" is modeled as an adversary that chooses the worst data.

Example: two retailers fighting over a fixed market. Retailers A and B each pick one campaign for the season: a price discount, an advertising push or a loyalty program. Market research estimates A's market share for each pair of campaigns. Shares add up to 100%, so the game is constant-sum, and subtracting 50 makes it zero-sum.

import numpy as np

moves = ["discount", "ads", "loyalty"]
# Market share of retailer A (%) for every pair of moves. B gets the rest.
share_A = np.array([[52, 56, 55],
                    [48, 50, 58],
                    [51, 54, 46]])

A = share_A - 50          # constant-sum (100) -> zero-sum: points gained over a 50/50 split
B = -A                    # B's payoff matrix is the negative of A's

print("payoff to A (share points over 50%):")
print("            " + "".join(f"{m:>9}" for m in moves))
for name, row in zip(moves, A):
    print(f"{name:>10}  " + "".join(f"{v:9d}" for v in row))

i, j = moves.index("ads"), moves.index("loyalty")
print(f"\nA plays ads, B plays loyalty: A gets {A[i, j]:+d}, B gets {B[i, j]:+d}")

# Mixed strategies: probability vectors over rows (x) and columns (y)
x = np.array([0.5, 0.5, 0.0])     # A flips a coin between discount and ads
y = np.array([0.2, 0.3, 0.5])     # B's mix
print(f"expected payoff to A, x^T A y = {x @ A @ y:+.2f}")
print("A's expected payoff per row against y:", A @ y)
# payoff to A (share points over 50%):
#              discount      ads  loyalty
#   discount          2        6        5
#        ads         -2        0        8
#    loyalty          1        4       -4
#
# A plays ads, B plays loyalty: A gets +8, B gets -8
# expected payoff to A, x^T A y = +4.15
# A's expected payoff per row against y: [ 4.7  3.6 -0.6]

The matrix is all A needs to reason about the competition, and all B needs too, since B's payoffs are its negative. The last line already hints at how mixed strategies are evaluated: against B's mix $y$, A's three pure campaigns are worth 4.7, 3.6 and $-0.6$ points, and A's coin flip between the first two is worth their average, 4.15. Whether A should flip a coin at all, and what B will actually do, is the subject of the next three topics.

Key takeaways

• A normal-form game lists players, pure strategies and payoffs. In a two-person zero-sum game a single matrix $A$ suffices: $a_{ij}$ is paid by the column player to the row player.
• The row player maximizes, the column player minimizes. Constant-sum games become zero-sum by subtracting a constant.
• Adding a constant to all payoffs or scaling them by a positive factor changes the value but not the optimal strategies.
• With mixed strategies $x$ and $y$, the expected payoff is the bilinear form $x^\top A y$.
• Unlike nature in Section 7.2, the opponent reacts to your choice, so worst-case reasoning is justified.

Practice

1. (Beginner) Write the payoff matrix of rock-paper-scissors for the row player (win $= 1$, loss $= -1$, tie $= 0$). Check that $A = -A^\top$. What does this property say about the two players' positions, and what do you expect the value of the game to be?
2. (Intermediate) Two TV networks schedule their flagship show at 8 pm or 9 pm. Audience studies say network 1 gets 60% of viewers if both choose 8 pm, 45% if both choose 9 pm, 70% if it takes 8 pm and network 2 takes 9 pm, and 35% in the opposite case. Build the zero-sum matrix and compute network 1's expected payoff for $x = (0.5, 0.5)$ against each pure strategy of network 2.
3. (Interview) "A colleague models a competitor's pricing decisions as a zero-sum game. When is that assumption wrong, and what goes wrong in the analysis?" Hint: is the total profit really fixed? Think about price wars that shrink both firms' profits, and about outcomes that are good for both. Section 8.2 treats such games.

Saddle Points and Pure Strategies

Why it matters. Some games have a stable solution in pure strategies: each player has a single best move that remains best even if the opponent learns it in advance. Checking for such a solution takes a few seconds, and when one exists the game is solved without any probability. When none exists, the check shows exactly how large the gap is that mixed strategies must close.

Theory. Think of each player as asking "what is the worst that can happen to me?".

• If the row player picks row $i$, the column player can hold it to $\min_j a_{ij}$, the security level of row $i$. The row player picks the row with the best security level, giving the lower value (maximin): $$ \underline{v} = \max_i \min_j a_{ij}. $$
• If the column player picks column $j$, the row player can extract $\max_i a_{ij}$. The column player picks the column with the smallest such loss, giving the upper value (minimax): $$ \overline{v} = \min_j \max_i a_{ij}. $$

The lower value never exceeds the upper value. For any $i$ and $j$, $\min_{j'} a_{ij'} \le a_{ij} \le \max_{i'} a_{i'j}$. The left side does not depend on $j$ and the right side does not depend on $i$, so taking the maximum over $i$ on the left and the minimum over $j$ on the right gives $\underline{v} \le \overline{v}$.

An entry $a_{i^* j^*}$ is a saddle point if it is the smallest entry in its row and the largest in its column:

$$ a_{i j^} ;\le; a_{i^ j^} ;\le; a_{i^ j} \qquad \text{for all } i, j. $$

The name comes from the shape of a horse saddle, which is a minimum along one direction and a maximum along the other. A saddle point exists exactly when $\underline{v} = \overline{v}$, and then this common number is the value $v$ of the game. Saddle points have three useful properties:

• Equilibrium. Neither player gains by deviating alone: the row player cannot do better in column $j^$, and the column player cannot do better in row $i^$.
• Same value. All saddle points of a matrix have the same value.
• Interchangeability. If $(i_1, j_1)$ and $(i_2, j_2)$ are saddle points, so are $(i_1, j_2)$ and $(i_2, j_1)$. Players need no coordination: each picks any of its saddle strategies.

Because the optimal pure strategy stays optimal even when announced, secrecy is worthless in a game with a saddle point.

The hand procedure is to write the row minima on the right and the column maxima at the bottom, then compare the best of each:

                 B: discount    ads    loyalty  | row min
A: discount            2*        6        5     |    2   <- largest row minimum
A: ads                -2         0        8     |   -2
A: loyalty             1         4       -4     |   -4
------------------------------------------------+
column max             2         6        8
                       ^ smallest column maximum
lower value 2 = upper value 2  ->  saddle point (discount, discount), value 2

Example: finding saddle points in code.

import numpy as np

moves = ["discount", "ads", "loyalty"]
A = np.array([[ 2, 6,  5],          # payoff to A (row), paid by B (column)
              [-2, 0,  8],
              [ 1, 4, -4]])

def pure_solution(A):
    row_min = A.min(axis=1)              # worst case of each row (A's security level)
    col_max = A.max(axis=0)              # worst case of each column for B
    lower, upper = row_min.max(), col_max.min()
    saddles = [(i, j) for i in range(A.shape[0]) for j in range(A.shape[1])
               if A[i, j] == row_min[i] == lower and A[i, j] == col_max[j] == upper]
    return row_min, col_max, lower, upper, saddles

row_min, col_max, lower, upper, saddles = pure_solution(A)
print("row minima:", row_min, "-> maximin (lower value) =", lower)
print("col maxima:", col_max, "-> minimax (upper value) =", upper)
for i, j in saddles:
    print(f"saddle point: A={moves[i]}, B={moves[j]}, value={A[i, j]}")

# Check the equilibrium property: no unilateral deviation helps
i, j = saddles[0]
print("A's payoffs if B stays on discount:", A[:, j], "-> best is", A[:, j].max())
print("B's losses  if A stays on discount:", A[i, :], "-> best is", A[i, :].min())

# A game without a saddle point (penalty kick, scoring probability for the kicker)
K = np.array([[0.55, 0.90],
              [0.95, 0.70]])
_, _, lo, up, s = pure_solution(K)
print(f"\npenalty kick: lower value {lo}, upper value {up}, saddle points: {s}")
# row minima: [ 2 -2 -4] -> maximin (lower value) = 2
# col maxima: [2 6 8] -> minimax (upper value) = 2
# saddle point: A=discount, B=discount, value=2
# A's payoffs if B stays on discount: [ 2 -2  1] -> best is 2
# B's losses  if A stays on discount: [2 6 5] -> best is 2
#
# penalty kick: lower value 0.7, upper value 0.9, saddle points: []

Both retailers should run a discount, and A ends the season with 52% of the market. Even if B announced its discount in advance, A could not do better than discounting too (2 beats $-2$ and 1), and B cannot reduce A's gain below 2 by switching (6 and 5 are worse for B). The penalty-kick matrix has no saddle point. By choosing a pure strategy, the kicker can guarantee only 0.70, while the goalkeeper can hold the kicker to 0.90 at best. The gap of 0.20 is the price of predictability, and the next topic shows how randomizing recovers most of it.

Key takeaways

• The lower value $\max_i \min_j a_{ij}$ is what the row player can guarantee with a pure strategy. The upper value $\min_j \max_i a_{ij}$ is what the column player can hold it to.
• Always $\underline{v} \le \overline{v}$. Equality holds exactly when the matrix has a saddle point, which is then the solution of the game.
• A saddle point is the minimum of its row and the maximum of its column. Saddle points share the same value and are interchangeable.
• In a game with a saddle point, announcing your strategy costs nothing. Without one, pure strategies leave a gap $\overline{v} - \underline{v} > 0$.

Practice

1. (Beginner) Find all saddle points of $A = \begin{pmatrix} 4 & 3 & 5 \ 2 & 1 & 6 \ 5 & 3 & 4 \end{pmatrix}$ by hand, using row minima and column maxima. Verify that they have the same value and illustrate the interchangeability property.
2. (Intermediate) Prove the interchangeability property: if $(i_1, j_1)$ and $(i_2, j_2)$ are saddle points, then $a_{i_1 j_1} = a_{i_2 j_2}$ and $(i_1, j_2)$ is also a saddle point. Hint: chain the saddle-point inequalities through $a_{i_1 j_2}$ and $a_{i_2 j_1}$.
3. (Interview) "Your competitor publishes its strategy before you choose. In a game with a saddle point, is that information worth anything? And in a game without one?" Hint: compare what each player can guarantee when moving first and when moving second, using $\underline{v}$ and $\overline{v}$.

Mixed Strategies

Why it matters. When there is no saddle point, every pure strategy can be exploited by an opponent who predicts it. Randomizing is the rational defense: an opponent who cannot predict your move cannot exploit it. This idea explains bluffing in poker, a kicker's choice of side in a penalty, random tax audits, and the randomized patrol schedules used to protect airports and ports.

Theory. A mixed strategy is a probability vector $x \in \Delta_m$ for the row player and $y \in \Delta_n$ for the column player. The expected payoff $x^\top A y$ is linear in $x$ for fixed $y$, and linear in $y$ for fixed $x$. Pure strategies are the vertices of the simplex, and a linear function over the simplex attains its extremes at vertices. This gives two working facts:

• Against a fixed $y$, some pure strategy is always a best response. So the worst case of a mixed strategy $x$ only needs to be checked against the pure columns: $$ \min_{y \in \Delta_n} x^\top A y = \min_j , (x^\top A)_j . $$
• Indifference principle. In an optimal pair $(x^, y^)$, every pure strategy a player uses with positive probability earns exactly the value $v$ against the opponent's optimal mix. If one used strategy earned more than another, moving probability toward it would increase the player's payoff, so the mix was not optimal.

The indifference principle turns the search for optimal mixes into linear equations. For a $2 \times 2$ game $A = \begin{pmatrix} a & b \ c & d \end{pmatrix}$ without a saddle point, the row player chooses $p = P(\text{row } 1)$ so that the column player gets the same result from both columns:

$$ p,a + (1-p),c ;=; p,b + (1-p),d \quad\Longrightarrow\quad p = \frac{d - c}{a - b - c + d}, \qquad q = \frac{d - b}{a - b - c + d}, \qquad v = \frac{a d - b c}{a - b - c + d}, $$

where $q = P(\text{column } 1)$ makes the row player indifferent in the same way. Notice the twist: a player's optimal mix is determined by the opponent's payoffs, because its purpose is to leave the opponent nothing to exploit. Improving one of your own options can therefore lower the probability with which you should use it (Practice 2).

A mixed strategy can be read as a frequency over many plays, or as a single genuinely random draw. Randomizing must be real: a pattern such as "left, right, left, right" looks balanced but is exploitable once spotted. Palacios-Huerta (2003) found that professional penalty takers mix sides at frequencies very close to the minimax predictions, with no detectable patterns.

Example: penalty kicks. The kicker aims left or right, and the goalkeeper dives left or right at the same moment. Entries are scoring probabilities. The kicker maximizes them and the goalkeeper minimizes them (a constant-sum game: the keeper's payoff is one minus the kicker's). The kicker is stronger on the right side: even when the keeper guesses correctly, a shot to the right scores 70% of the time against 55% to the left.

import numpy as np

# Scoring probability for the kicker (row player, maximizes).
# Rows: kicker aims Left / Right. Columns: goalkeeper dives Left / Right.
K = np.array([[0.55, 0.90],
              [0.95, 0.70]])

def solve_2x2(M):
    """Optimal mixed strategies of a 2x2 zero-sum game with no saddle point."""
    (a, b), (c, d) = M
    den = a - b - c + d
    p = (d - c) / den            # row player's prob. of row 1 (makes columns equal)
    q = (d - b) / den            # column player's prob. of column 1 (makes rows equal)
    v = (a * d - b * c) / den    # value of the game
    return np.array([p, 1 - p]), np.array([q, 1 - q]), v

x, y, v = solve_2x2(K)
print(f"kicker   aims left  with p = {x[0]:.4f}")
print(f"keeper   dives left with q = {y[0]:.4f}")
print(f"value (scoring probability) = {v:.4f}")
print("kicker's payoff vs each keeper column:", x @ K)    # equal -> keeper is indifferent
print("keeper's loss  vs each kicker row:   ", K @ y)    # equal -> kicker is indifferent

# What happens when the kicker is predictable?
rng = np.random.default_rng(0)
for name, p in [("always left", 1.0), ("always right", 0.0), ("optimal mix", x[0])]:
    mix = np.array([p, 1 - p])
    best_reply = np.argmin(mix @ K)                    # keeper exploits the known mix
    worst = (mix @ K)[best_reply]
    aim = np.where(rng.random(10_000) < p, 0, 1)       # simulate 10,000 kicks
    goals = rng.random(10_000) < K[aim, best_reply]    # each kick scores with prob. K[aim, dive]
    print(f"{name:13} keeper best reply: dive {'LR'[best_reply]}  "
          f"P(goal) = {worst:.3f}  simulated = {goals.mean():.3f}")
# kicker   aims left  with p = 0.4167
# keeper   dives left with q = 0.3333
# value (scoring probability) = 0.7833
# kicker's payoff vs each keeper column: [0.78333333 0.78333333]
# keeper's loss  vs each kicker row:    [0.78333333 0.78333333]
# always left   keeper best reply: dive L  P(goal) = 0.550  simulated = 0.544
# always right  keeper best reply: dive R  P(goal) = 0.700  simulated = 0.699
# optimal mix   keeper best reply: dive L  P(goal) = 0.783  simulated = 0.781

The kicker should aim left with probability $5/12 \approx 0.42$, and the keeper should dive left with probability $1/3$. With these mixes the kicker scores 78.3% of the time whatever the keeper does. Both entries of x @ K are equal, so the keeper's "best reply" to the optimal mix is only a tie-break: every reply gives 0.783. A predictable kicker does much worse: 55% when always aiming left, 70% when always aiming right. Randomizing lifts the kicker's guarantee from 0.70 to 0.783, and the keeper's mix brings the most the kicker can expect down from 0.90 to the same 0.783. The two guarantees now meet, and the next topic shows that this always happens.

Key takeaways

• A mixed strategy is a probability distribution over pure strategies. Its expected payoff $x^\top A y$ is bilinear.
• Against a fixed opponent mix, some pure strategy is a best response, so a mixed strategy's guarantee is $\min_j (x^\top A)_j$.
• Indifference principle: at the optimum, every strategy used with positive probability earns exactly the value against the opponent's optimal mix.
• For $2 \times 2$ games without a saddle point: $p = \frac{d-c}{a-b-c+d}$, $q = \frac{d-b}{a-b-c+d}$, $v = \frac{ad-bc}{a-b-c+d}$.
• Each player's optimal mix is set by the opponent's payoffs. Randomization must be genuine and free of patterns.

Practice

1. (Beginner) Solve the game $A = \begin{pmatrix} 3 & -1 \ -2 & 1 \end{pmatrix}$: check that there is no saddle point, compute $p$, $q$ and $v$ with the formulas, and verify both indifference conditions numerically with solve_2x2.
2. (Intermediate) The kicker practices and raises the scoring probability when aiming left while the keeper dives right from 0.90 to 0.95. Recompute the optimal mixes and the value. Does the kicker now aim left more or less often? Explain the result using the indifference principle.
3. (Interview) "Why would a rational player ever deliberately randomize? Against any fixed opponent strategy, some pure strategy is at least as good as any mix." Hint: the statement is true against a known opponent mix. Compare the guarantee of each pure strategy (0.55 and 0.70) with that of the optimal mix (0.783) when the opponent can react.

Minimax Theorem

Why it matters. Mixed strategies would be of limited use if it still mattered who commits first. Von Neumann's minimax theorem (1928) says that it does not: once mixing is allowed, every finite zero-sum game has a single value, and both players have strategies that guarantee it. The theorem is the foundation of game theory, and the same "min-max equals max-min" statement reappears in LP duality, robust optimization and adversarial machine learning.

Theory. Extend the lower and upper values to mixed strategies. Because the best reply to a mix can always be taken pure,

$$ \underline{v} = \max_{x \in \Delta_m} \min_{j} ,(x^\top A)j , \qquad \overline{v} = \min{y \in \Delta_n} \max_{i} ,(A y)_i . $$

The same argument as for pure strategies shows $\underline{v} \le \overline{v}$: whatever $x$ guarantees cannot exceed whatever $y$ concedes.

Minimax theorem. For every finite matrix $A$,

$$ \max_{x \in \Delta_m} \min_{y \in \Delta_n} x^\top A y ;=; \min_{y \in \Delta_n} \max_{x \in \Delta_m} x^\top A y ;=; v . $$

Consequences:

• Optimal strategies exist. There are $x^$ and $y^$ such that $(x^, y^)$ is a saddle point of the bilinear function: $x^\top A y^* \le x^{\top} A y^ \le x^{*\top} A y$ for all $x, y$.
• Guarantees. With $x^$ the row player gets at least $v$ whatever the opponent does. With $y^$ the column player pays at most $v$.
• Announcing is harmless. Revealing an optimal mixed strategy costs nothing (the outcome of each draw must stay secret, of course).
• Interchangeability. The sets of optimal strategies are convex polytopes, and any optimal $x$ paired with any optimal $y$ is an equilibrium.
• Symmetric games. If $A = -A^\top$ (both players have the same options and payoffs), then $v = 0$.

The inequality $\underline{v} \le \overline{v}$ is easy. Equality is the deep part: it can be proved with a separating hyperplane or, most directly for OR, with LP strong duality (next topic). Finiteness matters: in the game "each player names a positive integer and the larger number wins 1", no value exists (Practice 2). Sion's theorem extends the result to functions that are convex in one variable and concave in the other over compact convex sets, which is the setting of robust optimization ($\min_x \max_{u \in U}$) and adversarial training.

The graphical method for $2 \times n$ games. If the row player has two strategies, a mix is a single number $p = P(\text{row } 1)$. Against column $j$, the expected payoff $p,a_{1j} + (1-p),a_{2j}$ is a line in $p$. The column player picks the lowest line, so the row player's guarantee is the lower envelope of the lines, and the best $p$ is the highest point of that envelope. Only the columns whose lines pass through that point are used by the column player. For $m \times 2$ games, the same picture uses the upper envelope over $q$, and the column player looks for its lowest point.

Example: a patrol game. A security team (row, maximizes) patrols one of two routes, and an intruder (column, minimizes) tries one of three gates. The entries are the team's score: positive when the intruder is caught, negative when the intrusion succeeds.

import numpy as np

# Patrol game: security (row, maximizes) picks a route, intruder (column) picks a gate.
A = np.array([[ 3, -1, 1],      # route 1 vs gates A, B, C
              [-2,  4, 0]])     # route 2

# Row player's side: for each p = P(route 1), the intruder picks the worst column
p = np.linspace(0, 1, 100_001)
lines = np.outer(p, A[0]) + np.outer(1 - p, A[1])   # expected payoff per gate, shape (N, 3)
envelope = lines.min(axis=1)                         # lower envelope
k = envelope.argmax()
print(f"max over p of min over gates: p* = {p[k]:.4f}, lower value = {envelope[k]:.4f}")

# Column player's side: grid over the 3-gate simplex, row player picks the worst row
best = (np.inf, None)
g = np.linspace(0, 1, 601)
for y1 in g:
    for y2 in g[g <= 1 - y1 + 1e-12]:
        y = np.array([y1, y2, max(0.0, 1 - y1 - y2)])
        worst = (A @ y).max()                        # security's best reply
        if worst < best[0]:
            best = (worst, y)
print(f"min over y of max over routes: y* = {np.round(best[1], 4)}, upper value = {best[0]:.4f}")

# Pure strategies only: the gap the minimax theorem closes
print("pure maximin =", A.min(axis=1).max(), " pure minimax =", A.max(axis=0).min())
# max over p of min over gates: p* = 0.6667, lower value = 0.6667
# min over y of max over routes: y* = [0.     0.1667 0.8333], upper value = 0.6667
# pure maximin = -1  pure minimax = 1

The lines are $5p - 2$ (gate A), $4 - 5p$ (gate B) and $p$ (gate C). Plotting them shows the lower envelope (#) and its highest point O at $p = 2/3$:

 4.00 |bbb
      |   bbb
      |      bbbbb
 3.00 |           bbb                                             aa
      |              bbbbb                                   aaaaa
      |                   bbbb                           aaaa
 2.00 |                       bbb                    aaaa
      |                          bbbb             aaa
      |                              bbbbb    aaaa
 1.00 |                                   aaaa            cccccccccc
      |                              ##########O##cccccccc
      |           cccccccccccccccc###             ###
 0.00 |ccccccccccc            ####                   ####
      |                   ####                           ####
      |              #####                                   #####
-1.00 |           ###                                             ##
      |      #####
      |   ###
-2.00 |###
      +-------------------------------------------------------------
       0                             0.5       2/3                 1   p = P(route 1)

Two independent brute-force searches, one over the row player's mixes and one over the column player's, arrive at the same number, $2/3$, exactly as the theorem promises. With pure strategies the team could guarantee only $-1$ and the intruder could hold it to 1. The envelope peaks where the lines of gates B and C cross, so the intruder mixes only those two gates ($1/6$ and $5/6$). Gate A's line lies above the peak, so the intruder never uses it: at $p = 2/3$, gate A would give the team $4/3$.

Key takeaways

• With mixed strategies, $\max_x \min_y x^\top A y = \min_y \max_x x^\top A y = v$ for every finite matrix game.
• Optimal strategies $x^$ and $y^$ always exist, guarantee $v$ to each side, are interchangeable, and can be announced without loss.
• The minimax theorem is equivalent to LP strong duality. Sion's theorem extends it to convex-concave problems such as robust optimization.
• For $2 \times n$ games, the graphical method finds $p^*$ at the highest point of the lower envelope. Only the columns through that point are used.

Practice

1. (Beginner) Solve $A = \begin{pmatrix} 2 & 3 & 11 \ 7 & 5 & 2 \end{pmatrix}$ with the graphical method: write the three lines, find the highest point of the lower envelope, identify the active columns, and solve the resulting $2 \times 2$ game for the column player's mix.
2. (Intermediate) In the game where each player names a positive integer and the larger number wins 1 (ties pay 0), show that for every mixed strategy of the row player the column player has a reply that wins with probability arbitrarily close to 1. Conclude that $\underline{v} = -1 < 1 = \overline{v}$, and explain which hypothesis of the minimax theorem fails.
3. (Interview) "How does the minimax theorem relate to adversarial training in machine learning, or to robust optimization in OR?" Hint: both solve $\min_{\theta} \max_{\delta}$ problems. When can the order of min and max be swapped (convexity in one variable, concavity in the other), and what changes for nonconvex neural networks?

Solving Games via Linear Programming

Why it matters. The graphical method only works when one player has two strategies. Real games, such as patrol schedules, resource allocation contests or abstractions of poker, have hundreds or millions of strategies. Linear programming solves any finite zero-sum game in polynomial time. Even better, the two players' problems are a primal-dual pair (Section 2.4), so one solver call returns both optimal strategies, and the minimax theorem follows from strong duality.

Theory. The row player wants the mix with the best guarantee: maximize $v$ such that every column pays at least $v$ against $x$.

$$ \begin{aligned} \text{(Row)}\quad \max_{x, v} ;; & v \ \text{s.t.} ;; & \textstyle\sum_{i} a_{ij} x_i \ge v, && j = 1, \dots, n \quad (\text{dual variable } y_j \ge 0) \ & \textstyle\sum_i x_i = 1, && (\text{dual variable } w) \ & x \ge 0, ; v \text{ free.} \end{aligned} $$

The column player solves the mirror problem: minimize $w$ such that every row earns at most $w$ against $y$.

$$ \begin{aligned} \text{(Column)}\quad \min_{y, w} ;; & w \ \text{s.t.} ;; & \textstyle\sum_{j} a_{ij} y_j \le w, && i = 1, \dots, m \ & \textstyle\sum_j y_j = 1, \quad y \ge 0, ; w \text{ free.} \end{aligned} $$

Writing the dual of (Row) with the dual variables indicated above gives exactly (Column). Duality theory then delivers the whole minimax theorem:

LP duality fact (Section 2.4)	Game-theoretic meaning
Both LPs are feasible and bounded (any $x$, any $y$)	both players have optimal strategies
Strong duality: $v^* = w^*$	the minimax theorem: $\underline{v} = \overline{v}$
The dual values of (Row)'s column constraints	the column player's optimal mix $y^*$
Complementary slackness: $y_j^* > 0 \Rightarrow (x^{*\top} A)_j = v$	indifference principle: used columns earn exactly $v$
Complementary slackness: $(A y^)_i < v \Rightarrow x_i^ = 0$	a row that earns less than $v$ is never played

Older textbooks use an equivalent formulation without a free variable. Add a constant to all entries so that $v > 0$, set $u_i = x_i / v$, and solve $\min \sum_i u_i$ subject to $A^\top u \ge \mathbf{1}$, $u \ge 0$. Then $v = 1 / \sum_i u_i$ and $x = v,u$. The column player's version is $\max \sum_j z_j$ subject to $A z \le \mathbf{1}$. Modern solvers handle free variables directly, so the first formulation is simpler.

The LP has $m + 1$ variables and $n + 1$ constraints. When the number of pure strategies is astronomical (patrol routes, network paths, bidding schedules), the double oracle algorithm applies the column generation idea of Section 2.6: solve the game restricted to a few strategies, compute each player's best response to the opponent's current mix, add it if it improves, and repeat until no best response improves.

Example: Colonel Blotto. Colonel A has 4 regiments and Colonel B has 3, to be split between two battlefields. A side that outnumbers the other on a battlefield wins 1 point plus 1 point for each enemy regiment captured there. Ties score 0. Each split of the regiments is a pure strategy, and the code builds the $5 \times 4$ payoff matrix and solves (Row) with linprog.

import numpy as np
from scipy.optimize import linprog

# Colonel Blotto: A splits 4 regiments, B splits 3, over two battlefields.
# Winning a battlefield scores 1 plus the enemy regiments captured there; ties score 0.
SA = [(a, 4 - a) for a in range(4, -1, -1)]      # (4,0) (3,1) (2,2) (1,3) (0,4)
SB = [(b, 3 - b) for b in range(3, -1, -1)]      # (3,0) (2,1) (1,2) (0,3)

def field(a, b):
    """Payoff to A on one battlefield where A has a regiments and B has b."""
    return (1 + b) if a > b else -(1 + a) if a < b else 0

A = np.array([[sum(field(a, b) for a, b in zip(sa, sb)) for sb in SB] for sa in SA])
print("payoff matrix (rows = A's splits, cols = B's splits):\n", A)

def solve_zero_sum(A):
    """Row player's LP: max v s.t. sum_i a_ij x_i >= v for all j, sum x = 1, x >= 0."""
    m, n = A.shape
    c = np.r_[np.zeros(m), -1.0]                   # variables [x_1..x_m, v]; maximize v
    A_ub = np.c_[-A.T, np.ones(n)]                 # v - sum_i a_ij x_i <= 0 for each column j
    A_eq = np.r_[np.ones(m), 0.0][None, :]         # sum_i x_i = 1
    res = linprog(c, A_ub=A_ub, b_ub=np.zeros(n), A_eq=A_eq, b_eq=[1],
                  bounds=[(0, None)] * m + [(None, None)], method="highs")
    x, v = res.x[:m], res.x[m]
    y = -res.ineqlin.marginals                     # duals of the column constraints = B's strategy
    return x, y, v

x, y, v = solve_zero_sum(A)
print(f"value of the game: {v:.4f}")
for s, p in zip(SA, x):                            # abs() hides -0.0000 solver noise
    print(f"  A plays {s} with prob {abs(p):.4f}")
for s, q in zip(SB, y):
    print(f"  B plays {s} with prob {abs(q):.4f}")

# Certificates: x guarantees at least v against every column, y concedes at most v to every row
print("A's payoff vs each pure B:", np.round(x @ A, 4) + 0)
print("A's payoff per pure A row vs y:", np.round(A @ y, 4) + 0)
# payoff matrix (rows = A's splits, cols = B's splits):
#  [[ 4  2  1  0]
#  [ 1  3  0 -1]
#  [-2  2  2 -2]
#  [-1  0  3  1]
#  [ 0  1  2  4]]
# value of the game: 1.5556
#   A plays (4, 0) with prob 0.4444
#   A plays (3, 1) with prob 0.0000
#   A plays (2, 2) with prob 0.1111
#   A plays (1, 3) with prob 0.0000
#   A plays (0, 4) with prob 0.4444
#   B plays (3, 0) with prob 0.0333
#   B plays (2, 1) with prob 0.5333
#   B plays (1, 2) with prob 0.3556
#   B plays (0, 3) with prob 0.0778
# A's payoff vs each pure B: [1.5556 1.5556 1.5556 1.5556]
# A's payoff per pure A row vs y: [1.5556 1.5556 1.5556 1.1111 1.5556]

The value is $14/9 \approx 1.56$ points for A. A's optimal strategy is surprising: concentrate everything on one battlefield (each side with probability $4/9$), or split evenly ($1/9$), but never split 3-1. The last two lines are the optimality certificate. Against every pure B strategy, $x^$ earns exactly $14/9$, and against $y^$ no pure A strategy earns more than $14/9$. Complementary slackness is visible too. Split (1,3) earns only 1.11 against $y^*$, so it gets probability 0. Split (3,1) earns exactly $v$ and still gets probability 0, which is allowed, since complementary slackness only works in one direction. B's optimal strategy is not unique in this game: the solver returns one vertex of the polytope of optimal mixes.

Key takeaways

• The row player's LP maximizes $v$ subject to $A^\top x \ge v\mathbf{1}$, $\mathbf{1}^\top x = 1$, $x \ge 0$. The column player's LP is its dual.
• Strong duality gives the minimax theorem, and complementary slackness gives the indifference principle.
• One solver call returns both strategies: $x^$ from the primal and $y^$ from the duals of the column constraints.
• The certificate $\min_j (x^{\top} A)_j = \max_i (A y^)_i$ proves optimality without trusting the solver.
• For huge strategy sets, the double oracle algorithm generates strategies on demand, like column generation.

Practice

1. (Beginner) Use solve_zero_sum on rock-paper-scissors and on the penalty-kick matrix. Confirm the values and strategies found earlier, and inspect which constraints have zero dual values.
2. (Intermediate) Implement the classical formulation ($\min \sum_i u_i$ subject to $A^\top u \ge \mathbf{1}$, $u \ge 0$) after shifting the matrix by a constant. Check that it reproduces the Blotto solution. What goes wrong if you skip the shift and the value is negative?
3. (Interview) "A security agency must assign 5 patrol teams to 30 possible targets, and an attacker picks one target. There are $\binom{30}{5} = 142{,}506$ pure patrol schedules. How would you compute an optimal randomized schedule?" Hint: do not enumerate. Think about the double oracle algorithm (best responses as column generation), or a compact formulation over the coverage probability of each target.

Dominance Reduction

Why it matters. Before solving a game, it is often possible to delete strategies that no rational player would ever use. This shrinks a game enough to solve by hand (down to $2 \times 2$ or $2 \times n$), reduces the size of the LP, and tells decision makers which options are simply bad, which is often the most useful insight of all.

Theory. Because the two players have opposite goals, dominance runs in opposite directions for rows and columns:

Player	Goal	Strategy $r$ is strictly dominated by $s$ if
Row	maximize	$a_{sj} > a_{rj}$ for every column $j$
Column	minimize	$a_{is} < a_{ir}$ for every row $i$

With weak inequalities (and at least one strict), the dominance is weak. A strategy can also be dominated by a mix of other strategies. Row $r$ is dominated by a mix $\lambda$ if $\sum_k \lambda_k a_{kj} > a_{rj}$ for all $j$. Such a row may not be dominated by any single row, yet it is still never worth playing. Checking for mixed dominance is a small LP: maximize the margin $\varepsilon$ subject to $\sum_k \lambda_k a_{kj} \ge a_{rj} + \varepsilon$ for all $j$, with $\lambda$ a probability vector. The row is strictly dominated exactly when the optimal $\varepsilon$ is positive.

Dominance is applied iteratively: removing a row can make a column dominated, which can make another row dominated, and so on.

• Removing strictly dominated strategies is always safe: such strategies get probability zero in every optimal strategy, and the value and all optimal strategies of the reduced game are those of the original.
• Removing weakly dominated strategies preserves the value and at least one optimal strategy, but it can delete other optimal strategies, and the order of elimination can matter (Practice 2).

Example: reducing a $4 \times 4$ game to $2 \times 2$. The code repeatedly looks for a row, then a column, that is strictly dominated by a pure strategy or a mix, using the LP above. A column of $A$ is a row of $-A^\top$, so the same function serves both players.

import numpy as np
from scipy.optimize import linprog

def dominated_by_mix(M, k):
    """Is row k of M strictly dominated by a mix of the other rows? Returns (bool, mix)."""
    others = [i for i in range(M.shape[0]) if i != k]
    if not others:
        return False, None
    m, n = len(others), M.shape[1]
    # variables [x (over other rows), eps]; maximize eps s.t. x^T M_others >= M_k + eps
    A_ub = np.c_[-M[others].T, np.ones(n)]
    res = linprog(np.r_[np.zeros(m), -1.0], A_ub=A_ub, b_ub=-M[k],
                  A_eq=np.r_[np.ones(m), 0.0][None, :], b_eq=[1],
                  bounds=[(0, None)] * m + [(None, 1.0)], method="highs")
    return res.x[-1] > 1e-9, {i: round(float(w), 3) for i, w in zip(others, res.x[:m])}

def reduce_game(A, rows, cols):
    rows, cols = list(rows), list(cols)
    changed = True
    while changed:
        changed = False
        # Row player maximizes: drop a row beaten by a mix of other rows
        for k in range(len(rows)):
            dom, mix = dominated_by_mix(A, k)
            if dom:
                by = {rows[i]: w for i, w in mix.items() if w > 0}
                print(f"remove row {rows[k]:3} (dominated by {by})")
                A, rows, changed = np.delete(A, k, axis=0), rows[:k] + rows[k + 1:], True
                break
        if changed:
            continue
        # Column player minimizes: column k is dominated if -column k is dominated in -A^T
        for k in range(len(cols)):
            dom, mix = dominated_by_mix(-A.T, k)
            if dom:
                by = {cols[i]: w for i, w in mix.items() if w > 0}
                print(f"remove col {cols[k]:3} (dominated by {by})")
                A, cols, changed = np.delete(A, k, axis=1), cols[:k] + cols[k + 1:], True
                break
    return A, rows, cols

A = np.array([[8, 2, 9, 3],
              [4, 6, 5, 7],
              [7, 1, 0, 2],
              [5, 3, 6, 4]])
R, rows, cols = reduce_game(A, ["r1", "r2", "r3", "r4"], ["c1", "c2", "c3", "c4"])
print("reduced game, rows", rows, "cols", cols, "\n", R)

(a, b), (c, d) = R                                   # 2x2 closed form (no saddle point)
den = a - b - c + d
print(f"p(r1) = {(d - c) / den}, q(c1) = {(d - b) / den}, value = {(a * d - b * c) / den}")
# remove row r3  (dominated by {'r1': 1.0})
# remove row r4  (dominated by {'r1': 0.5, 'r2': 0.5})
# remove col c3  (dominated by {'c1': 1.0})
# remove col c4  (dominated by {'c2': 1.0})
# reduced game, rows ['r1', 'r2'] cols ['c1', 'c2']
#  [[8 2]
#  [4 6]]
# p(r1) = 0.25, q(c1) = 0.5, value = 5.0

The elimination sequence shows each kind of dominance:

start                  remove r3 (< r1)       remove r4 (< mix of r1, r2)
      c1 c2 c3 c4            c1 c2 c3 c4             c1 c2 c3 c4
  r1   8  2  9  3        r1   8  2  9  3         r1   8  2  9  3
  r2   4  6  5  7        r2   4  6  5  7         r2   4  6  5  7
  r3   7  1  0  2        r4   5  3  6  4
  r4   5  3  6  4

remove c3 (> c1)       remove c4 (> c2)
      c1 c2 c4               c1 c2
  r1   8  2  3           r1   8  2
  r2   4  6  7           r2   4  6

• r3 is beaten by r1 in every column (pure dominance).
• r4 = (5, 3, 6, 4) is not beaten by r1 (it does better in c2) or by r2 (it does better in c1), but the 50/50 mix of r1 and r2, (6, 4, 7, 5), beats it everywhere. A pure-only check would miss it.
• c3 is worse for the column player than c1 in every remaining row, but only after r3 is gone: in r3, c3 costs 0 against c1's 7. This is the iterative effect.
• c4 is beaten by c2 in every row.

The reduced $2 \times 2$ game has no saddle point, and the formulas give $x^* = (0.25, 0.75, 0, 0)$, $y^* = (0.5, 0.5, 0, 0)$ and $v = 5$. Against $y^$ the discarded rows earn only 4, and against $x^$ the discarded columns would cost the column player 6. Both checks confirm that nothing was lost.

Key takeaways

• The row player discards rows that are smaller everywhere. The column player discards columns that are larger everywhere.
• A strategy can be dominated by a mix of others even when no single strategy beats it. An LP that maximizes the dominance margin detects this.
• Apply dominance iteratively: each removal can create new dominance.
• Strict dominance is always safe. Weak dominance keeps the value but can delete some optimal strategies.

Practice

1. (Beginner) Reduce $A = \begin{pmatrix} 3 & 6 & 1 \ 5 & 2 & 3 \ 2 & 1 & 0 \end{pmatrix}$ by pure dominance (state which strategy dominates each removed one), then solve the remaining $2 \times 2$ game.
2. (Intermediate) For $A = \begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}$, find the value and all optimal strategies of both players. Then eliminate weakly dominated strategies (try column 1 first). Which optimal strategies of the column player disappear?
3. (Interview) "Your LP for a large zero-sum game is slow. A colleague suggests preprocessing with dominance. What does the check cost, and when is it worthwhile?" Hint: compare one pass of pairwise pure checks ($O(m^2 n)$), one LP per strategy for mixed dominance, and the number of passes, with the cost of a single LP solve. Consider when most strategies are obviously bad.

<a id="82-non-zero-sum-and-cooperative-games"></a>

8.2 Non-Zero-Sum and Cooperative Games

Most business interactions are not pure conflict: two firms can both lose in a price war, or both gain by agreeing on a technical standard. This subchapter drops the zero-sum assumption. It first covers non-cooperative games, where each player optimizes alone and the Nash equilibrium is the solution concept, then cooperative games, where players can sign binding agreements and the question becomes how to share the gains of working together.

Nash Equilibrium

Why it matters. Without the zero-sum structure, minimax reasoning breaks down: the other player is not trying to hurt you, only to help itself, so assuming the worst is needlessly pessimistic. What is needed is a notion of stable outcome, one where nobody regrets their choice given what the others did. The Nash equilibrium is that notion. It is the standard solution concept in economics, and OR uses it to model competitive markets, traffic and network routing, auctions, energy markets and shared computing resources.

Theory. A finite game has players $1, \dots, N$, strategy sets $S_i$ and payoff functions $u_i(s_1, \dots, s_N)$, which each player maximizes. Write $s_{-i}$ for the strategies of everyone except player $i$. With two players, the game is a bimatrix game $(A, B)$: when row $i$ meets column $j$, the row player gets $a_{ij}$ and the column player gets $b_{ij}$. A zero-sum game is the special case $B = -A$.

• A best response of player $i$ to $s_{-i}$ is any strategy that maximizes $u_i(\cdot, s_{-i})$.
• A Nash equilibrium is a profile $s^*$ in which every player's strategy is a best response to the others: no player can gain by changing strategy alone.

For mixed strategies in a bimatrix game, $(x^, y^)$ is a Nash equilibrium when

$$ x^{\top} A y^ \ge (A y^)_i ;; \forall i \qquad \text{and} \qquad x^{\top} B y^* \ge (x^{*\top} B)_j ;; \forall j . $$

Nash's theorem (1950): every finite game has at least one equilibrium in mixed strategies. The proof uses a fixed-point theorem (Brouwer or Kakutani) applied to the best-response map. It guarantees existence but, unlike the minimax theorem, offers no efficient algorithm. Nash equilibria are much less tidy than zero-sum solutions:

Property	Zero-sum games	General-sum games
Equilibrium payoffs	one value $v$ shared by all equilibria	different equilibria give different payoffs
Interchangeability	any optimal $x$ with any optimal $y$	mixing strategies from two equilibria can fail
Computation	one LP, polynomial time	PPAD-complete even for two players (Chen and Deng, 2006)
Efficiency	not applicable (the total is fixed)	equilibria can be Pareto-inefficient
Algorithms	simplex, interior point	support enumeration, Lemke-Howson pivoting

Three ways to find equilibria cover most small problems:

• Pure equilibria by best-response marking. In each column, mark the row player's best entries. In each row, mark the column player's best entries. Cells marked twice are pure equilibria.
• Mixed equilibria by indifference. As in zero-sum games, every strategy used with positive probability must earn the same payoff. The important twist is that the row player's mix is computed from the column player's payoffs $B$, since its job is to make the column player indifferent, and vice versa.
• Support enumeration. Guess which strategies each player uses (the supports), solve the indifference equations, and keep the solutions that are valid probabilities and leave no profitable deviation outside the supports. In nondegenerate games, both supports have the same size. The method is exponential in the number of strategies, but it is simple and exact for small games. Lemke-Howson, a pivoting method in the spirit of the simplex method, is the classical alternative.

Strategies can also be continuous, such as prices or quantities. Then the equilibrium is where the best-response functions intersect, and it can often be found by iterating best responses. Equilibria can be inefficient: the price of anarchy, the ratio between the optimal total welfare and the welfare of the worst equilibrium, measures how much selfish behavior costs. For selfish traffic routing with linear travel times it is at most $4/3$ (Roughgarden and Tardos, 2002).

Example 1: a standards war. Two firms each choose technology X or Y. Both want to be compatible, but firm 1 owns patents on X and firm 2 on Y:

                Firm 2: X     Firm 2: Y
Firm 1: X        (3, 2)        (0, 0)
Firm 1: Y        (0, 0)        (2, 3)
payoffs: (firm 1, firm 2)

import numpy as np
from itertools import combinations

def support_enumeration(A, B, tol=1e-9):
    """All Nash equilibria of a nondegenerate bimatrix game (A: row payoffs, B: column payoffs)."""
    m, n = A.shape
    eqs = []
    for k in range(1, min(m, n) + 1):
        for I in combinations(range(m), k):
            for J in combinations(range(n), k):
                # y on J makes the row player indifferent across I:  A[I,J] y - u = 0, sum y = 1
                My = np.block([[A[np.ix_(I, J)], -np.ones((k, 1))], [np.ones((1, k)), np.zeros((1, 1))]])
                # x on I makes the column player indifferent across J: B[I,J]^T x - w = 0, sum x = 1
                Mx = np.block([[B[np.ix_(I, J)].T, -np.ones((k, 1))], [np.ones((1, k)), np.zeros((1, 1))]])
                rhs = np.r_[np.zeros(k), 1.0]
                try:
                    sy, sx = np.linalg.solve(My, rhs), np.linalg.solve(Mx, rhs)
                except np.linalg.LinAlgError:
                    continue
                x, y = np.zeros(m), np.zeros(n)
                x[list(I)], y[list(J)] = sx[:k], sy[:k]
                if (x < -tol).any() or (y < -tol).any():
                    continue
                # No profitable deviation to a strategy outside the support
                if (A @ y).max() <= x @ A @ y + tol and (x @ B).max() <= x @ B @ y + tol:
                    eqs.append((x, y, x @ A @ y, x @ B @ y))
    return eqs

# Standards war: each firm picks technology X or Y. Both want to match, but disagree on which.
A = np.array([[3, 0],     # firm 1's payoffs (rows: firm 1 picks X, Y)
              [0, 2]])
B = np.array([[2, 0],     # firm 2's payoffs (cols: firm 2 picks X, Y)
              [0, 3]])
for x, y, u1, u2 in support_enumeration(A, B):
    print(f"firm 1 {np.round(x, 3)}  firm 2 {np.round(y, 3)}  payoffs ({u1:.2f}, {u2:.2f})")
# firm 1 [1. 0.]  firm 2 [1. 0.]  payoffs (3.00, 2.00)
# firm 1 [0. 1.]  firm 2 [0. 1.]  payoffs (2.00, 3.00)
# firm 1 [0.6 0.4]  firm 2 [0.4 0.6]  payoffs (1.20, 1.20)

There are three equilibria. In the two pure ones the firms coordinate, but each prefers a different one. The mixed one is the worst of all: firm 1 chooses X with probability 0.6, which is exactly what makes firm 2 indifferent ($2 \cdot 0.6 = 3 \cdot 0.4$), and the firms end up incompatible with probability $0.6 \cdot 0.6 + 0.4 \cdot 0.4 = 0.52$, earning 1.2 each. Game theory says what is stable, but not which stable outcome will occur. In practice that is settled by communication, industry consortia, focal points, or one firm moving first (see sequential games below).

Example 2: Cournot competition. Two firms choose production quantities $q_1, q_2$. The market price is $P = 100 - (q_1 + q_2)$ and the unit cost is 10. Firm 1's profit $(100 - q_1 - q_2 - 10),q_1$ is maximized at $q_1 = (90 - q_2)/2$, its best response to $q_2$.

# Cournot duopoly: inverse demand P = 100 - (q1 + q2), unit cost 10 for both firms.
a, c = 100, 10

def best_response(q_other):
    """argmax_q (a - q - q_other - c) q  ->  q = (a - c - q_other) / 2 (never negative)."""
    return max(0.0, (a - c - q_other) / 2)

q1, q2 = 0.0, 0.0
for it in range(1, 31):
    q1, q2 = best_response(q2), best_response(q1)     # simultaneous best-response update
    if it in (1, 2, 3, 5, 10, 30):
        print(f"iter {it:2}: q1 = {q1:7.3f}  q2 = {q2:7.3f}")

Q = q1 + q2
print(f"Nash (Cournot): q = {q1:.2f} each, price = {a - Q:.2f}, profit = {(a - Q - c) * q1:.2f} each")
qm = (a - c) / 2                                       # joint-profit (cartel) output
print(f"cartel: q = {qm / 2:.2f} each, price = {a - qm:.2f}, profit = {(a - qm - c) * qm / 2:.2f} each")
# iter  1: q1 =  45.000  q2 =  45.000
# iter  2: q1 =  22.500  q2 =  22.500
# iter  3: q1 =  33.750  q2 =  33.750
# iter  5: q1 =  30.938  q2 =  30.938
# iter 10: q1 =  29.971  q2 =  29.971
# iter 30: q1 =  30.000  q2 =  30.000
# Nash (Cournot): q = 30.00 each, price = 40.00, profit = 900.00 each
# cartel: q = 22.50 each, price = 55.00, profit = 1012.50 each

Best-response iteration oscillates and converges to the equilibrium $q_1 = q_2 = 30$, where each firm's output is a best response to the other's. It converges here because each best response has slope $-1/2$, which makes the iteration a contraction. With steeper reactions it can cycle forever. The equilibrium is not efficient for the firms: if both produced 22.5, each would earn 1012.50 instead of 900. But that agreement is not stable, because a firm's best response to 22.5 is 33.75. This tension between individual and joint interest is the subject of the next topic.

Key takeaways

• A Nash equilibrium is a profile in which no player gains by deviating alone. Every finite game has one in mixed strategies.
• Pure equilibria are found by marking best responses. Mixed equilibria come from indifference conditions, where each player's mix is computed from the other player's payoffs.
• Unlike zero-sum games, equilibria can be multiple, give different payoffs, be non-interchangeable and be Pareto-inefficient.
• Computing a Nash equilibrium is PPAD-complete in general. Support enumeration and Lemke-Howson work for small games.
• For continuous strategies, equilibria lie where best-response functions intersect.

Practice

1. (Beginner) Find all pure Nash equilibria of the bimatrix game with $A = \begin{pmatrix} 4 & 1 & 2 \ 3 & 3 & 1 \ 0 & 2 & 5 \end{pmatrix}$ and $B = \begin{pmatrix} 2 & 3 & 1 \ 1 & 4 & 0 \ 0 & 2 & 6 \end{pmatrix}$ by marking best responses. Then run support_enumeration to find any mixed equilibria.
2. (Intermediate) Generalize the Cournot code to $N$ identical firms. Show numerically (and then algebraically) that the equilibrium price approaches the unit cost as $N$ grows. Does simultaneous best-response iteration still converge for $N = 3$? Try updating one firm at a time instead.
3. (Interview) "Nash equilibria can be inefficient. Give an example from computing or networking, and explain how a system designer could fix it." Hint: Braess's paradox in traffic and packet routing, congestion control, overloaded shared clusters. Think about prices, tolls, quotas or scheduling rules that change the game so that the equilibrium becomes efficient.

Prisoner's Dilemma

Why it matters. The Prisoner's Dilemma is the most famous game because it captures, in four numbers, the conflict between individual and collective rationality. It explains price wars, arms races, overfishing and free-riding in teams. Its repeated version explains how cooperation can survive without contracts, which is central to understanding cartels, long-term supplier relationships and reputation systems.

Theory. Two suspects are questioned separately. Each can stay silent (cooperate with the partner, C) or confess (defect, D). Generically, the payoffs are

                 Other: C       Other: D
You: C            R, R           S, T
You: D            T, S           P, P
T = temptation, R = reward, P = punishment, S = sucker's payoff

with $T > R > P > S$, and usually also $2R > T + S$ (taking turns exploiting each other is worse than steady cooperation). Then:

• Defection strictly dominates. Whatever the other player does, D pays more: $T > R$ and $P > S$.
• The unique Nash equilibrium is $(D, D)$ with payoffs $(P, P)$.
• $(C, C)$ would give $(R, R)$, which is better for both. The equilibrium is Pareto-inefficient: individually rational choices produce a collectively irrational outcome.

The way out is to change the game:

• Finite repetition with a known last round does not help. In the last round defection dominates, so the round before it is effectively the last, and backward induction (next topic) unravels cooperation all the way to round one.
• Indefinite repetition does help. Suppose the game continues each round with discount factor $\delta \in (0, 1)$, which combines the time value of money and the probability that the relationship continues. Under the grim trigger strategy, a player cooperates until the other defects once, then defects forever. Deviating pays $T$ once and then $P$ forever, so cooperation is stable when $$ \frac{R}{1 - \delta} ;\ge; T + \frac{\delta P}{1 - \delta} \quad\Longleftrightarrow\quad \delta ;\ge; \frac{T - R}{T - P}. $$
• The folk theorem generalizes this: when players are patient enough, any feasible average payoff that gives each player more than its punishment payoff can be sustained as an equilibrium of the repeated game.
• Contracts, regulation and commitment devices change the payoffs themselves. For example, a "we match any competitor's price" guarantee removes the gain from undercutting, which is why competition authorities scrutinize such clauses.

In Axelrod's computer tournaments (1980), the winner was tit-for-tat: cooperate first, then copy the opponent's previous move. Axelrod attributed its success to being nice (never the first to defect), retaliatory, forgiving and easy to understand.

Example: a pricing duopoly. Two stores choose a high price (cooperate) or a low price (defect) each week. Weekly profits, in thousands of dollars:

                     Rival: high       Rival: low
You: high              10, 10            2, 14
You: low               14, 2             5, 5
T = 14 > R = 10 > P = 5 > S = 2,   2R = 20 > T + S = 16

The code checks dominance, runs a round-robin tournament of repeated-game strategies over 100 weeks, and computes the patience threshold for the grim trigger.

import numpy as np

# Pricing duopoly as a prisoner's dilemma. Index 0 = high price (cooperate), 1 = low price (defect).
# PAYOFF[my move][their move] = my weekly profit ($k)
PAYOFF = np.array([[10, 2],      # high vs high = R (reward),    high vs low = S (sucker)
                   [14, 5]])     # low  vs high = T (temptation), low  vs low = P (punishment)
T, R, P, S = PAYOFF[1, 0], PAYOFF[0, 0], PAYOFF[1, 1], PAYOFF[0, 1]
print("low price is dominant:", (PAYOFF[1] > PAYOFF[0]).all())

# One-shot: both defect. Repeated: strategies see the opponent's history.
def always_high(mine, theirs):  return 0
def always_low(mine, theirs):   return 1
def tit_for_tat(mine, theirs):  return theirs[-1] if theirs else 0           # copy last move
def grim(mine, theirs):         return 1 if 1 in theirs else 0               # punish forever
def tf2t(mine, theirs):         return 1 if theirs[-2:] == [1, 1] else 0     # forgive one defection
def alternate(mine, theirs):    return len(mine) % 2                          # high, low, high, ...

def play(s1, s2, rounds=100):
    h1, h2, tot1, tot2 = [], [], 0, 0
    for _ in range(rounds):
        a, b = s1(h1, h2), s2(h2, h1)
        tot1, tot2 = tot1 + PAYOFF[a, b], tot2 + PAYOFF[b, a]
        h1.append(a); h2.append(b)
    return tot1, tot2

players = [always_high, always_low, tit_for_tat, grim, tf2t, alternate]
score = {p.__name__: 0 for p in players}
for i, p in enumerate(players):                     # round robin, including self-play
    for q in players[i:]:
        s1, s2 = play(p, q)
        score[p.__name__] += s1
        if q is not p:
            score[q.__name__] += s2
for name, s in sorted(score.items(), key=lambda kv: -kv[1]):
    print(f"{name:12} {s:6d}")

# Infinitely repeated game: grim trigger sustains (high, high) if R/(1-d) >= T + d*P/(1-d)
print(f"cooperation is an equilibrium for discount factor d >= (T-R)/(T-P) = {(T - R) / (T - P):.3f}")
# low price is dominant: True
# grim           5440
# tit_for_tat    5293
# tf2t           5094
# always_high    4800
# alternate      4675
# always_low     4386
# cooperation is an equilibrium for discount factor d >= (T-R)/(T-P) = 0.444

In a single week, the low price is dominant. Over 100 weeks, the dominant one-shot strategy finishes last: retaliatory strategies punish it after the first week, so it earns $P = 5$ per week against them, while cooperative pairs earn $R = 10$. Grim and tit-for-tat do best in this population: they cooperate with cooperators and cannot be exploited for long. Tit-for-two-tats is too forgiving against alternate, which defects every other week and is never punished. No strategy is best against every population, and the ranking changes if the mix of opponents changes. The threshold $\delta \ge 4/9$ means that if the stores weigh next week's profit at more than about 44% of this week's, tacit collusion on high prices is self-enforcing. This is exactly the concern competition authorities have about markets with few players and transparent prices.

Key takeaways

• A Prisoner's Dilemma has $T > R > P > S$: defection strictly dominates, but mutual defection is worse for both than mutual cooperation.
• With a known final round, backward induction predicts defection in every round.
• With indefinite repetition, grim trigger sustains cooperation when $\delta \ge (T - R)/(T - P)$. The folk theorem extends this to many outcomes.
• Successful repeated-game strategies are nice, retaliatory, forgiving and clear, like tit-for-tat. Contracts and commitments can also change the payoffs directly.

Practice

1. (Beginner) Check that the pricing table satisfies $T > R > P > S$ and $2R > T + S$. Now change the temptation to $T = 22$ and the sucker payoff to $S = 0$. Which condition fails? Show that two stores taking turns undercutting each other (high/low, then low/high, and so on) would now earn more on average than steady mutual cooperation.
2. (Intermediate) Add noise: each intended move is flipped with probability 5%. Rerun the tournament with several random seeds and 1,000 rounds. Which strategy suffers most from mistakes, and why? Explain the "echo" effect between two tit-for-tat players.
3. (Interview) "Two cloud providers keep cutting prices on the same service. Use game theory to explain why, and what could stop it." Hint: one-shot versus repeated interaction, the discount factor and the expected length of the relationship, how easily price cuts are observed, new entrants, and product differentiation that changes the payoff table.

Sequential Games and Backward Induction

Why it matters. Many interactions happen in turns: a firm enters a market and the incumbent responds, a buyer makes an offer and the seller counteroffers, a leader builds capacity and followers adapt. In these games the order of moves and the ability to commit matter, and some threats are empty. Backward induction, the game-theoretic twin of the backward recursion of dynamic programming (Section 6.1), solves such games and filters out threats that would never be carried out.

Theory. A game in extensive form is a tree:

• each decision node belongs to one player, and its branches are that player's actions,
• each leaf gives a payoff vector,
• with perfect information, every player knows the full history when moving.

A strategy in an extensive-form game is a complete contingent plan: an action at every one of the player's decision nodes, including nodes that will not be reached when the plan is followed.

Backward induction solves a finite game of perfect information:

1. At each decision node whose children are all leaves, choose the action that is best for the player who moves there.
2. Replace the node with the payoff vector of that action.
3. Repeat until the root is reached.

Zermelo's theorem follows: every finite game of perfect information has a pure-strategy equilibrium (in principle, chess has a determined outcome). The solution is a subgame perfect equilibrium (Selten, 1965): a strategy profile that is a Nash equilibrium in every subgame, not only along the path actually played. This rules out non-credible threats, which are plans that would not be optimal to carry out if the moment came.

Two classic consequences:

• Commitment has value. A player who can bind itself in advance (by building capacity, signing a contract or burning bridges) can make a threat credible by changing its own future payoffs.
• Stackelberg leadership. A leader chooses first, anticipating the follower's best response $BR_2$. It solves $\max_{s_1} u_1\big(s_1, BR_2(s_1)\big)$, a bilevel optimization problem. Bilevel models are common in OR: network pricing and tolls, regulation, and Stackelberg security games, where a defender commits to a randomized patrol that the attacker observes before choosing a target.

Moving first is not always an advantage. In Cournot competition it is, but in matching pennies the second mover wins. Game-playing programs apply the same principle: minimax search with alpha-beta pruning is backward induction on a zero-sum game tree, truncated at a fixed depth and completed with an evaluation function.

Example: entry deterrence. A potential entrant decides whether to enter a market. If it enters, the incumbent decides whether to fight with a price war or to accommodate:

                     Entrant
                    /       \
             stay out        enter
                /                \
          (0, 10)             Incumbent
                              /        \
                          fight      accommodate
                           /              \
                       (-2, 1)           (3, 5)
payoffs: (entrant, incumbent)

In normal form, (stay out, fight if entry) is a Nash equilibrium: given the threat, staying out is optimal, and the threat costs the incumbent nothing because it is never tested. But if entry actually happened, fighting would give the incumbent 1 instead of 5, so the threat is not credible. The code solves the tree by backward induction, then solves a Stackelberg version of the Cournot market from the previous topic, where firm 1 commits to its quantity first.

# Entry deterrence. A node is either a payoff tuple (entrant, incumbent) or
# a decision: (player index, {action: subtree}).
TREE = (0, {"stay out": (0, 10),
            "enter":    (1, {"fight":       (-2, 1),
                             "accommodate": (3, 5)})})
NAMES = ["entrant", "incumbent"]

def backward_induction(node, path="root"):
    """Return (payoffs, plan) where plan maps each decision node to the chosen action."""
    if not isinstance(node[1], dict):                  # leaf: payoff tuple
        return node, {}
    player, children = node
    plan, best_action, best_payoff = {}, None, None
    for action, child in children.items():
        payoff, sub_plan = backward_induction(child, f"{path}/{action}")
        plan.update(sub_plan)                          # keep choices in EVERY subgame
        if best_payoff is None or payoff[player] > best_payoff[player]:
            best_action, best_payoff = action, payoff
    plan[path] = f"{NAMES[player]} -> {best_action}"
    return best_payoff, plan

payoff, plan = backward_induction(TREE)
for node, choice in sorted(plan.items()):
    print(f"{node:12} {choice}")
print("subgame perfect outcome payoffs:", payoff)

# Stackelberg: same Cournot market (P = 100 - Q, cost 10), but firm 1 commits first.
a, c = 100, 10
follower = lambda q1: max(0.0, (a - c - q1) / 2)     # stage 2: follower's best response
grid = [i / 100 for i in range(0, 9001)]             # stage 1: leader anticipates it
q1 = max(grid, key=lambda q: (a - q - follower(q) - c) * q)
q2 = follower(q1)
price = a - q1 - q2
print(f"Stackelberg: leader {q1:.1f}, follower {q2:.1f}, price {price:.1f}, "
      f"profits {(price - c) * q1:.2f} / {(price - c) * q2:.2f}")
# root         entrant -> enter
# root/enter   incumbent -> accommodate
# subgame perfect outcome payoffs: (3, 5)
# Stackelberg: leader 45.0, follower 22.5, price 32.5, profits 1012.50 / 506.25

The subgame perfect equilibrium is (enter, accommodate): the entrant correctly ignores the empty threat. To deter entry, the incumbent would have to change its own payoffs in advance, for example by investing in capacity that makes fighting cheaper than sharing the market. In the Stackelberg market, the leader commits to 45 units instead of the Cournot 30, and the follower responds with 22.5. The leader's profit rises from 900 to 1012.50, while the follower's falls to 506.25. Consumers gain too, since total output rises from 60 to 67.5 and the price falls from 40 to 32.5. The commitment must be real: in a simultaneous game, the leader's best response to 22.5 would be 33.75, not 45.

Key takeaways

• Extensive-form games are trees. A strategy specifies an action at every own decision node, even unreached ones.
• Backward induction solves finite perfect-information games from the leaves up, like the DP backward recursion, and gives a subgame perfect equilibrium.
• Subgame perfection removes non-credible threats: Nash equilibria that rely on actions a player would not actually take.
• Commitment has value. Stackelberg leadership is a bilevel optimization problem in which the leader anticipates the follower's best response.

Practice

1. (Beginner) In the ultimatum game, a proposer offers $k \in {0, 1, \dots, 10}$ dollars of $10 to a responder, who accepts (split as proposed) or rejects (both get 0). Find the subgame perfect equilibrium by backward induction, assuming the responder accepts when indifferent. Compare it with experiments, where typical offers are 40 to 50% and low offers are often rejected.
2. (Intermediate) Extend backward_induction with chance nodes, whose value is the probability-weighted average of their children. Model an incumbent that is "tough" with probability 0.3, in which case fighting pays it 6 instead of 1. Nature draws the type after entry. Should the entrant still enter?
3. (Interview) "How does backward induction relate to the minimax search used by chess engines, and why do engines need alpha-beta pruning and evaluation functions?" Hint: the tree has about $b^d$ nodes for branching factor $b$ and depth $d$. Think about which branches cannot change the decision, and what to do when the tree cannot be searched to the end.

Cooperative Games and the Core

Why it matters. When players can sign binding agreements, the question changes from "what will each player do?" to "which groups will form, and how will they share the gains?". Logistics firms share warehouses and trucks, municipalities share a water treatment plant, cloud tenants share reserved capacity, and hospitals form purchasing alliances. An allocation that some group could beat on its own will not last, because that group leaves. The core is the set of allocations no group wants to leave.

Theory. A cooperative game with transferable utility (a TU game) is a pair $(N, v)$: a set of $n$ players and a characteristic function $v$ that gives every coalition $S \subseteq N$ the total value $v(S)$ it can secure on its own, with $v(\varnothing) = 0$. Payoffs can be transferred freely, for example as money.

Many OR applications start from costs: $c(S)$ is the cost of serving coalition $S$ jointly. The associated savings game is

$$ v(S) = \sum_{i \in S} c({i}) - c(S), $$

the money saved by cooperating instead of operating alone.

Two structural properties matter:

• Superadditivity: $v(S \cup T) \ge v(S) + v(T)$ for disjoint $S$ and $T$. Merging never hurts, so the grand coalition $N$ is the natural outcome.
• Convexity (supermodularity): $v(S \cup {i}) - v(S) \le v(T \cup {i}) - v(T)$ for $S \subseteq T \subseteq N \setminus {i}$. The incentive to join grows with the size of the coalition, a "snowball" effect.

An allocation $x \in \mathbb{R}^n$ assigns $x_i$ to player $i$. Write $x(S) = \sum_{i \in S} x_i$. Then:

• $x$ is efficient if $x(N) = v(N)$: the whole value is distributed.
• $x$ is individually rational if $x_i \ge v({i})$: nobody would rather be alone.
• A coalition $S$ blocks $x$ if $x(S) < v(S)$: its members could leave and do better together.
• The core is the set of efficient allocations that no coalition blocks: $$ \text{Core}(v) = {, x : x(N) = v(N), ;; x(S) \ge v(S) ;; \forall S \subset N ,}. $$

The core is a polytope defined by $2^n - 1$ linear constraints, so linear programming is the natural tool. It can contain many allocations, exactly one, or none at all:

• Bondareva-Shapley theorem. The core is non-empty if and only if the game is balanced: $\sum_S \lambda_S v(S) \le v(N)$ for every family of weights $\lambda_S \ge 0$ with $\sum_{S \ni i} \lambda_S = 1$ for every player $i$. The proof is LP duality once again.
• Convex games always have a non-empty core, and it contains the Shapley value (next topic).
• The least core relaxes every coalition constraint by the smallest $\varepsilon$ that makes the system feasible: $\min \varepsilon$ subject to $x(S) \ge v(S) - \varepsilon$ and $x(N) = v(N)$. The core is non-empty if and only if $\varepsilon^* \le 0$. When $\varepsilon^* < 0$, the solution is a particularly stable allocation, with a cushion of $|\varepsilon^*|$ for every coalition. The nucleolus refines this idea lexicographically. It is unique, and it lies in the core whenever the core is non-empty.

An analogy: friends sharing a restaurant bill. If the split charges two of them more than they would pay eating together on their own, they will not join the group next time.

Example: three companies sharing logistics. Companies A, B and C have stand-alone logistics costs of 60, 50 and 40 ($k per month). Sharing warehouses and trucks lowers the cost of every group, and all three together pay 100. The code builds the savings game, computes the least core with an LP, tests the "split the bill equally" allocation, and examines a game whose core is empty.

import numpy as np
from itertools import combinations
from scipy.optimize import linprog

PLAYERS = "ABC"
# Stand-alone and joint logistics costs ($k/month) of three companies sharing warehouses
COST = {"A": 60, "B": 50, "C": 40, "AB": 80, "AC": 75, "BC": 65, "ABC": 100}
# Savings game: v(S) = sum of stand-alone costs - cost of S operating together
v = {S: sum(COST[p] for p in S) - c for S, c in COST.items()}
print("savings v(S):", v)

def least_core(v, players):
    """min eps s.t. x(S) >= v(S) - eps for every proper coalition S, x(N) = v(N).
    The core is non-empty iff the optimal eps <= 0."""
    n = len(players)
    coalitions = [S for k in range(1, n) for S in map("".join, combinations(players, k))]
    A_ub = [[-(p in S) for p in players] + [-1] for S in coalitions]   # -x(S) - eps <= -v(S)
    b_ub = [-v[S] for S in coalitions]
    res = linprog(np.r_[np.zeros(n), 1.0], A_ub=A_ub, b_ub=b_ub,
                  A_eq=[[1] * n + [0]], b_eq=[v[players]],
                  bounds=[(None, None)] * (n + 1), method="highs")
    return res.x[:n], res.x[n]

x, eps = least_core(v, PLAYERS)
print(f"least-core eps = {eps:.2f} -> core is {'non-empty' if eps <= 1e-9 else 'EMPTY'}")
print("least-core savings:", {p: round(float(xi), 2) for p, xi in zip(PLAYERS, x)})
print("costs paid:        ", {p: round(COST[p] - float(xi), 2) for p, xi in zip(PLAYERS, x)})

def blocking_coalitions(x, v, players):
    """Coalitions that receive less than they could secure on their own."""
    alloc = dict(zip(players, x))
    return [S for S in v if sum(alloc[p] for p in S) < v[S] - 1e-9]

# "Split the bill equally": each company pays 100/3 -> savings = stand-alone cost - 100/3
equal_bill = [COST[p] - 100 / 3 for p in PLAYERS]
print("equal bill, savings:", np.round(equal_bill, 2), "blocked by:", blocking_coalitions(equal_bill, v, PLAYERS))

# Three-player majority game: any 2 players can split 1 between them
maj = {"A": 0, "B": 0, "C": 0, "AB": 1, "AC": 1, "BC": 1, "ABC": 1}
x, eps = least_core(maj, PLAYERS)
print(f"majority game: least-core eps = {eps:.3f} at x = {np.round(x, 3)} -> core is "
      f"{'non-empty' if eps <= 1e-9 else 'EMPTY'}")
# savings v(S): {'A': 0, 'B': 0, 'C': 0, 'AB': 30, 'AC': 25, 'BC': 25, 'ABC': 50}
# least-core eps = -6.67 -> core is non-empty
# least-core savings: {'A': 18.33, 'B': 18.33, 'C': 13.33}
# costs paid:         {'A': 41.67, 'B': 31.67, 'C': 26.67}
# equal bill, savings: [26.67 16.67  6.67] blocked by: ['BC']
# majority game: least-core eps = 0.333 at x = [0.333 0.333 0.333] -> core is EMPTY

The alliance saves 50 per month, and the core is non-empty: there are ways to share the savings that every subgroup accepts. The least core gives every coalition at least 6.67 more than it could get on its own, a comfortable stability margin. Splitting the bill equally sounds fair but fails: B and C would pay $2 \times 33.33 = 66.67$, more than the 65 they would pay as a pair, so they would leave and the alliance would collapse. In the majority game, any two players can take the whole prize, and every division leaves some pair with at most $2/3$, less than the 1 it can secure alone. The core is empty, which explains why such coalitions are notoriously unstable.

Key takeaways

• A TU game assigns a value $v(S)$ to every coalition. Cost games become savings games via $v(S) = \sum_{i \in S} c({i}) - c(S)$.
• The core contains the efficient allocations that no coalition blocks: $x(N) = v(N)$ and $x(S) \ge v(S)$ for all $S$.
• The core is an LP-defined polytope. It can be empty, and Bondareva-Shapley (balancedness) characterizes when it is not.
• The least core LP tests non-emptiness and finds a stable allocation. Convex games always have a non-empty core.
• Intuitively "fair" rules such as equal splits can lie outside the core and break the coalition.

Practice

1. (Beginner) Rewrite the core constraints of the logistics game in terms of costs paid instead of savings. Is the allocation "pay in proportion to your stand-alone cost" in the core? Use blocking_coalitions to check.
2. (Intermediate) In the glove game, player 1 owns a left glove, players 2 and 3 each own a right glove, and only a matched pair is worth 1. Write $v$, compute the core with least_core and by hand, and interpret the result in terms of market power.
3. (Interview) "Three hospitals are considering a joint purchasing alliance. How would you propose splitting the savings so that the alliance holds together?" Hint: estimate $v(S)$ for every coalition, check the core with an LP, pick an allocation inside it (least core, nucleolus or Shapley if it lies in the core), and discuss which data you would need and how sensitive the result is to it.

Shapley Value

Why it matters. The core may contain many allocations or none, so it does not always give an answer. The Shapley value picks exactly one allocation from a few fairness axioms. It always exists and is easy to explain: each player receives its average marginal contribution. It is used to allocate costs (airport landing fees, shared network infrastructure), to measure voting power, and, as SHAP values, to explain the predictions of machine learning models.

Theory. Imagine the players arriving one at a time in a random order. When player $i$ arrives and finds coalition $S$ already present, it is credited with its marginal contribution $v(S \cup {i}) - v(S)$. The Shapley value $\varphi_i$ is the expected marginal contribution when all $n!$ arrival orders are equally likely. Counting the orders in which exactly the players of $S$ arrive before $i$ gives

$$ \varphi_i(v) = \sum_{S \subseteq N \setminus {i}} \frac{|S|! , (n - |S| - 1)!}{n!} , \big[ v(S \cup {i}) - v(S) \big]. $$

Shapley (1953) proved that this is the only allocation rule satisfying four axioms:

Axiom	Meaning
Efficiency	$\sum_i \varphi_i = v(N)$: the whole value is distributed
Symmetry	two players with identical contributions to every coalition get the same amount
Null player	a player that adds nothing to any coalition gets 0
Additivity	$\varphi(v + w) = \varphi(v) + \varphi(w)$: two games played together are allocated separately

How the Shapley value relates to the core:

Situation	Relation
Convex game	Shapley value lies in the core
Non-convex game with non-empty core	Shapley value may lie outside the core, so some coalition can block it
Empty core	Shapley value still exists (core-based rules give no answer)

Exact computation needs all $2^{n-1}$ coalitions for each player, which is practical up to about 20 to 25 players. Beyond that, Monte Carlo sampling of random orders gives an unbiased estimate with error $O(1/\sqrt{\text{samples}})$. Some games have closed forms. In the airport game (Littlechild and Owen, 1973), aircraft types need runways of increasing length. The Shapley value splits the cost of each runway segment equally among the aircraft that need that segment. In weighted voting games, the Shapley value is the Shapley-Shubik power index.

SHAP applies the same formula to machine learning. The players are the features, and $v(S)$ is the model's expected prediction when only the features in $S$ are known. It inherits the same exponential cost, which is why practical implementations use sampling (KernelSHAP) or exploit model structure (TreeSHAP).

Example: logistics savings and an airport runway.

import random
from itertools import combinations, permutations
from math import factorial

def shapley_exact(v, players):
    """phi_i = sum over S not containing i of |S|!(n-|S|-1)!/n! * (v(S+i) - v(S))."""
    n, phi = len(players), {}
    val = lambda S: v.get("".join(sorted(S)), 0)       # coalitions stored as sorted strings
    for i in players:
        others = [p for p in players if p != i]
        phi[i] = sum(factorial(k) * factorial(n - k - 1) / factorial(n) * (val(S + (i,)) - val(S))
                     for k in range(n) for S in combinations(others, k))
    return phi

# Logistics savings game from the previous topic
v = {"A": 0, "B": 0, "C": 0, "AB": 30, "AC": 25, "BC": 25, "ABC": 50}
print("Shapley (exact formula):", {p: round(s, 4) for p, s in shapley_exact(v, "ABC").items()})

# Same thing by averaging marginal contributions over all 3! arrival orders
contrib = {p: 0 for p in "ABC"}
for order in permutations("ABC"):
    for k, p in enumerate(order):
        before, after = "".join(sorted(order[:k])), "".join(sorted(order[:k + 1]))
        contrib[p] += v.get(after, 0) - v.get(before, 0)
print("Shapley (orderings):    ", {p: c / 6 for p, c in contrib.items()})

# Airport game: runway cost depends on the largest aircraft type that uses it.
# Required runway cost ($M) by aircraft type, with the number of airlines of each type.
types = [("regional", 30, 4), ("narrowbody", 60, 3), ("widebody", 120, 1)]
airlines = [(f"{t}{k}", cost) for t, cost, cnt in types for k in range(cnt)]
cost_of = lambda coalition: max((c for _, c in coalition), default=0)

def shapley_monte_carlo(players, cost, samples=20_000, seed=1):
    rng = random.Random(seed)
    phi = {name: 0.0 for name, _ in players}
    for _ in range(samples):
        order = players[:]
        rng.shuffle(order)                            # random arrival order
        for k, (name, _) in enumerate(order):
            phi[name] += cost(order[:k + 1]) - cost(order[:k])
    return {name: s / samples for name, s in phi.items()}

est = shapley_monte_carlo(airlines, cost_of)
# Closed form: split each runway segment equally among the airlines that need it
exact = {"regional": 30 / 8, "narrowbody": 30 / 8 + 30 / 4, "widebody": 30 / 8 + 30 / 4 + 60 / 1}
for t, _, _ in types:
    print(f"{t:10} exact {exact[t]:6.3f}  monte carlo {est[t + '0']:6.3f}")
print("total charged:", round(sum(est.values()), 3), "= runway cost", cost_of(airlines))
# Shapley (exact formula): {'A': 17.5, 'B': 17.5, 'C': 15.0}
# Shapley (orderings):     {'A': 17.5, 'B': 17.5, 'C': 15.0}
# regional   exact  3.750  monte carlo  3.767
# narrowbody exact 11.250  monte carlo 11.143
# widebody   exact 71.250  monte carlo 71.484
# total charged: 120.0 = runway cost 120

In the logistics alliance, the Shapley value gives savings of 17.5, 17.5 and 15, so the companies pay 42.5, 32.5 and 25. Every pair receives at least its stand-alone savings ($35 \ge 30$, $32.5 \ge 25$, $32.5 \ge 25$), so this allocation is in the core. It differs from the least-core allocation (18.33, 18.33, 13.33) of the previous topic: different fairness principles give different, equally defensible answers, and the choice should be agreed on before the numbers are known.

The airport example shows why the Shapley value is popular for cost allocation. The first $30M segment of runway is needed by all eight airlines, so each pays $30/8 = 3.75$. The next $30M segment is needed by the three narrowbody operators and the widebody operator, so each of them pays another $30/4 = 7.50$. The last $60M segment is needed only by the widebody operator, which pays it in full. Monte Carlo sampling with 20,000 orders comes within about 0.25 of the exact values, and the charges always add up to the full $120M, because efficiency holds for every single order.

Key takeaways

• The Shapley value is the expected marginal contribution of a player over uniformly random arrival orders.
• It is the unique rule satisfying efficiency, symmetry, the null player property and additivity.
• It always exists, but it lies in the core only for some games (always for convex games).
• Exact computation is exponential in $n$. Use Monte Carlo sampling of orders for many players, or closed forms such as the airport game.
• SHAP values in machine learning are Shapley values with features as players.

Practice

1. (Beginner) Compute by hand the Shapley value of the glove game from the previous topic (player 1 owns a left glove, players 2 and 3 each own a right glove). Is it in the core?
2. (Intermediate) In a weighted voting game, players A, B and C have 50, 30 and 20 votes, and 51 votes are needed to pass a motion ($v(S) = 1$ if $S$ has at least 51 votes, else 0). Compute the Shapley-Shubik power index with shapley_exact and compare it with the vote shares. Why is B's power equal to C's?
3. (Interview) "How are SHAP values computed in practice for a model with 100 features, when the exact formula needs $2^{99}$ coalitions per feature?" Hint: sampling random orders, KernelSHAP as a weighted linear regression, TreeSHAP's polynomial algorithm for tree ensembles, and what $v(S)$ means when features are missing (conditional versus interventional expectation).

<a id="9-stochastic-models"></a>