GAME ESSENCE

Mixed strategies; minimax theorem

When saddle points exist, the proper strategies and outcome are clear, but in some games there are no saddle points. The normal form of such a game is given below.

A guard is hired to protect two safes: safe A contains $10,000 and safe B contains $100,000. The guard can protect only one safe from the robber at a time. The robber and the guard must decide in advance, without knowing what the other will do, which safe to approach. If they go to the same safe, the robber gets nothing; if they go to different safes, the robber keeps the contents of the unprotected safe. In such a game, theory does not suggest any one particular strategy; instead, it prescribes that a strategy be chosen in accordance with a probability distribution, which in this simple example is fairly easy to determine. In larger, more complex games it involves solving a problem in linear programming and can be quite difficult.

To calculate the appropriate probability distribution in this case, each player adopts a strategy that makes him indifferent to what his opponent does. It can be assumed that the guard protects safe A with probability p and safe B with probability (1 - p). Thus, if the robber approaches safe A, he is successful whenever the guard protects safe B; in other words, he gets $10,000 with probability (1 - p) and $0 with probability p for an average gain of $10,000 (1 - p). Similarly, if the robber approaches safe B, he gets $100,000 with probability p and $0 with probability (1 - p) for an average gain of $100,000p. The guard will be indifferent to which safe the robber chooses if the average amount the robber gains is the same in both cases--that is, if $10,000 (1 - p) = $100,000p. It can then be calculated that p = ¹/₁₁. If the guard protects safe A with probability ¹/₁₁ and safe B with probability ¹⁰/₁₁, he loses, on the average, no more than $100,000/11, or about $9,091, whatever the robber does. Using the same kind of argument, it can be deduced that the robber will get an average of at least $9,091 if he tries to steal from safe A with probability ¹⁰/₁₁ and from safe B with probability ¹/₁₁. This solution in terms of mixed strategies is analogous to the solution of the game with a saddle point. The robber and the guard lose nothing if they announce the probabilities with which they will choose their respective strategies; and, if either uses the proper strategy, the (average) outcome will be the one predicted.

The minimax theorem, which von Neumann proved in 1928, states that every finite, two-person zero-sum game has a solution in mixed strategies. Specifically, it states that for every such game between players A and B there are a value, V, and mixed strategies for players A and B such that, if A adopts his appropriate mixed strategy, the outcome will be at least as favourable to A as V, while, if B adopts his appropriate mixed strategy, the outcome will be no more favourable to A than V. Thus, A and B have the motivation and the power to enforce the outcome V.