Dominance and mixed strategies by the Simplex algorithm

Dominance and mixed strategies by the Simplex algorithm

Spec 5.5 · Edexcel A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • A dominated strategy is never better than another, so delete it and give it probability 0.
  • Rose's row is dominated if every entry is ≤\le another row's; Colin's column is dominated if every entry is ≥\ge another column's.
  • To use Simplex, make every entry positive (add kk), let yj=qjVy_j=\frac{q_j}{V} and maximise P=∑yjP=\sum y_j subject to constraints ≤1\le1.
  • Read back: V=1PV=\frac1P, qj=Vyjq_j=Vy_j, Rose's probabilities from the profit row slack entries times VV.
  • Value of the original game =V−k=V-k.

Dominance

A strategy is dominated if another is at least as good whatever the opponent does. It would never be chosen, so delete it.

A strategy is dominated if another strategy is at least as good whatever the opponent does, so it would never be chosen in an optimal strategy.

Dominated rows and columns can be deleted before looking for a solution. Dominated strategies are played with probability 0.

Colin wants Rose's pay-off to be small, so for columns the dominated one is the column with the larger entries.

  1. 1

    Compare two rows or columns

    entry by entry

  2. 2

    Is one at least as good everywhere?

    Rose: every entry ≥; Colin: every entry ≤

  3. 3

    Delete the dominated one

    it would never be chosen

  4. 4

    Probability 0

    the deleted strategy is played with probability 0

Deleting dominated strategies

Rose (rows)

Dominated if:
every entry of row ii is ≤\le row kk
Why:
Rose can always do at least as well with row kk

Colin (columns)

Dominated if:
every entry of column jj is ≥\ge column ll
Why:
Colin can always make Rose's pay-off no bigger with column ll

Worked example

Reduce (528364213)\begin{pmatrix}5&2&8\\3&6&4\\2&1&3\end{pmatrix} by dominance.

Rose's pay-off matrix has rows (4,1)(4, 1), (2,3)(2, 3) and (1,0)(1, 0). Which row is dominated?

The reduced game

Check for a stable solution, or solve the smaller game. Deleting can be repeated, and every deleted strategy gets probability 0.

After deleting dominated strategies, check for a stable solution (maximin == minimax) and otherwise solve the smaller game, for instance the 2×22\times2 case by equating expected pay-offs.

Deleting can be repeated: a deletion may create new dominance.

State every deleted strategy with its reason, and give probability 0 to each in the final strategy.

For (5236)\begin{pmatrix}5&2\\3&6\end{pmatrix}, Rose plays row 1 with probability pp: her expected pay-off is 3+2p3+2p against column 1 and 6−4p6-4p against column 2.

0.10.20.30.40.50.60.70.80.911234567xy(0.5, 4)Against column 1: 3 + 2pAgainst column 2: 6 − 4p
The lines meet at p = 0.5, value 4.

Worked example

Solve (5236)\begin{pmatrix}5&2\\3&6\end{pmatrix} for both players.

In the 2×22\times2 game above, what is the probability qq that Colin plays column 1?

Converting to a linear programme

Make every entry positive, write Rose's expected gain against each row as at most VV, divide by VV and maximise P=∑yjP=\sum y_j.

Larger games can be solved with Simplex. The method below is for Colin, who chooses the columns.

Let Colin play column jj with probability qjq_j. Rose's expected gain against each row must be at most VV. Divide by VV and write yj=qjVy_j=\frac{q_j}{V}: each constraint becomes ∑jaijyj≤1\sum_j a_{ij}y_j\le1, and ∑yj=1V\sum y_j=\frac1V.

Colin wants VV as small as possible, so he maximises P=∑yjP=\sum y_j with yj≥0y_j\ge0.

For Rose, write the game from Colin's view (negate and transpose), then add kk.

  1. 1

    Add a constant k

    make every entry positive so V>0V>0; subtract kk at the end

  2. 2

    Write the constraints

    Rose's expected gain against each row is at most V

  3. 3

    Divide by V

    let yj=qj/Vy_j=q_j/V, so each constraint is at most 1

  4. 4

    Maximise P

    P=∑yj=1/VP=\sum y_j=1/V, with yj≥0y_j\ge0

Converting a game to a linear programme

Worked example

Set up the linear programme for Colin in (5236)\begin{pmatrix}5&2\\3&6\end{pmatrix}.

Why must every entry be made positive before forming the linear programme?

Solving by Simplex

Add slack variables and use the profit row P−y1−y2=0P-y_1-y_2=0. Pivot until the profit row has no negative entries.

Add slack variables rr, ss and form the initial tableau with profit row P−y1−y2=0P-y_1-y_2=0. Repeat these steps.

  • The pivot column has the most negative entry in the profit row.
  • The pivot row has the smallest non-negative ratio (value ÷\div positive entry).
  • Divide the pivot row by the pivot, then make the rest of the pivot column 0.

Stop when the profit row has no negative entries. Check that basic variables stay non-negative and PP increases each time.

  1. 1

    Pivot column

    most negative entry in the profit row

  2. 2

    Ratio test

    smallest non-negative value ÷ entry gives the pivot row

  3. 3

    Row operations

    make the pivot 1 and the rest of its column 0

  4. 4

    Check the profit row

    any negative entries left? If so, repeat

Then back to step 1

One iteration of the Simplex algorithm

Row y₁

y₁:
1
y₂:
0
r:
1/4
s:
-1/12
Value:
1/6

Row y₂

y₁:
0
y₂:
1
r:
-1/8
s:
5/24
Value:
1/12

Row P

y₁:
0
y₂:
0
r:
1/8
s:
1/8
Value:
1/4

Worked example

Maximise P=y1+y2P=y_1+y_2 subject to 5y1+2y2≤15y_1+2y_2\le1 and 3y1+6y2≤13y_1+6y_2\le1.

In the ratio test, how do you choose the pivot row?

Reading the solution

V=1PV=\frac1P, qj=Vyjq_j=Vy_j, Rose's probabilities are the slack entries times VV, and the original value is V−kV-k.

Once the profit row has no negative entries, read the solution from the tableau.

  1. V=1PV=\frac1P, the value of the adjusted game.
  2. qj=V yjq_j=V\,y_j for each column, with qj=0q_j=0 if yjy_j is not basic.
  3. Value of the original game =V−k=V-k.
  4. Rose's probabilities: the slack-column entries of the profit row, each multiplied by VV.

A game question wants probabilities and the value of the original game, not just PP or the yjy_j.

  1. 1

    Value of adjusted game

    V = 1 ÷ P

  2. 2

    Colin's probabilities

    q_j = V × y_j, with 0 if y_j is not basic

  3. 3

    Rose's probabilities

    slack entries of the profit row, each × V

  4. 4

    Value of original game

    V − k

Reading the final tableau
  • Adjusted valueV=1PV=\dfrac1P
  • Probabilitiesqj=V yjq_j=V\,y_j
  • Original valueV−kV-k

Worked example

Read the solution from the tableau above, where P=14P=\frac14, y1=16y_1=\frac16, y2=112y_2=\frac1{12} and the slack entries are 18\frac18 and 18\frac18.

You added k=3k=3 to every entry and the Simplex solution gives V=7V=7. What is the value of the original game?

Try an exam question

Rose's pay-off matrix is (316245102)\begin{pmatrix}3&1&6\\2&4&5\\1&0&2\end{pmatrix}. Use dominance to reduce the game, then find Rose's optimal strategy and the value of the game.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Which row can be removed because it is dominated?

1 mark, marked against the mark scheme

Revision notes