Questions on mixed strategies in game theory

Question 1

Explain why a game with no stable solution needs a mixed strategy, rather than the row that gives the best worst case.

Accepted Answer

If maximin and minimax differ, then whichever single pair of choices is made, one player can improve by switching. A predictable choice can be exploited, so the row player has to vary between rows with fixed probabilities. B1 for the instability, B1 for the need to randomise.

Question 2

Against two columns the expected pay-offs are 2 + 5p and 7 − 3p. Find the optimal p and the value of the game.

Accepted Answer

Equate the two: 2 + 5p = 7 − 3p, so 8p = 5 and p = 0.625. The value is 2 + 5(0.625) = 5.125, and 7 − 3(0.625) = 5.125 confirms it. M1 for equating the two expressions, A1 for p = 0.625, A1 for the value 5.125.

Question 3

In a game the row player plays R1 with probability p and R2 with probability 1 − p. One column pays the row player 5 against R1 and 2 against R2. Write down the expected pay-off against that column as a function of p, simplifying your answer.

Accepted Answer

The two outcomes against that column are 5, with probability p, and 2, with probability 1 − p, so the expected pay-off is 5p + 2(1 − p). M1 for weighting each entry by the probability of the row it sits in. Simplifying, that is 2 + 3p. A1. It is linear in p, which is why every column contributes a straight line to the graph, and at p = 0 and p = 1 it returns the column's own two entries, 2 and 5.

Question 4

In a 2 by 4 game the row player's four expected pay-off lines are drawn, and three of them pass through the highest point of the lower boundary. State which pair should be equated to find p, and what must be written down alongside the working.

Accepted Answer

Any two of the boundary pieces that meet at that point will do: they all cross there, so each pair gives the same p and the same value. B1 for any such pair serving. What has to be recorded is which pair was used, and that they are the two meeting at the peak of the lower boundary, since a pair chosen anywhere else crosses somewhere else. B1.

Question 5

A game has rows R1 (6, 2) and R2 (3, 7). Show it has no stable solution, then find the row player's optimal mix and the value.

Accepted Answer

Row minima are 2 and 3, so the row player's maximin is 3. Column maxima are 6 and 7, so the column player's minimax is 6. They differ, so there is no stable solution and no saddle point.
Let the row player play R1 with probability p, so R2 has probability 1 − p. Against C1 the expected pay-off is 6p + 3(1 − p) = 3 + 3p. Against C2 it is 2p + 7(1 − p) = 7 − 5p.
Equating: 3 + 3p = 7 − 5p, so 8p = 4 and p = 0.5.
The value is 3 + 3(0.5) = 4.5, and 7 − 5(0.5) = 4.5 agrees. B1 for the maximin 3, B1 for the minimax 6, B1 for stating there is no stable solution, M1 for the two expected pay-offs, A1 for p = 0.5, A1 for the value 4.5.

Question 6

A game has rows R1 (6, 2) and R2 (3, 7), and the row player's optimal mix gives it a value of 4.5. Find the column player's optimal mix and use it to check that value.

Accepted Answer

Let the column player play C1 with probability q. Against R1 the expected loss is 6q + 2(1 − q) = 2 + 4q. Against R2 it is 3q + 7(1 − q) = 7 − 4q.
Equating: 2 + 4q = 7 − 4q, so 8q = 5 and q = 0.625.
The value is 2 + 4(0.625) = 4.5, matching the value the row player's mix gives, so both mixes are right. M1 for the two expected losses, A1 for both expressions, M1 for equating them, A1 for q = 0.625, A1 for the value 4.5. Note that the two probabilities differ even though the value does not.

Question 7

A student says the row player should favour R2 here, since its entries 3 and 7 total more than R1's 6 and 2. Explain what is wrong.

Accepted Answer

The proportions are fixed by where the two expected pay-off lines cross, not by the sizes of the entries. Here the answer is an even split, even though R2 has the larger total. Favouring R2 would let the column player reply with C1, where R2 pays only 3, and that drags the guaranteed pay-off below 4.5. B1 for the proportions coming from the crossing point, B1 for the column player's reply, B1 for the effect on the guaranteed pay-off.

Question 8

A game has rows R1 (6, 4) and R2 (2, 3). A student writes the expected pay-offs 2 + 4p and 3 + p, equates them, and reports the mix p = 1/3 with value 10/3. Explain what has gone wrong, and give the correct optimal strategy and the value of the game.

Accepted Answer

The two expressions are correct, but equating them only finds where the lines cross. Both lines rise with p, so the lower boundary rises all the way across and its highest point is at the end p = 1, not at the crossing: at p = 1/3 the boundary is at 10/3 and still climbing. At p = 1 the guarantee is min(6, 4) = 4, better than the 10/3 quoted.
So the optimum is the pure strategy R1, with value 4.
The warning was there before any line was drawn: 6 > 2 and 4 > 3, so R1 dominates R2 and R2 should have been deleted first. Indeed the maximin and minimax are both 4, so this game is stable and never needed a mix at all. B1 for the boundary peaking at an end because both lines rise, M1 for checking the ends alongside the crossing, A1 for the value 4 at p = 1, B1 for the dominance of R1 over R2, B1 for noting the game is stable with saddle value 4.

