Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 37 ยท Mixed Strategies

The Minimax Theorem and Linear Programming

Learn von Neumann's minimax theorem and solve any zero-sum matrix game with scipy linprog: build the LP for the row and column player, check that the values agree, and try a Colonel Blotto game.

In Zero-Sum and Constant-Sum Games you found that some games have a saddle point and others, like matching pennies, do not: the best the row player can guarantee with a pure strategy (maximin) is lower than what the column player can hold them to (minimax). The cure was randomization. This lesson finishes the story with one of the oldest results in the field, John von Neumann's minimax theorem (1928), and shows that every zero-sum game can be solved exactly by linear programming.

The minimax theorem

Allow mixed strategies. For a zero-sum game with payoff matrix A for the row player define

  • the row player's guarantee: max over x of min over y of x @ A @ y
  • the column player's guarantee: min over y of max over x of x @ A @ y.

Theorem. In every finite two-player zero-sum game these two numbers are equal. The common value v is the value of the game. There exist optimal mixed strategies x* and y* such that x* guarantees the row player at least v against anything, and y* holds the row player to at most v; the pair (x*, y*) is a Nash equilibrium, and every equilibrium has the same value.

Think about what this means. In zero-sum games there is no advantage to moving second or to hiding your strategy: if the opponent learns your optimal mix x*, they still cannot hold you below v. So solving zero-sum games is a well-defined optimization problem, not a guessing game. (For general games, equilibria need not have this "safe" property.)

The row player's linear program

The row player wants to choose a probability vector x and a number v to maximize v subject to guaranteeing at least v against every pure column:

Text
maximize    v
subject to  sum_i x_i A[i, j] >= v   for every column j
            sum_i x_i = 1,  x_i >= 0

This is a linear program: the objective and constraints are linear in the unknowns (x, v). SciPy's linprog minimizes, so we minimize -v. The variable v is free (it can be negative), and each column constraint is rewritten as -x @ A[:, j] + v <= 0.

flowchart LR
    A["Payoff matrix A"] --> LP["LP: maximize v<br/>x @ A[:, j] >= v for every j<br/>sum x = 1, x >= 0"]
    LP --> X["Optimal mix x*"]
    LP --> V["Game value v"]

The security level of a mixed strategy is the minimum over the columns, so maximizing a lower bound v finds the best guarantee.

Python Solve a zero-sum game with linprog

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The function solves both players' problems and checks that the two values match, which is the minimax theorem in action. In the saddle-point game the optimal strategies are pure, with value 2, exactly as you found by hand earlier. In the asymmetric 2x3 game both players mix and the value is a fraction.

Why the two programs are linked

The column player's program is the dual of the row player's. Linear programming duality says the optimal values of a primal and its dual are equal, which is precisely the minimax theorem. It is a neat historical fact: von Neumann's game theory and George Dantzig's linear programming were two views of the same mathematics, and Dantzig credits a conversation with von Neumann for the realization.

Checking the answer and the guarantee

An optimal mix x* guarantees v against every column. We can test this directly: compute x @ A, which lists the row player's expected payoff against each pure column; its minimum must equal v. Columns where the guarantee holds with equality are the ones the column player actually uses.

Python The guarantee of an optimal strategy

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the second line: the third column gives the row player more than v (it is never used by the column player). An action that is not in the support of the optimal opposing mix is a pure strategy that the opponent is not willing to play, because it gives you more than the value.

A bigger example: Colonel Blotto

In Colonel Blotto, two commanders distribute their soldiers across several battlefields. On each field, the commander with more soldiers wins it. The payoff is the number of fields won minus the number lost. With 3 soldiers and 3 fields, each commander has 10 pure strategies (the ways to place 3 identical soldiers into 3 fields). Blotto is a symmetric zero-sum game, so its value is 0, but the optimal mix is interesting.

Python Solve a Blotto game

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The optimal play mixes three formations, each with probability one third, and never uses the all-in (3, 0, 0) or the evenly spread (1, 1, 1). Each of the three formations beats one of the other two and loses to the remaining one, a rock-paper-scissors cycle in disguise. The value is 0 because the game is symmetric, so neither side has an inherent advantage; the optimal strategy only protects you from being exploited. In real Blotto contests, such as election campaigns, unpredictability is the core of good strategy.

Limits of the method

  • It solves zero-sum games. For general-sum games, maximin and the equilibrium generally differ, and more machinery is needed (support enumeration works for small games).
  • The LP grows with the number of pure strategies. Large games, such as poker, use compressed representations and iterative algorithms, but they are built on the same theorem.
  • The optimal strategy is defensive. Against a weak opponent, a non-optimal strategy that exploits their mistakes can earn more than v, at the risk of being exploited in return.

Note: Minimax is how game-playing programs reason in adversarial settings. In sequential games like chess, "minimax search" applies the same idea along a tree of moves. You will meet that tree view in the chapter on sequential games.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the minimax theorem state about finite zero-sum games with mixed strategies?

    Von Neumann's theorem says that with mixed strategies the row player's best guarantee equals the least the column player can hold them to.
  2. 2. In the LP for the row player, what does the variable v represent?

    The constraints x @ A[:, j] >= v for every column j say the mix guarantees at least v; maximizing v finds the best guarantee.
  3. 3. How is the column player's linear program related to the row player's?

    LP duality links the two programs, and equal optimal values of primal and dual is exactly the minimax theorem.
  4. 4. The value of a symmetric zero-sum game such as Colonel Blotto is...

    If both players have the same strategies and swapping roles flips the sign of the payoff, neither side can guarantee more than 0, so the value is 0.

Summary

  • The minimax theorem: with mixed strategies, every finite zero-sum game has a value and optimal strategies, and maximin equals minimax.
  • The row player's optimal mix solves an LP: maximize v subject to x @ A[:, j] >= v for every column and x a probability vector.
  • The column player's LP is its dual, so both give the same value; scipy.optimize.linprog solves them.
  • Optimal strategies are defensive guarantees; they do not exploit a weak opponent.
  • Symmetric zero-sum games have value 0; Blotto-style games need unpredictable mixtures.

Next: Extensive-Form Games and Game Trees