Strategic Form Games & Nash Equilibrium
Strategic Form Games & Nash Equilibrium
A strategic-form (normal-form) game $G=(N,S,u)$ consists of a player set $N=\{1,\ldots,n\}$, strategy spaces $S_i$, and payoff functions $u_i:S\to\mathbb{R}$. Nash equilibrium, the central solution concept, identifies strategy profiles where no player can profitably deviate. John Nash's 1950 existence theorem guarantees equilibrium in every finite game, revolutionizing economics, biology, and political science.
Nash Equilibrium
A strategy profile $s^*=(s_1^*,\ldots,s_n^*)$ is a Nash equilibrium if for every player $i$ and every alternative strategy $s_i\in S_i$: $$u_i(s_i^*,s_{-i}^*)\geq u_i(s_i,s_{-i}^*)$$ where $s_{-i}^*$ denotes the strategies of all players except $i$. Equivalently, each $s_i^*$ is a best response to $s_{-i}^*$: $s_i^*\in\text{BR}_i(s_{-i}^*)=\arg\max_{s_i}u_i(s_i,s_{-i}^*)$.
Nash's Existence Theorem
Every finite strategic-form game has at least one Nash equilibrium (possibly in mixed strategies). The proof uses Kakutani's fixed-point theorem applied to the joint best-response correspondence $\text{BR}:S\to 2^S$, $s\mapsto\prod_i\text{BR}_i(s_{-i})$. Since each $S_i$ is compact convex (after mixing) and each $\text{BR}_i$ has a closed graph and convex values, Kakutani guarantees a fixed point $s^*\in\text{BR}(s^*)$.
Example 1
Find all Nash equilibria of the Prisoner's Dilemma with payoff matrix: (C,C)=(3,3), (C,D)=(0,5), (D,C)=(5,0), (D,D)=(1,1).
Solution: Defect (D) strictly dominates Cooperate (C) for both players: $u_i(D,s_{-i})>u_i(C,s_{-i})$ for all $s_{-i}$. The unique Nash equilibrium is $(D,D)$ with payoffs $(1,1)$, despite the Pareto-superior outcome $(C,C)=(3,3)$ being available. This social dilemma structure — rational individual behavior leading to collective inefficiency — makes the Prisoner's Dilemma the paradigm example of the tension between individual and collective rationality.
Example 2
Find all pure-strategy Nash equilibria of the coordination game: (A,A)=(2,2), (A,B)=(0,0), (B,A)=(0,0), (B,B)=(1,1).
Solution: Both $(A,A)$ and $(B,B)$ are Nash equilibria: in $(A,A)$, deviating to $B$ gives $0<2$; in $(B,B)$, deviating to $A$ gives $0<1$. This game has multiple equilibria with different payoffs, illustrating the equilibrium selection problem. The Pareto-dominant equilibrium $(A,A)$ is the risk-dominant equilibrium $(B,B)$... actually $(A,A)$ Pareto-dominates; $(B,B)$ is risk-dominant if $1>2\cdot 0$, i.e., always. Equilibrium selection requires refinements.
Practice
- Solve for all Nash equilibria (pure and mixed) of the Battle of Sexes game: (O,O)=(2,1),(O,F)=(0,0),(F,O)=(0,0),(F,F)=(1,2).
- Show that iterated elimination of strictly dominated strategies preserves Nash equilibria.
- In a $3\times 3$ game, construct an example where no pure-strategy NE exists.
- Prove: if $s^*$ is a Nash equilibrium and $s_i$ is a strictly dominant strategy for player $i$, then $s_i^*=s_i$.
Show Answer Key
1. Pure NE: (O,O) with payoffs (2,1) and (F,F) with payoffs (1,2). Mixed NE: Player 1 plays O with prob $p=2/3$, Player 2 plays O with prob $q=1/3$. Expected payoff: $(2/3, 2/3)$.
2. If $s_i$ is strictly dominated by $s_i'$, then in any NE $s^*$, player $i$ never plays $s_i$ (since deviating to $s_i'$ is always profitable). So eliminating $s_i$ preserves all NE.
3. Example: $A=\begin{pmatrix}0&1&-1\\-1&0&1\\1&-1&0\end{pmatrix}$ (Rock-Paper-Scissors). No pure NE exists: each pure strategy is beaten by another. The unique NE is the uniform mix $(1/3,1/3,1/3)$ for both players.
4. In any NE $s^*$, $u_i(s_i^*,s_{-i}^*)\ge u_i(s_i,s_{-i}^*)$ for all $s_i$. If $s_i$ is strictly dominant, $u_i(s_i,s_{-i})>u_i(s_i',s_{-i})$ for all $s_i'\neq s_i$ and all $s_{-i}$. In particular with $s_{-i}=s_{-i}^*$: $u_i(s_i,s_{-i}^*)>u_i(s_i^*,s_{-i}^*)$ unless $s_i^*=s_i$. So $s_i^*=s_i$.