Converting games to linear programming problems Flashcards
Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.
14 cards
Tap a card to flip it. Swipe right if you knew it, left if not.
See all 14 cards
- Why is a game converted to a linear programme?
- To solve higher order games, which cannot be solved with a simple graph, using the simplex algorithm.
- Why add a constant to every entry before the simplex algorithm?
- So that all entries (and the value ) are non-negative, as the simplex algorithm requires.
- What constant do you add?
- Usually the least integer that makes every entry non-negative.
- What happens to Rowan's optimal strategy when a constant is added to every entry?
- It does not change.
- What happens to the value of the game when a constant is added?
- It increases by , so subtract at the end.
- What does represent in the linear programme?
- The value of the (adjusted) game: Rowan's guaranteed expected pay-off.
- What is the objective function?
- Maximise .
- How many column constraints are there?
- One for each of Colin's columns, of the form .
- What constraint stops the probabilities being too large?
- .
- What non-negativity conditions are included?
- for every and .
- Alternative formulation using ?
- Minimise subject to for each column; then .
- How do you find the value of the original game?
- Value of the adjusted game minus the constant added.
- How do you find how often to play a row in plays?
- Multiply by the probability of that row.
- What does it mean if a column's expected pay-off is greater than ?
- Colin never plays that column in his optimal strategy.