A single-file HTML note on solution concepts and equilibrium existence, and expanded using the study questions that came up in discussion: Nash equilibrium, mixed strategies, correlated equilibrium, Kakutani, Wardrop equilibrium, and existence results for finite and infinite games.
A strategic-form game is
\[ G = \bigl(I, (S_i)_{i \in I}, (u_i)_{i \in I}\bigr), \]where \(I\) is the set of players, \(S_i\) is player \(i\)'s strategy set, and \(u_i : \prod_{j\in I} S_j \to \mathbb{R}\) is player \(i\)'s payoff.
A mixed strategy of player \(i\) is a probability distribution over \(S_i\):
\[ \sigma_i \in \Delta(S_i). \]If players randomize independently, the mixed-strategy profile is \(\sigma=(\sigma_i)_{i\in I}\in \prod_i \Delta(S_i)\), and expected payoff is
\[ u_i(\sigma) = \sum_{s \in S} \left(\prod_{j\in I}\sigma_j(s_j)\right) u_i(s). \]| Player 1 \ Player 2 | H | T |
|---|---|---|
| H | (1,-1) | (-1,1) |
| T | (-1,1) | (1,-1) |
No pure Nash equilibrium. In every cell, one player wants to switch.
Let \(q\) be the probability that player 2 plays \(H\). Player 1 must be indifferent between \(H\) and \(T\):
\[ u_1(H,q) = q(1) + (1-q)(-1) = 2q-1, \] \[ u_1(T,q) = q(-1) + (1-q)(1) = 1-2q. \]Set them equal:
\[ 2q-1 = 1-2q \quad \Longrightarrow \quad q=\tfrac12. \]By symmetry, player 2 is indifferent only if player 1 also chooses \(H\) with probability \(p=\tfrac12\).
In a mixed Nash equilibrium, players randomize independently. A correlated equilibrium allows a joint distribution over action profiles, so recommendations can be statistically related.
A mediator draws a random pure profile \(R=(R_1,\dots,R_n)\) from a joint distribution \(\pi \in \Delta(S)\). Player \(i\) sees only the recommendation \(R_i\).
After seeing \(R_i=s_i\), player \(i\) forms a posterior belief about the others' recommendations and decides whether following \(s_i\) is optimal.
Write the full profile as \(s=(s_i,s_{-i})\). Once \(s_i\) is fixed, the event \(R=s\) is exactly the same as the event \(R_{-i}=s_{-i}\). So
\[ \Pr(R=s \mid R_i=s_i) = \Pr(R_{-i}=s_{-i} \mid R_i=s_i). \]The lecture writes \(R=s\) because \(\pi\) is defined on the full profile space \(S\), but conceptually the conditioning is about beliefs over \(s_{-i}\).
Using conditional probability,
\[ \Pr(R=s \mid R_i=s_i) = \frac{\pi(s_i,s_{-i})}{\sum_{t_{-i}\in S_{-i}} \pi(s_i,t_{-i})}. \]If \(\Pr(R_i=s_i)>0\), multiplying both sides by the denominator gives the equivalent condition
\[ \sum_{s_{-i}\in S_{-i}} \pi(s_i,s_{-i}) \bigl[u_i(s_i,s_{-i}) - u_i(t_i,s_{-i})\bigr] \ge 0. \]This is useful because it is linear in \(\pi\), which is why the set of correlated equilibria is convex.
| Player 1 \ Player 2 | L | R |
|---|---|---|
| U | (5,1) | (0,0) |
| D | (4,4) | (1,5) |
There are two pure Nash equilibria: \((U,L)\) and \((D,R)\).
To find the mixed equilibrium, let player 1 choose \(U\) with probability \(p\), and player 2 choose \(L\) with probability \(q\).
\[ u_1(U,q)=5q,\qquad u_1(D,q)=4q + 1(1-q)=1+3q. \] \[ 5q = 1+3q \quad\Longrightarrow\quad q=\tfrac12. \] \[ u_2(L,p)=1p + 4(1-p)=4-3p, \] \[ u_2(R,p)=0p + 5(1-p)=5-5p. \] \[ 4-3p = 5-5p \quad\Longrightarrow\quad p=\tfrac12. \]So the mixed equilibrium gives each player expected payoff \(5/2\).
Suppose a public coin recommends:
Expected payoff becomes
\[ \tfrac12(5,1) + \tfrac12(1,5) = (3,3). \]Why follow the recommendation?
| Fact | Why it is true |
|---|---|
| Every mixed Nash equilibrium is a correlated equilibrium | Independent randomization is a special case of a joint distribution over profiles. |
| The set of correlated equilibria is convex | The defining inequalities are linear in \(\pi\). |
| The CE set contains the convex hull of mixed Nash equilibria | Because mixed Nash equilibria are inside the CE set and the CE set is convex. |
Do not search directly for \(\sigma^*\). Instead, define the best-response correspondence \(B\) and look for a fixed point:
\[ \sigma^* \in B(\sigma^*). \]If that happens, each player's mixed strategy is a best response to the others, which is exactly the definition of a mixed Nash equilibrium.
The full proof appears in Section 5 below, after Section 4 on Wardrop equilibrium.
Wardrop equilibrium is the network-flow analogue of Nash equilibrium when there is a continuum of infinitesimal users, such as many drivers in traffic.
Let \(f_p\) be the flow on path \(p\), and let \(c_p(f)\) be the cost of that path under total flow vector \(f\). A feasible flow \(f\) is a Wardrop equilibrium if
\[ f_p > 0 \quad \Longrightarrow \quad c_p(f) \le c_q(f)\ \text{for every feasible path } q. \]So any route that carries positive flow must be a cheapest route.
In the pricing-congestion model from the lecture, provider \(i\) chooses a price \(p_i\), link \(i\) has latency \(l_i(x_i)\), and the effective cost of using link \(i\) is
\[ p_i + l_i(x_i). \]With total demand \(d\) and reservation utility \(R\), a flow vector \(x=(x_i)_{i=1}^I\) is a Wardrop equilibrium if
\[ \sum_{i=1}^I x_i \le d, \] \[ p_i + l_i(x_i) = \min_j \{p_j + l_j(x_j)\} \quad \text{for all } i \text{ with } x_i > 0, \] \[ p_i + l_i(x_i) \le R \quad \text{for all } i \text{ with } x_i > 0, \]and if the minimal effective cost is strictly below \(R\), then all traffic is served:
\[ \sum_{i=1}^I x_i = d. \]Wardrop equilibrium is like Nash equilibrium for infinitely many negligible users. A single user cannot noticeably change congestion, so the relevant deviation is an infinitesimal switch of mass from one route to another.
This is the detailed fixed-point proof behind Nash's theorem. The main idea is not just a checklist of lemmas: it is a reusable existence pattern. Build a strategy space with the right topological shape, turn equilibrium into a fixed-point problem, and then use Kakutani to force a self-consistent profile.
Convex set. A set \(C\subseteq \mathbb{R}^m\) is convex if for all \(x,y\in C\) and every \(\lambda\in[0,1]\),
\[ \lambda x + (1-\lambda)y \in C. \]Standard simplex. The standard \(n\)-simplex is
\[ \Delta_n = \left\{p\in \mathbb{R}^{n+1} : p_k \ge 0 \text{ for all } k,\ \sum_{k=0}^n p_k = 1\right\}. \]For a player with \(|S_i|=m_i\) pure actions, the mixed-strategy set is exactly a standard simplex:
\[ \Sigma_i = \Delta(S_i) \cong \left\{p_i\in \mathbb{R}^{m_i} : p_i(a_i)\ge 0,\ \sum_{a_i\in S_i} p_i(a_i)=1\right\}. \]Compactness. In finite-dimensional Euclidean space, a set is compact if and only if it is closed and bounded. So each simplex \(\Sigma_i\) is compact because it is a closed and bounded subset of \(\mathbb{R}^{m_i}\).
Homeomorphism. A map \(h:A\to B\) between topological spaces is a homeomorphism if it is bijective, continuous, and \(h^{-1}:B\to A\) is also continuous. In that case, \(A\) and \(B\) have the same topological shape.
Correspondence. A correspondence \(B:X \rightrightarrows X\) assigns to each \(x\in X\) a set \(B(x)\subseteq X\), not a single point. This is necessary because best responses need not be unique.
Closed graph. The graph of \(B\) is
\[ \operatorname{Graph}(B)=\{(x,y)\in X\times X : y\in B(x)\}. \]We say \(B\) has a closed graph if whenever \(x^n\to x\), \(y^n\to y\), and \(y^n\in B(x^n)\) for all \(n\), then \(y\in B(x)\).
Why homeomorphism matters for fixed points. If \(h:A\to B\) is a homeomorphism and \(f:A\to A\) is continuous, then
\[ g = h\circ f\circ h^{-1}:B\to B \]is continuous, and \(g(y)=y\) if and only if \(f(h^{-1}(y))=h^{-1}(y)\). So fixed points are transported by homeomorphisms. This is why Brouwer is often proved on a standard simplex or ball and then transferred to any homeomorphic model. In this note, however, we apply Kakutani directly on \(\Sigma\), so no explicit homeomorphism is needed for the Nash proof itself.
For each player \(i\), define the simplex of mixed strategies
\[ \Sigma_i = \Delta(S_i). \]The full mixed strategy space is
\[ \Sigma = \prod_{i\in I} \Sigma_i. \]By the definitions above, each \(\Sigma_i\) is a nonempty compact convex set. Finite products preserve these properties, so \(\Sigma\) is exactly the kind of space on which Kakutani can operate.
A fixed point \(\sigma^* \in B(\sigma^*)\) means every player's mixed strategy is a best response to the others. So instead of directly solving many equilibrium inequalities at once, the proof reduces existence to a single fixed-point statement.
Kakutani is needed because \(B\) is usually set-valued: a player can have several best responses at the same profile. Brouwer handles single-valued maps, while Kakutani is the fixed-point theorem designed for correspondences.
When strategy sets are infinite, pure equilibrium may or may not exist. The answer depends on the shape of the payoff functions.
Let each player choose a number \(x_i \in [0,1]\), and suppose player \(i\)'s payoff is
\[ u_i(x_i,x_{-i}) = -\bigl(x_i - m_{-i}\bigr)^2, \]where \(m_{-i}\) is some average of the other players' actions. This payoff is continuous and concave in \(x_i\) because it is a negative quadratic. So the theorem guarantees a pure equilibrium exists.
A circle-location example: two players choose points on a circle and player 1 wants to maximize distance from player 2, while player 2 wants to minimize it. There is no pure Nash equilibrium because one player always wants to move away and the other wants to adjust in response.
This theorem is more powerful because it does not require concavity in the pure action. The price is that equilibrium may exist only after players mix, and the mixed-strategy spaces become infinite-dimensional.
These notes are included because they were precisely the places where the definitions started to feel abstract.
Fix a player \(i\), a recommendation \(s_i\), and a possible deviation \(t_i\).
\[ \sum_{s_{-i}} \Pr(R=s \mid R_i=s_i) \bigl[u_i(s_i,s_{-i}) - u_i(t_i,s_{-i})\bigr] \ge 0 \]This is just
\[ \mathbb{E}\!\left[ u_i(\text{follow}) - u_i(\text{deviate}) \,\middle|\, R_i=s_i \right] \ge 0. \]So the sum is not an unweighted sum over all \(s_{-i}\). It is a conditional expectation, using the belief induced by the recommendation.
Because the distribution \(\pi\) is defined over the full profile space \(S\). But once your recommendation \(s_i\) is fixed, writing \[ \Pr(R=s \mid R_i=s_i) \] is equivalent to writing \[ \Pr(R_{-i}=s_{-i} \mid R_i=s_i). \] The first notation keeps the joint distribution explicit; the second is often easier to interpret.
Two facts are enough:
So if \(\pi^1,\dots,\pi^k\) are mixed Nash equilibria and \(\lambda_1,\dots,\lambda_k\) are nonnegative weights summing to 1, then \[ \sum_{m=1}^k \lambda_m \pi^m \] is again a correlated equilibrium.
It generalizes fixed points from ordinary functions to correspondences (set-valued maps). Instead of asking for \[ f(x)=x, \] it asks for \[ x \in f(x). \] In game theory, \(f(x)\) is the set of best responses. So a fixed point means the strategy profile is one of its own best responses, which is exactly equilibrium.
Because the best-response correspondence over pure strategies satisfies Kakutani's conditions:
Kakutani then gives \(s^* \in B(s^*)\), which means every player is best responding in pure strategies.