Converting games to linear programming problems
Studying this course? Keep your progress in one place.
Key facts
- For a higher order game, find Rowan's optimal mixed strategy with a linear programme and the simplex algorithm.
- Add a constant to every entry so that ; the strategy is unchanged and the value rises by .
- Each column of the matrix gives one constraint: .
- Maximise subject to and all variables non-negative.
- The value of the original game is .
Why convert a game
A graph only works when one player has two strategies; larger games need a linear programme and the simplex algorithm.
For a higher order game (for example ), Rowan's optimal mixed strategy is found by turning the game into a linear programming problem and solving it with the simplex algorithm.
Rowan chooses probabilities for his rows. Against each of Colin's columns his expected pay-off is a linear expression in the . Colin will choose the worst column for Rowan, so Rowan maximises the smallest of these, called .
- 1
Make entries non-negative
add a constant to every entry
- 2
Formulate
one constraint per column, maximise
- 3
Simplex
add slack variables and pivot
- 4
Interpret
read and , then subtract
What does represent in the linear programme?
Making every entry non-negative
The simplex algorithm needs , so add the same constant to every entry and subtract it at the end.
Add a constant to every entry, usually the negative of the smallest entry, so all entries are non-negative.
Adding raises every expected pay-off by (the probabilities sum to 1), so Rowan's optimal strategy does not change. The value of the game increases by , so after solving subtract to get the original value.
- Add to every entrystrategy unchanged, value
Worked example
The game is adjusted so that the value can be found. What is the original value if the adjusted game has value ?
- 1
The smallest entry is , so add to every entry to get .
- 2
Solve the adjusted game: its value is .
- 3
Subtract to return to the original game.
The smallest entry of a pay-off matrix is . What constant is added, and what is the original value if the adjusted value is ?
Formulating the linear programme
Each column of the adjusted matrix gives one constraint, and you maximise .
For the adjusted matrix with entries , Rowan plays row with probability . Against column his expected pay-off is , and is at most this, so each column gives a constraint .
The probabilities cannot total more than 1, and all variables are non-negative. The objective function is .
Some questions use : minimise subject to for each column, and then . Use the form asked for.
- Maximise
- Each column
- Probabilities
Worked example
Formulate the linear programme for the adjusted matrix .
- 1
Column 1 has entries , so the constraint is .
- 2
Column 2 has entries , so the constraint is .
- 3
The probabilities satisfy .
For the adjusted matrix , which is the constraint from column 2?
Solving and interpreting
Pivot until the objective row has no negative entries, then read and each , and subtract from .
Introduce a slack variable for each constraint, set up the initial tableau, and pivot until there are no negative entries in the objective row.
The value of the original game is . Rowan's optimal strategy is the set of probabilities ; a probability of means that row is never played. In plays, play row about times.
Colin's strategy can be read from the objective row, under the slack variables of the column constraints. A column that is not tight is never played by Colin.
- Original value
- Plays of row in games
Rowan's optimal strategy has . In 40 plays, how many times should he choose row 1?
Try an exam question
The pay-off matrix to Rowan is . Rowan plays row with probability . State a suitable constant to add to every entry and formulate the linear programme for the adjusted game.
[4 marks]
- [1]The smallest entry is , so add to every entry.
- [1]The adjusted matrix is .
- [1]Constraints (one per column): and , with .
- [1]Maximise , with .
That's the notes covered.
Carry on to the next subtopic.
Try a question
What is the least integer that must be added to every entry so that no entry is negative?
1 mark, marked against the mark scheme
What is the least integer that must be added to every entry so that no entry is negative?
1 mark, marked against the mark scheme