1. introduction arXiv:1107.1520v2 [math.CO] 1 Aug 2012 YARON AZRIELI AND ERAN SHMAYA LIPSCHITZ GAMES Abstract. The Lipschitz constant of a finite normal–form game is the maximal change in some player’s payoff when a single opponent changes his strategy. We prove that games with small Lipschitz constant admit pure ϵ -equilibria, and pinpoint the maximal Lipschitz constant that is sufficient to imply existence of pure ϵ -equilibrium as a function of the number of players in the game and the number of strategies of each player. Our proofs use the probabilistic method. The use of mixed strategies in game theory is often criticized, since one is reluctant to view rational decisions as based on coin tossing (see, e.g., Rubinstein’s discussion [19, Section 3]). Thus the long tradition in the literature of identifying classes of games that admit pure equilibrium [14, 15, 18]. Pure Nash equilibria do not suffer from the conceptual difficulty of mixed strategies, which make this solution concept more appealing. This paper identifies a new class of games that admit pure ϵ -equilibrium. We call these games Lipschitz games , since their characterizing property is that the payoff of a player does not change much when a single opponent changes his strategy; thus, each player’s payoff function is Lipschitz in her opponents’ strategy profile. More precisely, we define the Lipschitz constant of a game to be the maximal change in some player’s payoff when a single opponent changes his strategy. If the Lipschitz constant is o (1 /n ) when the number of players n grows, then any game with sufficiently many players admits a pure ϵ -equilibrium, since 1 2010 Mathematics Subject Classification. Primary: 91A10. Secondary: 05D40. Key words and phrases. Pure equilibrium, Purification, Lipschitz games, Large games. Thanks to Joyee Deb and Ehud Kalai for helpful discussions about large games, to Ezra Einy for informing us about the Shapley-Folkman Theorem, to Roger Myerson for Remark 2.9, to Ron Peretz for comments on a previous version of the manuscript, to Marcin Peski for suggesting the network games application, to David Schmeidler for suggesting the current proof of Theorem 6.1 (which is simpler than our original proof) and to Rakesh Vohra for informing us about Gale-Berlekamp Switching Game.