Introduction

Picture rush hour. Every driver picks the route that is fastest for them right now. No one is being unreasonable — yet the city as a whole ends up stuck in more traffic than if a benevolent dispatcher had assigned everyone a road.

That gap between what selfish players reach on their own and the best the system could have done is the price of anarchy. It is a single number: the ratio of the cost at a selfish equilibrium to the cost of the coordinated optimum. A price of 1 means selfishness is free; a price of 1.5 means anarchy costs us 50% extra.

And it gets stranger. Sometimes adding a resource makes things worse for everyone — a brand-new road can slow down every single driver. That is Braess's paradox, and it is not a glitch. It is exactly what self-interest does when there is no coordination.

Route the Drivers

Here is a tiny road network. One hundred drivers travel from Start to End. Two roads get slower the more drivers use them (their time equals the fraction of drivers on them); two are fixed at one hour. There is also a free shortcut in the middle.

<p class="hint">100 drivers go from <b>Start</b> to <b>End</b>. Two roads change with
traffic (their time = the fraction of drivers using them); two are fixed at 1 hour.
Toggle the free shortcut, then let drivers act <b>selfishly</b> or coordinate for the
<b>social optimum</b>. Watch what the shortcut does.</p>
<div class="net">
  <svg viewBox="0 0 320 200" id="svg">
    <line class="edge" id="e_sa" x1="40" y1="100" x2="160" y2="40"/>
    <line class="edge" id="e_at" x1="160" y1="40" x2="280" y2="100"/>
    <line class="edge" id="e_sb" x1="40" y1="100" x2="160" y2="160"/>
    <line class="edge" id="e_bt" x1="160" y1="160" x2="280" y2="100"/>
    <line class="edge cross" id="e_ab" x1="160" y1="40" x2="160" y2="160"/>
    <circle class="node" cx="40" cy="100" r="16"/><text x="40" y="104">S</text>
    <circle class="node" cx="160" cy="40" r="16"/><text x="160" y="44">A</text>
    <circle class="node" cx="160" cy="160" r="16"/><text x="160" y="164">B</text>
    <circle class="node end" cx="280" cy="100" r="16"/><text x="280" y="104">T</text>
    <text class="lbl" id="l_sa" x="92" y="60">load</text>
    <text class="lbl" id="l_at" x="228" y="60">1 h</text>
    <text class="lbl" id="l_sb" x="92" y="148">1 h</text>
    <text class="lbl" id="l_bt" x="228" y="148">load</text>
    <text class="lbl" id="l_ab" x="172" y="104">free</text>
  </svg>
</div>
<label class="toggle"><input type="checkbox" id="shortcut" checked> Shortcut road A→B open (free)</label>
<div class="readout" id="readout"></div>
<div class="btns">
  <button id="selfish" type="button">Let drivers be selfish</button>
  <button id="social" type="button">Social optimum</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.net { display: flex; justify-content: center; }
