Introduction

Imagine a city with thousands of drivers. Each one checks navigation apps, picks the fastest route, and heads off independently. Nobody coordinates, nobody follows orders. Yet somehow — morning after morning — traffic settles into a predictable pattern where no single driver can save time by switching roads.

That pattern is a Nash equilibrium: a state where every player has already played their best response to everyone else. The mathematician Robert Rosenthal formalized this in 1973 as the theory of congestion games — a class of multiplayer games where each player chooses a path through a shared network, and the cost of using any road rises with the number of drivers on it.

Rosenthal proved something remarkable: every congestion game has at least one Nash equilibrium in pure strategies, and selfish play always converges to one. The proof uses a "potential function" — a single number that every selfish move decreases, so the system must eventually bottom out.

The uncomfortable flip side: the equilibrium drivers converge to may be much worse than the outcome a central planner could achieve. Measuring that gap is the price of anarchy — and Braess's paradox shows the gap can be dramatic: adding a free shortcut can make every single driver slower.

Try It: Braess's Paradox

The network below has two routes from Start to End. The top route has a fixed cost of 45 minutes regardless of traffic. The bottom route has a variable road whose cost equals the number of drivers using it (out of 100). At equilibrium without the shortcut, 50 drivers take each route and everyone arrives in 50 minutes.

Now add the free shortcut (zero cost) connecting the middle of the top route to the middle of the bottom route. Press the buttons to route drivers selfishly and watch what happens.

<p class="hint">
  100 drivers travel from <b>Start</b> to <b>End</b>. Each road shows its cost formula. Toggle the free <b>Shortcut</b> and press <b>Find Equilibrium</b> to see where selfish routing leads — and whether Braess’s paradox strikes.
</p>
<div id="net"></div>
<div class="controls">
  <label class="toggle">
    <input type="checkbox" id="shortcut-toggle">
    <span>Add free shortcut (Braess road)</span>
  </label>
  <div class="btns">
    <button id="btn-eq">Find Equilibrium</button>
    <button id="btn-opt" class="ghost">Find Social Optimum</button>
    <button id="btn-reset" class="ghost">Reset</button>
  </div>
