Nash Equilibrium

Why we need the concept (motivation)

In game theory, you rarely choose an action in isolation. Your outcome depends on others’ choices, and theirs depends on yours. So the usual “maximize my payoff” idea becomes intertwined: your best decision is a function of what you expect others to do.

We want a notion of stability: a predicted outcome that, once reached, doesn’t give any single player an incentive to unilaterally change course. Nash equilibrium formalizes this idea.

The basic objects

A (normal-form) game has:

• •Players i ∈ {1,…,n}
• •Strategy sets Sᵢ for each player i
• •Payoff functions uᵢ(s) where s is a strategy profile

A strategy profile is an assignment of one strategy to every player:

• •s = (s₁, s₂, …, sₙ)
• •sᵢ is player i’s strategy
• •s₋ᵢ denotes “everyone except i”:
• •s₋ᵢ = (s₁,…,sᵢ₋₁, sᵢ₊₁,…,sₙ)

So we can write payoffs as uᵢ(sᵢ, s₋ᵢ).

Definition (pure-strategy Nash equilibrium)

A strategy profile s* is a Nash equilibrium if no player can improve their payoff by changing only their own strategy, holding others fixed.

Formally, s* is a Nash equilibrium if ∀i and ∀sᵢ′ ∈ Sᵢ,

uᵢ(sᵢ, s₋ᵢ) ≥ uᵢ(sᵢ′, s₋ᵢ*)

Read it slowly:

• •Others keep playing s₋ᵢ*
• •Player i compares their equilibrium payoff uᵢ(sᵢ, s₋ᵢ)
• •Against any unilateral deviation sᵢ′
• •And finds no profitable deviation.

Intuition: “no profitable unilateral deviation”

A Nash equilibrium is not necessarily:

• •“The best overall outcome”
• •“Fair”
• •“Socially optimal”

It’s a self-enforcing outcome: if everyone believes the equilibrium will be played, it is consistent for each person to stick with their equilibrium strategy.

Best responses (another way to say the same thing)

Define player i’s best response set to others’ strategies s₋ᵢ:

BRᵢ(s₋ᵢ) = { sᵢ ∈ Sᵢ : uᵢ(sᵢ, s₋ᵢ) ≥ uᵢ(sᵢ′, s₋ᵢ) for all sᵢ′ ∈ Sᵢ }

Then s* is a Nash equilibrium iff:

sᵢ ∈ BRᵢ(s₋ᵢ) for all i

So a Nash equilibrium is exactly a profile of mutual best responses.

A quick sanity check: what Nash equilibrium is not

Nash equilibrium does not prevent two or more players from coordinating a deviation that benefits them jointly. It only blocks deviations by a single player at a time.

This matters because many “unstable” or “unreasonable” outcomes are eliminated by unilateral deviations, but some inefficient outcomes remain stable because escaping them requires coordination.

Pure vs mixed (preview)

Often, especially in finite games, a pure-strategy equilibrium might not exist. Nash’s major theorem says that if players can randomize (play mixed strategies), at least one Nash equilibrium exists.

We’ll build up to that idea after we understand the mechanics in pure strategies.

Why this mechanic matters

The definition is simple, but applying it requires a practical workflow:

1. 1)Hold others fixed.
2. 2)Compute a player’s best response.
3. 3)Find profiles where everyone is simultaneously best-responding.

In small games (2×2, 2×3), this is often easiest with payoff matrices. In larger games, it resembles an optimization problem: each player solves

maximize over sᵢ ∈ Sᵢ: uᵢ(sᵢ, s₋ᵢ)

Two-player matrix games

For two players (Row and Column), we represent payoffs as ordered pairs.

Example structure:

A pure Nash equilibrium is a cell where:

• •Row’s payoff is maximal within its column (given Column’s choice)
• •Column’s payoff is maximal within its row (given Row’s choice)

Algorithm: “underline best responses”

A common manual method:

1. 1)For each column, underline Row’s best payoff (Row’s best response).
2. 2)For each row, underline Column’s best payoff (Column’s best response).
3. 3)Any cell where both payoffs are underlined is a pure Nash equilibrium.

This is just the definition made visual.

Connection to optimization language

Suppose the strategy sets are numeric (e.g., choose a quantity qᵢ ≥ 0). Then a best response is literally an optimizer:

BRᵢ(q₋ᵢ) = argmax_{qᵢ ≥ 0} uᵢ(qᵢ, q₋ᵢ)

A Nash equilibrium is a fixed point of best responses:

qᵢ ∈ BRᵢ(q₋ᵢ) for all i

This “fixed point of best-response correspondences” viewpoint is the bridge to existence theorems and to computation methods.

Multiple equilibria, no equilibria

Two key phenomena appear immediately:

1) Multiple equilibria

• •More than one profile can satisfy mutual best responses.
• •Prediction may require refinement (risk dominance, trembling-hand perfection, focal points) or extra context.

2) No pure equilibrium

• •Some games have no cell where both players are best-responding.
• •Classic example: Rock–Paper–Scissors.

This motivates mixed strategies.

Dominated strategies (a useful simplifier)

A strategy sᵢ is strictly dominated if there exists another strategy tᵢ such that

uᵢ(tᵢ, s₋ᵢ) > uᵢ(sᵢ, s₋ᵢ) for all s₋ᵢ

A strictly dominated strategy is never a best response, so it cannot be used in any Nash equilibrium. Eliminating dominated strategies can simplify equilibrium search.

Comparing related “stability” notions

To avoid confusion, here’s a compact comparison:

A Nash equilibrium can be Pareto-inefficient (e.g., Prisoner’s Dilemma). That isn’t a bug—it’s the point: incentives can misalign with collective welfare.

Why mixed strategies enter the picture

