Equilibrium in discontinuous games without complete or transitive preferences

Abstract

Reny (Econ Theory, 2015) is used here to prove the existence of equilibrium in discontinuous games in which the players’ preferences need be neither complete nor transitive. The proof adapts important ideas from Shafer and Sonnenschein (J Math Econ 2:345–348, 1975).

1 Preliminaries

Let us briefly review one of the results in Reny (2015) that will be used here.

Let N be a finite set of players. For each $i\in N,$ let $X_{i}$ denote player i’s set of pure strategies which we assume is a nonempty, compact, convex, locally convex, subset of a Hausdorff topological vector space, and let $\ge _{i}$ denote player i’s preference relation, which we assume is a complete, reflexive, and transitive binary relation on $X=\times _{i\in N}X_{i}$. Let $G=(X_{i},\ge _{i})_{i\in N}$ denote the resulting game.

A strategy $x^{*}\in X$ is a (pure strategy) Nash equilibrium of G iff $x^{*}\ge _{i}(x_{i},x_{-i}^{*})$ for every $x_{i}\in X_{i}$ and for every $i\in N.$

For any subset I of the set of players N, let $B_{I}$ denote the set of strategies $x\in X$ at which every player $j\in N\backslash I$ is playing a best reply, i.e., $B_{I}=\{x\in X:\forall j\in N\backslash I,$ $x\ge _{j}(x_{j}^{\prime },x_{-j})$ $\forall x_{j}^{\prime }\in X_{j}\}.$ Note that $B_{N}=X$ and that $B_{\emptyset }$ is the set of pure strategy Nash equilibria of G.

For any set A,  let coA denote its convex hull. The definitions and theorem below are taken from Reny (2015).

Definition 1.1

The game $G=(X_{i},\ge _{i})_{i\in N}$ is point secure with respect to $I\subseteq N$ if whenever $x\in B_{I}$ is not a Nash equilibrium there is a neighborhood U of x and a point $\hat{x}\in X$ such that for every $y\in U\cap B_{I}$ there is a player $i\in I$ for whom,

$$\begin{aligned} y_{i}\notin co\{w_{i}:(w_{i},y_{-i})\ge _{i}(\hat{x}_{i},x_{-i}^{\prime })\},\quad \text { for every }x^{\prime }\text { in }U\cap B_{I}. \end{aligned}$$

Say that a correspondence $F:Y\twoheadrightarrow Z$ is co-closed if the correspondence whose value is coF(y) for each $y\in Y$ has a closed graph.¹ Requiring F to be co-closed does not require it to be convex-valued or to have a closed graph.²

Definition 1.2

The game $G=(X_{i},\ge _{i})_{i\in N}$ is correspondence secure with respect to $I\subseteq N$ if whenever $x\in B_{I}$ is not a Nash equilibrium there is neighborhood U of x and a co-closed correspondence $d:U\twoheadrightarrow X$ with nonempty values such that for every $y\in U\cap B_{I}$ there is a player $i\in I$ for whom,

$$\begin{aligned} y_{i}\notin co\{w_{i}:(w_{i},y_{-i})\ge _{i}(z_{i},x_{-i}^{\prime })\} \end{aligned}$$

holds for every $x^{\prime }\in U\cap B_{I}$ and every $z_{i}\in d_{i}(x^{\prime }).$

Theorem 1.3

Suppose that G is correspondence secure with respect to $I\subseteq N.$ If for each $i\in N\backslash I,$ player i’s best-reply correspondence has a closed graph and has nonempty and convex values, then G possesses a pure strategy Nash equilibrium.

2 An application to abstract games

We demonstrate here how Theorem 1.3 can be applied to yield a new result in settings in which preferences are neither complete nor transitive. Following Shafer and Sonnenschein (1975), for any strategy tuple $x\in X$ and for each player i the (possibly empty) set $P_{i}(x)$ contains those $z_{i}$ in $X_{i}$ such that $(z_{i},x_{-i})$ is strictly preferred by i to x. Preferences are not specified any further than this and hence need be neither complete nor transitive. Shafer and Sonnenschein (1975) further permit a player’s feasible set of strategies to depend upon all of the players’ strategies. This second feature is captured by endowing each player i with a feasibility correspondence $\mathcal {A}_{i}:X\twoheadrightarrow X_{i},$ where for any strategy tuple $x\in X,$ player i’s feasible choices are restricted to the set $\mathcal {A} _{i}(x)\subseteq X_{i}.$ These combine to yield an abstract game $\Gamma =(X_{i},\mathcal {A}_{i},P_{i})_{i=1}^{N}$.

