Among game theoretic concepts, mixed strategy is arguably the most difficult to digest. We don’t see people tossing coins all the time, and it’s difficult to justify rational decision as based on Lady Fortuna’s unpredictable caprices. The case of Nash Equilibrium is especially disturbing — if you are indifferent between a couple of strategies then why bother randomizing between them according to the mixture prescribed by the equilibrium. Just pick one of these strategies arbitrary and get it over with.

I know of two types of answers that game theory gives for this conundrum. One, which may be called interpretation of mixed strategies’ is arguing that the mixed strategies in Nash equilibrium do not reflect an actual randomization performed by the players: Epistemic game theory interprets mixed strategies as opponent’s beliefs about a player’s (non-randomized) strategy; Harsanyi’s Purification approach embeds a normal form game in a larger game with incomplete information and pure equilibrium. The other type of answers is identifying classes of games which admit pure equilibrium, such as games with strategic complementarity and potential games.

In my new paper with Yaron(pdf) we suggest another class of games which admit pure ${\epsilon}$-equilibrium, which means that no player gains more than ${\epsilon}$ from deviating. These are games in which a player’s payoff does not change much if one of her opponents changes his strategy:

Math and open problems below the fold…

An ${n}$–player game is given by finite sets ${\{A_i\}_{i=1}^n}$ of strategies and by payoff functions ${\left\{f_i:A\rightarrow [-1,1] \right\}_{i=1}^n}$, where ${A=\prod_{i=1}^n A_i}$ is the set of strategy profiles. As usual, we denote, for every player ${i}$, the set of opponents’ profiles by ${A_{-i}=\prod_{j\neq i}A_j}$.

Definition 1 The Lipschitz constant of the game is given by $\displaystyle \delta=\max\{|f_i(a_i,a_{-i}')-f_i(a_i,a_{-i}'')|\},$

where the maximum ranges over all players ${i}$, all strategies ${a_i\in A_i}$ and all pairs ${a_{-i}',a_{-i}''\in A_{-i}}$ that differ only in one coordinate.

Games with Lipschitz constant ${\delta}$ have the property that a player’s payoff does not change by more than ${\delta}$ when one of her opponent changes his strategy.

What we prove in this paper is that if the Lipschitz constant of a game is sufficiently small, then the game admit pure ${\epsilon}$-equilibrium, and we almost pin down the asymptotic of sufficiently small’ as a function of the number of players:

Theorem 2 Fix ${\epsilon>0}$ and ${m}$.

1. There exists ${K}$ (which depends on ${\epsilon}$ and ${m}$) such that every ${n}$-player game with ${m}$ actions for every player and Lipschitz constant smaller than ${K/\sqrt{n\log n}}$ admits pure ${\epsilon}$-equilibrium.
2. There exists ${C}$ such that for every ${n}$ large enough there exists an ${n}$-player game with ${m}$ actions for every player and Lipschitz constant smaller than ${C/\sqrt{n}}$ without pure ${\epsilon}$-equilibrium.

See, for sufficiently large ${n}$, if the Lipschitz constant is ${o\left(1/\sqrt{n\log n}\right)}$ then there is an ${\epsilon}$-equilibrium. If it is ${O\left(1/\sqrt{n}\right)}$ then there is no ${\epsilon}$-equilibrium. What is the exact asymptotic that is required for existence of pure ${\epsilon}$-equilibrium ? Dunno. That’s one of the open problem I promised.

The proofs of these theorems are non-constructive and use the probabilistic method: For the first part, we show that that a profile that is randomly realized by a mixed equilibrium (the existence of which follows from Nash’s Theorem) is, with positive probability, a pure ${\epsilon}$-equilibrium; For the second part, we show that a random game (picked according to a carefully chosen distribution over games with small Liphshitz constant) does not admit any Nash Equilibrium.

These results are related to the literature of large games, that is games with many players. Roughly speaking, there are two models of large games in the literature, Schmeidler’s non-atomic framework in which the set of players is the continuum and the game admits pure equilibrium, and Kalai’s model of games with finite number of players and ${\epsilon}$-equilibrium. Both models are anonymous games, which means all the players have the same set of strategies and a player’s payoff is a continuous function of the distribution of strategies of her opponents, but she doesn’t care which of the opponents played which strategy. Our games are not anonymous. In fact, we show that the continuity alone, captured by a small Lipschitz constant, is what drives the result about existence of pure equilibrium. It is interesting to note that the non-atomic anonymous is in some sense a limit model of finite anonymous games. This conclusion appears for example in a recent paper of Aaron(pdf). What is a good limit model for finite non-anonymous games with vanishing Lipschitz constant ? That’s another open problem.