Questions on game theory: play safe and stable solutions

Question 1

A pay-off matrix has the entry 5 where the first row meets the second column. State what this means for each player.

Accepted Answer

The matrix is written from the row player's point of view, so if those choices are made the row player gains 5 and the column player loses 5. The game is zero-sum, so the column player is looking for small entries, not large ones. B1 for the row player's gain of 5, B1 for the column player's loss.

Question 2

A game has row minima 4 and 2, and column maxima 7, 4 and 9. State whether it is stable and give the value if it is.

Accepted Answer

Maximin = max(4, 2) = 4 and minimax = min(7, 4, 9) = 4. They agree, so the game is stable with value 4, occurring where the first row meets the second column. M1 for comparing maximin with minimax, A1 for the value.

Question 3

State what makes a game zero-sum, and what makes a game constant-sum.

Accepted Answer

A game is zero-sum when the two players' pay-offs in every cell add to nought, so whatever one player gains the other loses. B1. It is constant-sum when those two pay-offs add to the same number k in every cell, which need not be nought. B1. A constant-sum game is converted to zero-sum form by taking k off the row player's entries, and the methods of this topic then apply to it unchanged.

Question 4

In a zero-sum game the row player's pay-offs are R1 (3, 7, 5) and R2 (3, 6, 4). State which row is dominated, and whether the dominance is strict or weak.

Accepted Answer

R1 is at least as good as R2 in every column, since 3 = 3, 7 > 6 and 5 > 4, so R2 is dominated by R1. B1. The two rows tie in the first column, so R1 is not strictly better everywhere and the dominance is weak. B1. Deletion is still the usual move, but the comparison has to be named as weak, because a weakly dominated row can tie with the one that displaces it rather than being beaten by it.

Question 5

In a zero-sum game the row player's pay-offs are R1 (4, 2, 6), R2 (1, 5, 3) and R3 (3, 3, 2). Find both play-safe strategies and say whether the game is stable.

Accepted Answer

Row minima are 2, 1 and 2, so the row player's maximin is 2, playing R1 or R3: both guarantee the same worst case.
Column maxima are 4, 5 and 6, so the column player's minimax is 4, playing C1.
Write the row minima and column maxima before comparing the maximin and minimax values.
Maximin 2 does not equal minimax 4, so the game is not stable and a mixed strategy is needed. All that has been established is that the value lies between 2 and 4. M1 A1 for the row minima and maximin, M1 A1 for the column maxima and minimax, A1 for the play-safe strategies, A1 for the game not being stable.

Question 6

In a zero-sum game the row player's pay-offs are R1 (5, 3, 7), R2 (6, 4, 8) and R3 (2, 1, 3). Show that the game has a stable solution and give the value and the strategies.

Accepted Answer

Row minima are 3, 4 and 1, so the maximin is 4, playing R2.
Column maxima are 6, 4 and 8, so the minimax is 4, playing C2.
They agree, so the game is stable with value 4, at R2 with C2. Neither player can improve by moving alone. Switching row loses the row player 1 or 3, and switching column costs the column player 2 or 4. M1 A1 for the maximin, M1 A1 for the minimax and the stable value.

Question 7

In a zero-sum game the row player's pay-offs are R1 (5, 3, 7), R2 (6, 4, 8) and R3 (2, 1, 3). Reduce the matrix as far as possible using dominance, and comment on the result.

Accepted Answer

R2 beats R1 in every column, since 6 > 5, 4 > 3 and 8 > 7, so R2 dominates R1. R2 also beats R3 everywhere, so R2 dominates R3: delete both rows.
In the single remaining row, the column player wants the smallest of 6, 4 and 8, so C2 dominates C1 and C3 and both go.
The matrix reduces to the single entry 4, so the game is stable with value 4 at R2 with C2. M1 A1 for the row dominance, M1 A1 for the column dominance and the value. Dominance reaches the answer without any comparison of maximin with minimax. Quote the inequalities that justify each deletion; 'looks worse' is not a justification.

Question 8

In a constant-sum game each cell records the row player's pay-off, and the two players' pay-offs in every cell add to 12. The row player's pay-offs are R1 (8, 5, 9), R2 (7, 6, 10) and R3 (4, 3, 6). Convert the game to zero-sum form, show that the converted game is stable, and find how much each player collects when both play safe.

Accepted Answer