A (pure) strategy $x\in X$ is an equilibrium of $\Gamma$ if for every player i,  $x_{i}\in \mathcal {A}_{i}(x)$ and $\mathcal {A}_{i}(x)\cap P_{i}(x)$ is empty. Shafer and Sonnenschein’s main result is as follows.

Theorem 2.1

[Shafer and Sonnenschein (1975)]. Let $(X_{i},\mathcal {A} _{i},P_{i})_{i=1}^{N}$ be an abstract game satisfying,

• (a) Each $X_{i}$ is a nonempty compact and convex subset of $\mathbb {R}^{n}$,

• (b) each $\mathcal {A}_{i}:X\twoheadrightarrow X_{i}$ is a nonempty-valued, convex-valued, continuous correspondence,

• (c) for each player i and each $x\in X$, $x_{i}\notin \mathcal {A} _{i}(x)\cap coP_{i}(x)$,³ and

• (d) each $P_{i}$ has an open graph in $X\times X_{i}$.

  Then an equilibrium exists.

We will generalize Theorem 2.1 by relaxing the assumption that each $P_{i}$ has an open graph (thereby allowing some discontinuities) and by allowing infinite dimensional strategy spaces. The idea of the proof is to construct a standard game G satisfying the hypotheses of Theorem and whose equilibria yield equilibria of the abstract game. The game we construct is discontinuous but the incentives provided are similar to those provided by the continuous surrogate utilities constructed the proof in Shafer and Sonnenschein (1975).

Theorem 2.2

Let $(X_{i},\mathcal {A}_{i},P_{i})_{i=1}^{N}$ be an abstract game satisfying,

• (a) Each $X_{i}$ is a nonempty, compact, convex subset of a locally convex topological vector space,

• (b) each $\mathcal {A}_{i}:X\twoheadrightarrow X_{i}$ is a nonempty-valued, convex-valued, continuous correspondence,

• (c) for each player i and each $x\in X$, $x_{i}\notin \mathcal {A} _{i}(x)\cap coP_{i}(x)$, and

• (d) whenever $x\in \times _{i}\mathcal {A}_{i}(x)$ is not an equilibrium, there is a neighborhood U of x, a player i,  and a co-closed correspondence $d_{i}:U \twoheadrightarrow X_{i}$ with nonempty values such that $d_{i}(x^{\prime })\subseteq P_{i}(x^{\prime })\cap \mathcal {A}_{i}(x^{\prime })$ for every $x^{\prime }$ in U. Then an equilibrium exists.

Remark 1

Note that (d) is satisfied if each $P_{i}$ has an open graph because if $x\in \times _{i}\mathcal {A}_{i}(x)$ is not an equilibrium, then for some player i there exists $\hat{x}_{i}\in P_{i}(x)\cap \mathcal {A}_{i}(x).$ The continuity of $\mathcal {A}_{i}$ and the open graph of $P_{i}$ imply that there is a convex neighborhood (by local convexity) $U_{i}$ of $\hat{x}_{i}$ and a neighborhood U of x,  such that⁴ $\emptyset \ne \mathcal {A} _{i}(x^{\prime })\cap clU_{i}\subseteq P_{i}(x^{\prime })$ for every $x^{\prime }\in U.$ Hence (d) is satisfied by setting $d_{i}(x^{\prime })= \mathcal {A}_{i}(x^{\prime })\cap clU_{i}$.

Remark 2

Condition (d) permits some discontinuities but fails, for example, for Bertrand duopoly.

Proof of Theorem 2.2

Define a game G as follows. Player A chooses $y\in X$ and players $i\in N$ choose $x_{i}\in X_{i}.$ Player A’s payoff is $u_{A}(x,y)=1$ if $y=x,$ and is 0 otherwise, and the payoff to any player $i\in N$ is,

