D2 5.5 - Games as linear programs | Edexcel A-Level Further Mathematics

If adding $2$ to every pay-off makes a game easier to calculate, would adding $3$ instead change how the players should play? The numbers in the optimisation change, but the original game and its best strategies do not.

You already know

A's mixed strategy assigns non-negative probabilities summing to one to its rows. Against each column, its expected pay-off is a probability-weighted sum. A maximises the least of those expectations; B tries to limit the largest response. A pay-off matrix is for row player A unless stated otherwise.

A linear program maximises or minimises a linear objective subject to linear constraints and stated variable domains. Here the decision variables are A's row probabilities and the expected pay-off it can guarantee. A game without a stable pure solution can be solved this way even when neither player has just two options.

A common augmentation

Add the same constant $K$ to every original matrix entry $a_{ij}$ , forming $c_{ij}=a_{ij}+K$ . Every pair of mixed strategies then increases A's expected pay-off by exactly $K$ , because their probabilities sum to one.

Thus optimal strategies are unchanged. If the augmented game has value $V$ , the original value to A is $v=V-K$ ; B's original value is $-v$ .

Choose $K$ as directed in a question. Making all entries non-negative is a common requirement. In our worked models choose every entry strictly positive, which also makes the Simplex starting construction below easy to justify. If the least original entry is $-1$ , either $K=2$ or $K=3$ does this.

For three rows with probabilities $p_1,p_2,p_3$ , a guarantee $V$ means that every column expectation is at least $V$ . There is one such constraint per column, not per row.

The probability model

For an augmented matrix $\boldsymbol C=(c_{ij})$ , maximise $P=V$ , subject to

V-\sum_i c_{ij}p_i\leq0\quad\text{for every column }j

\sum_i p_i=1,\qquad p_i\geq0

When the augmented entries are non-negative, take $V\geq0$ . Afterwards use

v=V-K

Not in the formula booklet: learn it.

For the positive augmented games used here, replace the probability equality temporarily by $\sum_i p_i\leq1$ to obtain an easy starting tableau. These intermediate variables represent allocated probability mass, not a complete playable strategy until the sum is one. No optimum can leave mass unused: adding it to any row increases every column expectation, since all entries are positive. A feasible positive guarantee exists, so an optimum uses the full mass. The relaxed program therefore has the same optimum as the probability model.

This auxiliary starting point is useful: $V=0$ and all $p_i=0$ satisfy its inequalities. Simplex moves between feasible tableaux until it reaches an optimal complete distribution.

Key idea

One row mixture must meet every column's guarantee constraint. Adding one common $K$ preserves strategy comparisons; subtract $K$ from A's final augmented value, then negate to obtain B's original value.

Check which quantity is preserved.

Construct the initial game tableau

A slack variable turns a less-than-or-equal constraint into an equation. Use non-negative $r_1,r_2,r_3$ for the three column constraints and $u$ for unused probability capacity:

V-\sum_i c_{ij}p_i+r_j=0,\qquad \sum_i p_i+u=1

Write the objective as $P-V=0$ . The tableau lists coefficients of variables, with the right-hand side in the Value column. The objective row labelled $P$ has an implicit coefficient $1$ on $P$ ; no separate $P$ column is needed.

Worked example 1: one constraint per opponent response

Question. Form an initial Simplex tableau for the following game, augmenting every entry by $2$ :

\boldsymbol A=\begin{pmatrix}0&-1&1\\1&0&-1\\-1&1&0\end{pmatrix}

Plan. Check pure stability, augment, read down each column, and add the probability-capacity row and objective.

Row minima are all $-1$ , column maxima all $1$ , so there is no stable pure solution. The augmented matrix is

\boldsymbol C=\begin{pmatrix}2&1&3\\3&2&1\\1&3&2\end{pmatrix}

Maximise $P=V$ , subject to

\begin{aligned} V-2p_1-3p_2-p_3&\leq0\\ V-p_1-2p_2-3p_3&\leq0\\ V-3p_1-p_2-2p_3&\leq0\\ p_1+p_2+p_3&\leq1 \end{aligned}

with all variables non-negative. Adding slack variables gives:

