“On the Existence of Pure and Mixed Strategy Nash Equilibria in Discontinuous Games,” Philip J. Reny (1999)

Most of the important results about the existence of equilibria in game theory have been known since the 1950s: von Neumann on zero sum games, Nash’s famous equilibrium (which von Neumann claimed was nothing but a trivial extension!), and Glicksburg’s theorem for infinite strategy spaces. The problem is that while many of these results rely on (usually innocuous) assumptions like convexity of the strategy space and quasiconcavity the payoff function, they also rely on the (often problematic) assumption that payoffs are continuous (or upper semicontinuous) in strategies. For instance, a first price auction or an all-pay auction (under the standard “equiprobable split” tie break rule, among others) are not continuous: in a first price auction, if I bid 2 and you bid 2 minus epsilon, then I get payoff 0, but if we both bid 2, then I get payoff equal to .5 times my private value minus 2. Many other economic problems have this characteristic. Where should I locate my ice cream shop on the Hotelling beach? How should I set my price when the market is a duopoly?

Incredibly, even in 2010, there is no set of necessary and sufficient conditions for the existence of Nash equilibria in such games. One school of thought is to say, well, maybe NE is not such a useful concept in games with infinite strategy spaces, and perhaps we ought consider some sort of epsilon-equilibria. Reny, however, prefers to push on and better understand the traditional existence question. In this paper, assuming throughout compactness and quasiconcavity, he defines a concept called “better reply security”. A payoff A at strategies X* is secure if I can choose an open neighborhood around X* such that no matter what other players choose from that neighborhood, there is an own-strategy X that gives me at least payoff A. A game is better reply secure if, whenever X* (which gives utilities U*) is not an equilibrium, for every element of the closure of the utilities given from sequences of strategies approaching X*, some player can secure strictly above U*. BRS turns out to be sufficient for the existence of pure strategy Nash equilibria. The proof of this result is written in Reny’s usual terse style, but is in the end not terribly difficult. Essentially, the utility function is approximated by a function which is lower semicontinuous, but is “close enough” to the original utility to be able to detect profitable Nash deviations. A nice property of topological vector spaces allows the problem to be simplified such that the new lsc function can be approximated by continuous functions, and with continuous functions we know how to guarantee existence by Glicksburg’s Theorem.

BRS may seem a hard property to check in practice, but Reny offers the following example. Consider Bertrand with two firms. Let the opponent firm vary his price within an epsilon range from y*. Let (x*,y*) not be an equilibrium. Payoffs are continuous except around points where firms set the same price, so these are the only points we need to check. The Bertrand equilibrium is for both firms to set price equal to the cost of production. Assume cost of production is 1 and only one unit – the lowest priced one – will be sold, and (x*,y*)=(2,2). Sequences of strategies approaching (2,2) are the ones where both firms prices the same, the ones where x prices slightly lower than y and makes all the sales, and the prices where y goes slightly lower than x and gets all the sales. For any of these sequences approaching (2,2), the high price firm can lower his price epsilon to become the low cost firm and make positive profits (hence can secure strictly more than zero). So the game is BRS, and hence has a Nash equilibrium.

There is, in fact, an easier (and weaker) condition to check which guarantees existence. A game is payoff secure if whenever opponents deviate in an open neighborhood of X, I have a strategy which guarantees me at least epsilon close to my payoff under X. A game is reciprocally upper semicontinuous if, for utilities in the closure of payoffs from some sequence of strategies, the utility of at least one player in the limit goes down, then at least one player’s utility must increase. Payoff security and RUSC jointly guarantee existence. Note that RUSC is implied by continuity of the sum of payoff functions (this is immediate – just think about it for a second). So, for example, the two firm Bertrand game from above has an equilibrium since the sum of payoffs is continuous (hence the game is RUSC) and payoff security holds by the fact that any player can get at least his payoff from X by slightly lowering his price, even when opponents deviate within an epsilon range from X. These two conditions seem, in practice, easier to check than BRS.

The rest of the paper generalizes the above result to existence of mixed strategy NE and symmetric NE. You may wonder whether still more general conditions guaranteeing existence have been discovered. To my knowledge, there haven’t been any major breakthroughs in the past decade, though Reny (2009) does generalize in a minor way the paper discussed here, albeit without proofs.

http://www.jstor.org/stable/2999512 (Gated JSTOR version, I’m afraid. Why don’t active research professors put their work on their websites? It boggles my mind.)

Advertisement