Consider the following problem ImI nu s to +1≥0,1a which we can interpret as follows: Player 2 chooses a2 so that every strategy of Player I yields u or less; indeed, Player 2 attempts to make u as small as possible. Not that u is unconstrained in sign The dual program is max u s t a1U+1v≤0,al1=1 i.e. Player 1 chooses a1 so each of Player 2's strategy yields at least v to Player 1 (think about it! ), i.e. at most -v to Player 2. Again, v is unconstrained Note that both programs are feasible(easy ); also, both programs are bounded because, say, in the dual program, v cannot be larger than the largest entry in the matrix U(which, if you think about it, is also obvious! )But then, by the Existence- Duality theorem of LP, both programs have optimal solutions, the optimal values are the same(so u= u), and the optimal solutions are complementary. In particular this means that a1(a1)>0 implies u1(a1, a2)=u, and similarly for 2. Thus, only actions which achieve the maximal payoff u against a2 receive positive probability; in other words, a1 only assigns positive probabilities to best responses(and similarly for a2). Hence, the optimal solutions of the dual LPs identify a Nash equilibrium; it is then easy to see that any Nash equilibrium satisfies the equality in Theorem 1(see Proposition 22.2 in OR if you don't see this), and we are doneConsider the following problem: min α2 u s.to − U · α2 + 1u ≥ 0, 1 0α2 = 1 which we can interpret as follows: Player 2 chooses α2 so that every strategy of Player 1 yields u or less; indeed, Player 2 attempts to make u as small as possible. Note that u is unconstrained in sign. The dual program is max α1 v s.to − α 0 1U + 10 v ≤ 0, α0 1 1 = 1 i.e. Player 1 chooses α1 so each of Player 2’s strategy yields at least v to Player 1 (think about it!), i.e. at most −v to Player 2. Again, v is unconstrained. Note that both programs are feasible (easy); also, both programs are bounded, because, say, in the dual program, v cannot be larger than the largest entry in the matrix U (which, if you think about it, is also obvious!) But then, by the Existence￾Duality theorem of LP, both programs have optimal solutions, the optimal values are the same (so u = v), and the optimal solutions are complementary. In particular, this means that α1(a1) > 0 implies u1(a1, α2) = u, and similarly for 2. Thus, only actions which achieve the maximal payoff u against α2 receive positive probability; in other words, α1 only assigns positive probabilities to best responses (and similarly for α2). Hence, the optimal solutions of the dual LPs identify a Nash equilibrium; it is then easy to see that any Nash equilibrium satisfies the equality in Theorem 1 (see Proposition 22.2 in OR if you don’t see this), and we are done. 6