DF6 - Games as linear programmes

DF6 - Games as linear programmes

A higher-order game can require more probabilities than a single graph can show. You will express each opponent response as an inequality, preserve the probability conditions, and use a valid simplex formulation to solve a three-by-three game. Shifting every pay-off by a constant provides a safe positive-pay-off model when necessary; the original value must be restored afterwards.

Formulating a higher-order game

How can we solve a three-by-three game when every pure row can lose 2? Consider this matrix for the row player:

A=(0−2−2−21−2−2−24).\mathbf A=\begin{pmatrix}0&-2&-2\\-2&1&-2\\-2&-2&4\end{pmatrix}.

There is no pure domination. Row minima are all −2-2, while column maxima are 0,1,40,1,4. There is no saddle point. To describe a row mixture, we need three probabilities rather than one.

Let pip_i be the probability of row ii. Against column 1, the expected pay-off is 0p1−2p2−2p30p_1-2p_2-2p_3. A guaranteed expectation vv must be no larger than this. Repeat for each column: the opponent may choose any of them.

Row-player game model

For a matrix (aij)(a_{ij}) for the row player, maximise vv, subject to

∑iaijpi≥vfor every column j,∑ipi=1,pi≥0.\sum_i a_{ij}p_i\geq v\quad\text{for every column }j, \qquad\sum_i p_i=1,\qquad p_i\geq0.

In this general model, vv can be negative, zero or positive. The game formulation is not supplied in the AQA formula booklet.

Checking pure columns is sufficient: an opponent mixture gives a weighted average of these column expectations, so if every one is at least vv, that average is too. There is one pay-off constraint per opposing pure strategy.

Worked example 1: maximising the row player's guarantee

Question. Formulate the row player's optimisation for the displayed three-by-three matrix.

Plan. Use one probability for each row and one lower-bound inequality for each column.

maximise vsubject to −2p2−2p3≥v−2p1+p2−2p3≥v−2p1−2p2+4p3≥vp1+p2+p3=1,p1,p2,p3≥0\begin{aligned} \text{maximise }&v\\ \text{subject to }&-2p_2-2p_3\geq v\\ &-2p_1+p_2-2p_3\geq v\\ &-2p_1-2p_2+4p_3\geq v\\ &p_1+p_2+p_3=1,\qquad p_1,p_2,p_3\geq0 \end{aligned}

Answer. This linear programme maximises the worst expected pay-off. No nonnegativity restriction has been placed on vv.

Check. The pure choice (p1,p2,p3)=(1,0,0)(p_1,p_2,p_3)=(1,0,0) gives expectations 0,−2,−20,-2,-2, exactly row 1 of the original matrix. Its largest feasible guarantee is −2-2, as the inequalities correctly show.

Keep the matrix and its viewpoint unchanged, but formulate the other player's decision. The column player minimises an upper bound on the same recorded gain.

Worked example 2: minimising the opponent's upper bound

Question. Formulate the column player's optimisation for the same row-player matrix. Let qjq_j be the probability of column jj, and ww an upper bound on the row player's expected gain.

Plan. Average across each row and require every row expectation to be at most ww.

minimise wsubject to −2q2−2q3≤w−2q1+q2−2q3≤w−2q1−2q2+4q3≤wq1+q2+q3=1,q1,q2,q3≥0\begin{aligned} \text{minimise }&w\\ \text{subject to }&-2q_2-2q_3\leq w\\ &-2q_1+q_2-2q_3\leq w\\ &-2q_1-2q_2+4q_3\leq w\\ &q_1+q_2+q_3=1,\qquad q_1,q_2,q_3\geq0 \end{aligned}

Answer. The constraints cap every row's expectation. The column player's own gain is the negative of the row-player value, not ww with its sign unchanged.

Check. At (q1,q2,q3)=(1,0,0)(q_1,q_2,q_3)=(1,0,0), the row expectations are 0,−2,−20,-2,-2. The smallest valid upper bound is w=0w=0, matching column 1's maximum. This checks both the direction of inequality and the coefficients.

A row strategy guaranteeing vv and a column strategy capping the pay-off at the same vv together prove the game's value. This remains an especially useful independent check after an LP solution.

Watch out

Multiply probabilities by the entries belonging to their own strategies. For row probabilities, read down each column, with expectations ≥v\geq v. For column probabilities, read along each row, with expectations ≤w\leq w. A transpose or reversed inequality changes the problem.

Translate a different matrix into a row model.

Probability constraints and a positive pay-off shift

Probabilities must sum to exactly 1, with zero allowed for an unused strategy. They are real numbers; an integer restriction would incorrectly prevent genuine mixing. An LP's auxiliary starting point, however, need not itself describe a play of the game if an equivalent optimisation has deliberately relaxed the probability sum.

