Nash Equilibria and Solution Concepts

"They asked me to predict what the agents would do. I gave them a fixed point and a warning: there are three of these, and I cannot tell you which one they will pick."

An Equilibrium With Selection Anxiety

The previous section gave us the two ways to write a game down: the normal form, a payoff matrix over simultaneous choices, and the extensive form, a tree of sequential moves. Writing a game down is not the same as saying what will happen in it. We now need a solution concept: a precise rule that takes a game and returns the strategy profiles we are willing to call outcomes. A good solution concept is predictive (agents acting in their own interest will tend to land there), self-consistent (it does not assume an agent will throw away payoff), and computable, at least in principle. The central solution concept, the one almost every multi-agent method in this book ultimately leans on, is the Nash equilibrium, and the cleanest way into it is to ask what each agent would do if it already knew everyone else's plan.

1. Best Response: The Atom of Every Solution Beginner

Fix all the other agents' strategies and ask a single agent a purely local question: given what everyone else is doing, what is the best I can do? The answer is the agent's best response. Write a strategy profile as $\sigma = (\sigma_i, \sigma_{-i})$, where $\sigma_i$ is agent $i$'s own strategy and $\sigma_{-i}$ collects the strategies of all the others. Agent $i$'s strategy is a best response when it maximizes $i$'s expected payoff $u_i$ holding the rest fixed:

Best response is a one-agent computation: it needs no agreement, no global view, only the beliefs an agent holds about the others. That locality is exactly why it scales to many interacting agents and why it is the building block of both the equilibrium definition below and the learning dynamics at the end of this section. The catch is that everyone is computing a best response at the same time, against a target that is itself shifting. A solution is the place where all of those local optimizations stop pointing somewhere else.

2. The Nash Equilibrium Intermediate

A strategy profile $\sigma^* = (\sigma_1^*, \dots, \sigma_n^*)$ is a Nash equilibrium when every agent is simultaneously best-responding to all the others. Equivalently, no agent can raise its own expected payoff by a unilateral deviation:

Read the inequality slowly: for each agent $i$, fixing everyone else at $\sigma_{-i}^*$, no other strategy $\sigma_i'$ does strictly better than $\sigma_i^*$. That is the entire content of the concept. It is a fixed point of the joint best-response map: plug the profile into "everyone best-responds" and the same profile comes back out. A pure-strategy equilibrium has each agent committing to one action; a mixed-strategy equilibrium has agents randomizing, and the inequality is then over expected payoffs. The randomization is not hand-waving: in a mixed equilibrium each agent is deliberately indifferent among the actions it mixes over, because if it strictly preferred one, it would put all its weight there and the profile would not be stable.

3. Existence: Nash's Theorem Intermediate

It would be a poor foundation if some games simply had no solution. Matching pennies, on the right of Figure 28.3.1, has no pure equilibrium at all: whatever deterministic choice one agent makes, the other has a strict reason to deviate, and the chase never ends. The resolution, and one of the most consequential results in the theory of interacting agents, is Nash's theorem.

Nash's theorem (1950): every finite game, meaning finitely many agents each with finitely many actions, has at least one Nash equilibrium in mixed strategies. The proof applies a fixed-point theorem (Brouwer's, or Kakutani's for the set-valued best-response map) to the joint best-response map on the compact, convex space of mixed-strategy profiles; a fixed point of that map is exactly a profile where everyone is best-responding, which is a Nash equilibrium. The price of guaranteed existence is that the guarantee is only for mixed strategies: matching pennies has an equilibrium, but you have to allow randomization to find it. For AI this is reassuring and demanding at once. Reassuring, because any finite multi-agent interaction we model has a well-defined predicted outcome. Demanding, because that outcome may require agents to randomize, and, as the next section shows, there may be more than one of them and reaching one may be expensive.

4. Multiplicity and the Selection Problem Intermediate

Existence is not uniqueness. The coordination game on the left of Figure 28.3.1 has two pure equilibria, and many games have more. When a game has several equilibria, the theory predicts a set of outcomes but does not, by itself, say which one a population of agents will reach. This is the equilibrium-selection problem, and it is not a technicality: two driver-assist policies that both prefer the same side of the road have two equilibria (all-left and all-right), both perfectly stable, and the entire safety question is which one a fleet coordinates on. Refinements try to narrow the set by adding plausibility conditions an equilibrium must survive, and the most important ones for AI are these.

