Game Theory LP Formulation

An $m \times n$ two-person zero-sum game is solved by formulating it as a pair of dual linear programs.

Row Player’s LP

Subject to $\sum_{i=1}^{m} p_i a_{ij} \ge v$ for every column $j$, $\sum_{i=1}^{m} p_i = 1$, $p_i \ge 0$.

Column Player’s LP

Subject to $\sum_{j=1}^{n} q_j a_{ij} \le v$ for every row $i$, $\sum_{j=1}^{n} q_j = 1$, $q_j \ge 0$.

The 2 LPs are duals of each other. Solving either with the simplex algorithm gives the game’s value $v$ and both players’ optimal mixed strategies.