Zero-sum games: mixed strategies, the minimax theorem, and an equilibrium proved by both players' guarantees

Every night a thief picks a room of a small museum to rob, and the night guard picks a room to watch. Neither knows the other's choice. If the guard is watching the room the thief robs, the thief is caught and loses 3. Otherwise the thief takes what the room holds.

The thief wants the largest expected haul and the guard wants the smallest, so this is a zero-sum game. Neither side should be predictable: a guard who always watches Gold loses 4 every night. A mixed strategy chooses at random, with fixed probabilities. Von Neumann's minimax theorem says that there is a number $v$ , the value of the game, such that:

the thief has a strategy that expects at least $v$ whatever the guard does, and
the guard has a strategy that holds the thief to at most $v$ whatever the thief does.

A pair of such strategies is its own proof. Each one guarantees $v$ from its side, so neither side can do better.

In code, a game is a matrix M. M[i][j] is what the row player (here, the thief) wins and the column player (the guard) loses when the row player plays $i$ and the column player $j$ .

Background: Zero-Sum Games.

Part A: make the other side indifferent

No room is safe for either side. The thief's worst case is $- 3$ whichever room it robs, and the guard's worst case is 4 or 9. So both must mix. If the thief robs Gold with probability $p$ , then watching Gold gives the thief $- 3 p + 4 (1 - p)$ and watching Silver gives $9 p - 3 (1 - p)$ . The thief chooses $p$ to make these equal, so that the guard gains nothing by choosing: $19 p = 7$ , so $p = \frac{7}{19}$ . The value is 27/19, about 1.42 a night.

The guard does the same from its side and watches Gold with probability $\frac{12}{19}$ , more often than Silver though Silver is robbed more often. Each side's probabilities are set by the other side's payoffs: the guard must make the thief indifferent, and Gold is where the thief has the most to win.

Part B: three equations for three rooms

Here every room is in play. If the thief robs each room some of the time, the guard's mix must make all three rooms equally good for the thief. With probabilities $g$ , $s$ , $b$ of watching Gold, Silver and Bronze, the three rooms give the thief $- 2 g + 9 s + 9 b$ , $6 g - 2 s + 6 b$ and $4 g + 4 s - 2 b$ . Setting them equal, with $g + s + b = 1$ , gives

$g = \frac{53}{101}, s = \frac{35}{101}, b = \frac{13}{101},$

and every room then gives the thief $\frac{326}{101} \approx 3.23$ . The thief's own optimal mix, found the same way, robs Gold, Silver and Bronze with probabilities $\frac{24}{101}$ , $\frac{33}{101}$ and $\frac{44}{101}$ . Both mixes are unique. Bronze is robbed most often and watched least: guarding it buys little.

Part C: the game is a linear program

Add a constant to every payoff so that all are positive. That shifts the value by the same constant and changes no strategy. Now, for the guard, consider

$max \sum_{j} z_{j} subject to M z \leq 1, z \geq 0 .$

For any feasible $z$ , the strategy $q = z / \sum_{j} z_{j}$ holds the thief to at most $1 / \sum_{j} z_{j}$ . Maximizing $\sum_{j} z_{j}$ minimizes that bound. The LP's dual, $min \sum_{i} y_{i}$ subject to $M^{⊤} y \geq 1$ , $y \geq 0$ , is the same construction for the thief. By LP duality both optima are equal, and the dual solution comes free from the final simplex tableau: it is the negated objective row under the slack columns.

The grader checks the result as a certificate. If ${min}_{j} (p M)_{j} \geq v$ and ${max}_{i} (M q)_{i} \leq v$ , then $v$ is the value and both strategies are optimal, whoever computed them and however.

Why not just play the game? Fictitious play has each side best-respond to the other's history so far. Robinson proved in 1951 that it converges to the value, but slowly: after 3000 rounds of part A, its guarantees are still about 0.005 from the value. Multiplicative weights needs about $\log n / ε^{2}$ rounds for accuracy $ε$ . Exact optimal strategies need an LP.

Part D: the minimax theorem from duality

The guard's problem is: minimize $v$ subject to $(M q)_{i} \leq v$ for every $i$ , $\sum_{j} q_{j} = 1$ and $q \geq 0$ . Its dual is: maximize $u$ subject to $(p^{⊤} M)_{j} \geq u$ for every $j$ , $\sum_{i} p_{i} = 1$ and $p \geq 0$ , which is exactly the thief's problem. Both are feasible and bounded, so strong duality makes their optimal values equal. That common value is the value of the game: ${max}_{p} {min}_{q} p^{⊤} M q = {min}_{q} {max}_{p} p^{⊤} M q$ .

The check in part C needs no knowledge of $v$ . For every guard strategy $q^{'}$ , $p^{⊤} M q^{'} = \sum_{j} q_{j}^{'} (p^{⊤} M)_{j} \geq v$ , so no guard holds this thief below $v$ . For every thief strategy $p^{'}$ , $p^{' ⊤} M q \leq v$ in the same way. So the value is at least $v$ and at most $v$ .

Going further

Learning to play. If both sides run multiplicative weights against each other, their average strategies approach an equilibrium (Freund and Schapire). That gives a proof of the minimax theorem with no LP at all; see Multiplicative Weights.
Games that are not zero-sum. Every finite game has a Nash equilibrium, but computing one is PPAD-complete even for two players (Daskalakis, Goldberg and Papadimitriou; Chen and Deng). The LP trick works only because one side's gain is the other's loss.
Guards who move first. Security games let the defender commit to a mixed strategy that the attacker observes before choosing. In a zero-sum game this costs the guard nothing, which is another reading of the minimax theorem. Such models have scheduled real patrols, at airports and ports.

References

J. von Neumann. Zur Theorie der Gesellschaftsspiele. Mathematische Annalen 100, 1928.
G. B. Dantzig. A proof of the equivalence of the programming problem and the game problem. In Activity Analysis of Production and Allocation, Wiley, 1951.
J. Robinson. An iterative method of solving a game. Annals of Mathematics 54(2), 1951.
Y. Freund, R. E. Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior 29, 1999.
C. Daskalakis, P. W. Goldberg, C. H. Papadimitriou. The complexity of computing a Nash equilibrium. SIAM Journal on Computing 39(1), 2009.
X. Chen, X. Deng, S.-H. Teng. Settling the complexity of computing two-player Nash equilibria. Journal of the ACM 56(3), 2009.

The Night Guard

Try your rule first