Simple Strategies for Large Zero-Sum Games with Applications to Complexity Theory
Richard J. Lipton, Neal E. Young · 1994
Von Neumann's Min-Max Theorem guarantees that each player of a zero-sum matrix game has an optimal mixed strategy. We show that each player has a near-optimal mixed strategy that chooses uniformly from a multiset of pure strategies of size logarithmic in the number of pure strategies available to the opponent. Thus, for exponentially large games, for which even representing an optimal mixed strategy can require exponential space, there are nearoptimal, linear-size strategies. These strategies are easy to play and serve as small witnesses to the approximate value of the game.