7.08a Pay-off matrix: zero-sum games

4 Kareem and Sam play a game in which each holds a hand of three cards.

• Kareem's cards are numbered 1, 2 and 5.
• Sam's cards are numbered 3, 4 and 6 .

In each round Kareem and Sam simultaneously choose a card from their hand, they show their chosen card to the other player and then return the card to their own hand.

• If the sum of the numbers on the cards shown is even then the number of points that Kareem scores is \(2 k\), where \(k\) is the number on Kareem's card.
• If the sum of the numbers on the cards shown is odd then the number of points that Kareem scores is \(4 - s\), where \(s\) is the number on Sam's card.
  1. Complete the pay-off matrix for this game, to show the points scored by Kareem.
  2. Write down which card Kareem should play to maximise the number of points that he scores for each of Sam's choices.
  3. Determine the play-safe strategy for Kareem.
  4. Explain why Kareem should never play the card numbered 1.

Sam chooses a card at random, so each of Sam's three cards is equally likely.

Calculate Kareem's expected score for each of his remaining choices.

6 Ryan and Casey are playing a card game in which they each have four cards.

• Ryan's cards have the letters A, B, C and D.
• Casey's cards have the letters W, X, Y and Z.

Each player chooses one of their four cards and they simultaneously reveal their choices. The table shows the number of points won by Ryan for each combination of strategies. \begin{table}[h] \end{table} For example, if Ryan chooses A and Casey chooses W then Ryan wins 4 points (and Casey loses 4 points). Both Ryan and Casey are trying to win as many points as possible.

1. Use dominance to reduce the \(4 \times 4\) table for the zero-sum game above to a \(4 \times 2\) table.
2. Determine an optimal mixed strategy for Casey.

2 In a game two players are each dealt five cards from a set of ten different cards.
Player 1 is dealt cards A, B, F, G and J.
Player 2 is dealt cards C, D, E, H and I. Each player chooses a card to play.
The players reveal their choices simultaneously. The pay-off matrix below shows the points scored by player 1 for each combination of cards. Pay-off for player 1 \begin{table}[h] \end{table}

1. Determine the play-safe strategy for player 1, ignoring any effect on player 2. The pay-off matrix below shows the points scored by player 2 for each combination of cards.
   Pay-off for player 2 Player 1 \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Player 2}

   		C	D	E	H
   \cline { 2 - 6 } A	2	2	0	1	I
   \cline { 2 - 6 } B	3	1	2	1	2
   \cline { 2 - 6 } F	3	2	2	1	0
   \cline { 2 - 6 } G	1	3	0	0	0
   \cline { 2 - 6 } J	2	1	0	3	1
   \cline { 2 - 6 }
   \cline { 2 - 6 }

   \end{table}
2. Use a dominance argument to delete two columns from the pay-off matrix. You must show all relevant comparisons.
3. Explain, with reference to specific combinations of cards, why the game cannot be converted to a zero-sum game.

5 The number of points won by player 1 in a zero-sum game is shown in the pay-off matrix below, where \(k\) is a constant. \begin{table}[h] \end{table}

1. In one game, player 2 chooses strategy H. Write down the greatest number of points that player 2 could win. You are given that strategy A is a play-safe strategy for player 1.
2. Determine the range of possible values for \(k\).
3. Determine the column minimax value.

7 Player 1 and player 2 are playing a two-person zero-sum game.
In each round of the game the players each choose a strategy and simultaneously reveal their choice. The number of points won in each round by player 1 for each combination of strategies is shown in the table below. Each player is trying to maximise the number of points that they win.
Player 2 Player 1

1. 1. Determine play-safe strategies for each player.
   2. Show that the game is not stable.
2. Show that the number of strategies available to player 1 cannot be reduced by dominance. You must make it clear which values are being compared. Player 1 intends to make a random choice between strategies \(\mathrm { X } , \mathrm { Y } , \mathrm { Z }\), choosing strategy X with probability \(x\), strategy Y with probability \(y\) and strategy Z with probability \(z\).
   Player 1 formulates the following LP problem so they can find the optimal values of \(x , y\) and \(z\) using the simplex algorithm. Maximise \(M = m - 4\) subject to \(m \leqslant 6 x + 4 y + 2 z\) $$\begin{aligned} & m \leqslant x + 5 y + 6 z \\ & m \leqslant 7 y + 8 z \\ & x + y + z \leqslant 1 \end{aligned}$$ and \(m \geqslant 0 , x \geqslant 0 , y \geqslant 0 , z \geqslant 0\)
