7.08a Pay-off matrix: zero-sum games

7

1. 1. Write down the pay-off matrix for Bex. 7
   2. Explain why the pay-off matrix for Bex can be written as

3 Summer and Haf play a zero-sum game. The pay-off matrix for the game is shown below. Haf 3

1. Show that the game has a stable solution.
   3
2. (i) State the value of the game for Summer. 3 (b) (ii) State the play-safe strategy for each player.

7 Kez and Lui play a zero-sum game. The game does not have a stable solution. The game is represented by the following pay-off matrix for Kez. 7

1. State, with a reason, why Kez should never play strategy \(\mathbf { K } _ { \mathbf { 2 } }\) 7
2. \(\quad\) Kez and Lui play the game 20 times.
   Kez plays their optimal mixed strategy.
   Find the expected number of times that Kez will play strategy \(\mathbf { K } _ { \mathbf { 3 } }\) Fully justify your answer.

6 Xander and Yvonne are playing a zero-sum game. The game is represented by the pay-off matrix for Xander. \begin{table}[h] \end{table} 6

1. Show that the game has a stable solution.
   6
2. State the play-safe strategy for each player. Play-safe strategy for Xander is \(\_\_\_\_\) Play-safe strategy for Yvonne is \(\_\_\_\_\) 6
3. The game that Xander and Yvonne are playing is part of a marbles challenge. The pay-off matrix values represent the number of marbles gained by Xander in each game. In the challenge, the game is repeated until one player has 24 marbles more than the other player. Explain why Xander and Yvonne must play at least 3 games to complete the challenge.

6 Victoria and Albert play a zero-sum game. The game is represented by the following pay-off matrix for Victoria. 6

1. Find the play-safe strategies for each player.
   6
2. State, with a reason, the strategy that Albert should never play.
   6
3. (i) Determine an optimal mixed strategy for Victoria.
   [0pt] [5 marks]
   6 (c) (ii) Find the value of the game for Victoria.
   6 (c) (iii) State an assumption that must made in order that your answer for part (c)(ii) is the maximum expected pay-off that Victoria can achieve.

8 Daryl and Clare play a zero-sum game. The game is represented by the following pay-off matrix for Daryl. Clare

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

1. Explain, with justification, why this matrix may be reduced to a \(3 \times 3\) matrix by removing option S from player A's choices.
2. Verify that there is no stable solution to the reduced game. Player A intends to make a random choice between options \(\mathrm { Q } , \mathrm { R }\) and T , choosing option Q with probability \(p _ { 1 }\), option R 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 linear programme, writing the constraints as inequalities. Maximise \(P = V\), where \(V =\) the value of original game + 3 $$\begin{aligned} \text { subject to } & V \leqslant 4 p _ { 1 } + 7 p _ { 2 } + 6 p _ { 3 } \\ & V \leqslant 8 p _ { 1 } + p _ { 3 } \\ & V \leqslant 6 p _ { 1 } + 4 p _ { 2 } + 3 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}$$
3. Explain why \(V\) cannot exceed any of the following expressions $$4 p _ { 1 } + 7 p _ { 2 } + 6 p _ { 3 } \quad 8 p _ { 1 } + p _ { 3 } \quad 6 p _ { 1 } + 4 p _ { 2 } + 3 p _ { 3 }$$
4. Explain why it is necessary to use the constraint \(p _ { 1 } + p _ { 2 } + p _ { 3 } \leqslant 1\) The Simplex algorithm is used to solve the linear programming problem.
   Given that the optimal value of \(p _ { 1 } = \frac { 7 } { 11 }\) and the optimal value of \(p _ { 3 } = 0\)
5. calculate the value of the game to player A .
   (3) Player B 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 }\)
6. Determine the optimal strategy for player B, making your working clear.

7. A two person zero-sum game is represented by the pay-off matrix for player A shown above. It is given that \(k\) is an integer.

1. Show that Q is the play-safe option for player A regardless of the value of \(k\). Given that Z is the play-safe option for player B ,
2. determine the range of possible values of \(k\). You must make your working clear.
3. Explain why player B should never play option X. 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 find the optimal values of \(p _ { 1 } , p _ { 2 }\) and \(p _ { 3 }\) using the Simplex algorithm.
   Given that \(k > - 4\), player A formulates the following objective function for the corresponding linear program. $$\text { Maximise } P = V \text {, where } V = \text { the value of the original game } + 4$$
