Converting games to linear programming problems

Converting games to linear programming problems

Spec DF6 · AQA A-Level Further Maths: Revision notes

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 kk to every entry so that V≥0V\ge0; the strategy is unchanged and the value rises by kk.
  • Each column of the matrix gives one constraint: V−a1jp1−a2jp2−⋯≤0V-a_{1j}p_1-a_{2j}p_2-\dots\le0.
  • Maximise P=VP=V subject to p1+p2+⋯≤1p_1+p_2+\dots\le1 and all variables non-negative.
  • The value of the original game is V−kV-k.

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 3×33\times3), 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 p1,p2,p3,…p_1,p_2,p_3,\dots for his rows. Against each of Colin's columns his expected pay-off is a linear expression in the pip_i. Colin will choose the worst column for Rowan, so Rowan maximises the smallest of these, called VV.

  1. 1

    Make entries non-negative

    add a constant kk to every entry

  2. 2

    Formulate

    one constraint per column, maximise P=VP=V

  3. 3

    Simplex

    add slack variables and pivot

  4. 4

    Interpret

    read pip_i and VV, then subtract kk

From game to answer

What does VV represent in the linear programme?

Making every entry non-negative

The simplex algorithm needs V≥0V\ge0, so add the same constant to every entry and subtract it at the end.

Add a constant kk to every entry, usually the negative of the smallest entry, so all entries are non-negative.

Adding kk raises every expected pay-off by kk (the probabilities sum to 1), so Rowan's optimal strategy does not change. The value of the game increases by kk, so after solving subtract kk to get the original value.

  • Add kk to every entrystrategy unchanged, value + k+\,k

Worked example

The game (−321−1)\begin{pmatrix} -3 & 2 \\ 1 & -1 \end{pmatrix} is adjusted so that the value can be found. What is the original value if the adjusted game has value 207\frac{20}{7}?

The smallest entry of a pay-off matrix is −4-4. What constant is added, and what is the original value if the adjusted value is 66?

Formulating the linear programme

Each column of the adjusted matrix gives one constraint, and you maximise VV.

For the adjusted matrix with entries aija_{ij}, Rowan plays row ii with probability pip_i. Against column jj his expected pay-off is ∑iaijpi\sum_i a_{ij}p_i, and VV is at most this, so each column gives a constraint V−a1jp1−a2jp2−⋯≤0V-a_{1j}p_1-a_{2j}p_2-\dots\le0.

The probabilities cannot total more than 1, and all variables are non-negative. The objective function is P=VP=V.

Some questions use xi=piVx_i=\frac{p_i}{V}: minimise ∑xi\sum x_i subject to ∑iaijxi≥1\sum_i a_{ij}x_i\ge1 for each column, and then V=1∑xiV=\frac{1}{\sum x_i}. Use the form asked for.

  • MaximiseP=VP=V
  • Each column jjV−a1jp1−a2jp2−⋯≤0V-a_{1j}p_1-a_{2j}p_2-\dots\le0
  • Probabilitiesp1+p2+⋯≤1p_1+p_2+\dots\le1

Worked example

Formulate the linear programme for the adjusted matrix (3105)\begin{pmatrix} 3 & 1 \\ 0 & 5 \end{pmatrix}.

For the adjusted matrix (3105)\begin{pmatrix} 3 & 1 \\ 0 & 5 \end{pmatrix}, which is the constraint from column 2?

Solving and interpreting

Pivot until the objective row has no negative entries, then read VV and each pip_i, and subtract kk from VV.

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 V−kV-k. Rowan's optimal strategy is the set of probabilities pip_i; a probability of 00 means that row is never played. In nn plays, play row ii about npinp_i 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 valueV−kV-k
  • Plays of row ii in nn gamesn×pin\times p_i

Rowan's optimal strategy has p1=0.25p_1=0.25. In 40 plays, how many times should he choose row 1?

Try an exam question

The pay-off matrix to Rowan is (−234−1)\begin{pmatrix} -2 & 3 \\ 4 & -1 \end{pmatrix}. Rowan plays row ii with probability pip_i. State a suitable constant to add to every entry and formulate the linear programme for the adjusted game.

[4 marks]

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

Revision notes