Introduction

Every rush-hour driver picks the fastest route for themselves. Every data packet on the internet takes the least-congested path its protocol can find. Neither driver nor packet is trying to help anyone else — yet the whole system somehow settles into a stable pattern. Why?

The answer, for a wide class of games, is the existence of a potential function: a single real-valued score over every possible combination of players' choices such that whenever any one player changes strategy to reduce their own cost, the potential function also decreases. One number tracks the entire population's incentives at once.

This idea was formalized in 1996 by Dov Monderer and Lloyd Shapley in their landmark paper Potential Games. The key theorem is elegant: if a potential function exists, then best-response dynamics always converge to a Nash equilibrium. No coordination needed; each player just chases their own interest, and the system is guaranteed to stabilize.

The classic example is a congestion game: players share resources (roads, links, servers), and a resource's cost to everyone rises with its load. Monderer and Shapley proved that every congestion game is a potential game — with the potential being a particular sum of partial costs — so every best-response walk in a congestion game terminates at equilibrium.

Try It: Route Traffic

Below is a small network with two paths from S to T. Each edge shows its current load and cost. Traffic is split between the two paths; drag the slider to adjust the split, or click Best-Response Step to let the system automatically move traffic toward the cheaper path — lowering the potential each time.

<div class="net-wrap">
  <svg id="net" viewBox="0 0 400 220" xmlns="http://www.w3.org/2000/svg"></svg>
</div>
<div class="controls">
  <label>Path 1 traffic (red): <span id="f1val">5</span> / 10
    <input type="range" id="slider" min="0" max="10" value="5" step="1">
  </label>
</div>
<div class="stats" id="stats"></div>
<div class="btns">
  <button id="stepBtn" type="button">Best-Response Step</button>
  <button id="resetBtn" type="button" class="ghost">Reset</button>
