Hard Further Maths Game theory Questions

Challenging, exam-style Further Maths Game theory questions with worked solutions. Stretch yourself on the hardest game-theory, mixed-strategy, dominance, linear-programming problems.

game-theorymixed-strategydominancelinear-programmingsaddle-pointstable-solution
Further Maths34 questionsStep-by-step solutions
Question 1
9 markschallenging
In a two-person zero-sum game the row player chooses a row and the column player chooses a column of the pay-off matrix M=(−21501−1312)M=\begin{pmatrix} -2 & 1 & 5 \\ 0 & 1 & -1 \\ 3 & 1 & 2 \end{pmatrix}, where each entry is the number of points the row player wins from the column player. This game is stable. At which position is the saddle point?
Show worked solution

Worked solution

  1. Write down the pay-off matrix

    M=(−21501−1312)M=\begin{pmatrix} -2 & 1 & 5 \\ 0 & 1 & -1 \\ 3 & 1 & 2 \end{pmatrix}

    Each entry is the row player's gain; the row player picks a row and the column player picks a column.

  2. Find the minimum entry of each row

    min⁡(row 1)=−2,min⁡(row 2)=−1,min⁡(row 3)=1\min(\text{row }1)=-2,\quad \min(\text{row }2)=-1,\quad \min(\text{row }3)=1

    The row minimum is the least the row player can gain by playing that row.

  3. Find the maximum entry of each column

    max⁡(col 1)=3,max⁡(col 2)=1,max⁡(col 3)=5\max(\text{col }1)=3,\quad \max(\text{col }2)=1,\quad \max(\text{col }3)=5

    The column maximum is the most the column player can lose by playing that column.

  4. Take the largest of the row minima

    max⁡imin⁡jMij=1\max_i\min_j M_{ij}=1

    This maximin value is what the row player can guarantee.

  5. Take the smallest of the column maxima

    min⁡jmax⁡iMij=1\min_j\max_i M_{ij}=1

    This minimax value is what the column player can hold the loss down to.

  6. Compare the maximin and the minimax

    max⁡imin⁡jMij=1=1=min⁡jmax⁡iMij\max_i\min_j M_{ij}=1=1=\min_j\max_i M_{ij}

    They are equal, so the game is stable and has a saddle point.

  7. Recall the pay-off convention

    Mij=row player’s gain when row i meets column jM_{ij}=\text{row player's gain when row }i\text{ meets column }j

    By convention the matrix records the row player's gains, so the column player's gains are the negatives of these numbers.

  8. Recall the maximin principle

    row player secures max⁡imin⁡jMij\text{row player secures }\max_i\min_j M_{ij}

    Choosing the row with the greatest row minimum guarantees the row player at least the maximin, whatever the column player does.

  9. Recall the minimax principle

    column player limits loss to min⁡jmax⁡iMij\text{column player limits loss to }\min_j\max_i M_{ij}

    Choosing the column with the least column maximum caps the column player's loss at the minimax.

  10. Recall the stability criterion

    stable  ⟺  max⁡imin⁡jMij=min⁡jmax⁡iMij\text{stable}\iff\max_i\min_j M_{ij}=\min_j\max_i M_{ij}

    A saddle point exists exactly when the maximin equals the minimax.

  11. Recall the minimax theorem

    every finite zero-sum game has a value\text{every finite zero-sum game has a value}

    Once mixed strategies are allowed the maximin equals the minimax, and this common number is the value of the game.

  12. Note that the players' interests are opposed

    row player maximises, column player minimises\text{row player maximises},\ \text{column player minimises}

    A single matrix suffices because one player's gain is the other's loss.

  13. Recall the definition of a dominated row

    row s dominated  ⟺  ∃r: Mrj≥Msj ∀j\text{row }s\text{ dominated}\iff\exists r:\ M_{rj}\ge M_{sj}\ \forall j

    A dominated row is never strictly better for the row player and may be deleted.

  14. Recall the definition of a dominated column

    column t dominated  ⟺  ∃u: Miu≤Mit ∀i\text{column }t\text{ dominated}\iff\exists u:\ M_{iu}\le M_{it}\ \forall i

    A dominated column is never strictly better for the column player and may be deleted.

  15. Note that deleting a dominated strategy leaves the value unchanged

    V(reduced)=V(original)V(\text{reduced})=V(\text{original})

    An optimal strategy never places any weight on a dominated row or column.

  16. Select the saddle-point position

    saddle at row 3, column 2, V=1\text{saddle at row }3\text{, column }2,\ V=1

    The saddle point sits in the maximin row and the minimax column.

Answer
(3,2)(3,2)
Question 2
9 markschallenging
In a two-person zero-sum game the row player chooses a row and the column player chooses a column of the pay-off matrix M=(236−4)M=\begin{pmatrix} 2 & 3 \\ 6 & -4 \end{pmatrix}, where each entry is the number of points the row player wins from the column player. Which one of the following statements about this game is correct?
Show worked solution

Worked solution

  1. Write down the pay-off matrix

    M=(236−4)M=\begin{pmatrix} 2 & 3 \\ 6 & -4 \end{pmatrix}

    Each entry is the row player's gain; the row player picks a row and the column player picks a column.

  2. Find the minimum entry of each row

    min⁡(row 1)=2,min⁡(row 2)=−4\min(\text{row }1)=2,\quad \min(\text{row }2)=-4

    The row minimum is the least the row player can gain by playing that row.

  3. Find the maximum entry of each column

    max⁡(col 1)=6,max⁡(col 2)=3\max(\text{col }1)=6,\quad \max(\text{col }2)=3

    The column maximum is the most the column player can lose by playing that column.

  4. Take the largest of the row minima

    max⁡imin⁡jMij=2\max_i\min_j M_{ij}=2

    This maximin value is what the row player can guarantee.

  5. Take the smallest of the column maxima

    min⁡jmax⁡iMij=3\min_j\max_i M_{ij}=3

    This minimax value is what the column player can hold the loss down to.

  6. Compare the maximin and the minimax

    max⁡imin⁡jMij=2<3=min⁡jmax⁡iMij\max_i\min_j M_{ij}=2<3=\min_j\max_i M_{ij}

    They differ, so the game has no saddle point and mixed strategies are needed.

  7. Recall the pay-off convention

    Mij=row player’s gain when row i meets column jM_{ij}=\text{row player's gain when row }i\text{ meets column }j

    By convention the matrix records the row player's gains, so the column player's gains are the negatives of these numbers.

  8. Recall the maximin principle

    row player secures max⁡imin⁡jMij\text{row player secures }\max_i\min_j M_{ij}

    Choosing the row with the greatest row minimum guarantees the row player at least the maximin, whatever the column player does.

  9. Recall the minimax principle

    column player limits loss to min⁡jmax⁡iMij\text{column player limits loss to }\min_j\max_i M_{ij}

    Choosing the column with the least column maximum caps the column player's loss at the minimax.

  10. Recall the stability criterion

    stable  ⟺  max⁡imin⁡jMij=min⁡jmax⁡iMij\text{stable}\iff\max_i\min_j M_{ij}=\min_j\max_i M_{ij}

    A saddle point exists exactly when the maximin equals the minimax.

  11. Recall the minimax theorem

    every finite zero-sum game has a value\text{every finite zero-sum game has a value}

    Once mixed strategies are allowed the maximin equals the minimax, and this common number is the value of the game.

  12. Note that the players' interests are opposed

    row player maximises, column player minimises\text{row player maximises},\ \text{column player minimises}

    A single matrix suffices because one player's gain is the other's loss.

  13. Recall the definition of a dominated row

    row s dominated  ⟺  ∃r: Mrj≥Msj ∀j\text{row }s\text{ dominated}\iff\exists r:\ M_{rj}\ge M_{sj}\ \forall j

    A dominated row is never strictly better for the row player and may be deleted.

  14. Recall the definition of a dominated column

    column t dominated  ⟺  ∃u: Miu≤Mit ∀i\text{column }t\text{ dominated}\iff\exists u:\ M_{iu}\le M_{it}\ \forall i

    A dominated column is never strictly better for the column player and may be deleted.

  15. Select the correct statement

    max⁡imin⁡jMij=2≠3=min⁡jmax⁡iMij\max_i\min_j M_{ij}=2\ne3=\min_j\max_i M_{ij}

    The maximin differs from the minimax, so there is no saddle point.

Answer
not stable\text{not stable}
Question 3
9 markschallenging
In a two-person zero-sum game the row player chooses a row and the column player chooses a column of the pay-off matrix M=(−214−1)M=\begin{pmatrix} -2 & 1 \\ 4 & -1 \end{pmatrix}, where each entry is the number of points the row player wins from the column player. The game has no saddle point. Which one of the following is the value of the game under optimal mixed play?
Show worked solution

Worked solution

  1. Write down the pay-off matrix

    M=(−214−1)M=\begin{pmatrix} -2 & 1 \\ 4 & -1 \end{pmatrix}

    Each entry is the row player's gain; the row player picks a row and the column player picks a column.

  2. Compare the maximin and the minimax

    max⁡imin⁡jMij=−1<1=min⁡jmax⁡iMij\max_i\min_j M_{ij}=-1<1=\min_j\max_i M_{ij}

    They differ, so the game has no saddle point and mixed strategies are needed.

  3. Let the row player mix over the surviving rows

    P(row 1)=p,P(row 2)=1−pP(\text{row }1)=p,\quad P(\text{row }2)=1-p

    The row player plays row 1 with probability pp and row 2 with probability 1−p1-p.

  4. Write the row player's expected pay-off against each column

    vs col 1: −2p+4(1−p)vs col 2: p−(1−p)\text{vs col }1:\ -2p+4(1-p)\quad\text{vs col }2:\ p-(1-p)

    Against column 1 the entries are -2 and 4; against column 2 they are 1 and -1.

  5. Set the two expected pay-offs equal and solve for pp

    −2p+4(1−p)=p−(1−p) ⇒ p=−5−8=58-2p+4(1-p)=p-(1-p)\ \Rightarrow\ p=\frac{-5}{-8}=\frac{5}{8}

    Equalising the pay-off against the two columns makes the column player indifferent, which is what an optimal mix does.

  6. Compute the value of the game

    V=−2p+4(1−p)=−2−8=14V=-2p+4(1-p)=\frac{-2}{-8}=\frac{1}{4}

    Substituting the optimal pp into the expected pay-off gives the value of the game.

  7. Recall the pay-off convention

    Mij=row player’s gain when row i meets column jM_{ij}=\text{row player's gain when row }i\text{ meets column }j

    By convention the matrix records the row player's gains, so the column player's gains are the negatives of these numbers.

  8. Recall the maximin principle

    row player secures max⁡imin⁡jMij\text{row player secures }\max_i\min_j M_{ij}

    Choosing the row with the greatest row minimum guarantees the row player at least the maximin, whatever the column player does.

  9. Recall the minimax principle

    column player limits loss to min⁡jmax⁡iMij\text{column player limits loss to }\min_j\max_i M_{ij}

    Choosing the column with the least column maximum caps the column player's loss at the minimax.

  10. Recall the stability criterion

    stable  ⟺  max⁡imin⁡jMij=min⁡jmax⁡iMij\text{stable}\iff\max_i\min_j M_{ij}=\min_j\max_i M_{ij}

    A saddle point exists exactly when the maximin equals the minimax.

  11. Recall the minimax theorem

    every finite zero-sum game has a value\text{every finite zero-sum game has a value}

    Once mixed strategies are allowed the maximin equals the minimax, and this common number is the value of the game.

  12. Note that the players' interests are opposed

    row player maximises, column player minimises\text{row player maximises},\ \text{column player minimises}

    A single matrix suffices because one player's gain is the other's loss.

  13. Recall the definition of a dominated row

    row s dominated  ⟺  ∃r: Mrj≥Msj ∀j\text{row }s\text{ dominated}\iff\exists r:\ M_{rj}\ge M_{sj}\ \forall j

    A dominated row is never strictly better for the row player and may be deleted.

  14. Recall the definition of a dominated column

    column t dominated  ⟺  ∃u: Miu≤Mit ∀i\text{column }t\text{ dominated}\iff\exists u:\ M_{iu}\le M_{it}\ \forall i

    A dominated column is never strictly better for the column player and may be deleted.

  15. Note that deleting a dominated strategy leaves the value unchanged

    V(reduced)=V(original)V(\text{reduced})=V(\text{original})

    An optimal strategy never places any weight on a dominated row or column.

  16. Recall how a mixed strategy is described

    a probability distribution over the pure strategies\text{a probability distribution over the pure strategies}

    Each pure strategy is played with some probability and the probabilities sum to one.

  17. Select the value of the game

    V=−2−8=14V=\frac{-2}{-8}=\frac{1}{4}

    Only this value equalises the expected pay-off against each of the opponent's pure strategies.

Answer
V=14V=\frac{1}{4}
Question 4
9 markschallenging
In a two-person zero-sum game the row player chooses a row and the column player chooses a column of the pay-off matrix M=(0550)M=\begin{pmatrix} 0 & 5 \\ 5 & 0 \end{pmatrix}, where each entry is the number of points the row player wins from the column player. The game has no saddle point. Which one of the following is the value of the game under optimal mixed play?
Show worked solution

Worked solution

  1. Write down the pay-off matrix

    M=(0550)M=\begin{pmatrix} 0 & 5 \\ 5 & 0 \end{pmatrix}

    Each entry is the row player's gain; the row player picks a row and the column player picks a column.

  2. Compare the maximin and the minimax

    max⁡imin⁡jMij=0<5=min⁡jmax⁡iMij\max_i\min_j M_{ij}=0<5=\min_j\max_i M_{ij}

    They differ, so the game has no saddle point and mixed strategies are needed.

  3. Let the row player mix over the surviving rows

    P(row 1)=p,P(row 2)=1−pP(\text{row }1)=p,\quad P(\text{row }2)=1-p

    The row player plays row 1 with probability pp and row 2 with probability 1−p1-p.

  4. Write the row player's expected pay-off against each column

    vs col 1: 0p+5(1−p)vs col 2: 5p\text{vs col }1:\ 0p+5(1-p)\quad\text{vs col }2:\ 5p

    Against column 1 the entries are 0 and 5; against column 2 they are 5 and 0.

  5. Set the two expected pay-offs equal and solve for pp

    0p+5(1−p)=5p ⇒ p=−5−10=120p+5(1-p)=5p\ \Rightarrow\ p=\frac{-5}{-10}=\frac{1}{2}

    Equalising the pay-off against the two columns makes the column player indifferent, which is what an optimal mix does.

  6. Compute the value of the game

    V=0p+5(1−p)=−25−10=52V=0p+5(1-p)=\frac{-25}{-10}=\frac{5}{2}

    Substituting the optimal pp into the expected pay-off gives the value of the game.

  7. Recall the pay-off convention

    Mij=row player’s gain when row i meets column jM_{ij}=\text{row player's gain when row }i\text{ meets column }j

    By convention the matrix records the row player's gains, so the column player's gains are the negatives of these numbers.

  8. Recall the maximin principle

    row player secures max⁡imin⁡jMij\text{row player secures }\max_i\min_j M_{ij}

    Choosing the row with the greatest row minimum guarantees the row player at least the maximin, whatever the column player does.

  9. Recall the minimax principle

    column player limits loss to min⁡jmax⁡iMij\text{column player limits loss to }\min_j\max_i M_{ij}

    Choosing the column with the least column maximum caps the column player's loss at the minimax.

  10. Recall the stability criterion

    stable  ⟺  max⁡imin⁡jMij=min⁡jmax⁡iMij\text{stable}\iff\max_i\min_j M_{ij}=\min_j\max_i M_{ij}

    A saddle point exists exactly when the maximin equals the minimax.

  11. Recall the minimax theorem

    every finite zero-sum game has a value\text{every finite zero-sum game has a value}

    Once mixed strategies are allowed the maximin equals the minimax, and this common number is the value of the game.

  12. Note that the players' interests are opposed

    row player maximises, column player minimises\text{row player maximises},\ \text{column player minimises}

    A single matrix suffices because one player's gain is the other's loss.

  13. Recall the definition of a dominated row

    row s dominated  ⟺  ∃r: Mrj≥Msj ∀j\text{row }s\text{ dominated}\iff\exists r:\ M_{rj}\ge M_{sj}\ \forall j

    A dominated row is never strictly better for the row player and may be deleted.

  14. Recall the definition of a dominated column

    column t dominated  ⟺  ∃u: Miu≤Mit ∀i\text{column }t\text{ dominated}\iff\exists u:\ M_{iu}\le M_{it}\ \forall i

    A dominated column is never strictly better for the column player and may be deleted.

  15. Note that deleting a dominated strategy leaves the value unchanged

    V(reduced)=V(original)V(\text{reduced})=V(\text{original})

    An optimal strategy never places any weight on a dominated row or column.

  16. Select the value of the game

    V=−25−10=52V=\frac{-25}{-10}=\frac{5}{2}

    Only this value equalises the expected pay-off against each of the opponent's pure strategies.

Answer
V=52V=\frac{5}{2}
Question 5
9 markschallenging
In a two-person zero-sum game the row player chooses a row and the column player chooses a column of the pay-off matrix M=(−1−425−1−105−3)M=\begin{pmatrix} -1 & -4 & 2 \\ 5 & -1 & -1 \\ 0 & 5 & -3 \end{pmatrix}, where each entry is the number of points the row player wins from the column player. To find the row player's optimal strategy by linear programming the constant 55 is added to every entry (so every entry is positive and the value V>0V>0); writing xi=pi/Vx_i=p_i/V the row player minimises x1+⋯+x3x_1+\cdots+x_3 subject to one ≥\ge constraint per column. Which one of the following is the constraint arising from column 33?
Show worked solution

Worked solution

  1. Write down the pay-off matrix

    M=(−1−425−1−105−3)M=\begin{pmatrix} -1 & -4 & 2 \\ 5 & -1 & -1 \\ 0 & 5 & -3 \end{pmatrix}

    Each entry is the row player's gain; the row player picks a row and the column player picks a column.

  2. Add the constant to make every entry positive

    M′=(41710445102)M'=\begin{pmatrix} 4 & 1 & 7 \\ 10 & 4 & 4 \\ 5 & 10 & 2 \end{pmatrix}

    Every entry of M′=M+5M'=M+5 is positive, so the value of the shifted game is positive.

  3. Set up the row player's linear programme

    minimise x1+⋯+x3,xi=piV\text{minimise }x_1+\cdots+x_3,\quad x_i=\frac{p_i}{V}

    Dividing the security inequalities by V>0V>0 turns the game into a linear programme in the xix_i.

  4. Write the constraint for column 3

    7x1+4x2+2x3≥17x_{1}+4x_{2}+2x_{3}\ge1

    The constraint for a column collects that column's (shifted) entries as the coefficients of the xix_i.

  5. Recall the pay-off convention

    Mij=row player’s gain when row i meets column jM_{ij}=\text{row player's gain when row }i\text{ meets column }j

    By convention the matrix records the row player's gains, so the column player's gains are the negatives of these numbers.

  6. Recall the maximin principle

    row player secures max⁡imin⁡jMij\text{row player secures }\max_i\min_j M_{ij}

    Choosing the row with the greatest row minimum guarantees the row player at least the maximin, whatever the column player does.

  7. Recall the minimax principle

    column player limits loss to min⁡jmax⁡iMij\text{column player limits loss to }\min_j\max_i M_{ij}

    Choosing the column with the least column maximum caps the column player's loss at the minimax.

  8. Recall the stability criterion

    stable  ⟺  max⁡imin⁡jMij=min⁡jmax⁡iMij\text{stable}\iff\max_i\min_j M_{ij}=\min_j\max_i M_{ij}

    A saddle point exists exactly when the maximin equals the minimax.

  9. Recall the minimax theorem

    every finite zero-sum game has a value\text{every finite zero-sum game has a value}

    Once mixed strategies are allowed the maximin equals the minimax, and this common number is the value of the game.

  10. Note that the players' interests are opposed

    row player maximises, column player minimises\text{row player maximises},\ \text{column player minimises}

    A single matrix suffices because one player's gain is the other's loss.

  11. Recall the definition of a dominated row

    row s dominated  ⟺  ∃r: Mrj≥Msj ∀j\text{row }s\text{ dominated}\iff\exists r:\ M_{rj}\ge M_{sj}\ \forall j

    A dominated row is never strictly better for the row player and may be deleted.

  12. Recall the definition of a dominated column

    column t dominated  ⟺  ∃u: Miu≤Mit ∀i\text{column }t\text{ dominated}\iff\exists u:\ M_{iu}\le M_{it}\ \forall i

    A dominated column is never strictly better for the column player and may be deleted.

  13. Note that deleting a dominated strategy leaves the value unchanged

    V(reduced)=V(original)V(\text{reduced})=V(\text{original})

    An optimal strategy never places any weight on a dominated row or column.

  14. Recall how a mixed strategy is described

    a probability distribution over the pure strategies\text{a probability distribution over the pure strategies}

    Each pure strategy is played with some probability and the probabilities sum to one.

  15. Select the constraint from column 3

    7x1+4x2+2x3≥17x_{1}+4x_{2}+2x_{3}\ge1

    Each column of M′M' gives one ≥1\ge 1 constraint of the LP.

Answer
7x1+4x2+2x3≥17x_{1}+4x_{2}+2x_{3}\ge1

Unlock 29 more Game theory questions

Create a free account to work through every Further Maths Game theory question with instant step-by-step worked solutions, progress tracking and interactive lessons.

  • Full worked solutions for every question
  • Interactive lessons and instant feedback
  • Track your mastery across every topic
Create a Free Account

No card required · Free forever

More Game theory practice

Practice QuestionsWorked Solutions

Related Decision Maths topics

AlgorithmsAllocation (assignment)Critical path analysisDecision analysisDynamic programmingFlows in networks