DF1–DF3 - Pay-off matrices and stable games

DF1–DF3 - Pay-off matrices and stable games

A good decision in a competitive game depends on what the other player can do. DF1 turns the rules into a pay-off matrix; DF2 finds each player's play-safe strategy; DF3 proves whether those choices give a stable solution. You will keep the pay-offs in one player's viewpoint and explain what the value of the game means.

Constructing a pay-off matrix

Can Alice guarantee a gain of £2 when Ben has three different responses? Suppose Alice chooses A or B and Ben chooses X, Y or Z, simultaneously and without seeing the other's choice. Their transfer rules are shown below.

Alice's choiceBen chooses XBen chooses YBen chooses Z
ABen pays Alice £2Ben pays Alice £5Ben pays Alice £3
BBen pays Alice £1Ben pays Alice £4No transfer

Each pound Alice gains is a pound Ben loses. There is no outside prize or fee.

Zero-sum game and pay-off matrix

In a zero-sum game, the two players' gains add to zero for every outcome. A pay-off matrix records the gain of one stated player for every pair of strategies. A positive entry is that player's gain; a negative entry is that player's loss; zero means no net gain.

A pure strategy means choosing one particular action. In this lesson, the matrix is for the row player, who wants larger entries; the column player wants smaller entries because those mean smaller losses, or larger gains, for them. The labels and stated viewpoint matter more than the physical position of a player's name.

Worked example 1: from transfers to entries

Question. Construct the pay-off matrix for Alice using the transfer rules above, with Alice's choices as rows.

Plan. Write Alice's signed gain at each row–column intersection.

XYZA253B140\begin{array}{c|rrr} &X&Y&Z\\\hline A&2&5&3\\ B&1&4&0 \end{array}

The entry in row A, column Y is 5 because Alice receives £5. The zero in row B, column Z records no transfer.

Answer. The displayed matrix is for Alice; Ben's gain at each outcome is the negative of its entry.

Check. At (A, Y), Alice gains £5 and Ben loses £5, giving a total gain of zero. At (B, Z), both gains are zero, also summing to zero.

Keep every game rule unchanged, but change whose gain is recorded and put that player in the rows. This requires both a sign change and an exchange of rows and columns.

Worked example 2: changing viewpoint

Question. Construct the pay-off matrix for Ben for the same game, with Ben's strategies as rows and Alice's as columns.

Plan. Negate each Alice pay-off, then place it under the same pair of strategy labels.

ABX−2−1Y−5−4Z−30\begin{array}{c|rr} &A&B\\\hline X&-2&-1\\ Y&-5&-4\\ Z&-3&0 \end{array}

For example, Ben's row Y and Alice's column A must give −5-5. In matrix notation this new matrix is −AT-\mathbf A^{\mathsf T}, where A\mathbf A was Alice's matrix.

Answer. Ben now maximises the entries of this new matrix. Alice minimises them.

Check. The same physical outcome (Alice A, Ben Y) still makes Ben lose £5. Simply transposing without negating would incorrectly turn that loss into a gain.

The bookkeeping is simple once you decide whose money the entries describe.

Watch out

A negative pay-off is not automatically bad for the column player. In a matrix for Alice, an entry −3-3 means Alice loses £3 and Ben gains £3. Change signs when changing viewpoint; exchange the labels too if you exchange the row and column players.

Construct a new matrix from its rules.

Maximin and minimax play-safe strategies

If Alice commits to a row, Ben could choose its smallest entry. To play safe, she compares these worst outcomes and chooses the largest. Ben does the reverse: for each column he considers the largest Alice could receive, then chooses the smallest of those upper limits.

Play-safe strategies

For a pay-off matrix (aij)(a_{ij}) for the row player, the maximin is the largest row minimum,

L=max⁡imin⁡jaij.L=\max_i\min_j a_{ij}.

A row attaining LL is a play-safe strategy for the row player. The minimax is the smallest column maximum,

U=min⁡jmax⁡iaij.U=\min_j\max_i a_{ij}.

A column attaining UU is a play-safe strategy for the column player. Ties can give more than one play-safe strategy.

The word “safe” concerns a guaranteed bound against any opposing choice. It does not mean “choose the largest entry anywhere”. You must identify the strategy as well as its bound.

Worked example 3: the opening game

Question. Find both play-safe strategies for Alice's matrix (253140)\begin{pmatrix}2&5&3\\1&4&0\end{pmatrix}, with rows A, B and columns X, Y, Z.

Plan. List row minima for Alice and column maxima for Ben.

row minima:2, 0⇒L=2column maxima:2, 5, 3⇒U=2\begin{aligned} \text{row minima}&:2,\ 0 &&\Rightarrow L=2\\ \text{column maxima}&:2,\ 5,\ 3 &&\Rightarrow U=2 \end{aligned}

Answer. Alice plays A, guaranteeing a gain of at least £2. Ben plays X, limiting Alice's gain to at most £2.

Check. Every entry of row A is at least 2, and every entry of column X is at most 2. Those direct comparisons verify the stated guarantees without relying on the labels “maximin” and “minimax”.

Change just the entry at (A, X) from 2 to −1-1. One bad outcome can change Alice's safest row even though the largest entry stays 5.

Worked example 4: one changed pay-off

Question. Find both play-safe strategies for (−153140)\begin{pmatrix}-1&5&3\\1&4&0\end{pmatrix}, with the same labels.

Plan. Recalculate the worst case for each pure choice.

row minima:−1, 0⇒L=0 at Bcolumn maxima:1, 5, 3⇒U=1 at X\begin{aligned} \text{row minima}&:-1,\ 0 &&\Rightarrow L=0\text{ at B}\\ \text{column maxima}&:1,\ 5,\ 3 &&\Rightarrow U=1\text{ at X} \end{aligned}

Answer. Alice's play-safe strategy is B; Ben's is X. Their pure-strategy bounds are 00 and 11.

Check. Row B never gives Alice less than 0. Column X never gives her more than 1. At the pair (B, X) the pay-off is 1, but Alice's guarantee remains 0 because Ben could instead choose Z.

Continue this lesson.

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

Create free account