7.08d Nash equilibrium: identification and interpretation

3 The 'Rovers' and the 'Collies' are two teams of dog owners who compete in weekly dog shows. The top three dogs owned by members of the Rovers are Prince, Queenie and Rex. The top four dogs owned by the Collies are Woof, Xena, Yappie and Zulu. In a show the Rovers choose one of their dogs to compete against one of the dogs owned by the Collies. There are 10 points available in total. Each of the 10 points is awarded either to the dog owned by the Rovers or to the dog owned by the Collies. There are no tied points. At the end of the competition, 5 points are subtracted from the number of points won by each dog to give the score for that dog. The table shows the score for the dog owned by the Rovers for each combination of dogs.

1. Explain why calculating the score by subtracting 5 from the number of points for each dog makes this a zero-sum game.
2. If the Rovers choose Prince and the Collies choose Woof, what score does Woof get, and how many points do Prince and Woof each get in the competition?
3. Show that column \(W\) is dominated by one of the other columns, and state which column this is.
4. Delete the column for \(W\) and find the play-safe strategy for the Rovers and the play-safe strategy for the Collies on the table that remains. Queenie is ill one week, so the Rovers make a random choice between Prince and Rex, choosing Prince with probability \(p\) and Rex with probability \(1 - p\).
5. Write down and simplify an expression for the expected score for the Rovers when the Collies choose Xena. Write down and simplify the corresponding expressions for when the Collies choose Yappie and for when they choose Zulu.
6. Using graph paper, draw a graph to show the expected score for the Rovers against \(p\) for each of the choices that the Collies can make. Using your graph, find the optimal value of \(p\) for the Rovers. If Queenie had not been ill, the Rovers would have made a random choice between Prince, Queenie and Rex, choosing Prince with probability \(p _ { 1 }\), Queenie with probability \(p _ { 2 }\) and Rex with probability \(p _ { 3 }\). The problem of choosing the optimal values of \(p _ { 1 } , p _ { 2 }\) and \(p _ { 3 }\) can be formulated as the following linear programming problem: $$\begin{array} { l l } \operatorname { maximise } & M = m - 4 \\ \text { subject to } & m \leqslant 6 p _ { 1 } + 5 p _ { 2 } , \\ & m \leqslant 3 p _ { 1 } + p _ { 2 } + 5 p _ { 3 } , \\ & m \leqslant 7 p _ { 1 } + 3 p _ { 2 } + 4 p _ { 3 } , \\ & p _ { 1 } + p _ { 2 } + p _ { 3 } \leqslant 1 \\ \text { and } & p _ { 1 } \geqslant 0 , p _ { 2 } \geqslant 0 , p _ { 3 } \geqslant 0 , m \geqslant 0 . \end{array}$$
7. Explain how the expressions \(6 p _ { 1 } + 5 p _ { 2 } , 3 p _ { 1 } + p _ { 2 } + 5 p _ { 3 }\) and \(7 p _ { 1 } + 3 p _ { 2 } + 4 p _ { 3 }\) were obtained. Also explain how the linear programming formulation tells you that \(M\) is a maximin solution. The Simplex algorithm is used to find the optimal values of the probabilities. The optimal value of \(p _ { 1 }\) is \(\frac { 5 } { 8 }\) and the optimal value of \(p _ { 2 }\) is 0 .
8. Calculate the optimal value of \(p _ { 3 }\) and the corresponding value of \(M\).

4 Ross and Collwen are playing a game in which each secretly chooses a magic spell. They then reveal their choices, and work out their scores using the tables below. Ross and Collwen are both trying to get as large a score as possible.

1. Explain how this can be rewritten as the following zero-sum game.

   		Collwen's choice
   		Fire	Ice	Gale
   \cline { 2 - 5 }	Fire	- 3	3	- 2
   \cline { 2 - 5 } Ross's choice	Ice	2	- 2	0
   \cline { 2 - 5 }	Gale	1	- 3	- 1
   \cline { 2 - 5 }

2. If Ross chooses Ice what is Collwen's best choice?
3. Find the play-safe strategy for Ross and the play-safe strategy for Collwen, showing your working. Explain how you know that the game is unstable.
4. Show that none of Collwen's strategies dominates any other.
5. Explain why Ross would never choose Gale, hence reduce the game to a \(2 \times 3\) zero-sum game, showing the pay-offs for Ross. Suppose that Ross uses random numbers to choose between Fire and Ice, choosing Fire with probability \(p\) and Ice with probability \(1 - p\).
6. Use a graphical method to find the optimal value of \(p\) for Ross.

