Linear programs and dual game values

What you will learn

Formulate a finite zero-sum game as primal and dual linear programs, derive a weighted-slack optimality certificate and distinguish objective-bound looseness from exploitable strategy error, including negative game values.

Prerequisites: Mixed supports and saddle certificates · Expected value as a weighted average

Turn a guaranteed payoff into a decision variable

Assume a finite simultaneous zero-sum game with independent random draws, a publicly known matrix and linear expected chip transfers. Row maximizes the displayed transfer and Column receives its negative. There are no fees, hidden types, sequential observations or utility curvature. Our original matrix has rows A,B and columns L,M,N: A=(3,−1,1), B=(−2,4,0). These are fictional net transfers, not a poker solver output. A row mixture is x=(p,1−p), with 0≤p≤1. Its three column payoffs are 5p−2, 4−5p and p. They are affine functions of the same decision p, not independent forecasts.

Introduce a second decision variable v, the payoff level Row promises to guarantee. The primal linear program maximizes v subject to v≤5p−2, v≤4−5p, v≤p and 0≤p≤1. Each inequality protects against one available column. Together they describe a feasible region in the p,v plane, lying below all three lines. A point in that region is a valid guarantee, even if v is unnecessarily low. Maximizing moves its level upward until an active barrier prevents further improvement. The variable v is unrestricted in sign: a game whose unavoidable transfer is negative still has a meaningful optimum. Nonnegative probabilities do not imply nonnegative payoffs.

Construct the dual by weighting constraints

Column chooses nonnegative weights yL,yM,yN summing to one. Multiplying the three primal payoff inequalities by these weights and adding gives v≤xᵀAy. To obtain a bound valid for every possible p, require both pure row values to be at most a new level w: 3yL−yM+yN≤w and −2yL+4yM≤w. The dual program minimizes w subject to these two inequalities and the probability constraints on y. Its variables are the constraint weights and the bound. This construction explains the reversed objective direction without memorizing a table of duality rules.

For any feasible primal and dual pair, v≤xᵀAy≤w. This is weak duality: a valid promised lower level cannot exceed a valid universal upper level. It is an algebraic statement about all mixtures, so a sampled game result cannot refute it. Finite matrix games also have matching optimal levels, by linear programming strong duality. Here both sides are feasible and bounded because matrix entries are finite and probability simplexes are nonempty. We will independently exhibit equal feasible levels for this particular matrix, rather than invoking the theorem as a substitute for checking our arithmetic.

Solve the original program and verify a dual upper bound

Compare the M and N barriers first. If p≤2/3, the N constraint gives v≤p≤2/3. If p≥2/3, the M constraint gives v≤4−5p≤2/3. These two cases cover every feasible p and establish a global upper bound of 2/3, even before considering L. At p=2/3, the three column payoffs are 4/3,2/3,2/3. Thus v=2/3 satisfies every primal inequality and attains the bound. L has slack 2/3; the other two barriers bind. The argument covers the entire continuous interval, beyond the six-token activity grid.

To construct matching dual weights, assign zero to L and let yM=t and yN=1−t. The two row values become 1−2t and 4t. Equalizing them yields 1=6t, so y=(0,1/6,5/6) and w=2/3. Direct evaluation checks A: −1/6+5/6=4/6. For B: 4/6+0=4/6. Independently enumerate the four positive joint cells under x=(2/3,1/3): their weighted transfers are −1/9,5/9,2/9,0, summing to 6/9=2/3. This cell sum agrees with both optimized levels without reusing the barrier calculation. The zero weight on L will acquire a precise slack interpretation next.

Account for every unit of objective gap

For any feasible pair define primal slacks sⱼ=(xᵀA)ⱼ−v and dual slacks tᵢ=w−(Ay)ᵢ. They are nonnegative. Their weighted sums are P=Σⱼyⱼsⱼ=u−v and D=Σᵢxᵢtᵢ=w−u, where u=xᵀAy. Adding gives w−v=P+D. This identity follows by expanding both sums and using the two probability totals. It accounts for the whole objective gap using local constraint residuals. If v=w, every nonnegative weighted term must vanish. Hence positive dual weight requires a tight primal constraint, and positive row mass requires a tight dual constraint. This is complementary slackness, including the direction of the implication.