4. 1. Formulate the constraints of the linear programming problem for player A. You should write the constraints as equations.
   2. Write down an initial Simplex tableau, making your variables clear. The Simplex algorithm is used to solve the linear programming problem. It is given that in the final Simplex tableau the optimal value of \(p _ { 1 } = \frac { 7 } { 37 }\), the optimal value of \(p _ { 2 } = \frac { 17 } { 37 }\) and all the slack variables are zero.
5. Determine the value of \(k\), making your method clear.

In game theory explain what is meant by

1. zero-sum game, [2]
2. saddle point. [2]

(Total 4 marks)

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

	\(B\) plays 1	\(B\) plays 2	\(B\) plays 3
\(A\) plays 1	5	7	2
\(A\) plays 2	3	8	4
\(A\) plays 3	6	4	9

1. Formulate the game as a linear programming problem for player \(A\), writing the constraints as equalities and clearly defining your variables. [5]
2. Explain why it is necessary to use the simplex algorithm to solve this game theory problem. [1]
3. Write down an initial simplex tableau making your variables clear. [2]
4. Perform two complete iterations of the simplex algorithm, indicating your pivots and stating the row operations that you use. [8]

(Total 16 marks)

The payoff matrix for player A in a two-person zero-sum game with value V is shown below.

	B
	I	II	III
\multirow{3}{*}{A}	I	6	\(-4\)	\(-1\)
	II	\(-2\)	5	3
	III	5	1	\(-3\)

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 marks]
2. Define your decision variables. [2 marks]
3. Write down the objective function in terms of your decision variables. [2 marks]
4. Write down the constraints. [2 marks]

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

	Y
	\(Y_1\)	\(Y_2\)
\multirow{2}{*}{X}	\(X_1\)	\(-2\)	4
	\(X_2\)	6	\(-1\)

1. Explain why the game does not have a saddle point. [3 marks]
2. Find the optimal strategy for
   1. player X, [8 marks]
   2. player Y.
3. Find the value of the game. [2 marks]

The payoff matrix for player \(A\) in a two-person zero-sum game is shown below. \begin{array}{c|c|c|c|c} & & \multicolumn{3}{c}{B}
& & \text{I} & \text{II} & \text{III}
\hline \multirow{3}{*}{A} & \text{I} & -3 & 4 & 0
& \text{II} & 2 & 2 & 1
& \text{III} & 3 & -2 & -1
\end{array} Find the optimal strategy for each player and the value of the game. [4 marks]

Ben and Jadzia play a zero-sum game. The game is represented by the following pay-off matrix for Ben.

	Jadzia
Strategy	X	Y	Z
A	-3	2	3
Ben B	6	0	-4
C	7	-1	1
D	6	-2	1

1. State, with a reason, which strategy Ben should never play. [1 mark]
2. Determine whether or not the game has a stable solution. Fully justify your answer. [3 marks]
3. Ben knows that Jadzia will always play her play-safe strategy. Explain how Ben can maximise his expected pay-off. [2 marks]

Daniel and Jackson play a zero-sum game. The game is represented by the following pay-off matrix for Daniel. Jackson

	Strategy	W	X	Y	Z
\multirow{4}{*}{Daniel}	A	3	\(-2\)	1	4
	B	5	1	\(-4\)	1
	C	2	\(-1\)	1	2
	D	\(-3\)	0	2	\(-1\)

Neither player has any strategies which can be ignored due to dominance.

1. Prove that the game does not have a stable solution. Fully justify your answer. [3 marks]
2. Determine the play-safe strategy for each player. [1 mark] Play-safe strategy for Daniel _______________________________________________ Play-safe strategy for Jackson ______________________________________________

Each day Alix and Ben play a game. They each choose a card and use the table below to find the number of points they win. The table shows the cards available to each player. The entries in the cells are of the form \((a, b)\), where \(a =\) points won by Alix and \(b =\) points won by Ben. Each is trying to maximise the points they win.

1. Explain why the table cannot be reduced through dominance no matter what values \(x\) and \(y\) have. [2]
2. Show that the game is not stable no matter what values \(x\) and \(y\) have. [2]
3. Find the Nash equilibrium solutions for the various values that \(x\) and \(y\) can have. [4]

The table shows the pay-off matrix for player \(A\) in a two-person zero-sum game between \(A\) and \(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. [3]
2. If player \(B\) knows that player \(A\) will use their play-safe strategy, which strategy should player \(B\) use? [1]
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. [2]
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. [2]
5. Show that the zero-sum game with the new pay-off value found in part (iv) has a Nash equilibrium and explain what this means for the players. [3]