6 At the final battle in a war game, the two opposing armies, led by General Rose, \(R\), and Colonel Cole, \(C\), are facing each other across a wide river. Each army consists of four divisions. The commander of each army needs to send some of his troops North and send the rest South. Each commander has to decide how many divisions (1,2 or 3) to send North. Intelligence information is available on the number of thousands of soldiers that each army can expect to have remaining with each combination of strategies. Thousands of soldiers remaining in \(R\) 's army \(C\) 's choice \(R\) 's choice Thousands of soldiers remaining in \(C\) 's army \(C\) 's choice \(R\) 's choice

1. Construct a table to show the number of thousands of soldiers remaining in \(R\) 's army minus the number of thousands of soldiers remaining in \(C\) 's army (the excess for \(R\) 's army) for each combination of strategies. The commander whose army has the greatest positive excess of soldiers remaining at the end of the game will be declared the winner.
2. Explain the meaning of the value in the top left cell of your table from part (i) (where each commander chooses strategy 1). Hence explain why this table may be regarded as representing a zero-sum game.
3. Find the play-safe strategy for \(R\) and the play-safe strategy for \(C\). If \(C\) knows that \(R\) will choose his play-safe strategy, which strategy should \(C\) choose? One of the strategies is redundant for one of the commanders, because of dominance.
4. Draw a table for the reduced game, once the redundant strategy has been removed. Label the rows and columns to show how many divisions have been sent North. A mixed strategy is to be employed on the resulting reduced game. This leads to the following LP problem:
   Maximise \(\quad M = m - 25\) Subject to \(\quad m \leqslant 15 x + 25 y + 35 z\) \(m \leqslant 45 x + 20 y\) \(x + y + z \leqslant 1\) and
5. Interpret what \(x , y\) and \(z\) represent and show how \(m \leqslant 15 x + 25 y + 35 z\) was formed. A computer runs the Simplex algorithm to solve this problem. It gives \(x = 0.5385 , y = 0\) and \(z = 0.4615\).
6. Describe how this solution should be interpreted, in terms of how General Rose chooses where to send his troops. Calculate the optimal value for \(M\) and explain its meaning. Elizabeth does not have access to a computer. She says that at the solution to the LP problem \(15 x + 25 y + 35 z\) must equal \(45 x + 20 y\) and \(x + y + z\) must equal 1 . This simplifies to give \(y + 7 z = 6 x\) and \(x + y + z = 1\).
7. Explain why there can be no valid solution of \(y + 7 z = 6 x\) and \(x + y + z = 1\) with \(x = 0\). Elizabeth tries \(z = 0\) and gets the solution \(x = \frac { 1 } { 7 }\) and \(y = \frac { 6 } { 7 }\).
8. Explain why this is not a solution to the LP problem.

4 Rowan and Colin are playing a game of 'scissors-paper-rock'. In each round of this game, each player chooses one of scissors ( \(\$$ ), paper ( \)\square\( ) or rock ( \)\bullet$ ). The players reveal their choices simultaneously, using coded hand signals. Rowan and Colin will play a large number of rounds. At the end of the game the player with the greater total score is the winner. The rules of the game are that scissors wins over paper, paper wins over rock and rock wins over scissors. In this version of the game, if a player chooses scissors they will score \(+ 1,0\) or - 1 points, according to whether they win, draw or lose, but if they choose paper or rock they will score \(+ 2,0\) or - 2 points. This gives the following pay-off tables. \includegraphics[max width=\textwidth, alt={}, center]{490ff276-6639-40a1-bffb-dc6967f3ab21-5_476_773_667_239} \includegraphics[max width=\textwidth, alt={}, center]{490ff276-6639-40a1-bffb-dc6967f3ab21-5_478_780_667_1071}

1. Use an example to show that this is not a zero-sum game.
2. Write down the minimum number of points that Rowan can win using each strategy. Hence find the strategy that maximises the minimum number of points that Rowan can win. Rowan decides to use random numbers to choose between the three strategies, choosing scissors with probability \(p\), paper with probability \(q\) and rock with probability \(( 1 - p - q )\).
3. Find and simplify, in terms of \(p\) and \(q\), expressions for the expected number of points won by Rowan for each of Colin's possible choices. Rowan wants his expected winnings to be the same for all three of Colin's possible choices.
4. Calculate the probability with which Rowan should play each strategy.

6 Rose is playing a game against a computer. Rose aims a laser beam along a row, \(A , B\) or \(C\), and, at the same time, the computer aims a laser beam down a column, \(X , Y\) or \(Z\). The number of points won by Rose is determined by where the two laser beams cross. These values are given in the table. The computer loses whatever Rose wins.

1. Find Rose's play-safe strategy and show that the computer's play-safe strategy is \(Y\). How do you know that the game does not have a stable solution?
2. Explain why Rose should never choose row \(C\) and hence reduce the game to a \(2 \times 3\) pay-off matrix.
3. Rose intends to play the game a large number of times. She decides to use a standard six-sided die to choose between row \(A\) and row \(B\), so that row \(A\) is chosen with probability \(a\) and row \(B\) is chosen with probability \(1 - a\). Show that the expected pay-off for Rose when the computer chooses column \(X\) is \(4 - 3 a\), and find the corresponding expressions for when the computer chooses column \(Y\) and when it chooses column \(Z\). Sketch a graph showing the expected pay-offs against \(a\), and hence decide on Rose's optimal choice for \(a\). Describe how Rose could use the die to decide whether to play \(A\) or \(B\). The computer is to choose \(X , Y\) and \(Z\) with probabilities \(x , y\) and \(z\) respectively, where \(x + y + z = 1\). Graham is an AS student studying the D1 module. He wants to find the optimal choices for \(x , y\) and \(z\) and starts off by producing a pay-off matrix for the computer.
4. Graham produces the following pay-off matrix.

   3	1	0
   0	1	2

   Write down the pay-off matrix for the computer and explain what Graham did to its entries to get the values in his pay-off matrix.
5. Graham then sets up the linear programming problem: $$\begin{array} { l l } \text { maximise } & P = p - 4 , \\ \text { subject to } & p - 3 x - y \leqslant 0 , \\ & p - y - 2 z \leqslant 0 , \\ & x + y + z \leqslant 1 , \\ \text { and } & p \geqslant 0 , x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$ The Simplex algorithm is applied to the problem and gives \(x = 0.4\) and \(y = 0\). Find the values of \(z , p\) and \(P\) and interpret the solution in the context of the game. {}

1. The payoff matrix for player \(A\) in a two-person zero-sum game is shown below.

Find the optimal strategy for each player and the value of the game.

5. The payoff matrix for player \(X\) in a two-person zero-sum game is shown below.

1. Using a graphical method, find the optimal strategy for player \(X\).
2. Find the optimal strategy for player \(Y\).
3. Find the value of the game.

3. A two-person zero-sum game is represented by the payoff matrix for player \(A\) shown below.

1. Represent the expected payoffs to \(A\) against \(B\) 's strategies graphically and hence determine which strategy is not worth considering for player \(B\).
2. Find the best strategy for player \(A\) and the value of the game.

6. The payoff matrix for player \(A\) in a two-person zero-sum game is shown below.

1. Applying the dominance rule, explain, with justification, which strategy can be ignored by
   1. player \(A\),
   2. player \(B\).
2. For the reduced table, find the optimal strategy for
   1. player \(A\),
   2. player \(B\).
3. Find the value of the game.

3 In the pay-off matrix below, the entry in each cell is of the form \(( r , c )\), where \(r\) is the pay-off for the player on rows and \(c\) is the pay-off for the player on columns when they play that cell.

1. Show that the play-safe strategy for the player on columns is P .
2. Demonstrate that the game is not stable. The pay-off for the cell in row Y , column P is changed from \(( 5,2 )\) to \(( y , p )\), where \(y\) and \(p\) are real numbers.
3. What is the largest set of values \(A\), so that if \(y \in A\) then row Y is dominated by another row?
4. Explain why column P can never be redundant because of dominance.

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.

6 The pay-off matrix for a game between two players, Sumi and Vlad, is shown below. If Sumi plays A and Vlad plays X then Sumi gets X points and Vlad gets 1 point. Sumi You are given that cell ( \(\mathrm { A } , \mathrm { X }\) ) is a Nash Equilibrium solution.

1. Find the range of possible values of X .
2. Explain what the statement 'cell (A, X) is a Nash Equilibrium solution' means for each player.
3. Find a cell where each player gets their maximin pay-off. Suppose, instead, that the game can be converted to a zero-sum game.
4. Determine the optimal strategy for Sumi for the zero-sum game.

5 In each turn of a game between two players they simultaneously each choose a strategy and then calculate the points won using the table below. They are each trying to maximise the number of points that they win. In each cell the first value is the number of points won by player 1 and the second value is the number of points won by player 2 .

1. Find the play-safe strategy for each player.
2. Explain why player 2 would never choose strategy Z .
3. Find the Nash equilibrium solution(s) or show that there is no Nash equilibrium solution. Player 2 chooses strategy X with probability \(p\) and strategy Y with probability \(1 - p\). You are given that when player 1 chooses strategy A, the expected number of points won by each player is the same.
4. 1. Calculate the value of \(p\).
   2. Determine which player expects to win the greater number of points when player 1 chooses strategy B.

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.

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.

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.