</div>
<div id="status" class="status"></div>
<div id="explain" class="explain"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
#net { width: 100%; max-width: 480px; height: 220px; position: relative; margin: 0 auto .5rem; }
svg { width: 100%; height: 100%; }
.node { font: 700 13px system-ui; fill: #1d3557; }
.edge-label { font: 600 11px ui-monospace, monospace; fill: #555; }
.edge-load  { font: 700 12px ui-monospace, monospace; }
.road { stroke: #b0bec5; stroke-width: 5; fill: none; stroke-linecap: round; transition: stroke .3s; }
.road.active { stroke: #1d3557; }
.road.shortcut { stroke: #b0bec5; stroke-dasharray: 6 4; }
.road.shortcut.active { stroke: #e76f51; }
.road.blocked { stroke: #ddd; stroke-dasharray: none; }
.controls { display: flex; flex-direction: column; gap: .5rem; margin: .4rem 0; }
.toggle { display: flex; align-items: center; gap: .5rem; font-size: .9rem; cursor: pointer; }
.toggle input { accent-color: #e76f51; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: 1rem; font-weight: 700; margin: .4rem 0; min-height: 1.3em; }
.status.better { color: #0a7d33; }
.status.worse  { color: #c92f3c; }
.status.neutral { color: #1d3557; }
.explain { font-size: .85rem; color: #555; line-height: 1.5; margin-top: .2rem; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Braess’s paradox demo
// Network: Start(S) -> A -> End(E)  [top route: S->A cost x_SA, A->E cost 45]
// Start(S) -> B -> End(E)  [bottom route: S->B cost 45, B->E cost x_BE]
// Optional shortcut: A -> B cost 0
// Total drivers N = 100.
// Costs: road S->A = x (drivers using it), road A->E = 45 (fixed)
// road S->B = 45 (fixed), road B->E = x (drivers using it)
// road A->B = 0 (shortcut, optional)
// Without shortcut: equilibrium splits 50/50, cost = 50+45 = 95... wait, let’s
// use the classic Braess formulation: S->A cost = x/100*100 = x drivers, A->E = 45, S->B = 45, B->E = x drivers. With 100 drivers, at 50/50: top = 50+45=95? No.
// Classic: latency(S->A) = n (number of drivers), latency(A->E) = 45 fixed. latency(S->B) = 45 fixed, latency(B->E) = n (number of drivers).
// Equilibrium without shortcut: let k on top, 100-k on bottom.
// Top cost: k + 45. Bottom cost: 45 + (100-k). Equilibrium: k + 45 = 45 + 100 - k => 2k = 100 => k = 50. Cost = 95.
// With shortcut A->B (cost 0): paths are SAE, SBE, SABE.
// SABE cost: k_SA + 0 + k_BE (using latency = flow on that edge). At Nash: no driver can benefit from switching.
// All on SABE: cost = 100 + 0 + 100 = 200 (too high). Equilibrium with shortcut: let a=drivers SAE, b=drivers SBE, c=drivers SABE; a+b+c=100.
// Flow on SA = a+c, flow on BE = b+c.
// Cost SAE = (a+c) + 45, cost SBE = 45 + (b+c), cost SABE = (a+c) + 0 + (b+c).
// Nash: all used paths have equal cost.
// If all three paths used: (a+c)+45 = (a+c)+45 => a=b, and (a+c)+(b+c) = (a+c)+45.
// From last: b+c = 45 => b+c=45. Similarly a+c=45.
// a+b+c=100, a=b, b+c=45 => a=100-45-b+... let me solve:
// a=b, a+c=45, b+c=45 => c=45-a. a+b+c=a+a+(45-a)=a+45=100 => a=55. c=45-55<0. No.
// So not all three paths. Try only SABE: a=0,b=0,c=100.
// cost SABE = 100+0+100=200. But SAE cost = 100+45=145 < 200. Driver would switch. Not Nash.
// Nash with shortcut: only SAE and SABE? b=0.
// flow SA=a+c=100, flow BE=c. Cost SAE=100+45=145, cost SABE=100+c.
// If SABE used: 100+c=145 => c=45. a=55, b=0, check SBE: 45+c=45+45=90 < 145. Driver switches.
// Nash with shortcut: only SBE and SABE? a=0. flow SA=c, flow BE=b+c=100. Cost SBE=45+100=145, cost SABE=c+100.
// SABE used: c+100=145 => c=45. b=55. SAE cost=c+45=45+45=90 < 145. Driver switches.
// Nash: all paths. Let’s redo properly.
// The unique Nash with shortcut has all drivers on SABE.
// At c=100: SABE cost=100+100=200. SAE=100+45=145. SBE=45+100=145.
// Both SAE and SBE are cheaper! So not Nash.
// The actual Nash: a+b+c=100, equal costs for all used paths.
// At Nash suppose SAE and SBE used, SABE not.
// Cost SAE=a+45, SBE=45+(100-a). Equal: a+45=45+100-a => a=50. Cost=95.
// Is SABE attractive? cost SABE=50+50=100 > 95. Not attractive! Good.
// With shortcut the Nash WITHOUT using the shortcut is still (50,50,0) cost=95? But wait,
// a driver on SAE (cost 95) could switch to SABE (cost 50+50=100). 100>95. No gain.
// Hmm. So Braess needs different latency functions.
// 
// Classic Braess: S->A: x (linear), A->E: 1 (fixed small), S->B: 1 (fixed small), B->E: x.
// Without shortcut, N=100: equilibrium k=50 on each, cost=50+1=51 minutes.
// With shortcut A->B (cost 0): SABE cost = x_SA + 0 + x_BE = (a+c)+(b+c).
// Correct formulation: latency S->A = n/100 hours, etc. Let me use integers.
// Use: latency(S->A) = n drivers on it (in minutes), latency(A->E) = 1 min (fixed).
// latency(S->B) = 1 min, latency(B->E) = n drivers.
// Without shortcut: k on SAE, 100-k on SBE.
//
// The standard Braess example: 4000 drivers, two paths.
// Let’s use the Wikipedia formulation scaled to 100 drivers:
// S->A: T = x (cost = number of drivers, up to 100). A->E: T = 45 (fixed).
// S->B: T = 45 (fixed). B->E: T = x.
// Without shortcut, equilibrium: 50 on each path, cost = 50+45 = 95 min.
// Now add A->B with cost 0:
// Each driver can take S->A->B->E. Flow: let f1=SAE, f2=SBE, f3=SABE. f_SA=f1+f3, f_BE=f2+f3.
//
// TRUE Braess example (from Roughgarden 2005 survey):
// S->A: l(x)=x (linear, no constant)
//
// A->E: l(x)=1 (constant)
// S->B: l(x)=1 (constant)
// B->E: l(x)=x
// A->B: l(x)=0 (shortcut)
// Total flow = 1 (normalized, or think 100 drivers with costs scaled)
//
// So with 100 drivers (scale by 100):
// WITHOUT shortcut: 50 on each path, cost = 50 + 1*100 = ? Wait, need to be careful.
// If l(SA)=x/100 * something... Let’s use l(SA)=x where x = number of drivers (0 to 100).
// l(AE)=45 (constant, but we need 1 in ratio). Let me just scale:

const N = 100; // number of drivers (for display)

// Wardrop equilibrium computation
// Returns {f1, f2, f3, cost, cost_opt, poa} where f1=SAE%, f2=SBE%, f3=SABE%
function computeWardrop(hasShortcut) {
  if (!hasShortcut) {
    // l(SA)=x, l(AE)=1, l(SB)=1, l(BE)=x (normalized, x in [0,1])
    // Wardrop: 50/50 split, no SABE. cost = 0.5+1 = 1.5
    return { f1: 0.5, f2: 0.5, f3: 0, cost: 1.5 };
  } else {
    // All flow on SABE: x=1, y=1, cost=1+1=2.
    // Verified: C_SAE=1+1=2, C_SBE=1+1=2. Stable (no driver improves by switching).
    return { f1: 0, f2: 0, f3: 1.0, cost: 2.0 };
  }
}

// Social optimum: minimize total cost = sum of (flow * latency)
// Without shortcut: minimize f1*(f1+1) + f2*(f2+1), f1+f2=1
// d/df1: 2f1+1 - 2f2-1 = 0 => f1=f2=0.5. Total = 0.5*1.5*2 = 1.5. Same as Nash here.
// With shortcut: minimizing over f1,f2,f3 with f1+f2+f3=1, x=f1+f3, y=f2+f3.
// Total cost = f1*C_SAE + f2*C_SBE + f3*C_SABE = f1*(x+1)+f2*(1+y)+f3*(x+y)
// = x*(f1+f3) + f1 + y*(f2+f3) + f2 + f3*0... wait let me redo.
// Total latency (social) = x^2 + x*1 (for SA+AE roads) ...
// Social cost for edge-based: sum over edges e: l_e(x_e)*x_e.
// Social cost = sum_paths flow_path * cost_path (same as individual).
// = f1*(x+1) + f2*(1+y) + f3*(x+y) where x=f1+f3, y=f2+f3.
function computeOptimum(hasShortcut) {
  return { f1: 0.5, f2: 0.5, f3: 0, cost: 1.5 };
}

let hasShortcut = false;
let mode = null; // 'eq' or 'opt'

// SVG layout
// Nodes: S(40,110), A(170,40), B(170,180), E(310,110)
const SX=50,SY=110, AX=170,AY=45, BX=170,BY=175, EX=310,EY=110;

function buildSVG(state) {
  const flows = state || { f1:0, f2:0, f3:0 };
  const fSA = (flows.f1+flows.f3)*N;
  const fAE = flows.f1*N;
  const fSB = flows.f2*N;
  const fBE = (flows.f2+flows.f3)*N;
  const fAB = flows.f3*N;

  function roadColor(flow) {
    const t = flow / N;
    const r = Math.round(29 + t*(200-29));
    const g = Math.round(53 + t*(50-53));
    const b = Math.round(87 + t*(50-87));
    return `rgb(${r},${g},${b})`;
  }
  function arrowPath(x1,y1,x2,y2,offset) {
    const dx=x2-x1, dy=y2-y1, len=Math.sqrt(dx*dx+dy*dy);
    const ux=dx/len, uy=dy/len;
    return `M${x1+ux*offset},${y1+uy*offset} L${x2-ux*offset},${y2-uy*offset}`;
  }
  const scW = (f) => Math.max(2, f/N*8+2);

  let shortcutLine = '';
  if (hasShortcut) {
    const col = fAB > 0 ? roadColor(fAB) : '#e76f51';
    const w = scW(fAB);
    shortcutLine = fmt(`<line x1="%AX%" y1="%AY%" x2="%BX%" y2="%BY%" stroke="%col%" stroke-width="%w%" stroke-dasharray="5 3" stroke-linecap="round"/>
    <text x="%v%" y="%v2%" class="edge-label" text-anchor="middle">Free</text>
    <text x="%v%" y="%v3%" class="edge-load" text-anchor="middle" fill="%col%">%round%</text>`, { AX: AX, AY: AY, BX: BX, BY: BY, col: col, w: w, v: (AX+BX)/2+10, v2: (AY+BY)/2, v3: (AY+BY)/2+14, round: Math.round(fAB) });
  }

  return fmt(`<svg viewBox="0 0 360 220" xmlns="http://www.w3.org/2000/svg">
    <!-- S->A -->
    <line x1="%SX%" y1="%SY%" x2="%AX%" y2="%AY%" stroke="%roadColor%" stroke-width="%scW%" stroke-linecap="round"/>
    <text x="%v%" y="%v2%" class="edge-label">l=x</text>
    <text x="%v%" y="%v3%" class="edge-load" fill="%roadColor%">%round%</text>
    <!-- A->E -->
    <line x1="%AX%" y1="%AY%" x2="%EX%" y2="%EY%" stroke="%roadColor2%" stroke-width="%scW2%" stroke-linecap="round"/>
    <text x="%v4%" y="%v5%" class="edge-label" text-anchor="middle">l=45</text>
    <text x="%v4%" y="%v6%" class="edge-load" text-anchor="middle" fill="%roadColor2%">%round2%</text>
    <!-- S->B -->
    <line x1="%SX%" y1="%SY%" x2="%BX%" y2="%BY%" stroke="%roadColor3%" stroke-width="%scW3%" stroke-linecap="round"/>
    <text x="%v7%" y="%v8%" class="edge-label">l=45</text>
    <text x="%v7%" y="%v9%" class="edge-load" fill="%roadColor3%">%round3%</text>
    <!-- B->E -->
    <line x1="%BX%" y1="%BY%" x2="%EX%" y2="%EY%" stroke="%roadColor4%" stroke-width="%scW4%" stroke-linecap="round"/>
    <text x="%v10%" y="%v11%" class="edge-label" text-anchor="middle">l=x</text>
    <text x="%v10%" y="%v12%" class="edge-load" text-anchor="middle" fill="%roadColor4%">%round4%</text>
    %shortcutLine%
    <!-- Nodes -->
    <circle cx="%SX%" cy="%SY%" r="16" fill="#1d3557" stroke="none"/>
    <text x="%SX%" y="%v13%" class="node" fill="white" text-anchor="middle" font-size="12">Start</text>
    <circle cx="%EX%" cy="%EY%" r="16" fill="#1d3557" stroke="none"/>
    <text x="%EX%" y="%v14%" class="node" fill="white" text-anchor="middle" font-size="12">End</text>
    <circle cx="%AX%" cy="%AY%" r="14" fill="#e8eef3" stroke="#1d3557" stroke-width="1.5"/>
    <text x="%AX%" y="%v15%" class="node" text-anchor="middle" font-size="13">A</text>
    <circle cx="%BX%" cy="%BY%" r="14" fill="#e8eef3" stroke="#1d3557" stroke-width="1.5"/>
    <text x="%BX%" y="%v16%" class="node" text-anchor="middle" font-size="13">B</text>
  </svg>`, { SX: SX, SY: SY, AX: AX, AY: AY, roadColor: roadColor(fSA), scW: scW(fSA), v: (SX+AX)/2-12, v2: (SY+AY)/2-6, v3: (SY+AY)/2+8, round: Math.round(fSA), EX: EX, EY: EY, roadColor2: roadColor(fAE), scW2: scW(fAE), v4: (AX+EX)/2, v5: (AY+EY)/2-20, v6: (AY+EY)/2-6, round2: Math.round(fAE), BX: BX, BY: BY, roadColor3: roadColor(fSB), scW3: scW(fSB), v7: (SX+BX)/2-12, v8: (SY+BY)/2+14, v9: (SY+BY)/2+28, round3: Math.round(fSB), roadColor4: roadColor(fBE), scW4: scW(fBE), v10: (BX+EX)/2, v11: (BY+EY)/2+22, v12: (BY+EY)/2+36, round4: Math.round(fBE), shortcutLine: shortcutLine, v13: SY+5, v14: EY+5, v15: AY+5, v16: BY+5 });
}

function render(state) {
  document.getElementById('net').innerHTML = buildSVG(state);
}

function showStatus(text, cls) {
  const s = document.getElementById('status');
  s.textContent = text;
  s.className = 'status ' + cls;
}
function showExplain(html) {
  document.getElementById('explain').innerHTML = html;
}

document.getElementById('shortcut-toggle').addEventListener('change', function() {
  hasShortcut = this.checked;
  mode = null;
  render(null);
  showStatus('', '');
  showExplain(hasShortcut
    ? `Shortcut A→B added (cost 0). Press <b>Find Equilibrium</b> to see Braess’s paradox.`
    : `Shortcut removed. Two routes: top (S→A→E) and bottom (S→B→E).`);
});

document.getElementById('btn-eq').addEventListener('click', function() {
  const eq = computeWardrop(hasShortcut);
  mode = 'eq';
  render(eq);
  const cost = eq.cost.toFixed(2);
  const drivers1 = Math.round(eq.f1 * N), drivers2 = Math.round(eq.f2 * N), drivers3 = Math.round(eq.f3 * N);
  if (!hasShortcut) {
    showStatus(fmt(`Equilibrium cost: %cost% units (%drivers1% on top, %drivers2% on bottom)`, { cost: cost, drivers1: drivers1, drivers2: drivers2 }), 'neutral');
    showExplain(`At the Nash equilibrium, 50 drivers take each route. Both routes cost 0.5 + 1 = <b>1.5 units</b>. Nobody can save time by switching.`);
  } else {
    showStatus(fmt(`⚠ Equilibrium cost: %cost% units — WORSE than without the shortcut!`, { cost: cost }), 'worse');
    showExplain(fmt(`All %drivers3% drivers rationally pile onto route S→A→B→E (cost free shortcut). But total congestion on A and B makes every driver pay 1+1 = <b>2.0 units</b> — a 33% increase. <b>This is Braess’s paradox</b> (Dietrich Braess, 1968): a free road made everyone slower.`, { drivers3: drivers3 }));
  }
});

document.getElementById('btn-opt').addEventListener('click', function() {
  const opt = computeOptimum(hasShortcut);
  mode = 'opt';
  render(opt);
  showStatus(fmt(`Social optimum cost: %cost% units (50 on each main route)`, { cost: opt.cost.toFixed(2) }), 'better');
  showExplain(hasShortcut
    ? `The social optimum IGNORES the shortcut: 50 on S→A→E, 50 on S→B→E, cost = <b>1.5 units</b>. The price of anarchy = 2.0 / 1.5 = <b>4/3</b> — the worst ratio for linear-latency networks.`
    : `With linear latencies, the Nash equilibrium IS the social optimum here. Price of anarchy = 1.`);
});

document.getElementById('btn-reset').addEventListener('click', function() {
  mode = null;
  render(null);
  showStatus('', '');
  showExplain('');
});

// Initial render
render(null);
showExplain(`Network ready. Each road label shows its latency function (x = number of drivers). Edge numbers show current flows (0 until you press a button).`);
Result
Console

With the shortcut, every rational driver defects to the lower path — and the equilibrium cost jumps to 100 minutes. The shortcut made things worse. This is Braess's paradox, first described by the mathematician Dietrich Braess in 1968.

The Real Complexity

Congestion games sit at the intersection of game theory and complexity theory in several fascinating ways.

Existence (easy to prove, hard to find)

Rosenthal's 1973 potential function argument guarantees that every congestion game has a pure Nash equilibrium. The potential

Φ=∑r∑k=1nrcr(k)\Phi = \sum_{r} \sum_{k=1}^{n_r} c_r(k)

— summing costs on each road up to its current load — strictly decreases with every selfish move. Since Φ\Phi is bounded below, selfish play must terminate. But finding an equilibrium quickly is a different matter: the problem is PLS-complete (Polynomial Local Search complete), meaning it is as hard as finding local optima in any problem solvable by local search. No polynomial-time algorithm is known.

The price of anarchy

The price of anarchy (PoA) — the ratio of the worst equilibrium cost to the socially optimal cost — measures how much selfish routing hurts. For networks with linear latency functions (cost =ax+b= ax + b where xx is the flow on that edge), Roughgarden and Tardos proved in 2002 that the price of anarchy is at most 4/3. That means the worst selfish outcome is never more than one-third worse than the optimum. For polynomial latency functions of degree dd, the PoA grows with dd and can be unbounded.

Braess's paradox as a theorem

The paradox is not a fluke: Roughgarden showed in 2001 that it is NP-hard to decide whether removing a road from a network can improve the equilibrium travel time. In other words, the network planner's problem — "which roads should I build?" — is itself computationally difficult. See also P vs NP for the broader landscape.

Where It Matters

The congestion-game model appears wherever many agents share resources and each optimizes selfishly:

  • Internet routing: data packets choose least-congested paths through routers. The internet's decentralized routing protocols create congestion-game equilibria — and Braess's paradox has been observed empirically in real networks.
  • Power grids: electricity flows by least-resistance paths (Kirchhoff's laws are a physical version of selfish routing). Adding transmission lines can paradoxically overload the grid.
  • Vaccination and herd immunity: each person's decision to vaccinate (or not) is a congestion game — free-riding on others' immunity lowers individual incentive to vaccinate, creating suboptimal equilibria.
  • Supply chains: competing firms choosing suppliers or routes create congestion; the price-of-anarchy framework quantifies the efficiency loss from decentralized decisions.
  • Algorithmic mechanism design: economists design tolls and taxes ("Pigouvian taxes") to close the gap between the selfish equilibrium and the social optimum, making congestion games central to modern market-design theory.

For related equilibrium concepts, see Nash Equilibrium; for the broader hardness landscape, see P vs NP.

Conclusion

Congestion games capture a deep truth about decentralized systems: individual rationality and collective optimality are not the same thing. Rosenthal's potential function guarantees that selfish drivers always reach an equilibrium — but Braess's paradox shows that equilibrium can be dramatically worse than what a planner could achieve, and that adding capacity can paradoxically hurt everyone.

The price of anarchy quantifies the cost of selfishness, and Roughgarden and Tardos's bound of 4/3 for linear networks is one of the most elegant results in algorithmic game theory. It tells us that, at least in simple road networks, the invisible hand is never more than one-third inefficient.

Whether that is reassuring or alarming may depend on how much you are stuck in traffic — and whether you know that the shortcut you are about to take might be making it worse for all of you.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/congestion-games/Content licensed under CC BY-NC 4.0.