Dominance and mixed strategies by the Simplex algorithm

Dominance and mixed strategies by the Simplex algorithm Test

Spec 5.5 · Edexcel A-Level Further Maths: Subtopic test

Studying this course? Keep your progress in one place.

Two ways to do this test

Question by question

One question at a time. Each answer is marked the moment you hand it in, so you learn as you go. Drago helps if you get stuck. All 10 questions, or just 5.

Exam mode

The whole paper in one go, timed like the real exam. Nothing is marked until you hand it in, then you get every mark explained.

10 questions, 27 marks

Edexcel A-Level Further Maths

Dominance and mixed strategies by the Simplex algorithm

Total 27 marks

Name

Class

Date

  1. 1
    Rose and Colin play a zero-sum game, with Rose choosing the rows. Rose's pay-off matrix is (357426215)\begin{pmatrix} 3 & 5 & 7 \\ 4 & 2 & 6 \\ 2 & 1 & 5 \end{pmatrix}.
    (a)
    Which row can be removed because it is dominated?
    [1 mark]
    • ARow 1
    • BRow 2
    • CRow 3
    • DNone of the rows
    (b)
    Which column can be removed because it is dominated?
    [1 mark]
    • AColumn 3
    • BColumn 2
    • CColumn 1
    • DNone of the columns
    (c)
    Use dominance to reduce the game to a 2×22\times2 game and find Rose's optimal strategy.
    [2 marks]

    Total for question 1: 4 marks

  2. 2
    Rose and Colin play a zero-sum game, with Rose choosing the rows and Colin choosing column jj with probability qjq_j. Rose's pay-off matrix is (−210−11−3)\begin{pmatrix} -2 & 1 \\ 0 & -1 \\ 1 & -3 \end{pmatrix}. To use the Simplex algorithm, a constant is added to every entry of the matrix.
    (a)
    What is the smallest integer that can be added to every entry so that all entries are positive?
    [1 mark]
    • A33
    • B−3-3
    • C22
    • D44
    (b)
    After adding 44 to every entry, Colin's Simplex problem has optimal value P=27P=\frac27. What is the value of the original game to Rose?
    [1 mark]
    • A72\frac72
    • B−12-\frac12
    • C12\frac12
    • D27\frac27
    (c)
    After adding 44 to every entry, formulate Colin's problem as a linear programme for the Simplex algorithm. Define y1y_1 and y2y_2 in terms of VV, the value of the adjusted game.
    [2 marks]

    Total for question 2: 4 marks

  3. 3
    Colin is the column player in a zero-sum game. After a constant 33 has been added to every entry, Rose's pay-off matrix is (264512)\begin{pmatrix} 2 & 6 & 4 \\ 5 & 1 & 2 \end{pmatrix}. Colin plays column jj with probability qjq_j and the value of the adjusted game is VV. Writing yj=qjVy_j=\frac{q_j}{V}, Colin's problem is: maximise P=y1+y2+y3P=y_1+y_2+y_3 subject to 2y1+6y2+4y3≤12y_1+6y_2+4y_3\le1, 5y1+y2+2y3≤15y_1+y_2+2y_3\le1 and y1,y2,y3≥0y_1,y_2,y_3\ge0. Slack variables rr and ss are added to the first and second constraints. The Simplex algorithm gives the optimal solution y1=18y_1=\frac18, y2=0y_2=0, y3=316y_3=\frac{3}{16}, P=516P=\frac{5}{16}.
    (a)
    Set up the initial Simplex tableau. Choosing the y1y_1 column as the pivot column, carry out one iteration and state the pivot element and the value of PP after it.
    [3 marks]
    (b)
    Use the optimal solution to find Colin's optimal mixed strategy and the value of the original game to Rose.
    [4 marks]

    Total for question 3: 7 marks

  4. 4
    Two phone networks, Zed and Yonder, each choose a pricing plan. The pay-off matrix shows Zed's gain in market share (percentage points), where Zed chooses between three plans (the rows) and Yonder chooses between four (the columns): (1−230−1324−2−31−1)\begin{pmatrix} 1 & -2 & 3 & 0 \\ -1 & 3 & 2 & 4 \\ -2 & -3 & 1 & -1 \end{pmatrix}. Every point gained by Zed is lost by Yonder.
    (a)
    Use dominance arguments to reduce the game to a 2×22\times2 game, justifying each deletion, and show that the reduced game has no stable solution.
    [6 marks]
    (b)
    Find the optimal mixed strategy for each network and the value of the game.
    [6 marks]

    Total for question 4: 12 marks

End of questions

Subtopic tests