3. Explain how the inequality \(m \leqslant 6 x + 4 y + 2 z\) was formed. The problem is solved by running the simplex algorithm on a computer.
   The printout gives a solution in which \(\mathrm { x } + \mathrm { y } = 1\).
   This means that the LP problem can be reduced to the following formulation.
   Maximise \(M = m - 4\) subject to \(m \leqslant 4 + 2 x\) \(\mathrm { m } \leqslant 5 - 4 \mathrm { x }\) \(m \leqslant 7 - 7 x\) and \(m \geqslant 0 , x \geqslant 0\)
4. Solve this problem to find the optimal values of \(x , y\) and \(z\) and the corresponding value of the game to player 1.

3 Amir and Beth play a zero-sum game.
The table shows the pay-off for Amir for each combination of strategies, where these values are known. \begin{table}[h] \end{table} You are given that \(\mathrm { a } < 0 < \mathrm { b } < \mathrm { c }\).
Amir's play-safe strategy is R.

1. Determine the range of possible values of \(a\). Beth's play-safe strategy is Y.
2. Determine the range of possible values of \(b\).
3. Determine whether or not the game is stable.

2 Annie and Brett play a two-person, simultaneous play game. The table shows the pay-offs for Annie and Brett in the form ( \(a , b\) ). So, for example, if Annie plays strategy K and Brett plays strategy S, Annie wins 2 points and Brett wins 6 points.

1. 1. Determine the play-safe strategy for Annie.
   2. Show that the play-safe strategy for Brett is T.
2. 1. If Annie knows that Brett is planning on playing strategy T, which strategy should Annie play to maximise her points?
   2. If Brett knows that Annie is planning on playing the strategy identified in part (b)(i), which strategy should Brett play to maximise his points?
3. Show that, for Brett, strategy R is weakly dominated.
4. Using a graphical method, determine the optimal mixed strategy for Brett.
5. Show that the game has no Nash equilibrium points.

5 Alex and Beth play a zero-sum game. Alex chooses a strategy P, Q or R and Beth chooses a strategy \(\mathrm { X } , \mathrm { Y }\) or Z . The table shows the number of points won by Alex for each combination of strategies. The entry for cell \(( \mathrm { P } , \mathrm { X } )\) is \(x\), where \(x\) is an integer. \begin{table}[h] \end{table} Suppose that P is a play-safe strategy.

1. 1. Determine the values of \(x\) for which the game is stable.
   2. Determine the values of \(x\) for which the game is unstable. The game can be reduced to a \(2 \times 3\) game using dominance.
2. Write down the pay-off matrix for the reduced game. When the game is unstable, Alex plays strategy P with probability \(p\).
3. Determine, as a function of \(x\), the value of \(p\) for the optimal mixed strategy for Alex. Suppose, instead, that P is not a play-safe strategy and the value of \(x\) is - 5 .
4. Show how to set up a linear programming formulation that could be used to find the optimal mixed strategy for Alex.

4 The table shows the pay-off matrix for player \(A\) in a two-person zero-sum game between \(A\) and \(B\). Player \(A\) Player \(B\)

1. Find the play-safe strategy for player \(A\) and the play-safe strategy for player \(B\). Use the values of the play-safe strategies to determine whether the game is stable or unstable.
2. If player \(B\) knows that player \(A\) will use their play-safe strategy, which strategy should player \(B\) use?
3. Suppose that the value in the cell where both players use their play-safe strategies can be changed, but all other entries are unchanged. Show that there is no way to change this value that would make the game stable.
4. Suppose, instead, that the value in one cell can be changed, but all other entries are unchanged, so that the game becomes stable. Identify a suitable cell and write down a new pay-off value for that cell which would make the game stable.
5. Show that the zero-sum game in the table above has a Nash equilibrium and explain what this means for the players.

8 John and Danielle play a zero-sum game which does not have a stable solution. The game is represented by the following pay-off matrix for John. Find the optimal mixed strategy for John.

2.

1. Explain what the term 'zero-sum game' means. Two teams, A and B , are to face each other as part of a quiz.
   There will be several rounds to the quiz with 10 points available in each round.
   For each round, the two teams will each choose a team member and these two people will compete against each other until all 10 points have been awarded. The number of points that Team A can expect to gain in each round is shown in the table below.

   \cline { 3 - 5 } \multicolumn{2}{c|}{}	Team B
   \cline { 3 - 5 } \multicolumn{2}{c|}{}	Paul	Qaasim	Rashid
   \multirow{3}{*}{Team A}	Mischa	5	6	3
   \cline { 2 - 5 }	Noel	4	1	7
   \cline { 2 - 5 }	Olive	4	5	8

   The teams are each trying to maximise their number of points.
