Existence of equilibrium in games with non-convex best-response correspondence

fixed-point-theoremsgame theorynash-equilibrium

Consider a two-player game where player 1 chooses $a\in[0,1]$, player 2 chooses $b\in[0,1]$ and the payoffs are two functions $f,g:[0,1]^2\to \mathbb{R}$ (resp.) which are $C^2$. We focus on player 1 but everything is also true for Player 2 ($f$ and $g$ are very similar).

The sign of the derivatives of $f$ w.r.t. to $a$ is unknown. In particular, it is not known whether $\tfrac{\partial^2 f}{\partial a^2}<0$ so it is not clear that the best-response correspondence $b\to argmax f(x,b)$ is convex valued and thus the standard fixed point theorems are not helpful.

However, I do know that $\tfrac{\partial f}{\partial b}<0$, $\tfrac{\partial^2 f}{\partial b^2}>0$ and $\tfrac{\partial^2 f}{\partial a\partial b}>0$ in the entire domain $[0,1]^2$.

The question is whether it is enough to ensure the existence of equilibrium or, if not, what would be a simple modification that ensures such existence?

For example, from $\tfrac{\partial^2 f}{\partial a\partial b}>0$ I can deduce that the BR correspondence is increasing, so if $a^*$ is a best response to some $b$, it is not a best response to any other $b$, and the best response to $b'>b$ is higher than $a^*$. This means (along with a similar argument for player 2) that any equilibrium must be at points where the BR correspondence returns a singleton.

Best Answer

The following is a special case of the Tarski fixed point theorem.

Let $F: [0,1]^2 \to [0,1]^2$ such that $(a',b') \ge (a,b)$ implies $F(a',b') \ge F(a,b)$. Then $F$ has a fixed point.

Note: In the above, we say $(x',y')\ge (x,y)$ if and only if both $x' \ge x$ and $y' \ge y$.

So in particular, if $F(a,b) = \big(BR_1(b), BR_2(a)\big)$ where both $BR_i(\cdot)$ are nondecreasing functions from $[0,1]\to [0,1]$, then $F$ satisfies the conditions needed and you're guaranteed an equilibrium.


More generally, this type of problem is an example of a supermodular game. For some nice notes on these, see here. The appeal of these kind of results is that you don't need (in general) smoothness or even continuity type conditions on your model primitives. The order-theoretic property of best-responses being 'weakly increasing' turns out to be enough to get equilibrium (and there's a wealth of useful results about comparative statics, convergence of various processes to equilibrium and so forth). The classical references are:

  • Milgrom & Roberts (1990) “Rationalizability and Learning in Games with Strategic Complementarities”
  • Milgrom & Shannon (1994) "Monotone Comparative Statics"