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 -equilibrium, which means that no player gains more than 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 –player game is given by finite sets of *strategies* and by *payoff functions* , where is the set of *strategy profiles*. As usual, we denote, for every player , the set of *opponents’ profiles* by .

Definition 1TheLipschitz constantof the game is given by

where the maximum ranges over all players , all strategies and all pairs that differ only in one coordinate.

Games with Lipschitz constant have the property that a player’s payoff does not change by more than 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 -equilibrium, and we almost pin down the asymptotic of `sufficiently small’ as a function of the number of players:

Theorem 2Fix and .

- There exists (which depends on and ) such that every -player game with actions for every player and Lipschitz constant smaller than admits pure -equilibrium.
- There exists such that for every large enough there exists an -player game with actions for every player and Lipschitz constant smaller than without pure -equilibrium.

See, for sufficiently large , if the Lipschitz constant is then there is an -equilibrium. If it is then there is no -equilibrium. What is the exact asymptotic that is required for existence of pure -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 -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 -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.

## 5 comments

October 5, 2010 at 5:53 pm

Brouwer, Tarski and the existence of Nash Equilibrium « The Leisure of the Theory Class[…] 5, 2010 by Eran This post is a sequel to my previous ad of a joint paper with Yaron, in which we prove existence of pure -equilibria in certain games. I am […]

October 6, 2010 at 12:07 am

GregLooks interesting. However, I am not sure I buy the motivation in the first two paragraphs. Sure, mixed Nash equilibrium (NE) may be less convincing than pure NE, but similarly pure epsilon-NE is less convincing than pure NE. Is there a reason why one should prefer pure epsilon-NE to mixed NE?

October 24, 2010 at 11:33 pm

Albert JiangHi Eran,

You might be interested in some of the related literature in computer science on the existence of approximate Nash equilibria with small support. Instead of controlling the lipshitz constant, they consider mixed strategies with small support. But the proof strategies might be related as they also use the probabilistic method.

Lipton, Markakis & Mehta, Playing Large Games with Simple Strategies

Hémon , Rougemont & Santha, Approximate Nash Equilibria for Multi-player Games

(see especially the use of McDiarmid’s inequality in Theorem 4 of this paper)

October 25, 2010 at 11:22 pm

Eranthanks ! i didn’t know about these papers

March 9, 2011 at 3:52 pm

Epsilon credible threats « The Leisure of the Theory Class[…] I strongly prefer strong -equilibrium. As I explained in another blog, I don’t care much for the idea that players toss coins to decide which action to play. The […]