Editing Nash equilibrium (section)

=== Alternate proof using the Brouwer fixed-point theorem ===

We have a game <math>G=(N,A,u)</math> where <math>N</math> is the number of players and <math>A = A_1 \times \cdots \times A_N</math> is the action set for the players. All of the action sets <math>A_i</math> are finite. Let <math>\Delta = \Delta_1 \times \cdots \times \Delta_N</math> denote the set of mixed strategies for the players. The finiteness of the <math>A_i</math>s ensures the compactness of <math>\Delta</math>.

We can now define the gain functions. For a mixed strategy <math>\sigma \in \Delta</math>, we let the gain for player <math>i</math> on action <math>a \in A_i</math> be
<math display="block">\text{Gain}_i(\sigma,a) = \max \{0, u_i(a, \sigma_{-i}) - u_i(\sigma_{i}, \sigma_{-i})\}.</math>

The gain function represents the benefit a player gets by unilaterally changing their strategy. We now define <math>g = (g_1,\dotsc,g_N)</math> where
<math display="block">g_i(\sigma)(a) = \sigma_i(a) + \text{Gain}_i(\sigma,a)</math>
for <math>\sigma \in \Delta, a \in A_i</math>. We see that
<math display="block">\sum_{a \in A_i} g_i(\sigma)(a) = \sum_{a \in A_i} \sigma_i(a) + \text{Gain}_i(\sigma,a) = 1 + \sum_{a \in A_i} \text{Gain}_i(\sigma,a) > 0.</math>

Next we define:
<math display="block">\begin{cases} f = (f_1, \cdots, f_N)  : \Delta \to \Delta \\ f_i(\sigma)(a) = \frac{g_i(\sigma)(a)}{\sum_{b \in A_i} g_i(\sigma)(b)} & a \in A_i \end{cases}</math>

It is easy to see that each <math>f_i</math> is a valid mixed strategy in <math>\Delta_i</math>. It is also easy to check that each <math>f_i</math> is a continuous function of <math>\sigma</math>, and hence <math>f</math> is a continuous function. As the cross product of a finite number of compact convex sets, <math>\Delta</math> is also compact and convex. Applying the Brouwer fixed point theorem to <math>f</math> and <math>\Delta</math> we conclude that <math>f</math> has a fixed point in <math>\Delta</math>, call it <math>\sigma^*</math>. We claim that <math>\sigma^*</math> is a Nash equilibrium in <math>G</math>. For this purpose, it suffices to show that
<math display="block"> \forall i \in \{1, \cdots, N\}, \forall a \in A_i: \quad \text{Gain}_i(\sigma^*,a) = 0.</math>

This simply states that each player gains no benefit by unilaterally changing their strategy, which is exactly the necessary condition for a Nash equilibrium.

Now assume that the gains are not all zero. Therefore, <math>\exists i \in \{1, \cdots, N\},</math> and <math>a \in A_i</math> such that <math>\text{Gain}_i(\sigma^*, a) > 0</math>. Then
<math display="block"> \sum_{a \in A_i} g_i(\sigma^*, a) = 1 + \sum_{a \in A_i} \text{Gain}_i(\sigma^*,a) > 1.</math>

So let
<math display="block">C = \sum_{a \in A_i} g_i(\sigma^*, a).</math>

Also we shall denote <math>\text{Gain}(i,\cdot)</math> as the gain vector indexed by actions in <math>A_i</math>. Since <math>\sigma^*</math> is the fixed point we have:
<math display="block">\begin{align}
\sigma^* = f(\sigma^*)  &\Rightarrow  \sigma^*_i =  f_i(\sigma^*) \\
&\Rightarrow \sigma^*_i = \frac{g_i(\sigma^*)}{\sum_{a \in A_i} g_i(\sigma^*)(a)} \\ [6pt]
&\Rightarrow \sigma^*_i = \frac{1}{C} \left (\sigma^*_i + \text{Gain}_i(\sigma^*,\cdot) \right ) \\ [6pt]
&\Rightarrow C\sigma^*_i = \sigma^*_i + \text{Gain}_i(\sigma^*,\cdot) \\
&\Rightarrow \left(C-1\right)\sigma^*_i = \text{Gain}_i(\sigma^*,\cdot) \\
&\Rightarrow \sigma^*_i = \left(\frac{1}{C-1}\right)\text{Gain}_i(\sigma^*,\cdot).
\end{align}</math>

Since <math>C > 1</math> we have that <math>\sigma^*_i</math> is some positive scaling of the vector <math>\text{Gain}_i(\sigma^*,\cdot)</math>. Now we claim that
<math display="block">\forall a \in A_i: \quad  \sigma^*_i(a)(u_i(a_i, \sigma^*_{-i}) - u_i(\sigma^*_i, \sigma^*_{-i})) = \sigma^*_i(a)\text{Gain}_i(\sigma^*, a) </math>

To see this, first if <math>\text{Gain}_i(\sigma^*, a) > 0</math> then this is true by definition of the gain function. Now assume that <math>\text{Gain}_i(\sigma^*, a) = 0</math>. By our previous statements we have that
<math display="block">\sigma^*_i(a) = \left(\frac{1}{C-1}\right)\text{Gain}_i(\sigma^*, a) = 0 </math>

and so the left term is zero, giving us that the entire expression is <math>0</math> as needed.

So we finally have that
<math display="block">\begin{align}
0 &= u_i(\sigma^*_i, \sigma^*_{-i}) - u_i(\sigma^*_i, \sigma^*_{-i}) \\
  &=  \left(\sum_{a \in A_i} \sigma^*_i(a)u_i(a_i, \sigma^*_{-i})\right) - u_i(\sigma^*_i, \sigma^*_{-i}) \\
 & =  \sum_{a \in A_i} \sigma^*_i(a) (u_i(a_i, \sigma^*_{-i}) - u_i(\sigma^*_i, \sigma^*_{-i})) \\ 
 & = \sum_{a \in A_i} \sigma^*_i(a) \text{Gain}_i(\sigma^*, a) && \text{ by the previous statements } \\
  &= \sum_{a \in A_i} \left( C -1 \right) \sigma^*_i(a)^2 > 0
\end{align}</math>

where the last inequality follows since <math>\sigma^*_i</math> is a non-zero vector. But this is a clear contradiction, so all the gains must indeed be zero. Therefore, <math>\sigma^*</math> is a Nash equilibrium for <math>G</math> as needed.