<p>Condition 3 can be written in the following way: <span class="math-container">$a^\ast \in B$</span> iff for all <span class="math-container">$i$</span> and all <span class="math-container">$j$</span>
<span class="math-container">$$
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})
$$</span>
As there are no ties, this can be written as:
<span class="math-container">$$
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})
$$</span></p>
<p>If <span class="math-container">$a^\ast$</span> is a Nash equilibrium (i.e. <span class="math-container">$\in A$</span>), then  for all <span class="math-container">$i$</span> and all <span class="math-container">$a_i$</span>:
<span class="math-container">$$
u_i(a_i^\ast, a_{-i}^\ast) \ge u_i(a_i, a_{-i}^\ast)
$$</span></p>
<blockquote>
<p>Is <span class="math-container">$A \subseteq B$</span>?</p>
</blockquote>
<p>Yes. Let <span class="math-container">$a^\ast \in A$</span>. We want to show that <span class="math-container">$a^\ast \in B$</span>. To show that <span class="math-container">$a^\ast \in B$</span>, we only need to look at deviations where <span class="math-container">$a_{i,j}^\ast$</span> changes for a particular <span class="math-container">$j$</span>. Towards this end, define <span class="math-container">$a_i = (a_{i,\ell}|\ell \le J)$</span> such that:
<span class="math-container">$$
a_{i,\ell} = \left\{\begin{array}{ll} a^\ast_{i,l} &amp;\text{ if } \ell \ne j\\ 1- a_{i,j}^\ast &amp;\text{ if } \ell = j \end{array}\right.
$$</span>
So <span class="math-container">$a_i$</span> differs from <span class="math-container">$a_i^\ast$</span> only because <span class="math-container">$a_{i,j}$</span> switched value (from 1 to 0 or vice versa). To show that <span class="math-container">$a^\ast \in B$</span>, we show the two conditions.</p>
<ol>
<li>If <span class="math-container">$a_{i,j}^\ast = 1$</span> , we have:</li>
</ol>
<p><span class="math-container">$$
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).
$$</span>
The inequality follows from the definition of a Nash equilibrium. The equalities follow from how we defined <span class="math-container">$a_i$</span>.</p>
<ol start="2">
<li>If <span class="math-container">$a^\ast_{i,j} = 0$</span>, we have:</li>
</ol>
<p><span class="math-container">$$
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).
$$</span>
This shows that <span class="math-container">$a^\ast \in B$</span>.</p>
<blockquote>
<p>If <span class="math-container">$B$</span> is empty, then <span class="math-container">$A$</span> is empty?</p>
</blockquote>
<p>This follows from <span class="math-container">$A \subseteq B$</span>. If <span class="math-container">$B = \emptyset$</span> and <span class="math-container">$A$</span> is a subset of <span class="math-container">$B$</span> then immediately <span class="math-container">$A = \emptyset$</span>.</p>
<p>Notice that the inclusion can be is strict, i.e. there are cases where <span class="math-container">$A \ne B$</span>. To see this, consider the case where <span class="math-container">$J = 2$</span> and the payoff table is the following.</p>
<div class="s-table-container">
<table class="s-table">
<thead>
<tr>
<th></th>
<th>(00)</th>
<th>(01)</th>
<th>(10)</th>
<th>(11)</th>
</tr>
</thead>
<tbody>
<tr>
<td><strong>(00)</strong></td>
<td>4,4</td>
<td>1,1</td>
<td>2,2</td>
<td>4,0</td>
</tr>
<tr>
<td><strong>(01)</strong></td>
<td>2,2</td>
<td>2,3</td>
<td>1,4</td>
<td>1,0</td>
</tr>
<tr>
<td><strong>(10)</strong></td>
<td>1,4</td>
<td>3,2</td>
<td>4,3</td>
<td>2,0</td>
</tr>
<tr>
<td><strong>(11)</strong></td>
<td>0,4</td>
<td>4,0</td>
<td>0,2</td>
<td>3,3</td>
</tr>
</tbody>
</table>
</div>
<p>We have that <span class="math-container">$(11,11)$</span> is in <span class="math-container">$B$</span> but not in <span class="math-container">$A$</span> as it is not a Nash equilibrium. The only Nash equilibrium is <span class="math-container">$(00,00)$</span>.</p>

