Lecture 24: Linear Programming and Two-Person Games

What this lecture covers

This lecture surveys a specific, classical corner of optimization: linear programming and its connection to two-person zero-sum games. Strang introduces the linear programming setup (a linear cost minimized subject to linear equality and inequality constraints), the geometric picture of a feasible set as a polyhedron, and two families of algorithms for solving it: the simplex method and interior-point methods. The centerpiece is duality, illustrated first through weak and strong duality, then through the max-flow min-cut example, and finally through the equivalent problem of finding optimal mixed strategies in a two-person zero-sum game.

This lecture stands somewhat apart from the deep-learning-focused material around it, covering a self-contained and historically important part of optimization theory. After watching, you should be able to state the linear programming problem and its dual, explain what max-flow min-cut duality means, and compute a mixed strategy equilibrium for a small two-person zero-sum game.

Key ideas

• Linear program (primal): minimize c^T x subject to Ax = b and x >= 0; the feasible set is the intersection of a linear subspace (shifted by b) with the non-negative orthant, forming a polyhedron.
• Corners solve linear programs: because the cost is linear, the optimal point of a linear program is always attained at a corner (vertex) of the feasible polyhedron.
• Simplex method: moves from corner to corner along edges that decrease the cost, stopping when no adjacent corner is better; developed by George Dantzig.
• Interior-point methods: move through the interior of the feasible set rather than along its boundary edges, popularized by Karmarkar's algorithm, and applicable more broadly to nonlinear, quadratic, and semidefinite programming.
• Duality: every linear program (the primal, a minimization) has a dual (a maximization) built from the same data; weak duality guarantees the dual's value is always at most the primal's, and strong duality states they are equal at the optimum, with no gap.
• Max-flow min-cut: the maximum flow through a network cannot exceed the total capacity of any cut separating source from sink, and at the optimum the two quantities are equal - a concrete instance of linear programming duality.
• Two-person zero-sum games and mixed strategies: when a payoff matrix has no saddle point in pure strategies, the optimal play is a mixed strategy (a probability distribution over rows or columns); solving for the optimal probabilities is equivalent to solving a linear program, connecting duality in linear programming to von Neumann's minimax theorem.

Walkthrough

Setting up linear programming (3:04)

Strang defines the linear program: minimize a linear cost c^T x subject to linear equality constraints Ax = b and the inequality x >= 0. Using a 3-variable, 1-constraint example, he shows the feasible set is a triangle (a polygon carved from the non-negative octant by a plane), and that the minimum cost is always reached at one of its corners.

Simplex and interior-point algorithms (10:19)

Two algorithmic approaches are introduced: the simplex method, which travels corner to corner along the boundary of the feasible set, always decreasing cost until no further improvement is possible, and interior-point methods (associated with Karmarkar), which move through the interior using calculus-based search directions, stopping short of the boundary to keep room to maneuver.

Weak and strong duality (15:30)

The dual problem is constructed by maximizing b^T y subject to A^T y <= c. Strang proves weak duality directly - b^T y <= c^T x for any feasible x and y - by chaining b^T y = x^T A^T y <= x^T c, using x >= 0 at the key step. Strong duality then states that at the optimal x* and y*, equality holds, meaning the maximum of the dual equals the minimum of the primal with no gap.

Max-flow min-cut (24:40)

Working through a small flow network with edge capacities, Strang shows how to bound the achievable flow into the sink by finding a cut - a set of edges separating source from sink - whose total capacity limits any possible flow. In the worked example, a maximum flow of 14 matches a minimum cut capacity of 14, illustrating strong duality concretely. He notes that although flow problems are naturally integer programs, relaxing to real-valued flows does not change the optimal value, so continuous methods like simplex or interior-point methods can be used safely.

Two-person zero-sum games (38:04)

Strang introduces a payoff matrix game between a minimizing player X and a maximizing player Y. When the matrix has a saddle point (a common example is given), pure strategies (a fixed row and column) are optimal. When no saddle point exists, players must use mixed strategies - probability distributions over their choices - and Strang solves a small 2x2 example by setting the expected payoffs equal across strategies, finding the equilibrium probability P = 2/3.

Connecting games to linear programming (50:15)

The lecture closes by noting that solving for optimal mixed strategies is itself a linear program, with the primal and dual corresponding to the two players' problems, and that this equivalence underlies von Neumann's minimax theorem for two-person zero-sum games. Strang mentions John Nash's extension of this theory to more general games as the basis for his Nobel Prize.

Before you watch

• No specific prior lecture in this course is required, since linear programming is introduced from scratch, though familiarity with matrix-vector notation from earlier lectures is assumed.
• Basic comfort with inequalities and systems of linear equations is helpful.

Check your understanding

1. Why is the optimal point of a linear program always at a corner of the feasible set rather than in its interior?
2. What is the difference between how the simplex method and interior-point methods search for the optimum?
3. In the max-flow min-cut example, why does the flow through the network never exceed the capacity of any cut?
4. Why does a payoff matrix without a saddle point require a mixed strategy rather than a pure strategy?