Question 9

A game has rows R1 (5, 1), R2 (2, 4) and R3 (3, 2), and no stable solution. By considering the column player's expected losses, find the column player's optimal mix graphically, state the value of the game, and name the row the row player never plays.

Accepted Answer

Let the column player play C1 with probability q. The expected loss against R1 is 5q + 1(1 − q) = 1 + 4q, against R2 it is 2q + 4(1 − q) = 4 − 2q, and against R3 it is 3q + 2(1 − q) = 2 + q.
Sketch the three lines over 0 ≤ q ≤ 1 and take the lowest point of the upper boundary, since the column player must guard against the row player picking the costliest row. At q = 0 the losses are 1, 4 and 2, so R2 is on top; at q = 1 they are 5, 2 and 3, so R1 is. The boundary's lowest point is where those two meet: 1 + 4q = 4 − 2q gives 6q = 3, so q = 0.5, and the value is 1 + 4(0.5) = 3.
At q = 0.5 the line for R3 is at 2 + 0.5 = 2.5, below the boundary, so against the optimal mix R3 pays the row player less than 3: the row player never plays R3. M1 for the three expected losses in terms of q, A1 for all three correct, M1 for equating the pair that meets at the lowest point of the upper boundary, A1 for q = 0.5, A1 for the value 3, B1 for R3 with the reason. The value 3 lies between the maximin of 2 and the minimax of 4, as it must.

Question 10

A game has rows R1 (6, 2, 0) and R2 (0, 2, 6). Show that it has no stable solution, find every optimal mix for the row player and the value of the game, and state the column player's optimal strategy.

Accepted Answer

Row minima are 0 and 0, so the maximin is 0; column maxima are 6, 2 and 6, so the minimax is 2. They differ, so there is no stable solution. B1.
With R1 played with probability p, the expected pay-offs are 6p + 0(1 − p) = 6p against C1, 2p + 2(1 − p) = 2 against C2, and 0p + 6(1 − p) = 6 − 6p against C3. M1 for the three expressions, A1 for all three, and note that C2 gives a horizontal line because its two entries are equal.
The lower boundary is the smallest of 6p, 2 and 6 − 6p. Now 6p is below 2 for p < 1/3, and 6 − 6p is below 2 for p > 2/3, so between those two values the boundary is the flat line at 2 and outside them it is lower. Its highest point is therefore the whole stretch 1/3 ≤ p ≤ 2/3, and the value of the game is 2. M1 for reading the lower boundary, A1 for the interval and the value.
The column player can hold the row player to 2 by playing C2 alone, since C2 pays 2 against either row, and 2 is the value, so that pure strategy is optimal. B1.

Question 11

In a zero-sum game the row player's pay-offs are R1 (4, 1, 3), R2 (2, 5, 1) and R3 (3, 2, 4). Show that the game has no stable solution and does not reduce by dominance, and formulate the search for the column player's optimal mixed strategy as a linear programming problem ready for the Simplex algorithm. Say why no constant needs to be added to the entries here.

Accepted Answer

Row minima are 1, 1 and 2, so the maximin is 2; column maxima are 4, 5 and 4, so the minimax is 4. They differ, so there is no stable solution. No row is at least as good as another in every column and no column is at least as small as another in every row, so nothing can be deleted. B1 for both checks.
Let q₁, q₂, q₃ be the probabilities with which the column player uses C1, C2 and C3, and let V be the value of the game. The column player pays out, so the objective is to minimise V. B1 for the variables and the direction.
Each row of the matrix gives one constraint, saying that the row player's expected pay-off against that row is at most V:
4q₁ + q₂ + 3q₃ ≤ V, against R1,
2q₁ + 5q₂ + q₃ ≤ V, against R2,
3q₁ + 2q₂ + 4q₃ ≤ V, against R3,
with q₁ + q₂ + q₃ = 1 and each q ≥ 0. M1 for one constraint per row, A1 for all three with the probabilities summing to 1.
Simplex needs every entry non-negative, and the smallest entry here is 1, so no constant has to be added and the value Simplex reports is the value of the game itself. B1.
The row player's own programme is the mirror image, maximising V with one constraint per column, and the two give the same value.

Question 12

A game has rows R1 (4, 1, 6) and R2 (2, 7, 3). Find the row player's optimal mix graphically and state which column the other player never uses. Then say how a 3 by 3 game would be handled instead.

Accepted Answer

