The Nucleolus

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?"

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">{{hint}}</p>
<div class="game-setup">
  <h3>{{heading_vals}}</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">{{note_grand}}</p>
</div>
<div class="slider-row">
  <label>{{label_a_share}} <b id="aVal">33</b></label>
  <input type="range" id="sliderA" min="0" max="100" value="33">
</div>
<div class="slider-row">
  <label>{{label_b_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">{{label_c_share}} <b id="cVal">34</b></div>
<table id="excessTable" class="exc-table">
  <thead><tr><th>{{th_coalition}}</th><th>{{th_standalone}}</th><th>{{th_share_paid}}</th><th>{{th_excess}}</th></tr></thead>
  <tbody></tbody>
</table>
<div class="status" id="status"></div>
<div class="btns">
  <button id="findBtn" type="button">{{btn_find}}</button>
  <button id="resetBtn" type="button" class="ghost">{{btn_reset}}</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; }

// Code not found

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 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 $2^{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 ($2^{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.

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.

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.