Simple Strategies for Large Zero-Sum Games with Applications to Complexity Theory

Richard Lipton, Neal E. Young

Von Neumann's Min-Max Theorem guarantees that each player of a zero-sum matrix game has an optimal mixed strategy. This paper gives an elementary proof that each player has a near-…