Introduction

Three firms share the cost of building a common water pipeline. Each pair of firms could build a smaller joint line, or every firm could build alone — but together they save the most. How should they split the total cost so that nobody feels cheated?

This is the central question of cooperative game theory: when a group can accomplish more together than separately, how do we fairly divide the gain (or the cost)? Many solution concepts exist — the Shapley value, the core, the bargaining set — but only one is guaranteed to be unique and to sit inside the core whenever the core is non-empty. That solution is the nucleolus.

Introduced by David Schmeidler in 1969, the nucleolus is the payoff vector that lexicographically minimizes the sorted vector of excesses across all coalitions. In plain language: it finds the split that makes the most-unhappy coalition as happy as possible, then breaks ties by making the second-most-unhappy as happy as possible, and so on. The result is a single, mathematically inevitable answer to "what is fair?"

Try It: Compute the Nucleolus

The demo below works with a 3-player cost-sharing game. Three players (A, B, C) can form any coalition. Each coalition has a value (the cost it would pay alone). A payoff vector assigns each player a share of the grand coalition cost; the excess of a coalition is how much more it pays under the proposed split than it would pay alone — the measure of its "complaint."

<p class="hint">A 3-player cost-sharing game. Each coalition’s <b>value</b> is its stand-alone cost. A payoff assigns each player their share of the grand-coalition cost (100). The <b>excess</b> of a coalition = (its cost share under the payoff) − (its stand-alone value). A positive excess means the coalition pays more than it could alone — a "complaint." The nucleolus minimizes the biggest complaint.</p>
<div class="game-setup">
  <h3>Coalition Values (stand-alone costs)</h3>
  <div class="vals">
    <label>v(A) <input type="number" id="vA" value="45" min="0" max="100"><span class="unit">pts</span></label>
    <label>v(B) <input type="number" id="vB" value="40" min="0" max="100"><span class="unit">pts</span></label>
    <label>v(C) <input type="number" id="vC" value="35" min="0" max="100"><span class="unit">pts</span></label>
    <label>v(AB) <input type="number" id="vAB" value="70" min="0" max="100"><span class="unit">pts</span></label>
    <label>v(AC) <input type="number" id="vAC" value="65" min="0" max="100"><span class="unit">pts</span></label>
    <label>v(BC) <input type="number" id="vBC" value="60" min="0" max="100"><span class="unit">pts</span></label>
  </div>
  <p class="note">Grand coalition v(ABC) = 100 (fixed). Sliders below set payoff for A and B; C gets the rest.</p>
</div>
<div class="slider-row">
  <label>A’s share: <b id="aVal">33</b></label>
  <input type="range" id="sliderA" min="0" max="100" value="33">
</div>
<div class="slider-row">
  <label>B’s share: <b id="bVal">33</b></label>
  <input type="range" id="sliderB" min="0" max="100" value="33">
</div>
<div id="cDisplay" class="c-display">C’s share: <b id="cVal">34</b></div>
<table id="excessTable" class="exc-table">
  <thead><tr><th>Coalition</th><th>Stand-alone</th><th>Share paid</th><th>Excess</th></tr></thead>
  <tbody></tbody>
</table>
<div class="status" id="status"></div>
<div class="btns">
  <button id="findBtn" type="button">Find Nucleolus</button>
  <button id="resetBtn" type="button" class="ghost">Reset Sliders</button>
