mathematics//game theory//minimax theorem
The minimax theorem is the result, proved by von Neumann in 1928, that in a finite two-player zero-sum game played with mixed strategies the best payoff a player can guarantee by announcing its strategy equals the best it can guarantee by keeping it secret; it is what lets an engineer design against an adversary by solving for the worst case, without having to guess the opponent's move. That common number is the **value of the game**.
The minimax theorem is the result, proved by von Neumann in 1928, that in a finite two-player zero-sum game played with mixed strategies the best payoff a player can guarantee by announcing its strategy equals the best it can guarantee by keeping it secret; it is what lets an engineer design against an adversary by solving for the worst case, without having to guess the opponent's move. That common number is the value of the game.
maxx miny x⊤G y = miny maxx x⊤G y\max_{x}\,\min_{y}\; x^{\top} G\, y \;=\; \min_{y}\,\max_{x}\; x^{\top} G\, yxmaxyminx⊤Gy=yminxmaxx⊤Gy
Here xxx and yyy are the two players' probability vectors over their actions and GGG is the payoff matrix of the first player, which the second wants to make small. The left side is the first player choosing first, with the opponent answering in full knowledge; the right side is the opponent choosing first. With pure strategies the two sides differ, and whoever must reveal first loses: a guard who always watches gate A of the inspection example concedes gate B. Allowing randomization closes the gap exactly, at the value 2/32/32/3 of the mixed strategy note.
Against an adversary, the worst-case mixed strategy is safe to publish. The opponent can learn the probabilities and gain nothing; only learning the individual draw would help it, which is why the draw needs a real source of randomness.
The value and both optimal strategies come out of one linear program (a few lines with scipy.optimize.linprog or cvxpy). The difficulty in practice is size: in patrol scheduling a pure strategy is a whole route, and the number of routes explodes combinatorially, so real systems generate strategies column by column instead of listing them.
Engineering met the idea under other names. H-infinity control designs a controller that does as well as possible against the worst disturbance a nature could choose, and adversarial training of networks minimizes a loss that an attacker maximizes (adversarial example). In decision theory the expected cost gives way to the worst case as soon as the other side reacts to what you do.
Minimax is pessimistic by design. Against a nature that does not adapt (wind, wear, rain) planning for the worst case wastes margin, and the expected cost under a calibrated belief is the right criterion. The word also names the alternating search of chess programs, a different use: there the moves are sequential and seen, and the theorem plays no part (Monte Carlo tree search is a modern relative of that search).
Outside zero-sum games the guarantee and the prediction separate, and the solution concept becomes the Nash equilibrium; a leader who commits in the open is the Stackelberg game.