Baseball Elimination

Introduction

In late September, the standings of a baseball division come with a quiet question attached: which teams are already mathematically out? A team is eliminated when no way of playing out the remaining games lets it finish with the most wins (a tie for first still counts as alive).

There is an easy way to be eliminated. Let $w_i$ be the wins of team $i$ and $r_i$ the games it still has to play. If team $x$ wins every remaining game it reaches $w_x + r_x$ wins. If some other team already has more than that, $x$ is out. This is called trivial elimination, and you can see it by reading the table.

The interesting case is non-trivial elimination: every rival's current wins are below $w_x + r_x$ , and yet $x$ is still dead. The reason hides in the schedule. Take the classic four-team example from the demo below: Philadelphia has 80 wins and 3 games left, so it can reach at most $83$ . Atlanta ( $83$ wins now) and New York ( $78$ ) still have six games against each other, and those six games hand out six wins to those two teams alone. Between them they will end with $83 + 78 + 6 = 167$ wins, an average of $83.5$ , so one of them finishes above $83$ whatever happens. Philadelphia is dead although no single rival has passed it yet.

Finding such a hidden obstruction by hand quickly becomes guesswork. In 1966 B. L. Schwartz showed in SIAM Review that the question can be answered exactly, in polynomial time, by building a small flow network and running a maximum-flow algorithm. The same idea was generalized by Alan Hoffman and Thomas Rivlin (the paper appeared in 1970), and today it is a standard application of maximum flow in algorithms courses.

The key idea: pretend that team $x$ wins every one of its remaining games, so its final total $M = w_x + r_x$ is fixed. Every other game still to be played will produce exactly one win, and that win must go to one of the two teams playing it. Can all those wins be handed out so that nobody ends above $M$ ? That is a supply-and-demand question, and supply-and-demand is exactly what flow networks model.

Try It: Is Your Team Out?

The table holds a division: wins (W), losses (L) and the number of games still to play between every pair of teams. Pick a team and the demo builds its network:

a source $s$ connected to one node for every pair of other teams that still play each other, with capacity equal to the number of games left in that pair;
each of those game nodes connected, with unlimited capacity, to the two teams involved, because either may win;
each team connected to the sink $t$ with capacity $w_x + r_x - w_i$ , the number of extra wins team $i$ can take before it passes $x$ .

<!-- Interface: preset buttons, standings table, team selector, step buttons, network drawing. -->
<div class="wrap">
  <p class="hint">Edit wins, losses and the games left between each pair of teams, pick the team you are worried about, and watch the flow network decide whether it can still finish first.</p>
  <div class="row presets">
    <button id="p_classic" type="button" class="ghost">Classic 4 teams</button>
    <button id="p_five" type="button" class="ghost">5 teams, subtle case</button>
    <button id="p_alive" type="button" class="ghost">5 teams, still alive</button>
  </div>
  <div class="scroll"><table id="tbl" class="tbl" aria-label="Standings and remaining games"></table></div>
  <p class="note">W = wins, L = losses, R = games left. The grid on the right holds the games left between each pair (it stays symmetric).</p>
  <div class="row">
    <label for="team">Team to test:</label>
    <select id="team"></select>
  </div>
  <div class="row">
    <button id="step" type="button">Next augmenting path</button>
    <button id="run" type="button">Run to the end</button>
    <button id="reset" type="button" class="ghost">Reset flow</button>
  </div>
  <div class="status" id="status" aria-live="polite"></div>
  <div class="scroll"><svg id="net" class="net" viewBox="0 0 640 160" role="img" aria-label="Flow network: source, one node per remaining game, one node per team, sink"></svg></div>
  <p class="legend">Left to right: source s, one node per pair of other teams with games left (capacity = games left), one node per team, sink t (capacity = wins that team may still add). Orange = current augmenting path, blue = carries flow, green = full edge, red dashed = minimum cut.</p>
  <div class="cert" id="cert" aria-live="polite"></div>
</div>