Basic variable	$V$	$p_1$	$p_2$	$p_3$	$r_1$	$r_2$	$r_3$	$u$	Value
$r_1$	$1$	$-2$	$-3$	$-1$	$1$	$0$	$0$	$0$	$0$
$r_2$	$1$	$-1$	$-2$	$-3$	$0$	$1$	$0$	$0$	$0$
$r_3$	$1$	$-3$	$-1$	$-2$	$0$	$0$	$1$	$0$	$0$
$u$	$0$	$1$	$1$	$1$	$0$	$0$	$0$	$1$	$1$
$P$	$-1$	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$

Why use columns? Each column is one possible choice by B, against which A's same row distribution must guarantee $V$ .

Answer. The displayed tableau is the required initial tableau. Its basic variables are $r_1,r_2,r_3,u$ .

Check. Their columns form an identity matrix in the constraint rows and have zero objective coefficients. Setting all non-basic variables to zero gives slack values $0,0,0,1$ , all feasible. The row probabilities do not yet sum to one at this auxiliary starting point.

Change only the original top-left entry from $0$ to $1$ , keeping the augmentation $2$ .

Worked example 2: change just one tableau coefficient

Question. Construct the initial tableau for the changed game.

Plan. Augment the changed entry and locate its column constraint.

\boldsymbol C=\begin{pmatrix}3&1&3\\3&2&1\\1&3&2\end{pmatrix}

Only the first constraint changes, to

V-3p_1-3p_2-p_3\leq0

The complete initial tableau is:

Basic variable	$V$	$p_1$	$p_2$	$p_3$	$r_1$	$r_2$	$r_3$	$u$	Value
$r_1$	$1$	$-3$	$-3$	$-1$	$1$	$0$	$0$	$0$	$0$
$r_2$	$1$	$-1$	$-2$	$-3$	$0$	$1$	$0$	$0$	$0$
$r_3$	$1$	$-3$	$-1$	$-2$	$0$	$0$	$1$	$0$	$0$
$u$	$0$	$1$	$1$	$1$	$0$	$0$	$0$	$1$	$1$
$P$	$-1$	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$

Why does just one coefficient change? The altered entry is the contribution of row 1 to B's first-column response. Other response expectations are unaffected.

Answer. Use the displayed tableau; its only change from worked example 1 is $-2$ to $-3$ in the $r_1$ row, $p_1$ column.

Check. The basis, Value column, probability-capacity equation and objective are unchanged. Pure row minima remain $-1$ and column maxima $1$ , so the changed game still lacks a stable pure solution.

A tableau contains signs as well as magnitudes: the guarantee term is positive in a constraint row, while the expected-pay-off terms are subtracted.

Watch out

Wrong: use one expected-pay-off constraint per row, or enter positive pay-off coefficients beside $V$ . Right: read down each augmented column and write $V-\text{expected pay-off}+\text{slack}=0$ .

Change the same original entry once more.

Use Simplex pivots, including zero-ratio ties

A basic variable has an identity column: one $1$ in its own constraint row and zeros in all other constraint rows and the objective row. Set non-basic variables to zero, then read basic values from the Value column. A pivot swaps one non-basic variable into the basis and one basic variable out, using equivalent row equations.

Simplex for these maximisation tableaux

Use this procedure with the objective written in the form $P-\text{objective expression}=0$ .

Choose a negative coefficient in the objective row as the entering column; use the most negative if instructed, as in our examples.
In constraint rows with a strictly positive entering-column entry, calculate $\text{Value}/\text{entry}$ . Choose the least non-negative ratio. A zero ratio is eligible; a tie can be resolved by a stated choice.
Divide the entire leaving row by its pivot entry. Rename its basic variable as the entering variable.
Eliminate the entering variable from every other row, including the objective, using the new pivot row. Update every column, including Value.
Repeat. When every variable coefficient in the objective row is non-negative, the current feasible basic solution is optimal.

Not in the formula booklet: learn it.

The ratio test prevents a basic value becoming negative. A zero-ratio pivot may change the basis while leaving the current point and objective unchanged. That is common at a game's auxiliary starting point; excluding zero would give an incorrect pivot.

