Dominance and mixed strategies by the Simplex algorithm
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 another row's; Colin's column is dominated if every entry is another column's.
- To use Simplex, make every entry positive (add ), let and maximise subject to constraints .
- Read back: , , Rose's probabilities from the profit row slack entries times .
- Value of the original game .
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
Compare two rows or columns
entry by entry
- 2
Is one at least as good everywhere?
Rose: every entry ≥; Colin: every entry ≤
- 3
Delete the dominated one
it would never be chosen
- 4
Probability 0
the deleted strategy is played with probability 0
| Rose (rows) | Colin (columns) | |
|---|---|---|
| Dominated if | every entry of row is row | every entry of column is column |
| Why | Rose can always do at least as well with row | Colin can always make Rose's pay-off no bigger with column |
Rose (rows)
- Dominated if:
- every entry of row is row
- Why:
- Rose can always do at least as well with row
Colin (columns)
- Dominated if:
- every entry of column is column
- Why:
- Colin can always make Rose's pay-off no bigger with column
Worked example
Reduce by dominance.
- 1
Row 3 is dominated by row 1: , and . Delete row 3.
- 2
Column 3 is dominated by column 1: and . Delete column 3.
Rose's pay-off matrix has rows , and . 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 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 , Rose plays row 1 with probability : her expected pay-off is against column 1 and against column 2.
Worked example
Solve for both players.
- 1
Equate Rose's expected pay-offs: , so and the value is .
- 2
Colin plays column 1 with probability : , that is , so .
In the game above, what is the probability 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 , divide by and maximise .
Larger games can be solved with Simplex. The method below is for Colin, who chooses the columns.
Let Colin play column with probability . Rose's expected gain against each row must be at most . Divide by and write : each constraint becomes , and .
Colin wants as small as possible, so he maximises with .
For Rose, write the game from Colin's view (negate and transpose), then add .
- 1
Add a constant k
make every entry positive so ; subtract at the end
- 2
Write the constraints
Rose's expected gain against each row is at most V
- 3
Divide by V
let , so each constraint is at most 1
- 4
Maximise P
, with
Worked example
Set up the linear programme for Colin in .
- 1
All entries are positive, so .
- 2
Rose's gain against rows 1 and 2: and .
- 3
Divide by : and .
Why must every entry be made positive before forming the linear programme?
Solving by Simplex
Add slack variables and use the profit row . Pivot until the profit row has no negative entries.
Add slack variables , and form the initial tableau with profit row . 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 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 increases each time.
- 1
Pivot column
most negative entry in the profit row
- 2
Ratio test
smallest non-negative value ÷ entry gives the pivot row
- 3
Row operations
make the pivot 1 and the rest of its column 0
- 4
Check the profit row
any negative entries left? If so, repeat
Then back to step 1
| Row y₁ | Row y₂ | Row P | |
|---|---|---|---|
| y₁ | 1 | 0 | 0 |
| y₂ | 0 | 1 | 0 |
| r | 1/4 | -1/8 | 1/8 |
| s | -1/12 | 5/24 | 1/8 |
| Value | 1/6 | 1/12 | 1/4 |
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 subject to and .
- 1
Initial tableau: : ; : ; : .
- 2
The profit row ties at ; take . Ratios and : pivot on the 5 in row .
- 3
Then the row is and row is .
- 4
Pivot column : ratios and , so pivot on the 4.8.
- 5
The profit row has no negatives: stop.
In the ratio test, how do you choose the pivot row?
Reading the solution
, , Rose's probabilities are the slack entries times , and the original value is .
Once the profit row has no negative entries, read the solution from the tableau.
- , the value of the adjusted game.
- for each column, with if is not basic.
- Value of the original game .
- Rose's probabilities: the slack-column entries of the profit row, each multiplied by .
A game question wants probabilities and the value of the original game, not just or the .
- 1
Value of adjusted game
V = 1 ÷ P
- 2
Colin's probabilities
q_j = V × y_j, with 0 if y_j is not basic
- 3
Rose's probabilities
slack entries of the profit row, each × V
- 4
Value of original game
V − k
- Adjusted value
- Probabilities
- Original value
Worked example
Read the solution from the tableau above, where , , and the slack entries are and .
- 1
.
- 2
and .
- 3
Rose: and .
- 4
No constant was added, so .
You added to every entry and the Simplex solution gives . What is the value of the original game?
Try an exam question
Rose's pay-off matrix is . Use dominance to reduce the game, then find Rose's optimal strategy and the value of the game.
[4 marks]
- [1]Row 3 is dominated by row 1 (, , ), so delete it.
- [1]Column 3 is dominated by column 1 (, ), so delete it.
- [1]Rose plays row 1 with probability : , so .
- [1]The value is 2.5 and Rose plays .
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
Which row can be removed because it is dominated?
1 mark, marked against the mark scheme