/* Colours follow the light or dark preference of the visitor. */
:root { --fg:#1f2933; --bg:#ffffff; --mut:#52606d; --line:#c3ccd6; --acc:#1d3557; --ok:#0a7d33; --bad:#c92f3c; --pth:#e8890c; --soft:#eef2f6; --fl:#2a6fb0; }
@media (prefers-color-scheme: dark) {
  :root { --fg:#e6ebf0; --bg:#1b2430; --mut:#a7b4c2; --line:#46566a; --acc:#7fb0e6; --ok:#4cc27a; --bad:#ff7a85; --pth:#ffb347; --soft:#243243; --fl:#6fb3f2; }
}
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: var(--fg); background: var(--bg); margin: 0; }
.wrap { padding: .6rem; }
.hint { font-size: .9rem; color: var(--mut); margin: 0 0 .6rem; line-height: 1.45; }
.note, .legend { font-size: .8rem; color: var(--mut); margin: .3rem 0; line-height: 1.4; }
.row { display: flex; gap: .5rem; flex-wrap: wrap; align-items: center; margin: .5rem 0; }
.scroll { overflow-x: auto; }
.tbl { border-collapse: collapse; font-size: .85rem; }
.tbl th, .tbl td { padding: 2px 4px; text-align: center; border-bottom: 1px solid var(--line); }
.tbl th { color: var(--mut); font-weight: 600; }
.tbl .nm { text-align: left; white-space: nowrap; font-weight: 600; padding-right: .6rem; }
.tbl .rem { font-weight: 700; color: var(--acc); }
.tbl .dg { color: var(--mut); }
.tbl input { width: 3.1em; padding: 3px 2px; text-align: center; font: inherit; color: var(--fg); background: var(--soft); border: 1px solid var(--line); border-radius: 5px; }
label { font-size: .9rem; font-weight: 600; }
select { font: inherit; padding: .3rem .5rem; color: var(--fg); background: var(--soft); border: 1px solid var(--line); border-radius: 6px; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid var(--acc); background: var(--acc); color: var(--bg); border-radius: 8px; cursor: pointer; }
button.ghost { background: transparent; color: var(--acc); }
button:disabled { opacity: .45; cursor: default; }
.status { font-size: .95rem; font-weight: 600; margin: .4rem 0; min-height: 2.8em; line-height: 1.4; }
.status.ok { color: var(--ok); }
.status.bad { color: var(--bad); }
.net { display: block; width: 100%; min-width: 520px; height: auto; background: var(--soft); border-radius: 8px; }
.ed { stroke: var(--line); stroke-width: 1.4; }
.ed.fl { stroke: var(--fl); stroke-width: 2.2; }
.ed.sat { stroke: var(--ok); }
.ed.pth { stroke: var(--pth); stroke-width: 4; }
.ed.cut { stroke: var(--bad); stroke-dasharray: 5 4; stroke-width: 3; }
.nd { fill: var(--bg); stroke: var(--acc); stroke-width: 1.6; }
.nd.s, .nd.t { fill: var(--acc); }
.nd.inS { stroke: var(--bad); stroke-width: 3; }
.nl { font: 600 10px system-ui, sans-serif; fill: var(--fg); pointer-events: none; }
.nd.s + .nl, .nd.t + .nl { fill: var(--bg); }
.el { font: 600 10px system-ui, sans-serif; fill: var(--mut); paint-order: stroke; stroke: var(--soft); stroke-width: 3px; }
.cap { font: 600 10px system-ui, sans-serif; fill: var(--mut); }
.cert { font-size: .9rem; line-height: 1.5; margin-top: .4rem; }
.cert:not(:empty) { padding: .5rem .7rem; border-left: 4px solid var(--bad); background: var(--soft); border-radius: 6px; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
const INF = 1000000;
// Core: builds the flow network and solves it with Edmonds-Karp (shortest augmenting paths found by breadth-first search).
const remOf = (g, i) => g[i].reduce((a, b) => a + b, 0);
function buildNet(teams, g, x) {
  const n = teams.length;
  const maxW = teams[x].w + remOf(g, x);
  const net = { x, maxW, nodes: [], edges: [], adj: [], total: 0, trivial: -1, flow: 0 };
  for (let i = 0; i < n; i++) if (i !== x && teams[i].w > maxW && net.trivial < 0) net.trivial = i;
  const addNode = (o) => { net.nodes.push(o); net.adj.push([]); return net.nodes.length - 1; };
  const addEdge = (u, v, cap) => {
    net.edges.push({ u, v, cap, flow: 0 }); net.adj[u].push(net.edges.length - 1);
    net.edges.push({ u: v, v: u, cap: 0, flow: 0 }); net.adj[v].push(net.edges.length - 1);
  };
  const s = addNode({ type: 's' });
  const others = [];
  for (let i = 0; i < n; i++) if (i !== x) others.push(i);
  const gameNodes = [];
  for (let a = 0; a < others.length; a++) for (let b = a + 1; b < others.length; b++) {
    const i = others[a], j = others[b];
    if (g[i][j] > 0) gameNodes.push({ i, j, c: g[i][j] });
  }
  const gid = gameNodes.map((gm) => addNode({ type: 'g', i: gm.i, j: gm.j, c: g[gm.i][gm.j] }));
  const tid = {};
  others.forEach((i) => { tid[i] = addNode({ type: 'T', i }); });
  const t = addNode({ type: 't' });
  net.s = s; net.t = t;
  gameNodes.forEach((gm, k) => {
    addEdge(s, gid[k], gm.c); net.total += gm.c;
    addEdge(gid[k], tid[gm.i], INF); addEdge(gid[k], tid[gm.j], INF);
  });
  others.forEach((i) => addEdge(tid[i], t, Math.max(0, maxW - teams[i].w)));
  return net;
}
function bfs(net) {
  const par = new Array(net.nodes.length).fill(-1);
  const seen = new Array(net.nodes.length).fill(false);
  seen[net.s] = true; const q = [net.s];
  while (q.length) {
    const u = q.shift();
    for (const ei of net.adj[u]) {
      const e = net.edges[ei];
      if (!seen[e.v] && e.cap - e.flow > 0) { seen[e.v] = true; par[e.v] = ei; q.push(e.v); }
    }
  }
  if (!seen[net.t]) return { path: null, seen };
  const path = []; let v = net.t;
  while (v !== net.s) { path.push(par[v]); v = net.edges[par[v]].u; }
  return { path: path.reverse(), seen };
}
function augment(net) {
  const r = bfs(net);
  if (!r.path) { net.seen = r.seen; return null; }
  let d = Infinity;
  for (const ei of r.path) d = Math.min(d, net.edges[ei].cap - net.edges[ei].flow);
  for (const ei of r.path) { net.edges[ei].flow += d; net.edges[ei ^ 1].flow -= d; }
  net.flow += d;
  return { path: r.path, delta: d };
}
function certificate(teams, g, net) {
  const R = [];
  net.nodes.forEach((nd, k) => { if (nd.type === 'T' && net.seen[k]) R.push(nd.i); });
  let wR = 0, gR = 0;
  R.forEach((i) => { wR += teams[i].w; });
  for (let a = 0; a < R.length; a++) for (let b = a + 1; b < R.length; b++) gR += g[R[a]][R[b]];
  return { R, wR, gR };
}
// Interface code: presets, table editing, drawing and buttons.
const PRESETS = {
  classic: { x: 1, teams: [
    { name: 'Atlanta', ab: 'ATL', w: 83, l: 71 }, { name: 'Philadelphia', ab: 'PHI', w: 80, l: 79 },
    { name: 'New York', ab: 'NY', w: 78, l: 78 }, { name: 'Montreal', ab: 'MON', w: 77, l: 82 }],
    g: [[0, 1, 6, 1], [1, 0, 0, 2], [6, 0, 0, 0], [1, 2, 0, 0]] },
  five: { x: 3, teams: ['A', 'B', 'C', 'D', 'E'].map((c, i) => ({ name: c, ab: c, w: [68, 68, 66, 65, 63][i], l: 0 })),
    g: [[0, 0, 3, 2, 2], [0, 0, 3, 1, 1], [3, 3, 0, 0, 1], [2, 1, 0, 0, 1], [2, 1, 1, 1, 0]] },
  alive: { x: 2, teams: null, g: null }
};
PRESETS.five.teams.forEach((t, i) => { t.l = 162 - t.w - remOf(PRESETS.five.g, i); });
PRESETS.alive.teams = PRESETS.five.teams; PRESETS.alive.g = PRESETS.five.g;
let TEAMS, G, X, NET, LAST = null, DONE = false, STEPS = 0;
const $ = (id) => document.getElementById(id);
const ab = (i) => TEAMS[i].ab;

function loadPreset(key) {
  const p = PRESETS[key];
  TEAMS = p.teams.map((t) => ({ name: t.name, ab: t.ab, w: t.w, l: t.l }));
  G = p.g.map((r) => r.slice()); X = p.x;
  renderTable(); renderSelect(); rebuild();
}
function renderSelect() {
  $('team').innerHTML = TEAMS.map((t, i) => '<option value="' + i + '"' + (i === X ? ' selected' : '') + '>' + t.name + '</option>').join('');
}
function renderTable() {
  const n = TEAMS.length;
  let h = '<tr><th>Team</th><th>W</th><th>L</th><th>R</th>';
  for (let j = 0; j < n; j++) h += '<th class="gh">' + ab(j) + '</th>';
  h += '</tr>';
  for (let i = 0; i < n; i++) {
    h += '<tr><td class="nm">' + TEAMS[i].name + '</td>';
    h += '<td><input type="number" min="0" max="199" data-k="w" data-i="' + i + '" value="' + TEAMS[i].w + '"></td>';
    h += '<td><input type="number" min="0" max="199" data-k="l" data-i="' + i + '" value="' + TEAMS[i].l + '"></td>';
    h += '<td class="rem" id="rem' + i + '">' + remOf(G, i) + '</td>';
    for (let j = 0; j < n; j++) {
      h += i === j ? '<td class="dg">·</td>' : '<td><input type="number" min="0" max="30" data-k="g" data-i="' + i + '" data-j="' + j + '" value="' + G[i][j] + '"></td>';
    }
    h += '</tr>';
  }
  $('tbl').innerHTML = h;
}
function onEdit(ev) {
  const el = ev.target; if (!el.dataset || !el.dataset.k) return;
  let v = parseInt(el.value, 10); if (isNaN(v) || v < 0) v = 0;
  const i = +el.dataset.i;
  if (el.dataset.k === 'g') {
    const j = +el.dataset.j; v = Math.min(v, 30); G[i][j] = v; G[j][i] = v;
    const mirror = document.querySelector('input[data-k="g"][data-i="' + j + '"][data-j="' + i + '"]');
    if (mirror) mirror.value = v;
    for (let r = 0; r < TEAMS.length; r++) $('rem' + r).textContent = remOf(G, r);
  } else { v = Math.min(v, 199); TEAMS[i][el.dataset.k] = v; }
  rebuild();
}
function rebuild() {
  NET = buildNet(TEAMS, G, X); LAST = null; DONE = false; STEPS = 0;
  $('cert').innerHTML = '';
  if (NET.trivial >= 0) { finish(); return; }
  setStatus(fmt("%team% can reach at most %w% + %r% = %max% wins. The other teams still play %g% games among themselves, and each win must be given to someone without pushing that team above %max%.", { team: TEAMS[X].name, w: TEAMS[X].w, r: remOf(G, X), max: NET.maxW, g: NET.total }), '');
  draw(); buttons();
}
function nodeName(k) {
  const nd = NET.nodes[k];
  if (nd.type === 's') return 's';
  if (nd.type === 't') return 't';
  if (nd.type === 'T') return ab(nd.i);
  return ab(nd.i) + '–' + ab(nd.j);
}
function step() {
  if (DONE) return;
  const r = augment(NET);
  if (!r) { finish(); return; }
  STEPS++; LAST = r.path;
  const names = [nodeName(NET.edges[r.path[0]].u)].concat(r.path.map((ei) => nodeName(NET.edges[ei].v)));
  setStatus(fmt("Path %n%: %path% (pushes %d%). Flow so far: %f% of %t%.", { n: STEPS, path: names.join(' → '), d: r.delta, f: NET.flow, t: NET.total }), '');
  draw(); buttons();
}
function runAll() { let guard = 0; while (!DONE && guard++ < 500) { step(); } }
function finish() {
  DONE = true; LAST = null;
  const nm = TEAMS[X].name;
  if (NET.trivial >= 0) {
    const o = TEAMS[NET.trivial];
    setStatus(fmt("%team% is eliminated trivially: winning every remaining game gives only %max% wins, but %other% already has %ow%.", { team: nm, max: NET.maxW, other: o.name, ow: o.w }), 'bad');
    $('cert').innerHTML = '';
    $('net').innerHTML = ''; buttons(); return;
  }
  NET.seen = bfs(NET).seen;
  if (NET.flow < NET.total) {
    const c = certificate(TEAMS, G, NET);
    const k = c.R.length, tot = c.wR + c.gR, best = Math.ceil(tot / k);
    const val = Math.round(tot / k * 100) / 100;
    setStatus(fmt("Maximum flow %f% < %t%: some games cannot be assigned. %team% is eliminated.", { team: nm, f: NET.flow, t: NET.total }), 'bad');
    $('cert').innerHTML = '<b>' + "Certificate (minimum cut)" + '</b><br>' +
      fmt("R = {%R%}: (w(R) + g(R)) / |R| = (%w% + %g%) / %k% = %v% > %max%", { R: c.R.map(ab).join(', '), w: c.wR, g: c.gR, k: k, v: val, max: NET.maxW }) + '<br>' +
      fmt("The teams in R will finish with %tot% wins between them (their current wins plus one winner for each game they play against each other), so the best of them ends with at least %best% wins, above the ceiling of %max%.", { tot: tot, best: best, max: NET.maxW });
  } else {
    setStatus(fmt("Maximum flow %f% = %t%: every remaining game can be assigned without anyone passing the ceiling. %team% is not eliminated (it can still tie for first).", { team: nm, f: NET.flow, t: NET.total }), 'ok');
    $('cert').innerHTML = '';
  }
  draw(); buttons();
}
function setStatus(t, cls) { const s = $('status'); s.textContent = t; s.className = 'status ' + cls; }
function buttons() { $('step').disabled = DONE; $('run').disabled = DONE; }

function draw() {
  const nodes = NET.nodes, gl = [], tl = [];
  nodes.forEach((nd, k) => { if (nd.type === 'g') gl.push(k); if (nd.type === 'T') tl.push(k); });
  const rows = Math.max(gl.length, tl.length, 3), rh = 40, H = rows * rh + 24;
  const pos = {};
  pos[NET.s] = [36, H / 2]; pos[NET.t] = [604, H / 2];
  gl.forEach((k, a) => { pos[k] = [200, 12 + (a + 0.5) * (H - 24) / gl.length]; });
  tl.forEach((k, a) => { pos[k] = [420, 12 + (a + 0.5) * (H - 24) / tl.length]; });
  const onPath = new Set((LAST || []).map((e) => e & ~1));
  const cutS = DONE && NET.seen && NET.flow < NET.total;
  let svg = '';
  NET.edges.forEach((e, ei) => {
    if (ei & 1) return;
    const p1 = pos[e.u], p2 = pos[e.v];
    const inf = e.cap >= INF, sat = !inf && e.flow === e.cap && e.cap > 0;
    let cls = 'ed';
    if (e.flow > 0) cls += ' fl';
    if (sat) cls += ' sat';
    if (onPath.has(ei)) cls += ' pth';
    if (cutS && NET.seen[e.u] && !NET.seen[e.v]) cls += ' cut';
    svg += '<line class="' + cls + '" x1="' + p1[0] + '" y1="' + p1[1] + '" x2="' + p2[0] + '" y2="' + p2[1] + '"/>';
    let lab = '';
    if (!inf) lab = e.flow + '/' + e.cap; else if (e.flow > 0) lab = String(e.flow);
    if (lab) {
      const f = 0.5;
      svg += '<text class="el" x="' + (p1[0] + (p2[0] - p1[0]) * f) + '" y="' + (p1[1] + (p2[1] - p1[1]) * f - 3) + '" text-anchor="middle">' + lab + '</text>';
    }
  });
  nodes.forEach((nd, k) => {
    const x = pos[k][0], y = pos[k][1];
    let cls = 'nd ' + nd.type;
    if (cutS && NET.seen[k]) cls += ' inS';
    const lab = nodeName(k);
    if (nd.type === 'g') svg += '<rect class="' + cls + '" x="' + (x - 28) + '" y="' + (y - 12) + '" width="56" height="24" rx="6"/>';
    else svg += '<circle class="' + cls + '" cx="' + x + '" cy="' + y + '" r="' + (nd.type === 'T' ? 17 : 13) + '"/>';
    svg += '<text class="nl" x="' + x + '" y="' + (y + 4) + '" text-anchor="middle">' + lab + '</text>';
  });
  svg += '<text class="cap" x="200" y="9" text-anchor="middle">games</text><text class="cap" x="420" y="9" text-anchor="middle">teams</text>';
  $('net').setAttribute('viewBox', '0 0 640 ' + (H + 6));
  $('net').innerHTML = svg;
}
$('tbl').addEventListener('change', onEdit);
$('team').addEventListener('change', () => { X = +$('team').value; rebuild(); });
$('step').addEventListener('click', step);
$('run').addEventListener('click', runAll);
$('reset').addEventListener('click', rebuild);
$('p_classic').addEventListener('click', () => loadPreset('classic'));
$('p_five').addEventListener('click', () => loadPreset('five'));
$('p_alive').addEventListener('click', () => loadPreset('alive'));
loadPreset('classic');

<!-- Interface: preset buttons, standings table, team selector, step buttons, network drawing. -->
<div class="wrap">
  <p class="hint">Edit wins, losses and the games left between each pair of teams, pick the team you are worried about, and watch the flow network decide whether it can still finish first.</p>
  <div class="row presets">
    <button id="p_classic" type="button" class="ghost">Classic 4 teams</button>
    <button id="p_five" type="button" class="ghost">5 teams, subtle case</button>
    <button id="p_alive" type="button" class="ghost">5 teams, still alive</button>
  </div>
  <div class="scroll"><table id="tbl" class="tbl" aria-label="Standings and remaining games"></table></div>
  <p class="note">W = wins, L = losses, R = games left. The grid on the right holds the games left between each pair (it stays symmetric).</p>
  <div class="row">
    <label for="team">Team to test:</label>
    <select id="team"></select>
  </div>
  <div class="row">
    <button id="step" type="button">Next augmenting path</button>
    <button id="run" type="button">Run to the end</button>
    <button id="reset" type="button" class="ghost">Reset flow</button>
  </div>
  <div class="status" id="status" aria-live="polite"></div>
  <div class="scroll"><svg id="net" class="net" viewBox="0 0 640 160" role="img" aria-label="Flow network: source, one node per remaining game, one node per team, sink"></svg></div>
  <p class="legend">Left to right: source s, one node per pair of other teams with games left (capacity = games left), one node per team, sink t (capacity = wins that team may still add). Orange = current augmenting path, blue = carries flow, green = full edge, red dashed = minimum cut.</p>
  <div class="cert" id="cert" aria-live="polite"></div>
</div>

/* Colours follow the light or dark preference of the visitor. */
:root { --fg:#1f2933; --bg:#ffffff; --mut:#52606d; --line:#c3ccd6; --acc:#1d3557; --ok:#0a7d33; --bad:#c92f3c; --pth:#e8890c; --soft:#eef2f6; --fl:#2a6fb0; }
@media (prefers-color-scheme: dark) {
  :root { --fg:#e6ebf0; --bg:#1b2430; --mut:#a7b4c2; --line:#46566a; --acc:#7fb0e6; --ok:#4cc27a; --bad:#ff7a85; --pth:#ffb347; --soft:#243243; --fl:#6fb3f2; }
}
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: var(--fg); background: var(--bg); margin: 0; }
.wrap { padding: .6rem; }
.hint { font-size: .9rem; color: var(--mut); margin: 0 0 .6rem; line-height: 1.45; }
.note, .legend { font-size: .8rem; color: var(--mut); margin: .3rem 0; line-height: 1.4; }
.row { display: flex; gap: .5rem; flex-wrap: wrap; align-items: center; margin: .5rem 0; }
.scroll { overflow-x: auto; }
.tbl { border-collapse: collapse; font-size: .85rem; }
.tbl th, .tbl td { padding: 2px 4px; text-align: center; border-bottom: 1px solid var(--line); }
.tbl th { color: var(--mut); font-weight: 600; }
.tbl .nm { text-align: left; white-space: nowrap; font-weight: 600; padding-right: .6rem; }
.tbl .rem { font-weight: 700; color: var(--acc); }
.tbl .dg { color: var(--mut); }
.tbl input { width: 3.1em; padding: 3px 2px; text-align: center; font: inherit; color: var(--fg); background: var(--soft); border: 1px solid var(--line); border-radius: 5px; }
label { font-size: .9rem; font-weight: 600; }
select { font: inherit; padding: .3rem .5rem; color: var(--fg); background: var(--soft); border: 1px solid var(--line); border-radius: 6px; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid var(--acc); background: var(--acc); color: var(--bg); border-radius: 8px; cursor: pointer; }
button.ghost { background: transparent; color: var(--acc); }
button:disabled { opacity: .45; cursor: default; }
.status { font-size: .95rem; font-weight: 600; margin: .4rem 0; min-height: 2.8em; line-height: 1.4; }
.status.ok { color: var(--ok); }
.status.bad { color: var(--bad); }
.net { display: block; width: 100%; min-width: 520px; height: auto; background: var(--soft); border-radius: 8px; }
.ed { stroke: var(--line); stroke-width: 1.4; }
.ed.fl { stroke: var(--fl); stroke-width: 2.2; }
.ed.sat { stroke: var(--ok); }
.ed.pth { stroke: var(--pth); stroke-width: 4; }
.ed.cut { stroke: var(--bad); stroke-dasharray: 5 4; stroke-width: 3; }
.nd { fill: var(--bg); stroke: var(--acc); stroke-width: 1.6; }
.nd.s, .nd.t { fill: var(--acc); }
.nd.inS { stroke: var(--bad); stroke-width: 3; }
.nl { font: 600 10px system-ui, sans-serif; fill: var(--fg); pointer-events: none; }
.nd.s + .nl, .nd.t + .nl { fill: var(--bg); }
.el { font: 600 10px system-ui, sans-serif; fill: var(--mut); paint-order: stroke; stroke: var(--soft); stroke-width: 3px; }
.cap { font: 600 10px system-ui, sans-serif; fill: var(--mut); }
.cert { font-size: .9rem; line-height: 1.5; margin-top: .4rem; }
.cert:not(:empty) { padding: .5rem .7rem; border-left: 4px solid var(--bad); background: var(--soft); border-radius: 6px; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
const INF = 1000000;
// Core: builds the flow network and solves it with Edmonds-Karp (shortest augmenting paths found by breadth-first search).
const remOf = (g, i) => g[i].reduce((a, b) => a + b, 0);
function buildNet(teams, g, x) {
  const n = teams.length;
  const maxW = teams[x].w + remOf(g, x);
  const net = { x, maxW, nodes: [], edges: [], adj: [], total: 0, trivial: -1, flow: 0 };
  for (let i = 0; i < n; i++) if (i !== x && teams[i].w > maxW && net.trivial < 0) net.trivial = i;
  const addNode = (o) => { net.nodes.push(o); net.adj.push([]); return net.nodes.length - 1; };
  const addEdge = (u, v, cap) => {
    net.edges.push({ u, v, cap, flow: 0 }); net.adj[u].push(net.edges.length - 1);
    net.edges.push({ u: v, v: u, cap: 0, flow: 0 }); net.adj[v].push(net.edges.length - 1);
  };
  const s = addNode({ type: 's' });
  const others = [];
  for (let i = 0; i < n; i++) if (i !== x) others.push(i);
  const gameNodes = [];
  for (let a = 0; a < others.length; a++) for (let b = a + 1; b < others.length; b++) {
    const i = others[a], j = others[b];
    if (g[i][j] > 0) gameNodes.push({ i, j, c: g[i][j] });
  }
  const gid = gameNodes.map((gm) => addNode({ type: 'g', i: gm.i, j: gm.j, c: g[gm.i][gm.j] }));
  const tid = {};
  others.forEach((i) => { tid[i] = addNode({ type: 'T', i }); });
  const t = addNode({ type: 't' });
  net.s = s; net.t = t;
  gameNodes.forEach((gm, k) => {
    addEdge(s, gid[k], gm.c); net.total += gm.c;
    addEdge(gid[k], tid[gm.i], INF); addEdge(gid[k], tid[gm.j], INF);
  });
  others.forEach((i) => addEdge(tid[i], t, Math.max(0, maxW - teams[i].w)));
  return net;
}
function bfs(net) {
  const par = new Array(net.nodes.length).fill(-1);
  const seen = new Array(net.nodes.length).fill(false);
  seen[net.s] = true; const q = [net.s];
  while (q.length) {
    const u = q.shift();
    for (const ei of net.adj[u]) {
      const e = net.edges[ei];
      if (!seen[e.v] && e.cap - e.flow > 0) { seen[e.v] = true; par[e.v] = ei; q.push(e.v); }
    }
  }
  if (!seen[net.t]) return { path: null, seen };
  const path = []; let v = net.t;
  while (v !== net.s) { path.push(par[v]); v = net.edges[par[v]].u; }
  return { path: path.reverse(), seen };
}
function augment(net) {
  const r = bfs(net);
  if (!r.path) { net.seen = r.seen; return null; }
  let d = Infinity;
  for (const ei of r.path) d = Math.min(d, net.edges[ei].cap - net.edges[ei].flow);
  for (const ei of r.path) { net.edges[ei].flow += d; net.edges[ei ^ 1].flow -= d; }
  net.flow += d;
  return { path: r.path, delta: d };
}
function certificate(teams, g, net) {
  const R = [];
  net.nodes.forEach((nd, k) => { if (nd.type === 'T' && net.seen[k]) R.push(nd.i); });
  let wR = 0, gR = 0;
  R.forEach((i) => { wR += teams[i].w; });
  for (let a = 0; a < R.length; a++) for (let b = a + 1; b < R.length; b++) gR += g[R[a]][R[b]];
  return { R, wR, gR };
}
// Interface code: presets, table editing, drawing and buttons.
const PRESETS = {
  classic: { x: 1, teams: [
    { name: 'Atlanta', ab: 'ATL', w: 83, l: 71 }, { name: 'Philadelphia', ab: 'PHI', w: 80, l: 79 },
    { name: 'New York', ab: 'NY', w: 78, l: 78 }, { name: 'Montreal', ab: 'MON', w: 77, l: 82 }],
    g: [[0, 1, 6, 1], [1, 0, 0, 2], [6, 0, 0, 0], [1, 2, 0, 0]] },
  five: { x: 3, teams: ['A', 'B', 'C', 'D', 'E'].map((c, i) => ({ name: c, ab: c, w: [68, 68, 66, 65, 63][i], l: 0 })),
    g: [[0, 0, 3, 2, 2], [0, 0, 3, 1, 1], [3, 3, 0, 0, 1], [2, 1, 0, 0, 1], [2, 1, 1, 1, 0]] },
  alive: { x: 2, teams: null, g: null }
};
PRESETS.five.teams.forEach((t, i) => { t.l = 162 - t.w - remOf(PRESETS.five.g, i); });
PRESETS.alive.teams = PRESETS.five.teams; PRESETS.alive.g = PRESETS.five.g;
let TEAMS, G, X, NET, LAST = null, DONE = false, STEPS = 0;
const $ = (id) => document.getElementById(id);
const ab = (i) => TEAMS[i].ab;

function loadPreset(key) {
  const p = PRESETS[key];
  TEAMS = p.teams.map((t) => ({ name: t.name, ab: t.ab, w: t.w, l: t.l }));
  G = p.g.map((r) => r.slice()); X = p.x;
  renderTable(); renderSelect(); rebuild();
}
function renderSelect() {
  $('team').innerHTML = TEAMS.map((t, i) => '<option value="' + i + '"' + (i === X ? ' selected' : '') + '>' + t.name + '</option>').join('');
}
function renderTable() {
  const n = TEAMS.length;
  let h = '<tr><th>Team</th><th>W</th><th>L</th><th>R</th>';
  for (let j = 0; j < n; j++) h += '<th class="gh">' + ab(j) + '</th>';
  h += '</tr>';
  for (let i = 0; i < n; i++) {
    h += '<tr><td class="nm">' + TEAMS[i].name + '</td>';
    h += '<td><input type="number" min="0" max="199" data-k="w" data-i="' + i + '" value="' + TEAMS[i].w + '"></td>';
    h += '<td><input type="number" min="0" max="199" data-k="l" data-i="' + i + '" value="' + TEAMS[i].l + '"></td>';
    h += '<td class="rem" id="rem' + i + '">' + remOf(G, i) + '</td>';
    for (let j = 0; j < n; j++) {
      h += i === j ? '<td class="dg">·</td>' : '<td><input type="number" min="0" max="30" data-k="g" data-i="' + i + '" data-j="' + j + '" value="' + G[i][j] + '"></td>';
    }
    h += '</tr>';
  }
  $('tbl').innerHTML = h;
}
function onEdit(ev) {
  const el = ev.target; if (!el.dataset || !el.dataset.k) return;
  let v = parseInt(el.value, 10); if (isNaN(v) || v < 0) v = 0;
  const i = +el.dataset.i;
  if (el.dataset.k === 'g') {
    const j = +el.dataset.j; v = Math.min(v, 30); G[i][j] = v; G[j][i] = v;
    const mirror = document.querySelector('input[data-k="g"][data-i="' + j + '"][data-j="' + i + '"]');
    if (mirror) mirror.value = v;
    for (let r = 0; r < TEAMS.length; r++) $('rem' + r).textContent = remOf(G, r);
  } else { v = Math.min(v, 199); TEAMS[i][el.dataset.k] = v; }
  rebuild();
}
function rebuild() {
  NET = buildNet(TEAMS, G, X); LAST = null; DONE = false; STEPS = 0;
  $('cert').innerHTML = '';
  if (NET.trivial >= 0) { finish(); return; }
  setStatus(fmt("%team% can reach at most %w% + %r% = %max% wins. The other teams still play %g% games among themselves, and each win must be given to someone without pushing that team above %max%.", { team: TEAMS[X].name, w: TEAMS[X].w, r: remOf(G, X), max: NET.maxW, g: NET.total }), '');
  draw(); buttons();
}
function nodeName(k) {
  const nd = NET.nodes[k];
  if (nd.type === 's') return 's';
  if (nd.type === 't') return 't';
  if (nd.type === 'T') return ab(nd.i);
  return ab(nd.i) + '–' + ab(nd.j);
}
function step() {
  if (DONE) return;
  const r = augment(NET);
  if (!r) { finish(); return; }
  STEPS++; LAST = r.path;
  const names = [nodeName(NET.edges[r.path[0]].u)].concat(r.path.map((ei) => nodeName(NET.edges[ei].v)));
  setStatus(fmt("Path %n%: %path% (pushes %d%). Flow so far: %f% of %t%.", { n: STEPS, path: names.join(' → '), d: r.delta, f: NET.flow, t: NET.total }), '');
  draw(); buttons();
}
function runAll() { let guard = 0; while (!DONE && guard++ < 500) { step(); } }
function finish() {
  DONE = true; LAST = null;
  const nm = TEAMS[X].name;
  if (NET.trivial >= 0) {
    const o = TEAMS[NET.trivial];
    setStatus(fmt("%team% is eliminated trivially: winning every remaining game gives only %max% wins, but %other% already has %ow%.", { team: nm, max: NET.maxW, other: o.name, ow: o.w }), 'bad');
    $('cert').innerHTML = '';
    $('net').innerHTML = ''; buttons(); return;
  }
  NET.seen = bfs(NET).seen;
  if (NET.flow < NET.total) {
    const c = certificate(TEAMS, G, NET);
    const k = c.R.length, tot = c.wR + c.gR, best = Math.ceil(tot / k);
    const val = Math.round(tot / k * 100) / 100;
    setStatus(fmt("Maximum flow %f% < %t%: some games cannot be assigned. %team% is eliminated.", { team: nm, f: NET.flow, t: NET.total }), 'bad');
    $('cert').innerHTML = '<b>' + "Certificate (minimum cut)" + '</b><br>' +
      fmt("R = {%R%}: (w(R) + g(R)) / |R| = (%w% + %g%) / %k% = %v% > %max%", { R: c.R.map(ab).join(', '), w: c.wR, g: c.gR, k: k, v: val, max: NET.maxW }) + '<br>' +
      fmt("The teams in R will finish with %tot% wins between them (their current wins plus one winner for each game they play against each other), so the best of them ends with at least %best% wins, above the ceiling of %max%.", { tot: tot, best: best, max: NET.maxW });
  } else {
    setStatus(fmt("Maximum flow %f% = %t%: every remaining game can be assigned without anyone passing the ceiling. %team% is not eliminated (it can still tie for first).", { team: nm, f: NET.flow, t: NET.total }), 'ok');
    $('cert').innerHTML = '';
  }
  draw(); buttons();
}
function setStatus(t, cls) { const s = $('status'); s.textContent = t; s.className = 'status ' + cls; }
function buttons() { $('step').disabled = DONE; $('run').disabled = DONE; }

function draw() {
  const nodes = NET.nodes, gl = [], tl = [];
  nodes.forEach((nd, k) => { if (nd.type === 'g') gl.push(k); if (nd.type === 'T') tl.push(k); });
  const rows = Math.max(gl.length, tl.length, 3), rh = 40, H = rows * rh + 24;
  const pos = {};
  pos[NET.s] = [36, H / 2]; pos[NET.t] = [604, H / 2];
  gl.forEach((k, a) => { pos[k] = [200, 12 + (a + 0.5) * (H - 24) / gl.length]; });
  tl.forEach((k, a) => { pos[k] = [420, 12 + (a + 0.5) * (H - 24) / tl.length]; });
  const onPath = new Set((LAST || []).map((e) => e & ~1));
  const cutS = DONE && NET.seen && NET.flow < NET.total;
  let svg = '';
  NET.edges.forEach((e, ei) => {
    if (ei & 1) return;
    const p1 = pos[e.u], p2 = pos[e.v];
    const inf = e.cap >= INF, sat = !inf && e.flow === e.cap && e.cap > 0;
    let cls = 'ed';
    if (e.flow > 0) cls += ' fl';
    if (sat) cls += ' sat';
    if (onPath.has(ei)) cls += ' pth';
    if (cutS && NET.seen[e.u] && !NET.seen[e.v]) cls += ' cut';
    svg += '<line class="' + cls + '" x1="' + p1[0] + '" y1="' + p1[1] + '" x2="' + p2[0] + '" y2="' + p2[1] + '"/>';
    let lab = '';
    if (!inf) lab = e.flow + '/' + e.cap; else if (e.flow > 0) lab = String(e.flow);
    if (lab) {
      const f = 0.5;
      svg += '<text class="el" x="' + (p1[0] + (p2[0] - p1[0]) * f) + '" y="' + (p1[1] + (p2[1] - p1[1]) * f - 3) + '" text-anchor="middle">' + lab + '</text>';
    }
  });
  nodes.forEach((nd, k) => {
    const x = pos[k][0], y = pos[k][1];
    let cls = 'nd ' + nd.type;
    if (cutS && NET.seen[k]) cls += ' inS';
    const lab = nodeName(k);
    if (nd.type === 'g') svg += '<rect class="' + cls + '" x="' + (x - 28) + '" y="' + (y - 12) + '" width="56" height="24" rx="6"/>';
    else svg += '<circle class="' + cls + '" cx="' + x + '" cy="' + y + '" r="' + (nd.type === 'T' ? 17 : 13) + '"/>';
    svg += '<text class="nl" x="' + x + '" y="' + (y + 4) + '" text-anchor="middle">' + lab + '</text>';
  });
  svg += '<text class="cap" x="200" y="9" text-anchor="middle">games</text><text class="cap" x="420" y="9" text-anchor="middle">teams</text>';
  $('net').setAttribute('viewBox', '0 0 640 ' + (H + 6));
  $('net').innerHTML = svg;
}
$('tbl').addEventListener('change', onEdit);
$('team').addEventListener('change', () => { X = +$('team').value; rebuild(); });
$('step').addEventListener('click', step);
$('run').addEventListener('click', runAll);
$('reset').addEventListener('click', rebuild);
$('p_classic').addEventListener('click', () => loadPreset('classic'));
$('p_five').addEventListener('click', () => loadPreset('five'));
$('p_alive').addEventListener('click', () => loadPreset('alive'));
loadPreset('classic');

Result

Console

Press Next augmenting path to see Edmonds–Karp find the shortest route from $s$ to $t$ that still has room (orange), push the bottleneck amount along it, and repeat. When no route is left, compare the flow with the total number of games: if some source edge is not full, the team is eliminated and the demo shows the certificate, the set of teams $R$ on the source side of the minimum cut.

Things to try. In the classic four-team preset, Philadelphia is eliminated even though it is within three wins of the leader, and Montreal is eliminated trivially (select it and read the message). Then load the five-team subtle case and switch between teams: D is out because A, B and C collectively must out-win its ceiling, yet none of them is individually decisive. Finally change one number of the remaining-games grid and see the verdict flip.

The Real Complexity

The reduction. Fix a team $x$ and let $M = w_x + r_x$ be its best possible total. If some $w_i > M$ , $x$ is trivially eliminated. Otherwise build the network:

source $s$ , sink $t$ ;
a game node $\{i,j\}$ for each pair of other teams with $g_{ij} > 0$ games left, with an edge $s \to \{i,j\}$ of capacity $g_{ij}$ ;
edges $\{i,j\} \to i$ and $\{i,j\} \to j$ of infinite capacity;
a team node $i$ for each other team, with an edge $i \to t$ of capacity $M - w_i \ge 0$ .

Let $G = \sum_{i<j;\, i,j \ne x} g_{ij}$ . Team $x$ is eliminated if and only if the maximum flow is smaller than $G$ . A flow that saturates every source edge is precisely an assignment of every remaining game to one of its two teams in which team $i$ gains at most $M - w_i$ wins.

function eliminated(x):
    M = w[x] + r[x]
    if any w[i] > M: return TRIVIAL(i)
    build network N(x)
    f = maxFlow(N)            # e.g. Edmonds-Karp
    if f < G:
        R = team nodes reachable from s in the residual graph
        return ELIMINATED, certificate R
    return ALIVE

The certificate (min cut). By the max-flow min-cut theorem, $f < G$ means some cut has capacity below $G$ . Because the middle edges are infinite, a finite cut that keeps a set $R$ of teams on the source side must also keep on that side only game nodes whose two teams lie in $R$ . Its capacity is

G - g(R) + \sum_{i \in R} (M - w_i) = G - g(R) + |R|\,M - w(R),

where $w(R) = \sum_{i\in R} w_i$ and $g(R)$ is the number of games left among teams of $R$ . The cut beats $G$ exactly when

\frac{w(R) + g(R)}{|R|} > M.

This is the Hoffman–Rivlin style certificate. It is checkable in a glance: the teams of $R$ will finish with a combined $w(R) + g(R)$ wins, so their average final total exceeds $M$ and at least one of them must end above $x$ . In the classic four-team example, $R = \{\text{Atlanta},\ \text{New York}\}$ gives $(83 + 78 + 6)/2 = 83.5 > 83$ for Philadelphia.

Cost. The network has $n-1$ team nodes and at most $\binom{n-1}{2}$ game nodes, so $\Theta(n^2)$ vertices and edges and $\Theta(n^2)$ space. The flow value is at most $G$ , so Ford–Fulkerson with augmenting paths found by breadth-first search (Edmonds–Karp) runs in $O(VE^2)$ , a crude $O(n^6)$ bound that is far from tight on real schedules. Testing all $n$ teams multiplies this by $n$ . Kevin Wayne (SIAM J. Discrete Mathematics, 2001) proved a structural property, that there is a threshold $W^{\ast}$ with team $i$ eliminated iff $w_i + r_i < W^{\ast}$ , so that all eliminated teams can be found with a single max-flow computation.

Where it breaks. The reduction relies on every game handing out exactly one unit of "wins". With the 3-1-0 scoring of football (3 points for a win, 1 for a draw, none for a loss), a game distributes 3 or 2 points depending on the result, so the supply is no longer fixed. In 2001 Walter Kern and Daniël Paulusma showed that deciding whether a team can still win the league under 3-1-0 scoring is NP-complete, while the older 2-1-0 scheme stays polynomial. Their paper classifies the complexity for every choice of point values. The jump from "flow" to "NP-complete" because of one rule change is a clean illustration of how thin the line between P and NP can be.

Where It Matters

Sports reporting and analytics. The "eliminated" markers in the standings are the practical face of this question. Variants ask for the smallest number of additional wins that guarantees a playoff berth, or which teams can still reach a given rank, as Hoffman and Rivlin studied.
Tournament and league design. The scoring system matters computationally. Organizers choosing between 2-1-0 and 3-1-0 are, without knowing it, choosing between an easy problem and an NP-complete one for anyone who wants to certify elimination.
Allocation under capacity. The network is a transportation problem: supplies (games) must be sent to sinks (teams) with capacities. The same pattern appears in bipartite matching, the assignment problem and min-cost flow, and the elimination certificate has the same shape as Hall's theorem for matchings.
Proofs of impossibility. Linear programs have the same duality: LP duality turns a failed feasibility problem into a short certificate. The min cut here is exactly that certificate, in combinatorial clothes.

Conclusion

Being out of a race is not always visible in the standings. Schwartz's 1966 insight was that the hidden part, how the remaining games can be shared out, is a flow problem: build the network for the team you want to test, and it is eliminated exactly when the maximum flow falls short of the games to be distributed.

The minimum cut turns that verdict into something you can show to a skeptic: a set of teams whose average final win total is above your ceiling. And the football variant, where a win is worth three points, reminds us that polynomial algorithms often live in a narrow valley: change the rules a little and the same question becomes NP-complete.

Comments

Loading comments...

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

Cookies & privacy

When max flow says you're out