Zero-Sum Linear Programming Bridge
The row player's maximum safe-value linear program and the column player's minimum safe-value dual linear program should be connected to the matrix-game guarantee definitions. Once optimal row and column safe strategies are available, they form a mixed Nash equilibrium of the zero-sum game.
This bridge is the natural entry point for algorithmic game theory treatments of zero-sum computation.
Proof
The row LP maximizes a scalar $v$ subject to the inequalities saying that the chosen mixed row strategy guarantees at least $v$ against every pure column. The dual column LP minimizes a scalar $w$ subject to the inequalities saying that the chosen mixed column strategy holds every pure row payoff to at most $w$. Strong duality gives optimal solutions with $v=w$. These two sets of inequalities are exactly the saddle-point inequalities for the matrix payoff, so the resulting mixed strategies form a zero-sum Nash equilibrium and realize the matrix-game value.
References
- [AGT, Section 1.4.2, Thm. 1.11] Nisan, Roughgarden, Tardos, and Vazirani, Algorithmic Game Theory. Optimal zero-sum LP solutions form a Nash equilibrium.