At our optimum the L slack is 2/3 and its dual weight is zero. M and N have positive dual weights and zero slacks. Both rows have positive mass and zero dual slacks. A tight constraint need not receive positive weight in other problems; complementary slackness alone neither proves uniqueness nor forces all tight constraints to be used. Feasibility remains essential. Negative residuals could cancel positive ones in an algebraic sum, but that cancellation would not be an optimality proof. The activity checks primal feasibility and dual feasibility before accepting either weighted budget.

Separate loose bounds, strategy errors and changes of origin

Keep both optimal strategies fixed but enter v=0 and w=1. The pair remains feasible. Its objective gap is one, with P=2/3 and D=1/3. Neither player has a profitable deviation: the positive gap comes entirely from loose level variables. Therefore a solver stopping report must distinguish the gap of the submitted LP variables from the smallest strategy deviation gap computed from their actual extrema. For a contrasting feasible but nonoptimal primal point, take p=1/2 and v=1/2 with the optimal dual mixture and w=2/3. Column payoffs are 1/2,3/2,1/2, u=2/3, P=1/6 and D=0. Raising p to 2/3 removes the remaining primal objective shortfall.

Now subtract two from every matrix entry. Since joint probabilities sum to one, every expected transfer drops by two. The strategies and slacks stay the same when v and w also drop by two; the common optimum becomes −4/3. Restricting v≥0 would make this primal model infeasible and falsely suggest the game has no solution. A uniform shift changes payoff origin, not incentives. Multiplying by a negative constant would instead exchange maximizing and minimizing roles and is not this transformation.

In the workshop transfer probability tokens, propose both objective levels, and calculate P and D. First preserve a feasible nonoptimal budget, then construct the zero-gap optimum. Reenter loose levels with those same strategies to witness objective looseness. Shift the matrix origin, rebuild the negative-valued certificate and compare the saved ledgers. Each model edit clears the submitted values; each input edit invalidates current feedback. Saved records retain their own assumptions locally during the visit. They do not award account credit, establish convergence of an optimization algorithm or model full poker play.

Hands-on: Build primal and dual slack ledgers

Construct feasible LP levels and constraint weights, reconcile weighted slack, separate loose bounds from strategy error and shift the payoff origin.

Common mistakes

• Constraining the payoff variable to be nonnegative because probabilities are nonnegative.
• Maximizing the dual upper level instead of minimizing it.
• Using cancellation of negative constraint residuals as an optimality certificate.
• Calling every positive submitted LP gap strategic exploitability.
• Forcing a positive dual weight on every tight constraint.

Keep these ideas

• A guaranteed level must lie below every column payoff.
• Dual probability weights bound all row payoffs from above.
• Feasible objective gap equals two nonnegative weighted-slack budgets.
• Complementary slackness follows from zero gap and feasibility.
• Uniform payoff shifts preserve strategies and slacks while moving the optimum.

Further reading

• MIT 6.854 Lecture 12: LP Duality ↗

  Read Duality, Strong Duality and complementary slackness discussion (HTML lines 12–117), plus unrestricted-variable sign conventions. Supports general optimization definitions only. Original matrix, weighted-slack budgets, loose-level witness and diagnostics; no source exercises, quotations or video reused. Checked 2026-10-25.

• MIT 6.7980 Lecture 3: section L3.1.1, zero-sum games and LP duality ↗

  Read section L3.1.1 on bilinear payoffs, minimax strategies and primal-dual formulation. Our two-by-three law, piecewise bound, four-cell arithmetic, origin-shift and loose-level examples are original. No video, full-course review, credential or source numerical example claimed. Checked 2026-10-25.