</div>
<div id="nucleolusResult" class="nuc-result" style="display:none"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.game-setup h3 { font-size: .95rem; margin: 0 0 .4rem; color: #1d3557; }
.vals { display: grid; grid-template-columns: repeat(3, 1fr); gap: .4rem .8rem; margin-bottom: .6rem; }
.vals label { display: flex; align-items: center; gap: .3rem; font-size: .88rem; }
.vals input { width: 54px; padding: 2px 4px; border: 1px solid #bcc6d0; border-radius: 5px; font-size: .9rem; text-align: right; }
.note { font-size: .82rem; color: #666; margin: .3rem 0 .8rem; }
.slider-row { display: flex; align-items: center; gap: .6rem; margin: .3rem 0; }
.slider-row label { width: 130px; font-size: .9rem; }
.slider-row input[type=range] { flex: 1; }
.c-display { font-size: .9rem; margin: .3rem 0 .7rem; color: #1d3557; font-weight: 600; }
.exc-table { width: 100%; border-collapse: collapse; margin: .5rem 0; font-size: .88rem; }
.exc-table th { background: #e8eef3; color: #1d3557; padding: 5px 8px; text-align: left; border: 1px solid #cdd9e3; }
.exc-table td { padding: 4px 8px; border: 1px solid #dde3e9; }
.exc-table tr.max-row td { background: #fff3cd; font-weight: 700; }
.exc-table .pos { color: #c92f3c; }
.exc-table .neg { color: #0a7d33; }
.status { font-size: .9rem; font-weight: 600; min-height: 1.2em; margin: .4rem 0; color: #444; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin: .5rem 0; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.nuc-result { background: #e8f5e9; border: 1px solid #a5d6a7; border-radius: 8px; padding: .6rem .8rem; font-size: .9rem; color: #1b5e20; margin-top: .4rem; }
.nuc-result strong { display: block; margin-bottom: .2rem; }
.unit { color: #888; font-size: .8rem; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Nucleolus for a 3-player cost-sharing game.
// Players: A, B, C. Grand coalition value fixed at 100.
// Coalition values set by user. Payoff: (xA, xB, xC) with xA+xB+xC=100.
// Excess of coalition S: e(S, x) = x(S) - v(S)  [cost paid by S minus stand-alone cost]
// The nucleolus minimises the lexicographically sorted excess vector (biggest first).
//
// For 3 players we enumerate all payoffs on a fine grid and pick the one minimising
// the max excess, breaking ties by the second-max excess, etc.

const GRAND = 100;
let vA = 45, vB = 40, vC = 35, vAB = 70, vAC = 65, vBC = 60;

function getVals() {
  vA  = Math.max(0, Math.min(GRAND, +document.getElementById('vA').value  || 0));
  vB  = Math.max(0, Math.min(GRAND, +document.getElementById('vB').value  || 0));
  vC  = Math.max(0, Math.min(GRAND, +document.getElementById('vC').value  || 0));
  vAB = Math.max(0, Math.min(GRAND, +document.getElementById('vAB').value || 0));
  vAC = Math.max(0, Math.min(GRAND, +document.getElementById('vAC').value || 0));
  vBC = Math.max(0, Math.min(GRAND, +document.getElementById('vBC').value || 0));
}

// Coalitions (excluding grand and empty): A, B, C, AB, AC, BC
function excesses(xA, xB, xC) {
  const xAB = xA + xB, xAC = xA + xC, xBC = xB + xC;
  return [
    { name: 'A',  exc: xA  - vA  },
    { name: 'B',  exc: xB  - vB  },
    { name: 'C',  exc: xC  - vC  },
    { name: 'AB', exc: xAB - vAB },
    { name: 'AC', exc: xAC - vAC },
    { name: 'BC', exc: xBC - vBC },
  ];
}

// Lexicographic comparison of sorted-descending excess vectors
function lexCompare(exA, exB) {
  const a = exA.map(e=>e.exc).sort((x,y)=>y-x);
  const b = exB.map(e=>e.exc).sort((x,y)=>y-x);
  for (let i = 0; i < a.length; i++) {
    if (a[i] - b[i] > 1e-9) return 1;
    if (b[i] - a[i] > 1e-9) return -1;
  }
  return 0;
}

// Find nucleolus by grid search (step = 0.1, fine enough for 3 players)
function findNucleolus() {
  getVals();
  let bestExc = null, bestXA = 0, bestXB = 0;
  const STEP = 0.1;
  for (let xA = 0; xA <= GRAND; xA += STEP) {
    for (let xB = 0; xB <= GRAND - xA; xB += STEP) {
      const xC = GRAND - xA - xB;
      if (xC < -1e-9) continue;
      const exc = excesses(xA, xB, Math.max(0, xC));
      if (bestExc === null || lexCompare(exc, bestExc) < 0) {
        bestExc = exc; bestXA = xA; bestXB = xB;
      }
    }
  }
  return { xA: bestXA, xB: bestXB, xC: GRAND - bestXA - bestXB, exc: bestExc };
}

// UI update
function clamp(v, lo, hi) { return Math.max(lo, Math.min(hi, v)); }

function updateDisplay() {
  getVals();
  const xA = +document.getElementById('sliderA').value;
  const rawB = +document.getElementById('sliderB').value;
  const xB = clamp(rawB, 0, GRAND - xA);
  const xC = GRAND - xA - xB;

  document.getElementById('aVal').textContent = xA;
  document.getElementById('bVal').textContent = xB;
  document.getElementById('cVal').textContent = xC.toFixed(1);

  const exc = excesses(xA, xB, xC);
  const maxExc = Math.max(...exc.map(e=>e.exc));

  const tbody = document.querySelector('#excessTable tbody');
  tbody.innerHTML = '';
  exc.forEach(({ name, exc: e }) => {
    const tr = document.createElement('tr');
    const isMax = Math.abs(e - maxExc) < 1e-9;
    if (isMax) tr.className = 'max-row';
    const share = name === 'A' ? xA : name === 'B' ? xB : name === 'C' ? xC :
                  name === 'AB' ? xA+xB : name === 'AC' ? xA+xC : xB+xC;
    const sv = name === 'A' ? vA : name === 'B' ? vB : name === 'C' ? vC :
               name === 'AB' ? vAB : name === 'AC' ? vAC : vBC;
    const cls = e > 1e-9 ? 'pos' : e < -1e-9 ? 'neg' : '';
    tr.innerHTML = `<td><b>${name}</b></td><td>${sv}</td><td>${share.toFixed(1)}</td><td class="${cls}">${e>0?'+':''}${e.toFixed(1)}</td>`;
    tbody.appendChild(tr);
  });

  const allNonPos = exc.every(e => e.exc <= 1e-9);
  document.getElementById('status').textContent =
    allNonPos ? `All excesses ≤ 0: this payoff is in the core!` :
    fmt(`Max complaint: %maxExc% (highlighted row)`, { maxExc: maxExc.toFixed(2) });
}

document.getElementById('sliderA').addEventListener('input', () => {
  const xA = +document.getElementById('sliderA').value;
  const sliderB = document.getElementById('sliderB');
  sliderB.max = GRAND - xA;
  if (+sliderB.value > GRAND - xA) sliderB.value = GRAND - xA;
  updateDisplay();
});
document.getElementById('sliderB').addEventListener('input', updateDisplay);
['vA','vB','vC','vAB','vAC','vBC'].forEach(id =>
  document.getElementById(id).addEventListener('change', updateDisplay)
);

document.getElementById('findBtn').addEventListener('click', () => {
  const res = findNucleolus();
  document.getElementById('sliderA').value = res.xA;
  document.getElementById('sliderB').max = GRAND - res.xA;
  document.getElementById('sliderB').value = res.xB;
  updateDisplay();
  const div = document.getElementById('nucleolusResult');
  div.style.display = 'block';
  const maxExc = Math.max(...res.exc.map(e=>e.exc));
  div.innerHTML = fmt(`<strong>Nucleolus found:</strong>
    A = %xA%, B = %xB%, C = %xC%<br>
    Maximum excess (minimized complaint): <b>%maxExc%</b>`, { xA: res.xA.toFixed(1), xB: res.xB.toFixed(1), xC: res.xC.toFixed(1), maxExc: maxExc.toFixed(2) });
  console.log(`Nucleolus:`, {xA: res.xA, xB: res.xB, xC: res.xC, maxExcess: maxExc});
});

document.getElementById('resetBtn').addEventListener('click', () => {
  document.getElementById('sliderA').value = 33;
  document.getElementById('sliderB').max = 100;
  document.getElementById('sliderB').value = 33;
  document.getElementById('nucleolusResult').style.display = 'none';
  updateDisplay();
});

updateDisplay();
Result
Console

Drag the sliders to set a payoff for player A and player B (C gets the remainder). Watch how the excess of each coalition changes. The nucleolus is the point where the maximum excess is minimized — the algorithm finds it for you automatically when you press Find Nucleolus.

The nucleolus always exists, is always unique, and whenever the core (the set of "stable" payoffs) is non-empty, the nucleolus lies inside it.

The Real Complexity

The nucleolus always exists and is unique — that is a theorem, not a hope. But computing it is a different story.

The algorithm: Schmeidler's original proof is constructive. You solve a sequence of linear programs (LPs): first minimize the maximum excess over all coalitions; then, with that maximum fixed, minimize the second-largest excess; and so on. Each LP has one variable per player and one constraint per coalition. In the worst case you need up to n LPs, each with up to 2n2^{n} constraints — one for every possible coalition.

For small games (a few dozen players) this sequence of LPs is perfectly practical. Modern LP solvers handle it in milliseconds.

For large games the exponential number of coalitions is the wall. A game with 50 players has over a quadrillion coalitions (2502^{50}). In general, computing the nucleolus for an arbitrary characteristic-function game is NP-hard (Deng & Papadimitriou, 1994).

Special structure saves us. For many games that arise in practice — airport cost-sharing, bankruptcy problems, weighted voting, network games — the coalitional values have compact representations and the nucleolus can be found in polynomial time. These special cases are why the nucleolus is so widely used in economics and operations research.

The contrast is familiar: a concept that is easy to define, always uniquely determined, but generically hard to compute — the same tension that appears throughout complexity theory, from linear programming to the Shapley value and beyond.

Where It Matters

The nucleolus is not just a theoretical curiosity. Its guarantee of uniqueness and fairness makes it the preferred solution in many real settings:

  • Airport cost-sharing: Airlines sharing a runway pay fees based on how much runway each needs. The nucleolus (or the closely related airport game solution) is provably fair and has been used by actual airports to justify their fee structures.
  • Bankruptcy and debt: When a firm cannot pay all creditors in full, the Talmudic "contested garment" solution and O'Neill's (1982) bankruptcy rule both coincide with the nucleolus of the associated game.
  • Telecommunications and utilities: When several municipalities share the cost of a fiber or water network, the nucleolus prescribes each party's fair contribution.
  • Supply-chain and logistics: Competing firms that share warehouses, trucks, or routes use nucleolus-based formulas to divide the savings from cooperation.
  • Weighted voting and political science: The nucleolus measures the "power" of each voter in a weighted majority game, giving a fairness counterpart to the Shapley-Shubik index.

Whenever a group must split a cost or benefit and every subgroup can credibly threaten to walk away, the nucleolus answers "what share makes that threat least persuasive?" — and it answers with a single, unchallengeable number.

Conclusion

The nucleolus gives cooperative game theory something rare: a concept that is always uniquely defined, always exists, and carries a clear fairness story — minimize the loudest complaint, then the next loudest, until nothing can be improved.

It sits at the intersection of optimization (each step is a linear program), fairness (it lives in the core whenever the core exists), and complexity (computing it for a general game is NP-hard). That combination puts the nucleolus in the same distinguished company as the Nash equilibrium and the Shapley value: a concept clean enough to use in policy, deep enough to keep theorists busy for decades.

The next time a group of stakeholders squabbles over how to share a cost, remember: there is always a mathematically optimal answer. Finding it efficiently is the hard part — and that hardness is itself a theorem.

Share this article

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

Comments

Loading comments...

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