2. State the number of points that Team B will expect to gain each round if Team A chooses Noel and Team B chooses Rashid.
3. Explain why subtracting 5 from each value in the table will model this situation as a zero-sum game.
4. 1. Find the play-safe strategies for the zero-sum game.
   2. Explain how you know that the game is not stable. At the last minute, Olive becomes unavailable for selection by Team A.
      Team A decides to choose its player for each round so that the probability of choosing Mischa is \(p\) and the probability of choosing Noel is \(1 - p\).
5. Use a graphical method to find the optimal value of \(p\) for Team A and hence find the best strategy for Team A. For this value of \(p\),
6. 1. find the expected number of points awarded, per round, to Team A,
   2. find the expected number of points awarded, per round, to Team B.
      

4. The table below gives the pay-off matrix for a zero-sum game between two players, Aljaz and Brendan. The values in the table show the pay-offs for Aljaz. You may not need to use all of these tables
You may not need to use all the rows and columns \includegraphics[max width=\textwidth, alt={}, center]{bbdfa492-6578-484a-a0b5-fcdb78020b83-06_437_832_1201_139}

3. Two teams, A and B , each have three team members. One member of Team A will compete against one member of Team B for 10 rounds of a competition. None of the rounds can end in a draw. Table 1 shows, for each pairing, the expected number of rounds that the member of Team A will win minus the expected number of rounds that the member of Team B will win. These numbers are the scores awarded to Team A. This competition between Teams A and B is a zero-sum game. Each team must choose one member to play. Each team wants to choose the member who will maximise its score. \begin{table}[h] \end{table}

1. 1. Find the number of rounds that Team A expects to win if Team A chooses Mischa and Team B chooses Paul.
   2. Find the number of rounds that Team B expects to win if Team A chooses Noel and Team B chooses Qaasim. Table 1 models this zero-sum game.
2. 1. Find the play-safe strategies for the game.
   2. Explain how you know that the game is not stable.
3. Determine which team member Team B should choose if Team B thinks that Team A will play safe. Give a reason for your answer. At the last minute, Rashid is ill and is therefore unavailable for selection by Team B.
4. Find the best strategy for Team B, defining any variables you use.

3. In your answer to this question you must show detailed reasoning. A two-person zero-sum game is represented by the following pay-off matrix for player A.

1. Verify that there is no stable solution to this game. Player B plays their option X with probability \(p\).
2. Use a graphical method to find the optimal value of \(p\) and hence find the best strategy for player B.
3. Find the value of the game to player A .
4. Hence find the best strategy for player A .

3. Terry and June play a zero-sum game. The pay-off matrix shows the number of points that Terry scores for each combination of strategies.

1. Explain the meaning of 'zero-sum' game.
2. Verify that there is no stable solution to the game.
3. Write down the pay-off matrix for June.
4. 1. Find the best strategy for June, defining any variables you use.
   2. State the value of the game to Terry. Let Terry play option A with probability \(t\).
5. By writing down a linear equation in \(t\), find the best strategy for Terry.

3. A two-person zero-sum game is represented by the following pay-off matrix for player \(A\).

1. 1. Show that this game is stable.
   2. State the value of this game to player \(B\). Option S is removed from player A's choices and the reduced game, with option S removed, is no longer stable.
2. Write down the reduced pay-off matrix for player \(B\). Let \(B\) play option X with probability \(p\) and option Y with probability \(1 - p\).
3. Use a graphical method to find the optimal value of \(p\) and hence find the best strategy for player \(B\) in the reduced game.
4. 1. Find the value of the reduced game to player \(A\).
   2. State which option player \(A\) should never play in the reduced game.
   3. Hence find the best strategy for player \(A\) in the reduced game.

3. Haruki and Meera play a zero-sum game. The game is represented by the following pay-off matrix for Haruki.

1. Determine whether the game has a stable solution. Option Y for Meera is now removed.
2. Write down the reduced pay-off matrix for Meera.
3. 1. Given that Meera plays Option X with probability \(p\), determine her best strategy.
   2. State the value of the game to Haruki.
   3. State which option(s) Haruki should never play. The number of points scored by Haruki when he plays Option C and Meera plays Option X changes from - 1 to \(k\) Given that the value of the game is now the same for both players,
4. determine the value of \(k\). You must make your method and working clear.

4. A two person zero-sum game is represented by the following pay-off matrix for player A.

1. Verify that there is no stable solution.
2. 1. Find the best strategy for player A.
   2. Find the value of the game to her.

4. A two person zero-sum game is represented by the pay-off matrix for player A shown above.