If a game has no pure equilibrium, should we conclude it has no stable outcome? Nash’s insight: allow players to randomize over pure actions.

Randomization can make opponents indifferent among their options, removing profitable deviations.

Mixed strategies as probability distributions

For player i with k pure strategies, a mixed strategy is a probability vector pᵢ:

pᵢ = (pᵢ1, …, pᵢk) where pᵢj ≥ 0 and ∑ⱼ pᵢj = 1

A mixed-strategy profile is (p₁, …, pₙ).

Payoffs become expected payoffs. In a two-player finite game, the expected payoff to player i is:

E[uᵢ] = ∑_{a∈A} ∑_{b∈B} p₁(a) p₂(b) uᵢ(a,b)

(Generalizes to n players with ∑ over all action profiles.)

Definition (mixed-strategy Nash equilibrium)

A mixed-strategy profile (p₁

,…,pₙ) is a Nash equilibrium if no player can increase expected payoff by changing only their own distribution.

Formally, for every i and every alternative mixed strategy qᵢ,

E[uᵢ(pᵢ, p₋ᵢ)] ≥ E[uᵢ(qᵢ, p₋ᵢ)]

This is the same logic as pure strategies, but with expectations.

The key property: indifference over the support

If player i mixes among multiple pure strategies with positive probability, then in equilibrium those strategies must yield equal expected payoff (otherwise i would shift probability to the better one).

Let Sᵢ⁺ be the support (strategies played with positive probability). Then for any a, a′ ∈ Sᵢ⁺:

E[uᵢ(a, p₋ᵢ)] = E[uᵢ(a′, p₋ᵢ)]

And any strategy outside the support must do no better:

E[uᵢ(a_out, p₋ᵢ)] ≤ E[uᵢ(a, p₋ᵢ)] for a ∈ Sᵢ⁺

This “equalize payoffs” rule is the workhorse for solving 2×2 mixed equilibria.

Solving a 2×2 mixed equilibrium (template)

Suppose Row has strategies R₁,R₂ and Column has C₁,C₂.

Let Column play C₁ with probability q (and C₂ with 1−q).

Row’s expected payoff from R₁ and R₂ are linear functions of q:

E[u_R(R₁)] = q·u_R(R₁,C₁) + (1−q)·u_R(R₁,C₂)

E[u_R(R₂)] = q·u_R(R₂,C₁) + (1−q)·u_R(R₂,C₂)

If Row mixes between R₁ and R₂ in equilibrium, then set them equal and solve for q.

Similarly, let Row play R₁ with probability p and solve for p by making Column indifferent.

Why existence is guaranteed (high-level)

For finite games, Nash (1950–51) proved at least one mixed equilibrium exists. Intuitively:

• •Mixed strategies form a compact, convex set (a simplex).
• •Best responses can be seen as a correspondence with a fixed point.

You don’t need the full proof here, but you should internalize the consequence:

Even when no pure equilibrium exists, the game still has a stable prediction in mixed strategies.

Interpreting mixed strategies

Be careful with interpretation:

• •Randomization can be literal (a mixed action, a coin flip).
• •Or it can represent uncertainty about types, trembles, or population heterogeneity.

In any case, the equilibrium condition remains: no unilateral change improves expected payoff.

Nash equilibrium as a baseline for strategic prediction

In many domains, Nash equilibrium is the default “solution concept”:

• •Oligopoly pricing/quantity competition
• •Network routing and congestion
• •Security games (defender vs attacker allocations)
• •Auctions and bidding (with additional assumptions)

The practical value is that it turns interactive decision-making into a set of consistency constraints: everyone’s strategy must be optimal given the others.

Efficiency vs incentives (Prisoner’s Dilemma lesson)

A central theme in mechanism design and market design is that Nash equilibria can be inefficient.

Let social welfare be W(s) = ∑ᵢ uᵢ(s).

• •A social planner would choose s maximizing W(s).
• •Players choose strategies leading to Nash equilibria.

The gap between equilibrium welfare and optimal welfare motivates:

• •Changing rules (mechanism design)
• •Adding incentives, taxes, or transfers
• •Designing information and timing

Connection to Mechanism Design

Mechanism design asks: can we design a game so that desirable outcomes occur in equilibrium?

In a mechanism, the equilibrium concept is often Nash equilibrium (or Bayesian Nash equilibrium when there is private information). The designer wants:

• •Good outcomes (high welfare, fairness, revenue)
• •Incentive compatibility: truthful or intended behavior is a best response

So Nash equilibrium is the “target” condition: the mechanism is successful if the intended outcome is a Nash equilibrium of the induced game.

Connection to Zero-Sum Games

Zero-sum games are those where u₁(s) = −u₂(s).

• •In zero-sum games, equilibrium has a particularly strong meaning: it coincides with minimax optimal play.
• •Mixed strategies are often essential.

For zero-sum games, the Nash equilibrium value (the game value) is stable and can be found via linear programming.

Cautionary notes: limitations and refinements

Nash equilibrium is powerful but not the end of the story.

Common limitations:

• •Multiple equilibria: which one is selected?
• •Coordination issues: equilibria may be risk-dominated or fragile.
• •Non-credible threats in dynamic games: Nash may allow unreasonable strategies off the equilibrium path (addressed by subgame perfection).

Still, Nash equilibrium is the foundational equilibrium concept that most refinements build upon.

Mental model to keep

A good working mental model:

1. 1)Fix everyone else’s strategies s₋ᵢ.
2. 2)Ask: what would I do to maximize uᵢ(sᵢ, s₋ᵢ)?
3. 3)A Nash equilibrium is where this answer is “I would keep doing what I’m already doing,” for every i.

That stable-point idea is what makes Nash equilibrium central across economics, CS, and ML (e.g., multi-agent learning and GAN-like setups).