A dominant-strategy equilibrium is the strongest and rarest: each agent has a single action that is best regardless of what the others do, so no beliefs about opponents are needed at all. When it exists (as in the prisoner's dilemma, where defection dominates), prediction is trivially robust, which is why Section 28.6 prizes mechanisms that make truth-telling a dominant strategy. A subgame-perfect equilibrium refines the set for sequential (extensive-form) games of Section 28.2: it requires the strategy to be a Nash equilibrium in every subgame, ruling out threats that an agent would not actually carry out, and you compute it by backward induction from the leaves of the game tree. A correlated equilibrium goes the other way and enlarges the solution set: a trusted shared signal (a traffic light is the canonical example) privately recommends an action to each agent, and the profile is a correlated equilibrium when no agent wants to deviate from its recommendation given what the signal implies about the others. Correlated equilibria can achieve payoffs no Nash equilibrium reaches, they are easier to compute (a linear program rather than a fixed-point search), and natural learning dynamics converge to them, which is why they recur in multi-agent learning.

5. The Computational Reality: PPAD-Hardness and Learning Advanced

Here the theory collides with practice in a way that shapes how AI actually uses equilibria. Nash's theorem proves an equilibrium exists but is non-constructive: it does not hand you one. Computing a Nash equilibrium is, in general, PPAD-complete (Daskalakis, Goldberg, and Papadimitriou, 2009), a complexity class for fixed-point problems widely believed to admit no polynomial-time algorithm. The practical upshot is blunt: for a general game with many agents or many actions, you should not expect to compute an exact Nash equilibrium directly, and any system design that assumes you can is building on sand.

Distributed AI sidesteps the wall with a different question. Instead of solving for an equilibrium, let the agents learn their way toward one by repeatedly playing and adapting. Two dynamics dominate. In fictitious play, each agent best-responds to the empirical frequency of the others' past actions, updating its beliefs as it observes more rounds; for important game classes (zero-sum and certain potential games) the empirical play converges to a Nash equilibrium. In no-regret learning, each agent runs an online algorithm that guarantees its average payoff approaches that of the best fixed action in hindsight; a classical result says that when all agents use no-regret algorithms, the empirical distribution of play converges to the set of correlated equilibria. These dynamics are local, communication-light, and robust to the messiness of real systems, which is exactly the profile distributed AI needs. They are the bridge from the static fixed point of this section to the repeated-game and learning treatment of Section 28.7, and to the policy-learning machinery of multi-agent reinforcement learning in Chapter 30, which builds on the distributed reinforcement-learning infrastructure of Chapter 20.

6. Computing and Learning Equilibria from Scratch Intermediate

The code below makes every idea in this section concrete with nothing but NumPy. It finds the pure Nash equilibria of two $2 \times 2$ games by direct best-response analysis, derives the mixed equilibrium of matching pennies in closed form from the indifference condition, and then runs fictitious play to show empirical behavior converging toward that mixed equilibrium, the right panel of Figure 28.3.1 brought to life round by round.

import numpy as np

# Two 2-player games as payoff bimatrices (A = row player's payoff, B = column's).
def pure_nash(A, B):
    """Return all pure-strategy Nash equilibria as (row, col) index pairs."""
    n, m = A.shape
    eq = []
    for i in range(n):
        for j in range(m):
            row_best = A[i, j] >= A[:, j].max() - 1e-12   # row can't beat col j
            col_best = B[i, j] >= B[i, :].max() - 1e-12    # col can't beat row i
            if row_best and col_best:
                eq.append((i, j))
    return eq

# Coordination game: two pure equilibria on the diagonal.
A1 = np.array([[3.0, 0.0], [0.0, 2.0]])
B1 = np.array([[2.0, 0.0], [0.0, 3.0]])
print("Game 1  (coordination)")
print("  pure Nash equilibria (row,col):", pure_nash(A1, B1))

# Matching pennies: no pure equilibrium, one mixed equilibrium.
A2 = np.array([[1.0, -1.0], [-1.0, 1.0]])
B2 = -A2
print("Game 2  (matching pennies)")
print("  pure Nash equilibria (row,col):", pure_nash(A2, B2) or "none")

# Closed-form mixed equilibrium: each player randomizes to make the OTHER
# indifferent between its two actions (the indifference condition).
def mixed_2x2(A, B):
    a, b, c, d = A[0,0], A[0,1], A[1,0], A[1,1]
    q = (d - c) / (a - b - c + d)        # col's prob on action 0
    e, f, g, h = B[0,0], B[0,1], B[1,0], B[1,1]
    p = (h - f) / (e - g - f + h)        # row's prob on action 0
    return p, q

p, q = mixed_2x2(A2, B2)
print(f"  mixed equilibrium: row plays action 0 w.p. {p:.3f}, col w.p. {q:.3f}")

# Fictitious play: each agent best-responds to the empirical mix of the other.
def fictitious_play(A, B, steps, seed=0):
    rng = np.random.default_rng(seed)
    row_counts = np.zeros(A.shape[0]); col_counts = np.zeros(A.shape[1])
    row_counts[rng.integers(A.shape[0])] += 1     # seed the history
    col_counts[rng.integers(A.shape[1])] += 1
    for _ in range(steps):
        col_mix = col_counts / col_counts.sum()
        row_mix = row_counts / row_counts.sum()
        row_counts[int(np.argmax(A @ col_mix))] += 1   # row best-responds
        col_counts[int(np.argmax(row_mix @ B))] += 1   # col best-responds
    return row_counts / row_counts.sum(), col_counts / col_counts.sum()

for T in (100, 1000, 20000):
    rm, cm = fictitious_play(A2, B2, T)
    print(f"  fictitious play, {T:6d} rounds: row mix {rm.round(3)}, col mix {cm.round(3)}")

Game 1  (coordination)
  pure Nash equilibria (row,col): [(0, 0), (1, 1)]
Game 2  (matching pennies)
  pure Nash equilibria (row,col): none
  mixed equilibrium: row plays action 0 w.p. 0.500, col w.p. 0.500
  fictitious play,    100 rounds: row mix [0.446 0.554], col mix [0.485 0.515]
  fictitious play,   1000 rounds: row mix [0.516 0.484], col mix [0.494 0.506]
  fictitious play,  20000 rounds: row mix [0.503 0.497], col mix [0.502 0.498]

The two halves of the output are the two ways AI meets an equilibrium. The top half computes equilibria, which is feasible here only because the games are tiny and the indifference condition is a two-variable equation; scale either game up and the PPAD wall of Section 5 makes this approach hopeless. The bottom half learns one, and that approach keeps working as the game grows, which is why it, not the solver, is the template for large multi-agent systems.

import nashpy as nash
import numpy as np

game = nash.Game(np.array([[1, -1], [-1, 1]]),    # row payoffs (matching pennies)
                 np.array([[-1, 1], [1, -1]]))    # column payoffs
for row_strategy, col_strategy in game.support_enumeration():
    print(row_strategy, col_strategy)             # -> [0.5 0.5] [0.5 0.5]

7. Why Equilibria Are the Right Lens, and Their Limits Beginner

Equilibria earn their central place because they are the only self-consistent predictions of self-interested behavior: any outcome that is not an equilibrium contains an agent with a reason to move, so it cannot be where the system rests. That makes equilibrium analysis the natural feasibility test for any coordination scheme, the foundation the cooperative games of Section 28.4 and the mechanisms of Section 28.6 build on, and the static backdrop against which the learning dynamics of Section 28.7 play out. The same lens recurs whenever agents interact in this book, from contract-net bidding in distributed problem solving (Chapter 27) to the communication-efficient adaptation studied in distributed optimization (Chapter 10).

The limits are equally important to carry forward. Equilibrium assumes agents are rational and, in the classic definition, that beliefs are somehow consistent, assumptions real bots and humans violate. Multiplicity means the concept often predicts a set, not a point, and leaves selection unresolved. Hardness means exact computation is usually off the table. And equilibrium is silent on quality: the rest point can be far from the social optimum, the gap we will quantify as the price of anarchy in Section 28.5. These are not reasons to abandon the lens but the reasons the chapter continues: cooperative solution concepts, welfare and efficiency, mechanism design, and learning dynamics each address one of these limits in turn.