Game theory LP formulation

7. A two-person zero-sum game is represented by the following pay-off matrix for player A. Formulate the game as a linear programming problem for player A. Write the constraints as inequalities. Define your variables clearly.
(Total 7 marks)

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 to this game.
2. Find the best strategy for player A.

6. 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.
2. Formulate the game as a linear programming problem for player A. Define your variables clearly. Write the constraints as equations.
3. Write down an initial simplex tableau, making your variables clear.

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.

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

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.

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.

1. 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.

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 \(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{2}{*}{A} & \text{I} & -2 & 3 & -1
& \text{II} & 4 & -5 & 2
\end{array}

1. Formulate this information as a linear programming problem, the solution to which will give the optimal strategy for player \(B\). [7 marks]
2. By solving this linear programming problem, find the optimal strategy for player \(B\) and the value of the game. [14 marks]

[21 marks]