Worked example 3: solve a complete small game

Question. Solve $\left(\begin{smallmatrix}1&-1\\-1&1\end{smallmatrix}\right)$ by Simplex, augmenting by $2$ . Use the most negative objective coefficient and take the first row in a ratio tie.

Plan. Use augmented matrix $\left(\begin{smallmatrix}3&1\\1&3\end{smallmatrix}\right)$ , form the starting tableau, and pivot until the objective row has no negative coefficient.

Basic variable	$V$	$p_1$	$p_2$	$r_1$	$r_2$	$u$	Value
$r_1$	$1$	$-3$	$-1$	$1$	$0$	$0$	$0$
$r_2$	$1$	$-1$	$-3$	$0$	$1$	$0$	$0$
$u$	$0$	$1$	$1$	$0$	$0$	$1$	$1$
$P$	$-1$	$0$	$0$	$0$	$0$	$0$	$0$

First pivot. $V$ enters. The first two ratios are both $0/1=0$ ; $u$ 's $V$ coefficient is zero, so that row is ineligible. Choose $r_1$ to leave. Its pivot is already $1$ . Subtract this row from the second row and add it to $P$ ; $u$ is unchanged.

Basic variable	$V$	$p_1$	$p_2$	$r_1$	$r_2$	$u$	Value
$V$	$1$	$-3$	$-1$	$1$	$0$	$0$	$0$
$r_2$	$0$	$2$	$-2$	$-1$	$1$	$0$	$0$
$u$	$0$	$1$	$1$	$0$	$0$	$1$	$1$
$P$	$0$	$-3$	$-1$	$1$	$0$	$0$	$0$

Second pivot. $p_1$ enters. Eligible ratios are $0/2=0$ in $r_2$ , and $1/1=1$ in $u$ . Thus $r_2$ leaves. Divide that row by $2$ . Add three new pivot rows to $V$ and $P$ , and subtract one from $u$ .

Basic variable	$V$	$p_1$	$p_2$	$r_1$	$r_2$	$u$	Value
$V$	$1$	$0$	$-4$	$-1/2$	$3/2$	$0$	$0$
$p_1$	$0$	$1$	$-1$	$-1/2$	$1/2$	$0$	$0$
$u$	$0$	$0$	$2$	$1/2$	$-1/2$	$1$	$1$
$P$	$0$	$0$	$-4$	$-1/2$	$3/2$	$0$	$0$

Third pivot. $p_2$ enters; only $u$ has a positive entry in that column, giving ratio $1/2$ . Divide $u$ 's row by $2$ ; add four new pivot rows to $V$ and $P$ , and one to $p_1$ .

Basic variable	$V$	$p_1$	$p_2$	$r_1$	$r_2$	$u$	Value
$V$	$1$	$0$	$0$	$1/2$	$1/2$	$2$	$2$
$p_1$	$0$	$1$	$0$	$-1/4$	$1/4$	$1/2$	$1/2$
$p_2$	$0$	$0$	$1$	$1/4$	$-1/4$	$1/2$	$1/2$
$P$	$0$	$0$	$0$	$1/2$	$1/2$	$2$	$2$

Why stop? The objective equation is

P+\tfrac12 r_1+\tfrac12 r_2+2u=2

All variables on the left besides $P$ are non-negative, so $P\leq2$ . The current solution attains that upper bound.

Answer. $p_1=p_2=1/2$ , $V=2$ ; the original value is $2-2=0$ . B also uses its two columns equally.

Check. Each original column gives expectation zero against A's mixture; each original row gives zero against B's mixture. Thus both game guarantees agree. The two initial zero-ratio pivots left $P$ at zero; the final pivot raised it to $2$ .

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account

Last Accessed

Core Pure Mathematics

Further Pure Mathematics 1

Further Pure Mathematics 2

Further Statistics 1

Further Statistics 2

Further Mechanics 1

Further Mechanics 2

Decision Mathematics 1

Decision Mathematics 2

D2 5.5 - Games as linear programs

Turn a guaranteed pay-off into linear constraints

Construct the initial game tableau

Use Simplex pivots, including zero-ratio ties

Continue this lesson.

Learn faster with Nova