Zero-sum games, play-safe strategies and saddle points

Zero-sum games, play-safe strategies and saddle points

Spec 5.1–2 · Edexcel A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • In a zero-sum game one player's gain is the other's loss. The matrix gives Rose's pay-offs; Colin's is the negative.
  • Rose's play-safe (maximin) strategy: the row with the largest row minimum.
  • Colin's play-safe (minimax) strategy: the column with the smallest column maximum.
  • A stable solution exists if and only if maximin == minimax. The common value is the value of the game.
  • If maximin << minimax there is no stable solution and players need mixed strategies.

The pay-off matrix

Rose chooses a row, Colin chooses a column, and the entry is Rose's gain. Colin's pay-off is its negative.

In a two-person zero-sum game one player's gain is exactly the other's loss, so the total pay-off is always zero.

The pay-off matrix is written from the row player's point of view (Rose) unless you are told otherwise. Rose chooses a row, Colin chooses a column, and the entry is Rose's gain.

A negative entry is a loss for Rose. Colin's pay-off is the negative of the entry.

−3−2−101234Column 1Column 2Colin’s columnRose’s pay-off
  • Rose plays row 1
  • Rose plays row 2
Rose’s pay-offs from the matrix (positive = gain, negative = loss) for each pair of choices.

Colin plays column 1

Rose plays row 1:
2
Rose plays row 2:
−3

Colin plays column 2

Rose plays row 1:
−1
Rose plays row 2:
4

Worked example

In the game (2−1−34)\begin{pmatrix}2&-1\\-3&4\end{pmatrix}, Rose plays row 2 and Colin plays column 1. What happens?

The entry for a pair of strategies is −5-5. What does this mean?

Play-safe strategies

Guard against the worst case: Rose picks the row with the largest minimum, Colin the column with the smallest maximum.

A play-safe strategy guards against the worst case, assuming the opponent plays the best reply.

  • Rose (rows): find the minimum of each row, then choose the row with the largest of these. This is her maximin strategy.
  • Colin (columns): find the maximum of each column (the most he could lose), then choose the column with the smallest of these. This is his minimax strategy.

Write the row minima beside the matrix and the column maxima beneath it.

−2−1012Row 1Row 2Row 3RowRow minimum
Row minima for the matrix: −2, 2 and −1. The largest is 2, so Rose’s maximin is row 2.

Column 1

Row 1:
4
Row 2:
3
Row 3:
−1
Column maximum:
4

Column 2

Row 1:
−2
Row 2:
2
Row 3:
0
Column maximum:
2

Column 3

Row 1:
1
Row 2:
5
Row 3:
6
Column maximum:
6

Row minimum

Row 1:
−2
Row 2:
2
Row 3:
−1
Column maximum:
–

Worked example

Find the play-safe strategies for (4−21325−106)\begin{pmatrix}4&-2&1\\3&2&5\\-1&0&6\end{pmatrix}.

Rose has row minima 1, −4-4, 0. Which row does she play?

Stable solutions and saddle points

A game is stable if and only if maximin equals minimax. The common value is the value of the game, at a saddle point.

A game has a stable solution if and only if maximin == minimax. The common value is the value of the game.

The entry where the play-safe row and column meet is a saddle point: the least entry in its row and the greatest entry in its column.

At a stable solution neither player can do better by changing strategy alone. A game can have more than one saddle point, all with the same value.

In the example above the saddle point is row 2, column 2 and the value is 2.

−20246123Row or column numberValue
  • Row minimum
  • Column maximum
Row minima (−2, 2, −1) and column maxima (4, 2, 6): the largest minimum equals the smallest maximum, 2, so the game is stable.
  • Stable solutionmaximin == minimax
  • Value of the gamethe common value, as Rose's pay-off

For (3120)\begin{pmatrix}3&1\\2&0\end{pmatrix}, is there a stable solution?

No stable solution

Maximin is never greater than minimax. If it is smaller, there is no stable solution and play-safe choices are predictable.

The maximin is never greater than the minimax. If maximin << minimax there is no stable solution: Rose can only guarantee the maximin, Colin can only hold her to the minimax, and neither value is reached by a pair of pure strategies.

A play-safe choice is predictable, so players need to mix their strategies at random (the next topic).

−4−3−2−1012345maximin −1minimax 2

Stable

Condition:
maximin = minimax
Meaning:
a saddle point; a value of the game

Not stable

Condition:
maximin < minimax
Meaning:
players mix their strategies

Worked example

Show that (2−1−34)\begin{pmatrix}2&-1\\-3&4\end{pmatrix} has no stable solution.

Maximin is 1 and minimax is 3. What can you say?

Exam method

Write the matrix, find maximin and minimax, compare, then conclude in context. If the game is given from Colin's view, the roles swap.

Follow the same steps every time.

If you are given the game from Colin's point of view, the roles swap: Colin's play-safe strategy then maximises his minimum entry.

"Show that there is a stable solution" needs both numbers, maximin and minimax, and a statement that they are equal.

  1. 1

    Write the matrix

    from the correct player's view

  2. 2

    Find maximin and minimax

    row minima, take the largest; column maxima, take the smallest

  3. 3

    Compare

    if equal, state the saddle point, strategies and value; if not, say there is no stable solution

  4. 4

    Conclude in context

    name the strategies and sign the pay-off for the right player

Exam method for zero-sum games

What must a "show there is a stable solution" answer include?

Try an exam question

Rose's pay-off matrix is (5362143−17)\begin{pmatrix}5&3&6\\2&1&4\\3&-1&7\end{pmatrix}. Show that the game has a stable solution, and state each player's play-safe strategy and the value of the game.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Which row is Rose's play-safe strategy?

1 mark, marked against the mark scheme

Revision notes