Subtract 12 from every entry: the converted rows are R1 (−4, −7, −3), R2 (−5, −6, −2) and R3 (−8, −9, −6), and the column player's pay-off is now minus the row player's, so the game is zero-sum.
Row minima are −7, −6 and −9, so the maximin is −6, at R2. Column maxima are −4, −6 and −2, so the minimax is −6, at C2. They agree, so the converted game is stable with value −6 at R2 with C2.
Add the 12 back: the original game is worth −6 + 12 = 6 to the row player, and the column player collects the other 12 − 6 = 6. M1 for subtracting the constant from every entry, A1 for the converted matrix, M1 for the row minima and column maxima, A1 for maximin = minimax = −6, A1 for restoring the 12 to give 6, B1 for the column player's 6. Subtracting a fixed number leaves every comparison between entries as it was, which is why the play-safe pair is R2 with C2 in either form; only the value moves with the entries.

Question 9

Two players simultaneously show one, two or three fingers. If the total shown is even, the column player pays the row player that total in pounds; if it is odd, the row player pays the column player that total. Construct the pay-off matrix from the row player's point of view, and find the row player's play-safe strategy.

Accepted Answer

Each entry is the total of the two numbers shown, taken positive when that total is even and negative when it is odd, because the matrix records what the row player receives. M1 for the sign rule applied to the total.
Showing one finger gives 1 + 1 = 2 even, 1 + 2 = 3 odd and 1 + 3 = 4 even, so R1 is (2, −3, 4). The same reading gives R2 (−3, 4, −5) and R3 (4, −5, 6). A1 for all nine entries.
The row minima are −3, −5 and −5, so the row player's maximin is −3, playing R1. M1 for the row minima, A1 for the maximin with the row named.
Every row has a negative worst case, so play safe here guarantees only that the loss is held to 3: showing one finger is the least bad of the three against a column player choosing perfectly.

Question 10

In a zero-sum game the row player's pay-offs are R1 (6, 3, 7, 7), R2 (2, 8, 4, 9) and R3 (5, 2, 3, 1). Reduce the matrix as far as dominance allows, justifying every deletion, and state what is left and why it needs a mixed strategy.

Accepted Answer

No column is dominated to start with: whichever pair is compared, one of the three rows reverses the inequality.
Among the rows, R1 beats R3 in every column, since 6 > 5, 3 > 2, 7 > 3 and 7 > 1, so R1 dominates R3 strictly and R3 is deleted. M1 A1 for the row comparison with the four inequalities.
Now compare the columns again over the two rows that remain. C1 is (6, 2) against C3 (7, 4) and C4 (7, 9), and the column player wants small entries, so C1 dominates both C3 and C4 and they go. M1 A1 for the column comparisons.
Deleting R3 first is what makes those comparisons available: while R3 was present, C1 gave 5 against C3's 3 and C4's 1, so neither column was dominated. B1 for the order mattering.
What is left is the two by two game with rows (6, 3) and (2, 8). Its row minima are 3 and 2, so the maximin is 3, and its column maxima are 6 and 8, so the minimax is 6. They differ, so there is no saddle point and a mixed strategy is needed. B1.

Question 11

In a game each cell gives both players' pay-offs, the row player's first. The first row holds (7, 3) and (5, 6), and the second row holds (4, 5) and (2, 7). Determine whether the game can be converted to zero-sum form, showing your test.

Accepted Answer

The test is whether the two pay-offs add to the same constant in every cell. M1 for adding the pair in each cell.
The four totals are 7 + 3 = 10, 5 + 6 = 11, 4 + 5 = 9 and 2 + 7 = 9. A1 for 10, 11, 9 and 9.
They are not all equal, so the game is not constant-sum. B1.
There is therefore no single number to subtract from the row player's entries that would make the column player's pay-offs their negatives, and the game cannot be converted: the methods of this topic, which all read one matrix from the row player's side, do not apply to it. B1.

Question 12

In a zero-sum game the row player's pay-offs are R1 (6, 0, 7), R2 (4, k, 5) and R3 (3, 1, 8), where k is an integer with 1 ≤ k ≤ 9. Find all the values of k for which the game has a stable solution, and state the value of the game in each case.

Accepted Answer