</div>
<p class="hint">At Wardrop equilibrium both paths cost the same — no unit of traffic can switch paths and save cost.</p>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 14px; }
.net-wrap { background: #f0f4f8; border-radius: 10px; padding: 4px; margin-bottom: 10px; }
svg { width: 100%; display: block; }
.controls { margin: 6px 0; }
label { font-size: .9rem; display: flex; flex-direction: column; gap: 4px; }
input[type=range] { width: 100%; accent-color: #1d3557; }
.stats { font-size: .9rem; background: #e8eef3; border-radius: 8px; padding: 8px 12px; margin: 8px 0; line-height: 1.7; }
.stats b { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: 6px; }
button { font: 600 14px system-ui; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.hint { font-size: .82rem; color: #555; margin: 8px 0 0; line-height: 1.4; }
.eq-msg { color: #0a7d33; font-weight: 700; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Network: two parallel paths S -> T, total flow = 10 units.
// Path 1 (red):  one edge with cost c1(f1) = 2 * f1
// Path 2 (blue): one edge with cost c2(f2) = 3 * f2  (f2 = 10 - f1)
//
// Wardrop / Nash equilibrium (integer): c1(f1) = c2(f2)
//   2*f1 = 3*(10-f1)  =>  2f1 = 30 - 3f1  =>  5f1 = 30  =>  f1 = 6, f2 = 4
//   c1(6) = 12, c2(4) = 12  ✓
//
// Rosenthal potential: Phi(f1) = sum_{k=1}^{f1} 2k + sum_{k=1}^{f2} 3k
//                               = f1*(f1+1) + 3*f2*(f2+1)/2
const TOTAL = 10;

function cost1(f1) { return 2 * f1; }
function cost2(f2) { return 3 * f2; }

function potential(f1) {
  const f2 = TOTAL - f1;
  // sum_{k=1}^{f1} 2k = 2 * f1*(f1+1)/2 = f1*(f1+1)
  // sum_{k=1}^{f2} 3k = 3 * f2*(f2+1)/2
  return f1 * (f1 + 1) + 3 * f2 * (f2 + 1) / 2;
}

function bestResponseStep(f1) {
  const f2 = TOTAL - f1;
  const c1 = cost1(f1);
  const c2 = cost2(f2);
  // Move one unit from the more expensive path to the cheaper one
  if (c1 > c2 && f1 > 0) return f1 - 1;
  if (c2 > c1 && f2 > 0) return f1 + 1;
  return f1; // equilibrium: costs are equal (or no flow to shift)
}

// SVG helpers
const SVG_NS = 'http://www.w3.org/2000/svg';
function svgEl(tag, attrs, text) {
  const e = document.createElementNS(SVG_NS, tag);
  Object.entries(attrs).forEach(([k, v]) => e.setAttribute(k, v));
  if (text !== undefined) e.textContent = text;
  return e;
}

function drawNetwork(f1) {
  const f2 = TOTAL - f1;
  const c1 = cost1(f1), c2 = cost2(f2);
  const svg = document.getElementById('net');
  svg.innerHTML = '';

  // Node positions
  const S = [60, 110], T = [340, 110];
  // Upper (path 1) and lower (path 2) midpoints
  const M1 = [200, 55], M2 = [200, 165];

  const paths = [
    { from: S, mid: M1, to: T, flow: f1, cost: c1, color: '#e63946', label: fmt('Path 1: cost = 2×%f1% = %c1%', { f1: f1, c1: c1 }) },
    { from: S, mid: M2, to: T, flow: f2, cost: c2, color: '#457b9d', label: fmt('Path 2: cost = 3×%f2% = %c2%', { f2: f2, c2: c2 }) }
  ];

  paths.forEach(({ from, mid, to, flow, color, label }) => {
    // Draw arc through midpoint as two line segments
    const segs = [[from, mid], [mid, to]];
    segs.forEach(([[x1,y1],[x2,y2]]) => {
      svg.appendChild(svgEl('line', { x1,y1,x2,y2, stroke:'#cdd9e3', 'stroke-width':10, 'stroke-linecap':'round' }));
      const w = Math.max(3, flow * 1.6);
      svg.appendChild(svgEl('line', { x1,y1,x2,y2, stroke:color, 'stroke-width':w, 'stroke-linecap':'round', opacity:0.75 }));
    });
    // Arrowhead at T
    const [ax,ay] = to; const [mx,my] = mid;
    const angle = Math.atan2(ay - my, ax - mx);
    const len = 10;
    const a1x = ax - len*Math.cos(angle-0.4), a1y = ay - len*Math.sin(angle-0.4);
    const a2x = ax - len*Math.cos(angle+0.4), a2y = ay - len*Math.sin(angle+0.4);
    svg.appendChild(svgEl('polygon', { points:`${ax},${ay} ${a1x},${a1y} ${a2x},${a2y}`, fill:color, opacity:0.85 }));
    // Label near midpoint
    const lx = (mid[0]+to[0])/2, ly = mid[1] < 110 ? mid[1]-12 : mid[1]+18;
    svg.appendChild(svgEl('text', { x:lx, y:ly, 'font-size':11, 'text-anchor':'middle', fill:color, 'font-family':'system-ui', 'font-weight':'bold' }, label));
  });

  // Nodes
  [[S,'S'],[T,'T']].forEach(([[cx,cy],name]) => {
    svg.appendChild(svgEl('circle', { cx, cy, r:20, fill:'#1d3557', stroke:'none' }));
    svg.appendChild(svgEl('text', { x:cx, y:cy+5, 'font-size':14, 'text-anchor':'middle', fill:'#fff', 'font-family':'system-ui', 'font-weight':'bold' }, name));
  });
}

function updateStats(f1) {
  const f2 = TOTAL - f1;
  const c1 = cost1(f1), c2 = cost2(f2);
  const phi = potential(f1);
  const atEq = bestResponseStep(f1) === f1;
  const eqNote = atEq
    ? " " + fmt('<span class="eq-msg">✓ Equilibrium! Both paths cost %c1%.</span>', { c1: c1 })
    : (c1 < c2
      ? " " + '→ Path 1 is cheaper; best response moves traffic there.'
      : " " + '→ Path 2 is cheaper; best response moves traffic there.');
  document.getElementById('stats').innerHTML =
    fmt('<b>Path 1</b> (red): flow = %f1%, cost per unit = <b>%c1%</b><br><b>Path 2</b> (blue): flow = %f2%, cost per unit = <b>%c2%</b><br><b>Potential Φ</b> = %phi%%eqNote%', { f1: f1, c1: c1, f2: f2, c2: c2, phi: phi, eqNote: eqNote });
}

function render(f1) {
  document.getElementById('f1val').textContent = f1;
  document.getElementById('slider').value = f1;
  drawNetwork(f1);
  updateStats(f1);
}

let state = 5;
render(state);

document.getElementById('slider').addEventListener('input', e => {
  state = +e.target.value;
  render(state);
});

document.getElementById('stepBtn').addEventListener('click', () => {
  const next = bestResponseStep(state);
  if (next !== state) {
    state = next;
    render(state);
  }
});

document.getElementById('resetBtn').addEventListener('click', () => {
  state = 5;
  render(state);
});

// --- Node verification of core math ---
// Equilibrium: f1=6, f2=4, c1=12, c2=12
console.assert(cost1(6) === 12, 'cost1(6) should be 12');
console.assert(cost2(4) === 12, 'cost2(4) should be 12');
console.assert(cost1(6) === cost2(4), 'Costs equal at equilibrium f1=6');

// Best-response at various points
console.assert(bestResponseStep(0) === 1,  'f1=0: c1=0 < c2=30, move to path1');
console.assert(bestResponseStep(10) === 9, 'f1=10: c1=20 > c2=0, move to path2');
console.assert(bestResponseStep(5) === 6,  'f1=5: c1=10 < c2=15, move to path1');
console.assert(bestResponseStep(7) === 6,  'f1=7: c1=14 > c2=9, move to path2');
console.assert(bestResponseStep(6) === 6,  'f1=6: equilibrium, no change');

// Potential strictly decreases each best-response step
const phi5 = potential(5);  // f1=5 -> step -> f1=6
const phi6 = potential(6);
const phi7 = potential(7);  // f1=7 -> step -> f1=6
console.assert(phi6 < phi5, 'Potential decreases: phi(6) < phi(5)');
console.assert(phi6 < phi7, 'Potential decreases: phi(6) < phi(7)');

// Phi(6) = 6*7 + 3*4*5/2 = 42 + 30 = 72
console.assert(phi6 === 72, fmt('phi(6) = 72, got %phi6%', { phi6: phi6 }));
// Phi(5) = 5*6 + 3*5*6/2 = 30 + 45 = 75
console.assert(phi5 === 75, fmt('phi(5) = 75, got %phi5%', { phi5: phi5 }));
// Phi(7) = 7*8 + 3*3*4/2 = 56 + 18 = 74
console.assert(phi7 === 74, fmt('phi(7) = 74, got %phi7%', { phi7: phi7 }));

console.log('All assertions passed. Equilibrium at f1=6, phi=72.');
Result
Console

Watch the Potential Φ value fall with every best-response step. When no single unit of traffic can switch paths and lower its own cost, the system has reached Wardrop equilibrium — the continuous analogue of Nash equilibrium for routing, where all used paths have equal cost.

The Theory

A game is an exact potential game (Monderer & Shapley, 1996) when there exists a function Φ\Phi over the joint strategy space such that for every player ii and every pair of strategies sis_i vs si′s_i' (with all others fixed):

Φ(si′,s−i)−Φ(si,s−i)=ci(si′,s−i)−ci(si,s−i)\Phi(s_i', s_{-i}) - \Phi(s_i, s_{-i}) = c_i(s_i', s_{-i}) - c_i(s_i, s_{-i})

The potential changes by exactly the amount the deviating player's cost changes. This immediately implies:

  • Finite Improvement Property: every sequence of strict improvements is finite (the potential is a discrete Lyapunov function, strictly decreasing each step).
  • Convergence guarantee: best-response dynamics terminate at a pure Nash equilibrium — provably, without any coordination.
  • Nash equilibria = local minima of Φ: finding equilibria reduces to finding local optima of one scalar function.

Congestion games (Rosenthal, 1973) are the archetypal example. Each player picks a subset of shared resources; each resource ee has a cost function ce(k)c_e(k) that depends only on how many players use it. The Rosenthal potential is:

Φ(s)=∑e∑k=1∣e∣ce(k)\Phi(s) = \sum_e \sum_{k=1}^{|e|} c_e(k)

where the sum over kk runs up to the number of players currently using edge ee. Monderer and Shapley showed that every congestion game has this potential, so every best-response walk terminates. The Price of Anarchy — how much worse the equilibrium is versus a centrally optimized solution — is a separate question that depends on the specific cost functions, and is the subject of ongoing research.

Where It Matters

Potential games describe any system where selfish agents share resources and adapt greedily. The guaranteed convergence to equilibrium makes them a natural model for:

  • Internet routing: TCP congestion control and BGP route selection are approximate best-response dynamics on a congestion game. The potential function is why large-scale routing stabilizes rather than oscillating forever.
  • Spectrum and channel assignment: wireless devices picking frequency channels to minimize interference form a congestion game. Potential-game analysis proves distributed channel-selection protocols converge.
  • Load balancing: jobs assigned to machines, with cost equal to machine load, form a classic congestion game (the "scheduling on unrelated machines" variant is NP-hard to optimize centrally, yet best-response converges).
  • Network formation: agents choosing which links to build or use in peer-to-peer and social networks often satisfy the potential property, explaining observed structural stability.
  • Evolutionary game theory: replicator dynamics in biology converge to equilibrium in potential games — giving a formal reason why evolutionarily stable strategies exist in these settings.

The flip side: equilibria in potential games may be far from socially optimal. The Price of Anarchy in routing games can reach 4/3 for linear costs (Roughgarden & Tardos, 2002) — meaning selfish routing wastes up to one-third of network capacity versus a centrally planned optimum.

Conclusion

Potential games reveal a beautiful hidden order: when a single function shadows every player's selfish incentives, the system is guaranteed to stabilize. No authority coordinates the drivers on a highway or the packets on the internet — each agent follows its own gradient, and the potential function ensures the walk always terminates at equilibrium.

Monderer and Shapley's 1996 insight transformed how we understand distributed systems: look for the potential, and convergence is free. The open questions — how bad the equilibrium can be, how quickly dynamics converge, and whether approximate potentials give approximate guarantees — remain active frontiers connecting game theory, algorithms, and network science. The next time your video call quality drops as millions of others stream the same event, remember: the internet is running a best-response walk, chasing a potential function toward equilibrium.

Share this article

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

Comments

Loading comments...

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