Simple strategies for large zero-sum games with applications to complexity theory

By Richard Jay 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. This paper gives an elementary proof that each player has a near-optimal mixed strategy that chooses uniformly at random from a multiset of pure strategies of size logarithmic in the number of pure strategies available to the opponent. For exponentially large games, for which even representing an optimal mixed strategy can require exponential space, it follows that there are near-optimal, linear-size strategies. These strategies are easy to play and serve as small witnesses to the approximate value of the game. As a corollary, it follows that every language has small ``hard'' multisets of inputs certifying that small circuits can't decide the language. For example, if SAT does not have polynomial-size circuits, then, for each n and c, there is a set of n^(O(c)) Boolean formulae of size n such that no circuit of size n^c (or algorithm running in time n^c) classifies more than two-thirds of the formulae succesfully.

Subfields: Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Reinforcement Learning

Citations in the corpus

Generalization and Equilibrium in Generative Adversarial Nets (GANs) (2017, background): “We show that (as is folklore in game theory [Lipton and Young, 1994]) that we can approximate this min-max solution with mixture of ﬁnitely many generators and discriminators.”
Playing large games using simple strategies (2003, methodology): “For the class of two-person zero-sum games, results for approximate minmax strategies have been proved independently by Lipton and Young [ 18 ] and Alth ofer [1].”
Minimax Theorem for Latent Games or: How I Learned to Stop Worrying about Mixed-Nash and Love Neural Nets (2020, methodology): “This proof is inspired from the proof of (Lipton and Young, 1994, Theorem 2) and (Arora et al., 2017, Theorem B.3).”
Gradient-Based Algorithms for Finding Nash Equilibria in Extensive Form Games (2007, background): “We note that this is a substantial improvement to the black-box generic complexity bound 3 There has been work on finding -equilibria in two-player normal-form games [11, 12].”