Game theory to LP

A question is this type if and only if it involves converting a two-person zero-sum game into a linear programming problem to find optimal mixed strategies.

2 questions · Challenging +1.5

Sort by: Default | Easiest first | Hardest first
Edexcel FD2 2023 June Q8
17 marks Challenging +1.8
8. A two-person zero-sum game is represented by the pay-off matrix for player A shown below. \section*{Player B} Player A
\cline { 2 - 4 } \multicolumn{1}{c|}{}Option XOption YOption Z
Option Q- 325
Option R2- 10
Option S4- 2- 1
Option T- 402
  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.
    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.
AQA Further Paper 3 Discrete 2024 June Q9
6 marks Challenging +1.2
Janet and Samantha play a zero-sum game. The game is represented by the following pay-off matrix for Janet. Samantha
Strategy\(S_1\)\(S_2\)\(S_3\)
\multirow{4}{*}{Janet}\(J_1\)276
\(J_2\)551
\(J_3\)438
\(J_4\)164
  1. Explain why Janet should never play strategy \(J_4\) [1 mark]
  2. Janet wants to maximise her winnings from the game. She defines the following variables. \(p_1 = \) the probability of Janet playing strategy \(J_1\) \(p_2 = \) the probability of Janet playing strategy \(J_2\) \(p_3 = \) the probability of Janet playing strategy \(J_3\) \(v = \) the value of the game for Janet Janet then formulates her situation as the following linear programming problem. Maximise \(P = v\) subject to \(2p_1 + 5p_2 + 4p_3 \geq v\) \(7p_1 + 5p_2 + 3p_3 \geq v\) \(6p_1 + p_2 + 8p_3 \geq v\) and \(p_1 + p_2 + p_3 \leq 1\) \(p_1, p_2, p_3 \geq 0\)
    1. Complete the initial Simplex tableau for Janet's situation in the grid below. [2 marks]
      \(P\)\(v\)\(p_1\)\(p_2\)\(p_3\)value
    2. Hence, perform one iteration of the Simplex algorithm, showing your answer on the grid below. [2 marks]
      \(P\)\(v\)\(p_1\)\(p_2\)\(p_3\)value
  3. Further iterations of the Simplex algorithm are performed until an optimal solution is reached. The grid below shows part of the final Simplex tableau.
    \(p_1\)\(p_2\)value
    10\(\frac{1}{12}\)
    01\(\frac{1}{2}\)
    Find the probability of Janet playing strategy \(J_3\) when she is playing to maximise her winnings from the game. [1 mark]