With R1 played with probability p, the expected pay-offs are 2 + 2p against C1, 7 − 6p against C2, and 3 + 3p against C3. Sketch all three over 0 to 1 and take the highest point of the lower boundary.
At p = 0 the values are 2, 7 and 3; at p = 1 they are 4, 1 and 6. The lower boundary is C1 rising and C2 falling, and they meet where 2 + 2p = 7 − 6p, so 8p = 5 and p = 0.625, giving a value of 3.25.
There C3 is worth 3 + 3(0.625) = 4.875, above the boundary, so C3 is never used: it would hand the row player more than 3.25.
M1 for the three expected pay-off expressions, A1 for all three correct, M1 for reading the lower boundary, A1 for p = 0.625, A1 for the value 3.25, B1 for the column never used, B1 for the linear programming route.
A 3 by 3 game has no single p to plot, so it is converted into a linear program: add a constant to every entry to make them positive if needed, maximise the value subject to one constraint per opposing choice, solve by Simplex, then subtract the constant again.

Question 13

In a zero-sum game the row player's pay-offs are R1 (2, −1, 3), R2 (0, 4, −2) and R3 (1, 2, 1). Show that the game has no stable solution, and formulate the search for the row player's optimal mixed strategy as a linear programming problem ready for the Simplex algorithm, stating how the value of the original game is recovered at the end.

Accepted Answer

Row minima are −1, −2 and 1, so the maximin is 1; column maxima are 2, 4 and 3, so the minimax is 2. They differ, so there is no stable solution, and with three rows and three columns there is no single p to plot, so the game goes to linear programming. No row or column dominates another here, so the matrix does not reduce first.
Simplex needs non-negative entries and the most negative is −2, so add 3 to every entry: the rows become (5, 2, 6), (3, 7, 1) and (4, 5, 4), all positive, and the value rises by exactly 3 because every outcome does.
Let p₁, p₂, p₃ be the probabilities of R1, R2 and R3, and V the value of the shifted game.
Maximise V subject to
5p₁ + 3p₂ + 4p₃ ≥ V, against C1,
2p₁ + 7p₂ + 5p₃ ≥ V, against C2,
6p₁ + p₂ + 4p₃ ≥ V, against C3,
p₁ + p₂ + p₃ = 1, with each p_i ≥ 0.
Each constraint says the expected pay-off against one column is at least V, so maximising V pushes the guarantee as high as the mix allows. After Simplex reports V, the value of the original game is V − 3. B1 for maximin 1 against minimax 2, M1 for adding a constant to every entry, A1 for the shifted matrix with every entry positive, B1 for defining the probabilities and V and maximising V, M1 for one constraint per opposing column, A1 for all three constraints with the probabilities summing to 1, B1 for recovering the value as V − 3.

Question 14

A 2 by 2 zero-sum game has rows R1 (a, b) and R2 (c, d), with no stable solution, and a − b − c + d is not zero. Show that the row player's optimal mix is p = (d − c)/(a − b − c + d) and that the value of the game is (ad − bc)/(a − b − c + d). Verify both on the game with rows R1 (5, 1) and R2 (2, 4).

Accepted Answer

Let the row player use R1 with probability p. Against C1 the expected pay-off is ap + c(1 − p) = c + (a − c)p, and against C2 it is bp + d(1 − p) = d + (b − d)p. M1 for both expressions.
With no stable solution the optimum is where the two lines cross, so equate them: c + (a − c)p = d + (b − d)p, giving p(a − c − b + d) = d − c and hence p = (d − c)/(a − b − c + d). M1 for equating and collecting the p terms, A1 for p.
Substituting into the first expression, the value is c + (a − c)(d − c)/(a − b − c + d). Over the common denominator the numerator is c(a − b − c + d) + (a − c)(d − c) = ca − cb − c² + cd + ad − ac − cd + c² = ad − bc, so the value is (ad − bc)/(a − b − c + d). M1 for the substitution, A1 for the value.
For rows (5, 1) and (2, 4) the denominator is 5 − 1 − 2 + 4 = 6, so p = (4 − 2)/6 = 1/3 and the value is (20 − 2)/6 = 3. Checking directly, 5(1/3) + 2(2/3) = 3 and 1(1/3) + 4(2/3) = 3, which agree. B1 for the verification.
The denominator vanishes when a + d = b + c, and then the two lines are parallel: they never cross, the optimum sits at an end of the interval, and the mix is a pure strategy instead.

Question 15

Show that the value of a zero-sum game is at least the row player's maximin and at most the column player's minimax, and state what this gives you as a check on a calculated value.

Accepted Answer

The value is what each player can guarantee when both play optimally.
The row player may simply play the maximin row and nothing else. That row's smallest entry is the maximin, so whatever the column player does the row player collects at least that much. A mixed strategy is available too and cannot do worse than the best pure one, so the value is at least the maximin. M1 for the pure maximin row being available, A1 for the lower bound.
The column player may play the minimax column and nothing else. That column's largest entry is the minimax, so whatever the row player does the row player collects at most that much, and the value is at most the minimax. M1 for the pure minimax column, A1 for the upper bound.
So a value worked out from a graph or from a linear program must land between the two, and one outside them is wrong before the arithmetic is even reread. B1.
When the two bounds coincide they trap the value between equal numbers, which is the stable case: the mixed strategies are then not needed at all.