D2 5.1, 5.2 - Zero-sum games and stable solutions

D2 5.1, 5.2 - Zero-sum games and stable solutions

You will interpret a pay-off matrix, find each player's play-safe strategy, and identify stable solutions and game values.

Read every entry from the row player's point of view

Can both players make their best defensive choice and still leave one of them losing? Yes. A stable game need not be fair: stability describes the choices, while the value says who benefits.

You already know

Positive and negative numbers can represent gains and losses. The minimum is the smallest entry in a list, and the maximum is the largest. Reversing the sign changes one person's gain into an equal loss.

A two-person game has exactly two players. Each chooses an option, and the resulting pair determines the pay-off. Here the players choose without seeing the other's current choice.

Two-person zero-sum game

In a zero-sum game, one player's gain equals the other's loss. Their two pay-offs add to zero on every play.

Unless stated otherwise, a pay-off matrix is written for row player A. A chooses a row and wants the entry large. Column player B chooses a column and wants that same entry small, because B's own gain is its negative.

For example, an entry −3-3 means A loses 33 and B gains 33. An entry zero means neither gains. “Zero-sum” does not mean every entry is zero, and a situation in which both players gain 11 is not zero-sum.

Use this matrix, with pay-offs in pounds to A:

A's option \ B's optionXYZ
R331166
S440033
T554422

If A chooses T and B chooses Y, A gains 44 and B loses 44. If A chooses R and B chooses Z, A gains 66; this is attractive to A, but B has no reason to agree to that column.

A pure strategy means always choosing one specified option. A play-safe pure strategy protects a player against the least favourable response, rather than assuming the opponent chooses randomly or helpfully.

Key idea

Keep one point of view throughout: A maximises the printed pay-off, B minimises it. Find B's own gain by negating the printed entry, not by reversing how its column is read.

Use a negative entry to check the convention.

Find the row maximin and column minimax

If A commits to a row, B can select the smallest entry in it. A therefore compares row minima and chooses the largest. If B commits to a column, A can select the largest entry in it. B compares column maxima and chooses the smallest.

Play-safe pure strategies

For row-player pay-offs aija_{ij}, calculate

L=max⁡imin⁡jaijrow maximinL=\max_i\min_j a_{ij} \qquad\text{row maximin} U=min⁡jmax⁡iaijcolumn minimaxU=\min_j\max_i a_{ij} \qquad\text{column minimax}

A row attaining LL guarantees A at least LL. A column attaining UU holds A to at most UU. Tied attaining rows or columns are all valid play-safe choices.

Not in the formula booklet: learn it.

Both bounds are stated in A's pay-off units. B's guarantee of its own gain is −U-U. Do not minimise B's own negative pay-off as well; that would reverse B's aim twice.

Worked example 1: two different safety bounds

Question. Find the play-safe strategies and bounds for the displayed matrix.

Plan. Write every row minimum and column maximum, then take the appropriate outer extreme.

A rowRST
Row minimum110022
B columnXYZ
Column maximum554466

Hence

L=max⁡(1,0,2)=2,U=min⁡(5,4,6)=4L=\max(1,0,2)=2,\qquad U=\min(5,4,6)=4

Why choose T rather than the row containing 66? The entry 66 needs B to choose Z; T gives the largest guaranteed result regardless of B's response.

Answer. A's play-safe choice is T, guaranteeing at least 22 pounds. B's play-safe choice is Y, limiting A to at most 44 pounds.

Check. T's entries 5,4,25,4,2 are all at least 22, and Y's entries 1,0,41,0,4 are all at most 44. B thereby guarantees its own gain is at least −4-4.

Worked example 2 changes only the TZ entry, from 22 to 33.

Worked example 2: improve one player's guarantee

Question. Recalculate the pure play-safe strategies and bounds after that change.

Plan. Update the affected row minimum and column maximum, then compare all rows and columns again.

RowRSTMinimum103ColumnXYZMaximum546\begin{array}{c|ccc} \text{Row}&R&S&T\\\hline \text{Minimum}&1&0&3 \end{array} \qquad \begin{array}{c|ccc} \text{Column}&X&Y&Z\\\hline \text{Maximum}&5&4&6 \end{array}

Therefore

L=3,U=4L=3,\qquad U=4

Why does the Z maximum stay 66? RZ still equals 66, larger than the altered entry. A change in one entry need not change both safety bounds.

Answer. A still chooses T, now guaranteeing at least 33. B still chooses Y, holding A to at most 44.

Check. The changed T row is 5,4,35,4,3; its least entry is 33, while the Y column is unchanged.

If L<UL<U, the bounds leave a gap. They do not identify a single exact value, and averaging them has no general justification. Mixed strategies in the next lesson can improve on pure play-safe choices.

Watch out

Wrong: find row maxima and column minima, or select the largest entry anywhere. Right: A maximises its row minimum; B minimises the printed column maximum.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account