For a matrix with strictly positive entries, we may maximise a nonnegative guarantee VV using ∑pi≤1\sum p_i\leq1 instead of equality. This has a feasible all-slack start at pi=V=0p_i=V=0. Why is the final answer still a genuine distribution? Some normalised mixture guarantees a positive amount, so the optimum has V>0V>0. If its total mass were s<1s<1, then s>0s>0, and replacing pi,Vp_i,V by pi/s,V/sp_i/s,V/s would remain feasible and increase VV. This contradicts optimality. Thus at an optimum the sum is 1. Strict positivity also bounds VV, so there is a finite optimum.

This relaxation is not a universal probability rule. If every entry were −2-2, the real game would have value −2-2, but the relaxed zero vector with guarantee 0 would falsely improve it. To obtain a positive matrix, add the same sufficiently large constant to every entry.

Constant pay-off shift

For normalised probabilities, adding KK to every pay-off adds KK to every expected pay-off:

∑i(aij+K)pi=∑iaijpi+K(∑ipi=1).\sum_i(a_{ij}+K)p_i=\sum_i a_{ij}p_i+K \qquad\left(\sum_i p_i=1\right).

Optimal strategies are unchanged, and the shifted value satisfies V=v+KV=v+K. After solving, restore v=V−Kv=V-K. Choose KK so every shifted entry is strictly positive when using the positive-game relaxation above. Not in the formula booklet: learn the reasoning.

A shift changes the pay-off table, not the probabilities. Once the positive model is ready, write each lower bound as V−Ej≤0V-E_j\leq0, add a nonnegative slack, and include one slack for ∑pi≤1\sum p_i\leq1. All right sides are nonnegative, so the ordinary feasible-start simplex method now applies.

Worked example 3: building a valid simplex start

Question. For the opening matrix A\mathbf A, add K=3K=3 to each entry. Formulate a positive-game simplex model and its initial tableau.

Plan. Shift every entry, use the justified probability relaxation, and put objective coefficient +1+1 in the tableau.

B=A+3J=(311141117),\mathbf B=\mathbf A+3\mathbf J= \begin{pmatrix}3&1&1\\1&4&1\\1&1&7\end{pmatrix},

where J\mathbf J has every entry equal to 1. Maximise P=VP=V, with constraints V−3p1−p2−p3≤0V-3p_1-p_2-p_3\leq0, V−p1−4p2−p3≤0V-p_1-4p_2-p_3\leq0, V−p1−p2−7p3≤0V-p_1-p_2-7p_3\leq0, p1+p2+p3≤1p_1+p_2+p_3\leq1, and V,pi≥0V,p_i\geq0. Add slacks r,s,t,ur,s,t,u in that order:

PVp1p2p3rstuvalueR01−100000000R101−3−1−110000R201−1−4−101000R301−1−1−700100R40011100011\begin{array}{c|rrrrrrrrr|r} &P&V&p_1&p_2&p_3&r&s&t&u&\text{value}\\\hline R_0&1&-1&0&0&0&0&0&0&0&0\\ R_1&0&1&-3&-1&-1&1&0&0&0&0\\ R_2&0&1&-1&-4&-1&0&1&0&0&0\\ R_3&0&1&-1&-1&-7&0&0&1&0&0\\ R_4&0&0&1&1&1&0&0&0&1&1 \end{array}

Answer. The all-slack basis has r=s=t=0,u=1r=s=t=0,u=1, with V=pi=0V=p_i=0, so it is feasible for this auxiliary model. The original value will be v=V−3v=V-3.

Check. The shifted uniform row mixture gives expectations 5/3,2,35/3,2,3, so a positive guarantee is available. The relaxation proof therefore forces the optimal probability sum to 1, even though the initial sum is zero.

Increase only the shift from 3 to 4. The probability solution must stay the same; the shifted objective will rise by one.

Worked example 4: another valid shift

Question. Build the same simplex model using K=4K=4, stating exactly what changes and how to restore the original value.

Plan. Add one more to every shifted entry, then rebuild each expected-pay-off constraint.

C=(422252228).\mathbf C=\begin{pmatrix}4&2&2\\2&5&2\\2&2&8\end{pmatrix}.

The pay-off rows of the tableau become

01−4−2−21000001−2−5−20100001−2−2−800100.\begin{array}{rrrrrrrrr|r} 0&1&-4&-2&-2&1&0&0&0&0\\ 0&1&-2&-5&-2&0&1&0&0&0\\ 0&1&-2&-2&-8&0&0&1&0&0 \end{array}.

The objective and probability-sum rows remain unchanged, with the same column order as above.

Answer. This is also a feasible positive-game model. Restore v=V−4v=V-4, rather than subtracting 3. For any normalised strategy, its new expectations are one greater than under B\mathbf B.

Check. For example, the pure row-2 expectations change from (1,4,1)(1,4,1) under B\mathbf B to (2,5,2)(2,5,2) under C\mathbf C, a uniform increase of one. Their relative advantages are unchanged, as required.

The zero right sides create tied zero ratios when VV first enters. This is a legitimate degenerate start, already covered by simplex: choose an eligible zero-ratio row and continue. Do not pivot on the probability row, whose VV-coefficient is zero.

Continue this lesson.

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

Create free account