Work in terms of k. The row minima are 0, min(4, k) and 1, so the maximin is k when k ≤ 4 and 4 when k ≥ 4.
The column maxima are 6, max(1, k) and 8, so the minimax is min(6, k) for k ≥ 1, which is k when k ≤ 6 and 6 when k ≥ 6.
Setting the two equal, they agree only while both equal k, that is for k = 1, 2, 3, 4, and then the value of the game is k, at R2 with C2. M1 A1 for the maximin in terms of k, M1 A1 for the minimax in terms of k, A1 for the four values of k, A1 for the value of the game. For k = 5 the maximin is 4 against a minimax of 5, and for k ≥ 6 it is 4 against 6, so those games are not stable.
Note that maximin never exceeds minimax. The entry where the play-safe row meets the play-safe column is at least that row's minimum and at most that column's maximum, so the two agree only when that entry is smallest in its row and largest in its column, which is exactly a saddle point. Answers that produce a maximin above the minimax have an arithmetic error somewhere.

Question 13

A zero-sum game between Rachel and Colin is tabulated from Colin's point of view: his strategies C1 (−4, −2, 3) and C2 (1, −1, 0) label the rows, Rachel's strategies R1, R2 and R3 label the columns, and each entry is the amount Colin receives. Rewrite the game from Rachel's point of view, and determine whether it has a stable solution, giving the value of the game if it does.

Accepted Answer

Rachel's gain is minus Colin's, and her strategies must label the rows, so transpose the table and change every sign. Rachel's rows are R1 (4, −1), R2 (2, 1) and R3 (−3, 0), with Colin's C1 and C2 as the columns.
Row minima are −1, 1 and −3, so Rachel's maximin is 1, at R2. Column maxima are 4 and 1, so Colin's minimax is 1, at C2.
They agree, so the game is stable with value 1 at R2 with C2: Rachel gains 1 and Colin pays 1, which matches the −1 in his own table where C2 meets R2. M1 for transposing and changing signs, A1 for Rachel's matrix, M1 for the row minima and column maxima, A1 for maximin = minimax = 1, A1 for the stable solution at R2 with C2 and its value. Changing the signs without transposing, or transposing alone, reads the game as if a large entry were good for Colin's opponent, and reverses every later comparison.

Question 14

In a zero-sum game the row player's pay-offs are R1 (2, 0, 4), R2 (2, 1, 4) and R3 (0, 1, 3). Reduce the matrix by dominance, stating in each case whether the dominance used is strict or weak, and hence find the game's Nash equilibrium, justifying the name.

Accepted Answer

Compare R2 (2, 1, 4) with R1 (2, 0, 4): it is better in C2, since 1 > 0, and ties in C1 and C3, so R2 dominates R1 weakly. Against R3 (0, 1, 3) it is better in C1 and C3 and ties in C2, so R2 dominates R3 weakly. Delete both rows, naming the comparisons as weak because of the ties.
In the remaining row (2, 1, 4) the column player wants the smallest entry, and 1 < 2 with 1 < 4, so C2 dominates C1 and C3 strictly.
The matrix reduces to the single entry 1: the game is stable with value 1 at R2 with C2.
That pair is a Nash equilibrium because neither player gains by changing alone: against C2 the row player drops to 0 by moving to R1 and gains nothing by moving to R3, and against R2 the column player pays 2 or 4 by switching column. M1 for the row comparisons, A1 for both weak deletions with the ties named, M1 for the column comparison, A1 for the strict deletion leaving the single entry, A1 for the value 1 at R2 with C2, B1 for the justification that neither player gains by moving alone.

Question 15

A zero-sum game has a saddle point at the cell where row i meets column j, meaning that the row maximin and the column minimax are equal and both occur there. Show that the entry in that cell is the smallest in its row and the largest in its column. Hence show that if the game has a second saddle point, at row k with column l, the two saddle points hold the same entry.

Accepted Answer

Write a for the entry where row i meets column j. The maximin is the largest of the row minima and it occurs at row i, so it is the smallest entry of row i; the minimax is the smallest of the column maxima and it occurs at column j, so it is the largest entry of column j. The two are equal to each other and both equal a, so a is at once the smallest in its row and the largest in its column. M1 A1 for the two readings agreeing at that cell.
Now let b be the entry where row k meets column l, also a saddle point, and let c be the entry where row i meets column l. Since a is smallest in row i and c lies in row i, a ≤ c. M1. Since b is largest in column l and c lies in column l, c ≤ b. M1. So a ≤ b.
Running the same argument through the entry where row k meets column j gives b ≤ a. A1 for the reversed chain. Hence a = b and both saddle points hold the same entry. A1.