1. Verify that there is no stable solution to this game. Player A intends to make a random choice between options \(\mathrm { P } , \mathrm { Q }\) and R , choosing option P with probability \(p _ { 1 }\), option Q with probability \(p _ { 2 }\) and option R with probability \(p _ { 3 }\) Player A wants to find the optimal values of \(p _ { 1 } , p _ { 2 }\) and \(p _ { 3 }\) using the Simplex algorithm. Player A formulates the following linear programming problem for the game, writing the constraints as inequalities. $$\begin{aligned} & \text { Maximise } P = V \\ & \text { subject to } V \geqslant 3 p _ { 1 } - 4 p _ { 2 } + p _ { 3 } \\ & \\ & V \geqslant - 2 p _ { 1 } + 4 p _ { 2 } + 2 p _ { 3 } \\ & V \geqslant - 2 p _ { 2 } - p _ { 3 } \\ & p _ { 1 } + p _ { 2 } + p _ { 3 } \leqslant 1 \\ & p _ { 1 } \geqslant 0 , p _ { 2 } \geqslant 0 , p _ { 3 } \geqslant 0 , V \geqslant 0 \end{aligned}$$
2. Correct the errors made by player A in the linear programming formulation of the game, giving reasons for your answer.
3. Write down an initial Simplex tableau for the corrected linear programming problem. The Simplex algorithm is used to solve the corrected linear programming problem. The optimal values are \(p _ { 1 } = 0.6 , p _ { 2 } = 0\) and \(p _ { 3 } = 0.4\)
4. Calculate the value of the game to player A.
5. Determine the optimal strategy for player B, making your reasoning clear.

7. Alexis and Becky are playing a zero-sum game. Alexis has two options, Q and R . Becky has three options, \(\mathrm { X } , \mathrm { Y }\) and Z .
Alexis intends to make a random choice between options Q and R , choosing option Q with probability \(p _ { 1 }\) and option R with probability \(p _ { 2 }\) Alexis wants to find the optimal values of \(p _ { 1 }\) and \(p _ { 2 }\) and formulates the following linear programme, writing the constraints as inequalities. $$\begin{aligned} & \text { Maximise } P = V \\ & \text { where } V = 3 + \text { the value of the gan } \\ & \text { subject to } V \leqslant 6 p _ { 1 } + p _ { 2 } \\ & \qquad \begin{aligned} & V \leqslant 8 p _ { 2 } \\ & V \leqslant 4 p _ { 1 } + 2 p _ { 2 } \\ & p _ { 1 } + p _ { 2 } \leqslant 1 \\ & p _ { 1 } \geqslant 0 , p _ { 2 } \geqslant 0 , V \geqslant 0 \end{aligned} \end{aligned}$$

1. Complete the pay-off matrix for Alexis in the answer book.
2. Use a graphical method to find the best strategy for Alexis.
3. Calculate the value of the game to Alexis. Becky intends to make a random choice between options \(\mathrm { X } , \mathrm { Y }\) and Z , choosing option X with probability \(q _ { 1 }\), option Y with probability \(q _ { 2 }\) and option Z with probability \(q _ { 3 }\)
4. Determine the best strategy for Becky, making your method and working clear.

8. A two-person zero-sum game is represented by the pay-off matrix for player A shown below. \section*{Player B} Player A

1. Verify that there is no stable solution to this game.
2. Explain why player A should never play option T. You must make your reasoning clear. Player A intends to make a random choice between options \(\mathrm { Q } , \mathrm { R }\) and S , choosing option \(Q\) with probability \(p _ { 1 }\), option \(R\) with probability \(p _ { 2 }\) and option \(S\) with probability \(p _ { 3 }\) Player A wants to calculate the optimal values of \(p _ { 1 } , p _ { 2 }\) and \(p _ { 3 }\) using the Simplex algorithm.
3. 1. Formulate the game as a linear programming problem for player A. You should write the constraints as equations.
   2. Write down an initial Simplex tableau for this linear programming problem, making your variables clear. The linear programming problem is solved using the Simplex algorithm. The optimal value of \(p _ { 1 }\) is \(\frac { 6 } { 11 }\) and the optimal value of \(p _ { 2 }\) is 0
4. Find the best strategy for player B, defining any variables you use.

7. A two person zero-sum game is represented by the pay-off matrix for player A, shown above.

1. Verify that there is no stable solution to this game. Player A intends to make a random choice between options \(\mathrm { R } , \mathrm { S }\) and T , choosing option R with probability \(p _ { 1 }\), option S with probability \(p _ { 2 }\) and option T with probability \(p _ { 3 }\) Player A wants to find the optimal values of \(p _ { 1 } , p _ { 2 }\) and \(p _ { 3 }\) using the Simplex algorithm.
   Player A formulates the following objective function for the corresponding linear programme. $$\text { Maximise } P = V \quad \text { where } V = \text { the value of the game } + 3$$
