Nash Equilibrium

Why Does This Exist?

When two ad bidders, two networks, or two agents interact, asking what each does "optimally" is ill-posed: the best move depends on the other's move. Nash equilibrium (1950) cuts the knot. A profile is an equilibrium when each player's strategy is a best response to the others: nobody profits by deviating solo. It predicts rest points of strategic interaction and anchors the rest of game theory: zero-sum games refine it for pure conflict, correlated equilibrium relaxes it with mediation, and game-theoretic optimization computes it by learning dynamics.

The one idea you need first

A best response maximizes your payoff holding others fixed. Write $BR_1(s_2)$ for player 1's best reply to player 2's strategy $s_2$. Equilibrium is mutual best response: $s_1 \in BR_1(s_2)$ and $s_2 \in BR_2(s_1)$ simultaneously.

Think of It Like This

How It Actually Works

For finite games, check each cell: would either player gain by moving alone? Cells surviving both checks are pure-strategy equilibria. Nash's theorem guarantees at least one equilibrium in mixed strategies (probability distributions over actions) for every finite game.

Mixed equilibrium comes from indifference: at equilibrium each player randomizes to make the other indifferent among the actions they mix over. For matching pennies (payoffs $\pm 1$), row mixes $(1/2, 1/2)$ because only then is column indifferent between heads and tails, and vice versa.

Worked example

Coordination with a safe option. Payoffs (row, column):

Pure checks: (Up, Left) survives (deviating gives $2 < 3$ for row, $2 < 3$ for column). (Down, Right) survives ($0 < 1$ both). Two pure equilibria plus one mixed. Mixed: row plays Up with $p$ making column indifferent: $3p + 0(1-p) = 2p + 1(1-p)$, so $3p = p + 1$, $p = 1/2$. Column plays Left with $q$: $3q + 2(1-q) = 0q + 1(1-q)$ gives $q + 2 = 1 - q$, $q = -1/2$: impossible. So the fully mixed equilibrium does not exist here; instead column mixes to make row indifferent only if row's payoffs allowed it. Recompute honestly: row indifferent needs $3q + 0 = 2q...$ wait, row payoff for Up is $3q + 0(1-q) = 3q$; for Down $2q + 1(1-q) = q + 1$. Set equal: $3q = q + 1$, $q = 1/2$. Column indifferent needs $3p + 2(1-p) = 0p + 1(1-p)$: $p + 2 = 1 - p$, $p = -1/2$: impossible, so column never mixes both actions at equilibrium; the mixed equilibrium has column playing a pure action. Conclusion: exactly two pure equilibria and no fully mixed one. Checking feasibility (probabilities in $[0,1]$) is part of the method, and here it rules one candidate out.

Code

1def pure_nash(row: list[list[float]], col: list[list[float]]) -> list[tuple[int, int]]:2    out = []3    n_rows, n_cols = len(row), len(row[0])4    for r in range(n_rows):5        for c in range(n_cols):6            if all(row[r][c] >= row[rr][c] for rr in range(n_rows)):7                if all(col[r][c] >= col[r][cc] for cc in range(n_cols)):8                    out.append((r, c))  # no solo deviation pays9    return out10
11
12row = [[3, 0], [2, 1]]13col = [[3, 2], [0, 1]]14print(pure_nash(row, col))  # -> [(0, 0), (1, 1)]

Both diagonal cells survive; off-diagonals fail one player's check each.

Watch Out For

The Quick Version

• Nash means mutual best response: no profitable solo deviation.
• Every finite game has a mixed-strategy equilibrium; pure ones may number zero, one, or several.
• Mixed strategies come from indifference conditions, with feasibility checks in $[0,1]$.
• The worked game has exactly two pure equilibria at $(0,0)$ and $(1,1)$, paying $(3,3)$ and $(1,1)$.
• Stability never implies welfare or uniqueness; selection needs more story.
• Noisy opponents favor risk-dominant equilibria over fragile high-payoff ones.

What to Read Next

• Probability Foundations
• Convexity and Loss Landscapes