Skip to content
Tutorials Center
My learning

Topics

Lesson 8 of 37 ยท Games and Strategies

Zero-Sum and Constant-Sum Games

Understand zero-sum and constant-sum games, compute security levels with maximin and minimax, find saddle points in a payoff matrix, and see why some games have none.

Some games are pure conflict. If you win a point, I lose a point; if you gain a customer, I lose one. Whatever one player gains, the other loses. Such games are called zero-sum, and they are the oldest and cleanest case in game theory. Chess, poker (ignoring the house's cut), tennis points and a penalty kick are all close to zero-sum.

They are also the easiest games to solve, because there is no room for cooperation or bargaining: each player simply tries to do as well as possible against a perfectly hostile opponent. In this lesson you will define them precisely, learn the idea of a security level, and find saddle points, which are the pure-strategy solutions. For games without a saddle point you will need mixed strategies and the minimax theorem.

Definitions

A two-player game is zero-sum if the payoffs add up to zero in every cell: A[i, j] + B[i, j] = 0, that is, B = -A. So only one matrix is needed. By convention it holds the row player's payoffs, the row player maximizes it, and the column player, who receives the negative, minimizes it.

A game is constant-sum if the payoffs in every cell add up to the same constant c. Splitting a fixed prize, or two firms sharing 100 percent of a market, are constant-sum games. A constant-sum game is strategically identical to a zero-sum game: subtract c/2 from both payoffs and you get a zero-sum game with the same best choices.

Python Recognizing zero-sum and constant-sum games

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.

Security levels: the worst case you can guarantee

Imagine you are the row player and you expect the worst: whatever row you commit to, the column player will reply with the column that hurts you most. For each row i, the worst case is the smallest entry in that row, min_j A[i, j]. You pick the row whose worst case is best:

maximin value = max_i min_j A[i, j].

This is your security level: a payoff you can guarantee by playing the maximin row, no matter what the opponent does. The column player does the mirror image. They face the largest entry in each column, and pick the column whose largest entry is smallest:

minimax value = min_j max_i A[i, j].

This is the least amount the column player can limit the row player to. It is always true that maximin <= minimax. (The row player's guarantee cannot exceed what the column player can hold them to.)

Python Maximin and minimax by hand and in code

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.

In this example the minima of the rows are 1, 0, 2 and the maxima of the columns are 6, 2, 5. The row player can secure 2 by playing the third row, and the column player can hold the row player to 2 by playing the second column. The two values coincide.

Saddle points

When maximin == minimax, the common value is the value of the game, and the pair of strategies achieving it is a saddle point. The entry at a saddle point is simultaneously the smallest in its row and the largest in its column. It is a pure-strategy equilibrium: neither player can do better by changing their own choice. Neither player has anything to hide, since the best move holds even if the opponent knows it in advance.

flowchart LR
    R["Row player<br/>maximizes the worst row minimum"] --> M["maximin"]
    C["Column player<br/>minimizes the worst column maximum"] --> N["minimax"]
    M --> E{"maximin = minimax?"}
    N --> E
    E -->|"yes"| S["Saddle point<br/>value of the game"]
    E -->|"no"| X["Need mixed strategies"]

Pure strategies solve the game only when the two guarantees meet.

Python Find all saddle points

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.

If a game has more than one saddle point, they all have the same value, and the rows and columns can be mixed and matched: if (i, j) and (k, l) are saddle points, so are (i, l) and (k, j). That is a property of zero-sum games that general games do not share.

When there is no saddle point

Matching pennies is the standard counterexample. Each player secretly turns a coin heads or tails. If the coins match, the row player wins 1; if not, the column player wins 1. The row minima are -1 and -1 so maximin is -1. The column maxima are 1 and 1 so minimax is 1. The row player can only guarantee -1, the column player can only hold them to 1: a gap of 2. Any pure strategy is exploitable. If you always play heads, I will always play tails.

The cure is randomization. If both players pick heads or tails with probability one half, the expected payoff is 0 whatever the opponent does. This is the main idea of the next chapter, and one of the great results of the field, John von Neumann's minimax theorem: allowing mixed strategies, in every finite zero-sum game maximin equals minimax. So every finite zero-sum game has a value, and each player has an optimal strategy that guarantees it.

Python Why pure strategies fail in matching pennies

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.

Using the idea in practice

Security-level thinking is a defensive idea. It is the right answer when you cannot predict the opponent or when the opponent is truly hostile (a security attacker, a chess engine). It can be too cautious when the opponent is not hostile, as in many business interactions where both sides can gain. The prisoner's dilemma from Dominant Strategies is not zero-sum and shows why: there, protecting yourself against the worst case leads both players to defect.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A game is zero-sum when...

    Zero-sum means A + B = 0 in every cell, so one player's gain is exactly the other's loss.
  2. 2. In the matrix [[3, 1], [2, 4]] (row player's payoffs), what is the maximin value?

    Row minima are 1 and 2, so the best worst-case is 2. The column maxima are 3 and 4, so minimax is 3. There is no saddle point.
  3. 3. What is a saddle point?

    At a saddle point maximin equals minimax, so neither player can gain by deviating.
  4. 4. Why does matching pennies have no saddle point in pure strategies?

    The row player can only guarantee -1 and the column player can only limit the row player to 1. Randomizing closes the gap.

Summary

  • Zero-sum means B = -A; constant-sum games are equivalent to zero-sum games after a shift.
  • Maximin is the best worst-case payoff of the row player; minimax is the least the column player can hold them to; maximin <= minimax.
  • If they are equal, there is a saddle point, a pure-strategy equilibrium, and the common value is the value of the game.
  • Matching pennies has no saddle point, so the players must randomize.
  • Von Neumann's minimax theorem says that with mixed strategies every finite zero-sum game has a value.

Next: Classic 2x2 Games