2. Determine an initial Simplex tableau, making your variables and working clear. After several iterations of the Simplex algorithm, a possible final tableau is

   b.v.	\(V\)	\(p _ { 1 }\)	\(p _ { 2 }\)	\(p _ { 3 }\)	r	\(s\)	\(t\)	\(u\)	Value
   \(p _ { 3 }\)	0	0	0	1	\(\frac { 1 } { 10 }\)	\(- \frac { 3 } { 80 }\)	\(- \frac { 1 } { 16 }\)	\(\frac { 33 } { 80 }\)	\(\frac { 33 } { 80 }\)
   \(p _ { 2 }\)	0	0	1	0	\(- \frac { 1 } { 10 }\)	\(\frac { 13 } { 80 }\)	\(- \frac { 1 } { 16 }\)	\(\frac { 17 } { 80 }\)	\(\frac { 17 } { 80 }\)
   V	1	0	0	0	\(\frac { 1 } { 2 }\)	\(\frac { 5 } { 16 }\)	\(\frac { 3 } { 16 }\)	\(\frac { 73 } { 16 }\)	\(\frac { 73 } { 16 }\)
   \(p _ { 1 }\)	0	1	0	0	0	\(- \frac { 1 } { 8 }\)	\(\frac { 1 } { 8 }\)	\(\frac { 3 } { 8 }\)	\(\frac { 3 } { 8 }\)
   \(P\)	0	0	0	0	\(\frac { 1 } { 2 }\)	\(\frac { 5 } { 16 }\)	\(\frac { 3 } { 16 }\)	\(\frac { 73 } { 16 }\)	\(\frac { 73 } { 16 }\)

3. 1. State the best strategy for player A.
   2. Calculate the value of the game for player B. Player B intends to make a random choice between options \(\mathrm { X } , \mathrm { Y }\) and Z .
4. Determine the best strategy for player B, making your method and working clear.
   (3)

5. A two person zero-sum game is represented by the pay-off matrix for player A given above.

1. Explain, with justification, how this matrix may be reduced to a \(3 \times 3\) matrix.
2. Find the play-safe strategy for each player and verify that there is no stable solution to this game. The game is formulated as a linear programming problem for player A .
   The objective is to maximise \(P = V\), where \(V\) is the value of the game to player A.
   One of the constraints is that \(p _ { 1 } + p _ { 2 } + p _ { 3 } \leqslant 1\), where \(p _ { 1 } , p _ { 2 } , p _ { 3 }\) are the probabilities that player A plays 1, 2, 3 respectively.
3. Formulate the remaining constraints for this problem. Write these constraints as inequalities. The Simplex algorithm is used to solve the linear programming problem.
   The solution obtained is \(p _ { 1 } = 0 , p _ { 2 } = \frac { 3 } { 7 } , p _ { 3 } = \frac { 4 } { 7 }\)
4. Calculate the value of the game to player A.

5 In each round of a card game two players each have four cards. Every card has a coloured number.

• Player A's cards are red 1 , blue 2 , red 3 and blue 4.
• Player B's cards are red 1 , red 2 , blue 3 and blue 4 .

Each player chooses one of their cards. The players then show their choices simultaneously and deduce how many points they have won or lost as follows:

• If the numbers are the same both players score 0 .
• If the numbers are different but are the same colour, the player with the lower value card scores the product of the numbers on the cards.
• If the numbers are different and are different colours, the player with the higher value card scores the sum of the numbers on the cards.
• The game is zero-sum.
  1. Complete the pay-off matrix for this game, with player A on rows.
  2. Determine the play-safe strategy for each player.
  3. Use dominance to show that player A should not choose red 3 . You do not need to identify other rows or columns that are dominated.
  4. Determine, with a reason, whether the game is stable or unstable.

3 Lee and Maria are playing a strategy game. The tables below show the points scored by Lee and the points scored by Maria for each combination of strategies. Points scored by Lee Lee's choice \begin{table}[h] \end{table} Points scored by Maria Lee's choice \includegraphics[max width=\textwidth, alt={}, center]{a51b112d-1f3f-4214-94c1-8b9cd7eb831c-3_335_481_392_1139}

1. Show how this game can be reformulated as a zero-sum game.
2. By first using dominance to eliminate one of Lee's choices, use a graphical method to find the optimal mixed strategy for Lee.