svg { width: 100%; max-width: 360px; height: auto; }
.edge { stroke: #adb1b8; stroke-width: 6; stroke-linecap: round; }
.edge.hot { stroke: #e63946; }
.edge.off { stroke-dasharray: 4 6; opacity: .35; }
.node { fill: #e8eef3; stroke: #1d3557; stroke-width: 2; }
.node.end { fill: #1d3557; }
text { font: 700 13px ui-monospace, monospace; fill: #1d3557; text-anchor: middle; }
.node.end + text { fill: #fff; }
.lbl { font: 600 10px system-ui, sans-serif; fill: #555; }
.toggle { display: block; font-size: .9rem; margin: .4rem 0; cursor: pointer; }
.readout { font-size: .95rem; line-height: 1.6; margin: .5rem 0; min-height: 5.2em;
           background: #f4f6f9; border: 1px solid #dde3ea; border-radius: 8px; padding: .6rem .8rem; }
.readout b { color: #1d3557; }
.big { font-weight: 700; }
.warn { color: #c92f3c; font-weight: 700; }
.good { color: #0a7d33; font-weight: 700; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button:nth-child(2) { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// The "price of anarchy" = (cost when everyone is selfish) / (cost of the
// coordinated optimum). This classic network reproduces Braess’s paradox:
// adding a fast road can make EVERY driver slower at equilibrium.
// Fixed edges (A-T, S-B) cost 1 hour. The shortcut A-B is free.
const N = 100;

function avgTime(top, bottom, cross){
  const loadSA = (top + cross) / N;   // S->A used by Top + Cross routes
  const loadBT = (bottom + cross) / N; // B->T used by Bottom + Cross routes
  const tTop = loadSA + 1;             // S-A (load) + A-T (1h)
  const tBottom = 1 + loadBT;          // S-B (1h) + B-T (load)
  const tCross = loadSA + loadBT;      // S-A (load) + A-B (free) + B-T (load)
  return (top*tTop + bottom*tBottom + cross*tCross) / N;
}

// Best-response dynamics: repeatedly move one driver off the slowest route
// onto the fastest, until nobody can improve — a Nash (selfish) equilibrium.
function equilibrium(shortcut){
  let top = N/2, bottom = N/2, cross = 0;
  for(let i=0; i<4000; i++){
    const loadSA=(top+cross)/N, loadBT=(bottom+cross)/N;
    const tTop=loadSA+1, tBottom=1+loadBT, tCross = shortcut ? (loadSA+loadBT) : Infinity;
    const R=[['top',tTop,top],['bottom',tBottom,bottom],['cross',tCross,cross]];
    const used=R.filter(r=>r[2]>0);
    const worst=used.reduce((a,b)=>a[1]>b[1]?a:b);
    const best=R.reduce((a,b)=>a[1]<b[1]?a:b);
    if(worst[1]-best[1] < 1e-9) break;
    if(worst[0]==='top')top--; else if(worst[0]==='bottom')bottom--; else cross--;
    if(best[0]==='top')top++; else if(best[0]==='bottom')bottom++; else cross++;
  }
  return {top,bottom,cross,avg:avgTime(top,bottom,cross)};
}

// Social optimum: search every split for the lowest AVERAGE travel time.
function socialOpt(shortcut){
  let best={avg:Infinity,top:0,bottom:0,cross:0};
  const maxC = shortcut ? N : 0;
  for(let cross=0; cross<=maxC; cross++)
    for(let top=0; top<=N-cross; top++){
      const a=avgTime(top, N-cross-top, cross);
      if(a<best.avg) best={top,bottom:N-cross-top,cross,avg:a};
    }
  return best;
}

const $ = id => document.getElementById(id);
function paint(r){
  $('e_ab').classList.toggle('off', !$('shortcut').checked);
  // highlight S-A and B-T red when heavily loaded (cross route hammers them)
  const loadSA=(r.top+r.cross)/N, loadBT=(r.bottom+r.cross)/N;
  $('e_sa').classList.toggle('hot', loadSA>0.75);
  $('e_bt').classList.toggle('hot', loadBT>0.75);
}
function show(label, r, baseline){
  paint(r);
  const t = r.avg.toFixed(2);
  let extra='';
  if(baseline!=null){
    const slower = r.avg > baseline + 1e-9;
    extra = slower
      ? fmt('<br><span class="warn">⚠ Braess’s paradox: the shortcut made everyone slower (%baseline% h → %t% h).</span>', { baseline: baseline.toFixed(2), t: t })
      : '<br><span class="good">No paradox here — the shortcut didn’t hurt.</span>';
  }
  $('readout').innerHTML =
    fmt('<b>%label%</b><br>Top route: %top% · Bottom: %bottom% · Shortcut S→A→B→T: %cross%<br>Average travel time: <span class="big">%t% hours</span>%extra%', { label: label, top: r.top, bottom: r.bottom, cross: r.cross, t: t, extra: extra });
}

let lastSocialNoShortcut = null;
$('selfish').addEventListener('click', ()=>{
  const sc = $('shortcut').checked;
  const r = equilibrium(sc);
  // baseline = selfish time WITHOUT the shortcut, to expose the paradox
  const base = sc ? equilibrium(false).avg : null;
  show('Selfish equilibrium (everyone for themselves)', r, base);
});
$('social').addEventListener('click', ()=>{
  const r = socialOpt($('shortcut').checked);
  show('Social optimum (coordinated)', r, null);
});
$('shortcut').addEventListener('change', ()=>{ paint({top:50,bottom:50,cross:0}); $('readout').innerHTML='Pick a strategy below.'; });
paint({top:50,bottom:50,cross:0});
$('readout').innerHTML='Pick a strategy below.';
Result
Console

Run Social optimum with the shortcut open: the best plan ignores the shortcut entirely and splits traffic evenly — 1.5 hours each. Now run Let drivers be selfish: everyone piles onto the shortcut and the average jumps to 2.0 hours. The price of anarchy here is 2.0 / 1.5 ≈ 1.33. Then close the shortcut and let drivers be selfish again — they speed up. Demolishing a road made everyone faster.

The Real Complexity

How bad can anarchy get, exactly? This is not an open question waiting on a proof — large parts of it are settled theorems.

  • The concept was introduced in 1999 by Elias Koutsoupias and Christos Papadimitriou, who asked how far a Nash equilibrium can sit from the social optimum.
  • The bound is tight for traffic. In 2002 Tim Roughgarden and Éva Tardos proved that for networks with linear congestion (delay grows in proportion to load — exactly our demo), the price of anarchy is at most 4/3, and this is the worst possible. Our little network hits that bound dead-on: 2.0 / 1.5 = 4/3.
  • Worse latencies, worse anarchy. Make the delays grow faster (degree-d polynomials) and the bound climbs; with unbounded latencies it can blow up entirely.
  • What stays hard. Finding a Nash equilibrium in a general game is PPAD-complete — believed intractable, a cousin of the questions behind P vs NP. And deciding the best coordinated routing is itself an optimization problem akin to max-flow and other Nash-equilibrium computations.

So the headline is precise: anarchy has a provably bounded cost in nice cases (4/3 for linear traffic), but pinning down equilibria in general is exactly where computation gets hard.

Where It Matters

Whenever many independent agents share a congestible resource, the price of anarchy is lurking:

  • Traffic and urban planning. Braess's paradox is real: closing streets in Seoul, Stuttgart and New York has improved flow. A new road is not automatically a faster city.
  • The Internet. Packets and BGP routes are chosen locally and selfishly; the same theory bounds how much that decentralization costs versus central control.
  • Cloud and load balancing. Jobs that each grab the least-loaded server reach an equilibrium that designers compare against the optimal schedule — close to the world of load balancing.
  • Markets and mechanism design. Knowing the price of anarchy tells you when to add tolls, prices or incentives to steer selfish behavior back toward the optimum.

The lesson is practical: you rarely get to command everyone, so you design the rules so that selfish play lands near the social optimum anyway.

Conclusion

The price of anarchy turns a fuzzy worry — "won't everyone acting selfishly mess things up?" — into a number you can prove things about. For linear traffic it never exceeds 4/3; for harsher congestion it grows; and Braess's paradox warns that more capacity can make every user worse off.

The deep point is that good outcomes are rarely automatic. Left alone, a crowd settles into an equilibrium that no one can improve unilaterally yet everyone would happily trade away. Closing a road, adding a toll, or nudging an incentive can beat any amount of extra asphalt. Like Nash equilibrium and the limits behind P vs NP, the price of anarchy reminds us that the hard part is not choosing well — it is getting a whole system to choose well together.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/price-of-anarchy/Content licensed under CC BY-NC 4.0.