# LIPSCHITZ GAMES 

YARON AZRIELI AND ERAN SHMAYA 

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. 

## 1. introduction 

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 