$$\begin{aligned} u_{i}(x,y)=\left\{ \begin{array}{c} 1, \\ 0, \\ -1, \end{array} \right. \left. \begin{array}{l} \text {if }x_{i}\in P_{i}(y)\cap \mathcal {A}_{i}(y) \\ \text {if }x_{i}\in \mathcal {A}_{i}(y)\backslash P_{i}(y) \\ \text {if }x_{i}\notin \mathcal {A}_{i}(y)\text {.} \end{array} \right. \end{aligned}$$

This completes the description of G.

If (x, y) is an equilibrium of G,  then optimization by players $i\in N$ implies each $x_{i}\in \mathcal {A}_{i}(y)$ and optimization by player A implies $y=x$. Hence, $x_{i}\in \mathcal {A}_{i}(x)$ for $i\in N.$ Because by hypothesis $x_{i}\notin \mathcal {A}_{i}(x)\cap coP_{i}(x)$ for each $i\in N$ we have a fortiori that $x_{i}\notin \mathcal {A}_{i}(x)\cap P_{i}(x)$ and hence that $u_{i}(x,x)=0$ for $i\in N.$ But equilibrium in G requires $u_{i}((x_{i}^{\prime },x_{-i}),x)\le u_{i}(x,x)=0$ for every $x_{i}^{\prime }\in X_{i}$ and every $i\in N$ from which we conclude that $P_{i}(x)\cap \mathcal {A}_{i}(x)$ is empty for every $i\in N.$ Hence, if (x, y) is an equilibrium of G,  then x is an equilibrium of the abstract game. By Theorem 1.3, it therefore suffices to show that G,  with player set $N\cup \{A\},$ is correspondence secure with respect to N.

Because $B_{\{A\}},$ the set of $(x,y)\in X\times X$ at which player A is best replying is the diagonal of $X\times X,$ the condition that G is correspondence secure with respect to N reduces to the following. For every $x\in X$ that is not an equilibrium of the original abstract game, there is a neighborhood $U\subseteq X$ of x and a co-closed correspondence $d:U\twoheadrightarrow X$ with nonempty values such that for every $y\in U$ there is a player $i\in N$ for whom

$$\begin{aligned} y_{i}\notin co\{w_{i}:u_{i}((w_{i},y_{-i}),y)\ge u_{i}((z_{i},x_{-i}^{\prime }),x^{\prime })\} \end{aligned}$$

(1)

holds for every $x^{\prime }$ in U and every $z_{i}$ in $d_{i}(x^{\prime }).$ Thus, it suffices to verify this condition.

Suppose then that $x\in X$ is not a Nash equilibrium of the abstract game. Let $\mathcal {A}~=\times _{i}\mathcal {A}_{i}.$ There are two cases. Either $x\in \mathcal {A}(x)$ or not. If not, then because $\mathcal {A}$ is closed, there is a neighborhood U containing x such that $y\notin \mathcal {A}(y)$ holds for every y in U. Set $d(y)=\mathcal {A}(y)$ for y in U. For every y in U there is a player i for whom $y_{i}\notin \mathcal {A} _{i}(y).$ Evidently, $u_{i}((z_{i},x_{-i}^{\prime }),x^{\prime })\ge 0$ for every $x^{\prime }\in U$ and every $z_{i}\in d_{i}(x^{\prime })=\mathcal {A} _{i}(x^{\prime }).$ Hence, $\{w_{i}:u_{i}((w_{i},y_{-i}),y)\ge u_{i}((z_{i},x_{-i}^{\prime }),x^{\prime })\}$ is contained in $\{w_{i}:u_{i}((w_{i},y_{-i}),y)\ge 0\}=\mathcal {A}_{i}(y)$ and () follows because $\mathcal {A}_{i}(y)$ is convex and $y_{i}\notin \mathcal {A}_{i}(y).$

On the other hand, suppose that $x\in \mathcal {A}(x).$ Then by hypothesis, there is a neighborhood U of x,  a player i and a co-closed $d_{i}:U\twoheadrightarrow X_{i}$ with nonempty values such that $d_{i}(x^{\prime })\subseteq P_{i}(x^{\prime })\cap \mathcal {A}_{i}(x^{\prime })$ for every $x^{\prime }$ in U. Consequently, $u_{i}((z_{i},x_{-i}^{ \prime }),x^{\prime })=1$ for every $x^{\prime }$ in U and every $z_{i}$ in $d_{i}(x^{\prime }).$ Hence, $\{w_{i}:u_{i}((w_{i},y_{-i}),y)\ge u_{i}((z_{i},x_{-i}^{\prime }),x^{\prime })\}=\{w_{i}:u_{i}((w_{i},y_{-i}),y)=1\}=\mathcal {A}_{i}(y)\cap P_{i}(y),$ and so (1) follows because $y_{i}\notin \mathcal {A} _{i}(y)\cap coP_{i}(y).$ $\square$