Characterising a set of outcomes containing the collection of pure strategy Nash equilibria

Question

Consider a game with $N$ players, each indexed by $i=1,...,N$. Every player $i$ has to choose a $J\times 1$ vector of actions $a_i\equiv (a_{i,1},...,a_{i,J})$ where each $a_{i,j}$ can be zero or one. The payoff of each player $i$ is $u_i(a_i, a_{-i})$, where $a_{-i}$ denotes the actions of the other players.

A pure strategy Nash equilibrium (PSNE) of the game is $a^*\equiv (a_1^*,...,a_N^*)$ solving $$ (1) \quad a_i^*\in argmax_{a_i\in \{0,1\}^J} u_i(a_i, a^*_{-i}) \quad \forall i=1,...,N $$

Note that if $a^*$ is a PSNE, then $$ (2) \quad \text{If $a^*_{i,j}$=0, then } u_i(a^*_i, a^*_{-i})\geq u_i(a^*_i+\{a_{i,j}=1\}, a^*_{-i})\\ \quad \quad \text{If $a^*_{i,j}$=1, then } u_i(a^*_i, a^*_{-i})\geq u_i(a^*_i+\{a_{i,j}=0\}, a^*_{-i})\\ \forall i=1,...,N \quad \forall j=1,...,J $$ where $a^*_i+\{a_{i,j}=1\}$ denotes $a^*$ where $a^*_{i,j}=0$ is replaced by one; $a^*_i+\{a_{i,j}=0\}$ denotes $a^*$ where $a^*_{i,j}=1$ is replaced by zero.

Claim: Assume that ties are zero probability events. Then, an action profile $a$ satisfies (2) if and only if $$ (3) \quad a_{i,j}=1\{u_i(a_i+\{a_{i,j}=1\}, a_{-i})- u_i(a_i+\{a_{i,j}=0\}, a_{-i})\geq 0\}\\ \forall i=1,...,N \quad \forall j=1,...,J $$

Question: Let $A$ be the set of PSNE. Let $B$ be the set of $a$ satisfying (3). Is $A\subseteq B$? If $B$ is empty, then $A$ is empty?

Answer 1

Condition 3 can be written in the following way: $a^\ast \in B$ iff for all $i$ and all $j$ $$ a^\ast_{i,j} = 1 \iff u_i(a_i^\ast + \{a_{i,j} = 1\}, a^\ast_{-i}) \ge u_i(a_i^\ast + \{a_{i,j} = 0\}, a^\ast_{-i}) $$ As there are no ties, this can be written as: $$ a^\ast_{i,j} = 1 \to u_i(a_i^\ast + \{a_{i,j} = 1\}, a^\ast_{-i}) \ge u_i(a_i^\ast + \{a_{i,j} = 0\}, a^\ast_{-i}),\\ a^\ast_{i,j} = 0 \to u_i(a_i^\ast + \{a_{i,j} = 0\}, a^\ast_{-i}) \ge u_i(a_i^\ast + \{a_{i,j} = 1\}, a^\ast_{-i}) $$

If $a^\ast$ is a Nash equilibrium (i.e. $\in A$), then for all $i$ and all $a_i$: $$ u_i(a_i^\ast, a_{-i}^\ast) \ge u_i(a_i, a_{-i}^\ast) $$

Is $A \subseteq B$?

Yes. Let $a^\ast \in A$. We want to show that $a^\ast \in B$. To show that $a^\ast \in B$, we only need to look at deviations where $a_{i,j}^\ast$ changes for a particular $j$. Towards this end, define $a_i = (a_{i,\ell}|\ell \le J)$ such that: $$ a_{i,\ell} = \left\{\begin{array}{ll} a^\ast_{i,l} &\text{ if } \ell \ne j\\ 1- a_{i,j}^\ast &\text{ if } \ell = j \end{array}\right. $$ So $a_i$ differs from $a_i^\ast$ only because $a_{i,j}$ switched value (from 1 to 0 or vice versa). To show that $a^\ast \in B$, we show the two conditions.

1. If $a_{i,j}^\ast = 1$ , we have:

$$ u_i(a_i^\ast, a_{-i}^\ast) = u_i(a_i^\ast + \{a_{i,j} = 1\}, a_{-i}^\ast),\\ \ge u_i(a_i, a_{-i}^\ast) = u_i(a_i^\ast + \{a_{i,j} = 0\}, a_{-i}^\ast). $$ The inequality follows from the definition of a Nash equilibrium. The equalities follow from how we defined $a_i$.

2. If $a^\ast_{i,j} = 0$, we have:

$$ u_i(a_i^\ast, a_{-i}^\ast) = u_i(a_i^\ast + \{a_{i,j} = 0\}, a_{-i}^\ast),\\ \ge u_i(a_i, a_{-i}^\ast) = u_i(a_i^\ast + \{a_{i,j} = 1\}, a_{-i}^\ast). $$ This shows that $a^\ast \in B$.

If $B$ is empty, then $A$ is empty?

This follows from $A \subseteq B$. If $B = \emptyset$ and $A$ is a subset of $B$ then immediately $A = \emptyset$.

Notice that the inclusion can be is strict, i.e. there are cases where $A \ne B$. To see this, consider the case where $J = 2$ and the payoff table is the following.

	(00)	(01)	(10)	(11)
(00)	4,4	1,1	2,2	4,0
(01)	2,2	2,3	1,4	1,0
(10)	1,4	3,2	4,3	2,0
(11)	0,4	4,0	0,2	3,3

We have that $(11,11)$ is in $B$ but not in $A$ as it is not a Nash equilibrium. The only Nash equilibrium is $(00,00)$.