Converting games to linear programming problems

Converting games to linear programming problems Flashcards

Spec DF6 · AQA A-Level Further Maths: 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 VV) 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 kk is added?
It increases by kk, so subtract kk at the end.
What does VV represent in the linear programme?
The value of the (adjusted) game: Rowan's guaranteed expected pay-off.
What is the objective function?
Maximise P=VP=V.
How many column constraints are there?
One for each of Colin's columns, of the form V−a1jp1−a2jp2−…≤0V-a_{1j}p_1-a_{2j}p_2-\ldots\leq0.
What constraint stops the probabilities being too large?
p1+p2+…≤1p_1+p_2+\ldots\leq1.
What non-negativity conditions are included?
pi≥0p_i\geq0 for every ii and V≥0V\geq0.
Alternative formulation using xi=piVx_i=\frac{p_i}{V}?
Minimise ∑xi\sum x_i subject to ∑aijxi≥1\sum a_{ij}x_i\geq1 for each column; then V=1∑xiV=\frac{1}{\sum x_i}.
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 nn plays?
Multiply nn by the probability of that row.
What does it mean if a column's expected pay-off is greater than VV?
Colin never plays that column in his optimal strategy.

Flashcards