CC BY-SA 4.0
2021-05-01T15:01:49.200Z
2021-05-01T15:01:49.200Z
tdm
<p>Consider a game with <span class="math-container">$N$</span> players, each indexed by <span class="math-container">$i=1,...,N$</span>. Every player <span class="math-container">$i$</span> has to choose a <span class="math-container">$J\times 1$</span> <strong>vector</strong> of actions <span class="math-container">$a_i\equiv (a_{i,1},...,a_{i,J})$</span> where each <span class="math-container">$a_{i,j}$</span> can be <strong>zero or one</strong>. The payoff of each player <span class="math-container">$i$</span> is <span class="math-container">$u_i(a_i, a_{-i})$</span>, where <span class="math-container">$a_{-i}$</span> denotes the actions of the other players.</p>
<p>A pure strategy Nash equilibrium (PSNE) of the game is <span class="math-container">$a^*\equiv (a_1^*,...,a_N^*)$</span> solving
<span class="math-container">$$
(1) \quad a_i^*\in argmax_{a_i\in \{0,1\}^J} u_i(a_i, a^*_{-i}) \quad \forall i=1,...,N
$$</span></p>
<p>Note that if <span class="math-container">$a^*$</span> is a PSNE, then
<span class="math-container">$$
(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
$$</span>
where <span class="math-container">$a^*_i+\{a_{i,j}=1\}$</span> denotes <span class="math-container">$a^*$</span> where <span class="math-container">$a^*_{i,j}=0$</span> is replaced by one; <span class="math-container">$a^*_i+\{a_{i,j}=0\}$</span> denotes <span class="math-container">$a^*$</span> where <span class="math-container">$a^*_{i,j}=1$</span> is replaced by zero.</p>
<p><strong>Claim:</strong> Assume that ties are zero probability events. Then, an action profile <span class="math-container">$a$</span> satisfies (2) if and only if
<span class="math-container">$$
(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
$$</span></p>
<p><strong>Question:</strong> Let <span class="math-container">$A$</span> be the set of PSNE. Let <span class="math-container">$B$</span> be the set of <span class="math-container">$a$</span> satisfying (3). Is <span class="math-container">$A\subseteq B$</span>? If <span class="math-container">$B$</span> is empty, then <span class="math-container">$A$</span> is empty?</p>

CC BY-SA 4.0
2021-04-30T22:30:25.910Z
The last $N$ should be a $J$, right?
VARulle
CC BY-SA 4.0
2021-04-30T22:34:38.590Z
I edited this (and a missing bracket).
VARulle
CC BY-SA 4.0
2021-05-01T11:01:27.067Z
@user3285148 For you question, are you also assuming that ties never occur?
tdm
CC BY-SA 4.0
2021-05-01T11:32:38.133Z
Yes, ties never occur.
Star
<game-theory><nash-equilibrium>
Characterising a set of outcomes containing the collection of pure strategy Nash equilibria
Star
# Characterising a set of outcomes containing the collection of pure strategy Nash equilibria

(Asked by: username_0 on 2021-04-30)

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?

**Tags:** game-theory, nash-equilibrium

> **Comments:**
> **username_1**: The last $N$ should be a $J$, right?  
> **username_1**: I edited this (and a missing bracket).  
> **username_2**: @user3285148 For you question, are you also assuming that ties never occur?  
> **username_0**: Yes, ties never occur.  

---

## 1 answers

### Answer by username_2 on 2021-05-01. Score: 3 | Accepted answer

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)$.


---

