Discrete Mathematics 6: Game theoryAQA A-Level Further Maths: Topic test

1. 1
   Alex and Beth play a zero-sum game. At the same time, Alex chooses row 1, 2 or 3 and Beth chooses column 1, 2 or 3. The pay-off matrix gives Alex's winnings in points: $\begin{pmatrix}4&3&6\\5&2&1\\3&4&2\end{pmatrix}$.

   (a)

   Which row is Alex's play-safe strategy?

   [1 mark]

   • ARow 2
   • BRow 1
   • CRow 3
   • DRow 1 and row 3 are equally safe

   (b)

   What is the minimax value, which is the least of the column maximums?

   [1 mark]

   • A3
   • B6
   • C5
   • D4

   (c)

   Show that this game has no stable solution.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   Two ice-cream sellers choose at the same time whether to set up on the beach or in the park. Seller 1's pay-off is the number of customers gained, in hundreds, and Seller 2 loses the same number. If both choose the beach, Seller 1 gains 5. If Seller 1 chooses the beach and Seller 2 the park, Seller 1 gains 8. If Seller 1 chooses the park and Seller 2 the beach, Seller 1 gains 3. If both choose the park, Seller 1 gains 4.

   (a)

   What is the pay-off to Seller 1 when Seller 1 chooses the park and Seller 2 chooses the beach?

   [1 mark]

   • A3
   • B8
   • C4
   • D5

   (b)

   What is Seller 2's play-safe strategy?

   [1 mark]

   • APark
   • BEither, as they are equally safe
   • CBeach
   • DThere is no play-safe strategy

   (c)

   Show that the game has a stable solution and state the value of the game.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   Ines and Jo play a zero-sum game. At the same time, Ines chooses row 1, 2 or 3 and Jo chooses column 1, 2 or 3. The pay-off matrix gives Ines's winnings in points: $\begin{pmatrix}2&5&3\\4&1&6\\1&4&2\end{pmatrix}$.

   (a)

   Identify a row and a column that can be removed because they are dominated, giving reasons, and write down the reduced matrix.

   [3 marks]

   (b)

   Ines plays row 1 with probability $p$ and row 2 with probability $1-p$ in the reduced game. Find the optimal value of $p$ and the value of the game.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   Faye and Gus play a zero-sum game. At the same time, Faye chooses row 1, 2 or 3 and Gus chooses column 1, 2 or 3. The pay-off matrix gives Faye's winnings in points, where a negative value is a loss: $\begin{pmatrix}1&0&4\\2&1&1\\0&3&-1\end{pmatrix}$.

   (a)

   (i) Find each player's play-safe strategy and show that there is no stable solution. (ii) Faye plays rows 1, 2 and 3 with probabilities $\frac14$, $\frac12$ and $\frac14$. Find her expected winnings against each of Gus's columns and state what this shows.

   [6 marks]

   (b)

   Gus wants to minimise Faye's winnings. To convert the game to a linear programming problem for Gus, 2 is added to every pay-off. Gus plays column $j$ with probability $q_j$, the value of the new game is $v$ and $y_j=\frac{q_j}{v}$. (i) Formulate the problem as a linear programming problem to maximise $P=y_1+y_2+y_3$. (ii) The solution is $y_1=\frac1{13}$, $y_2=\frac2{13}$, $y_3=\frac1{13}$, with $P=\frac4{13}$. Find Gus's optimal strategy and the value of the original game.

   [6 marks]

   Total for question 4: 12 marks

5. 5
   Cara and Dev play a zero-sum game. At the same time, Cara chooses row 1, 2 or 3 and Dev chooses column 1, 2 or 3. The pay-off matrix gives Cara's winnings in points: $\begin{pmatrix}-1&3&2\\3&4&3\\5&-2&1\end{pmatrix}$.

   (a)

   What is the value of the game for Cara?

   [1 mark]

   • A4
   • B5
   • C3
   • D2

   (b)

   Which choices of row and column give a stable solution?

   [1 mark]

   • ARow 2 and column 3
   • BRow 2 and column 1
   • CRow 3 and column 1
   • DRow 1 and column 3

   (c)

   Show that neither player can improve their pay-off by changing their choice alone from the stable solution.

   [2 marks]

   Total for question 5: 4 marks

6. 6
   Mia and Noor play a zero-sum game. At the same time, Mia chooses row 1 or 2 and Noor chooses column 1, 2 or 3. The pay-off matrix gives Mia's winnings in points: $\begin{pmatrix}6&2&7\\1&5&6\end{pmatrix}$.

   (a)

   Which statement about dominance is correct?

   [1 mark]

   • AColumn 1 is dominated by column 3
   • BRow 1 dominates row 2
   • CNo row or column is dominated
   • DColumn 3 is dominated by column 1

   (b)

   Mia plays row 1 with probability $p$ and row 2 with probability $1-p$. What is her expected pay-off when Noor plays column 2?

   [1 mark]

   • A$2+3p$
   • B$5-3p$
   • C$2p+5$
   • D$7$

   (c)

   Use the dominance in part (a) to reduce the game, and find Mia's optimal strategy and the value of the game.

   [2 marks]

   Total for question 6: 4 marks

7. 7
   Hana and Idris play a zero-sum game. At the same time, Hana chooses row 1, 2 or 3 and Idris chooses column 1, 2 or 3. The pay-off matrix gives Hana's winnings in points, where a negative value is a loss: $\begin{pmatrix}-3&2&3\\-1&4&-3\\4&-1&2\end{pmatrix}$. The game is to be converted into a linear programming problem for Idris.

   (a)

   Explain why a constant is added to every pay-off before the conversion, find the smallest whole number that makes every pay-off positive, and write down the new matrix.

   [3 marks]

   (b)

   Idris plays column $j$ with probability $q_j$. After adding the constant, the value of the game is $v$, and $y_j=\frac{q_j}{v}$. Formulate Idris's problem as a linear programming problem to maximise $P=y_1+y_2+y_3$.

   [4 marks]

   Total for question 7: 7 marks

8. 8
   Kai and Lee play a zero-sum game. At the same time, Kai chooses row 1 or 2 and Lee chooses column 1, 2 or 3. The pay-off matrix gives Kai's winnings in points: $\begin{pmatrix}5&2&4\\1&6&3\end{pmatrix}$.

   (a)

   Kai plays row 1 with probability $p$. Find the optimal value of $p$ and the value of the game, show that Lee should not play column 3, and find Lee's optimal strategy.

   [6 marks]

   (b)

   Lee solves the game as a linear programming problem. Lee plays column $j$ with probability $q_j$, $v$ is the value of the game and $y_j=\frac{q_j}{v}$. (i) Write down the linear programming problem that Lee solves, to maximise $P=y_1+y_2+y_3$. (ii) Slack variables $r$ and $s$ are added and the simplex algorithm gives a final tableau with rows $y_1+\frac9{14}y_3+\frac3{14}r-\frac1{14}s=\frac17$, $y_2+\frac{11}{28}y_3-\frac1{28}r+\frac5{28}s=\frac17$ and $P+\frac1{28}y_3+\frac5{28}r+\frac3{28}s=\frac27$. Use this to find Lee's optimal strategy and the value of the game.

   [6 marks]

   Total for question 8: 12 marks

End of questions