7.08b Dominance: reduce pay-off matrix

3 Basil runs a luxury hotel. He advertises summer breaks at the hotel in several different magazines. Last summer he won the opportunity to place a full-page colour advertisement in one of four magazines for the price of the usual smaller advertisement. The table shows the expected additional weekly income, in \(\pounds\), for each of the magazines for each possible type of weather. Basil wanted to maximise the additional income.

1. Explain carefully why no magazine choice can be rejected using a dominance argument.
2. Treating the choice of strategies as being a zero-sum game, find Basil's play-safe strategy and show that the game is unstable.
3. Calculate the expected additional weekly income for each magazine choice if the weather is rainy with probability 0.4 and sunny with probability 0.6 . Suppose that the weather is rainy with probability \(p\) and sunny with probability \(1 - p\).
4. Which magazine should Basil choose if the weather is certain to be sunny ( \(p = 0\) ), and which should he choose if the weather is certain to be rainy ( \(p = 1\) )?
5. Graph the expected additional weekly income against \(p\). Hence advise Basil on which magazine he should choose for the different possible ranges of values of \(p\).

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.

2. The payoff matrix for player \(A\) in a two-person zero-sum game with value \(V\) is shown below. Formulate this information as a linear programming problem, the solution to which will give the optimal strategy for player \(B\).

1. Rewrite the matrix as necessary and state the new value of the game, \(v\), in terms of \(V\).
2. Define your decision variables.
3. Write down the objective function in terms of your decision variables.
4. Write down the constraints.

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.

6 Drew and Emma play a game in which they each choose a strategy and then use the tables below to determine the pay-off that each receives.

1. Convert the game into a zero-sum game, giving the pay-off matrix for Drew.
2. Determine the optimal mixed strategy for Drew.
3. Determine the optimal mixed strategy for Emma.

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.

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.

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.

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.

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.

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.