vault

Coalitional Games

54 min read

Coalitional Games

A coalitional game (also called a cooperative game or a characteristic-function game) throws away everything normal-form game theory cares about — who can do what, in what order, observing what — and keeps exactly one thing: for every subset S of the players, a single number v(S) saying what that subset can guarantee itself. The pair (N, v) is the whole model. Shoham and Leyton-Brown put the abstraction plainly: “we are not concerned with how the agents make individual choices within a coalition, how they coordinate, or any other such detail; we simply take the payoff to a coalition as given” (Multiagent Systems, ch. 12). Having thrown away the strategies, you can no longer ask “what will they do?”; you can only ask which divisions of the grand coalition’s worth are stable. The dominant answer is the core: the set of payoff vectors that no coalition can beat by walking out. This note is about the core — how to compute it exactly, why it is frequently empty, and the theorem (Bondareva–Shapley) that says precisely when.

Scope, and what lives next door

This note owns the core and its relatives (ε-core, least core, nucleolus) plus the emptiness question. The Shapley value — a fairness answer rather than a stability answer — has its own note; it appears here only where the two concepts collide, which they do in interesting ways. Nash Equilibrium is the non-cooperative counterpart and the contrast is load-bearing throughout.

Mental Model: the game is a function on the power set

In a non-cooperative game, the object of study is a function on strategy profiles. In a coalitional game, the object of study is a function on subsets of players. That single change of domain is the whole conceptual leap.

flowchart LR
    subgraph NC["Non-cooperative game"]
        A1["strategy sets<br/>S₁ × S₂ × ... × Sₙ"] --> A2["uᵢ : profile → ℝ<br/>one utility per player"]
        A2 --> A3["Solution concept:<br/>Nash equilibrium<br/><i>no INDIVIDUAL deviates</i>"]
    end
    subgraph CO["Coalitional game"]
        B1["player set N"] --> B2["v : 2^N → ℝ<br/>one worth per COALITION<br/>v(∅) = 0"]
        B2 --> B3["Solution concept:<br/>the core<br/><i>no COALITION deviates</i>"]
    end
    NC -.->|"forget the strategies,<br/>keep what groups can get"| CO

What it shows: the two halves of game theory differ in the domain of the primitive function — profiles versus subsets. The insight: the core is not a competitor to Nash equilibrium at the same level of description; it is what stability becomes when the unit of deviation is a group rather than an individual. Shoham and Leyton-Brown make the relation exact: the core is the analogue not of Nash equilibrium but of strong Nash equilibrium, which requires stability against joint deviations by arbitrary coalitions (mas.pdf §12.2.2; the strong-equilibrium concept is Aumann’s, defined in Nisan et al. §1.7.1).

Transferable and non-transferable utility

Two model variants, and the distinction decides which mathematics applies.

  • Transferable utility (TU). A coalition’s worth is a single number that its members can split however they like. This is justified “whenever there is a universal currency that is used for exchange in the system” (mas.pdf §12.1.1). A TU game is a pair (N, v) with v : 2^N → ℝ and v(∅) = 0. Everything computable in this note is TU.
  • Non-transferable utility (NTU). A coalition’s achievable outcomes form a set C(S) ⊆ ℝ^S of payoff vectors, not a number to be divided. Nisan et al. give the motivating case: a network design where each member of S suffers a delay, and “as delays are nontransferrable, this setting is best modeled as an NTU cost-sharing game” (ch. 15.1). Stable Matching and Top Trading Cycles are NTU games in disguise — you cannot pay someone to be matched to a worse partner.

The NTU core is defined by the same idea — no coalition S and vector x ∈ C(S) with xⱼ better than αⱼ for every j ∈ S — and coincides with the TU definition when C(S) happens to be a simplex. But the characterisation theorem is weaker. Scarf’s theorem gives only a sufficient condition for NTU non-emptiness, and Nisan et al. note that its proof “uses an adaptation of the Lemke–Howson algorithm”, with worst-case running time exponential in |A| — “in contrast to the proof of the Bondareva–Shapley theorem, which gives a polynomial-time algorithm for computing a point in the core of the game, if the core is nonempty” (given a suitable representation or separation oracle). TU is the tractable half of the subject, and that is why almost all the algorithmic literature lives there.

Cost games are the same thing with a sign flip

Half the literature writes c(S) (a cost to be shared) rather than v(S) (a worth to be divided), and flips every inequality. Nisan et al. work entirely in costs; Shoham and Leyton-Brown entirely in payoffs. Translating is mechanical — set v(S) = −c(S) — but the inequality directions invert, and mixing conventions mid-derivation is the single most common way to get a sign error in this subject.

Payoff convention (v)Cost convention (c)
EfficiencyΣᵢ∈N xᵢ = v(N)Σⱼ∈A αⱼ = c(A) (“budget balance”)
Core propertyΣᵢ∈S xᵢ ≥ v(S)Σⱼ∈S αⱼ ≤ c(S)
Readingthe coalition already gets at least what it could earn alonethe coalition is charged no more than it would pay alone
Core-emptiness LPminimise Σ xᵢ; empty iff optimum > v(N)maximise Σ αⱼ; empty iff optimum < c(A)

The core, defined as a linear feasibility problem

An allocation x ∈ ℝⁿ is in the core if it is efficient and coalitionally rational:

efficiency :   Σ_{i ∈ N} x_i = v(N)
core property: Σ_{i ∈ S} x_i ≥ v(S)   for every S ⊆ N

Symbol by symbol: N is the set of all n players (the grand coalition); S ranges over all 2ⁿ − 1 non-empty subsets; xᵢ is player i’s share; v(S) is what S could obtain by seceding. Note that the constraint for S = N together with efficiency forces equality, so writing only the inequalities (as Shoham and Leyton-Brown do in Definition 12.2.9) is equivalent.

The definition is implicit — it names no allocation, it filters a set of them — and that is exactly what makes it computable: core membership and core non-emptiness are linear feasibility problems (mas.pdf, Eq. 12.1). Every claim in this note about a specific game was checked by solving those linear programs in exact rational arithmetic.

A useful hierarchy sits above the core:

flowchart TB
    F["Feasible payoffs<br/>Σ xᵢ ≤ v(N)<br/><i>weakly budget balanced</i>"]
    P["Pre-imputations<br/>Σ xᵢ = v(N)<br/><i>efficient</i>"]
    I["Imputations<br/>+ xᵢ ≥ v({i}) ∀i<br/><i>individually rational</i>"]
    C["The CORE<br/>+ Σ_{i∈S} xᵢ ≥ v(S) ∀S<br/><i>coalitionally rational</i>"]
    F --> P --> I --> C
    S["Shapley value<br/><i>always exists, always unique</i>"] -.->|"always a pre-imputation;<br/>NOT always in the core"| P
    NU["Nucleolus<br/><i>always exists, always unique</i>"] -.->|"in the core whenever<br/>the core is non-empty"| C

What it shows: the nested rationality conditions, from “don’t overspend” to “no group wants out”. The insight: each arrow shrinks the solution set, and the last shrink can take it to the empty set — which is why the two single-point concepts hang off the side. The Shapley value is guaranteed to be a pre-imputation but not an imputation and not in the core; the nucleolus is guaranteed to be in the core exactly when the core is non-empty. Both statements were re-verified numerically below, and the first surprises people.

The core can be empty — and here is the smallest example

Take three players who must split £1 by majority vote. Any two of them can outvote the third and take the whole pound; a lone player gets nothing:

v({1}) = v({2}) = v({3}) = 0
v({1,2}) = v({1,3}) = v({2,3}) = 1
v({1,2,3}) = 1

Suppose x = (x₁, x₂, x₃) is in the core. The three pair constraints say x₁ + x₂ ≥ 1, x₁ + x₃ ≥ 1, x₂ + x₃ ≥ 1. Add all three: 2(x₁ + x₂ + x₃) ≥ 3, so Σxᵢ ≥ 3/2. But efficiency demands Σxᵢ = v(N) = 1. Contradiction — the core is empty. The argument is three lines and it is the entire difficulty of the subject in miniature: the coalitions collectively promise more than the grand coalition has.

Running the linear program confirms it exactly, with no floating point anywhere:

=== Three-player majority game: v(S)=1 iff |S|>=2, else 0 ===
  min sum x subject to the core constraints = 3/2   v(N) = 1   -> core empty
  Bondareva-Shapley dual optimum = 3/2
     certificate lambda: {(1,2): 1/2, (1,3): 1/2, (2,3): 1/2}
  Shapley value: (1/3, 1/3, 1/3)   in core? False
  nucleolus:     (1/3, 1/3, 1/3)
  superadditive? True   convex? False

The gap 3/2 − 1 = 1/2 is not a metaphor: it is the amount by which the game over-promises, and it is what the ε-core and least core (below) charge for.

Shapley worked this exact family out in RM-4601 §3: for a superadditive three-player game the only condition for a non-empty core is v({1,2}) + v({1,3}) + v({2,3}) ≤ 2·v({1,2,3}). The majority game sits at 3 > 2 and fails it; everything below is the general machinery behind that one inequality.

The same pathology shows up in real allocation problems, not just voting toys. Nisan et al.’s facility location game (Example 15.2/15.4) has three clients {a,b,c} and a set of facilities; c(S) is the minimum cost of opening facilities and connecting everyone in S. With two facilities the cost function is c(a)=4, c(b)=3, c(c)=3, c(ab)=6, c(bc)=4, c(ac)=7, c(abc)=8 and the core is non-empty. Add a third facility — a strictly better option for the coalition {a,c}, dropping c(ac) from 7 to 5 — and the core vanishes. Reproducing both cases exactly:

=== Nisan et al. Example 15.4: facility-location cost game ===
  original (c(a,c)=7):  max Σα = 8, c(N) = 8  -> core NON-EMPTY, gamma = 1
     book's candidate (4,2,2) in core? True
     book's candidate (4,1,3) in core? True
  third facility added (c(a,c)=5): max Σα = 15/2, c(N) = 8 -> core EMPTY
     best achievable budget balance gamma = 15/16

Every number matches the book, including the 7.5/8 budget-balance factor it quotes — my LP returns the exact fraction 15/16. The moral is worth stating loudly: making one coalition’s outside option cheaper destroyed the stability of the whole allocation. Improving the technology made the cost-sharing problem unsolvable. That is a systems lesson, not just an economics one.

The Bondareva–Shapley theorem: emptiness is LP duality

The characterisation of non-emptiness was found independently by O. N. Bondareva and L. S. Shapley. Shapley’s side of it I have now read in the original: RAND Memorandum RM-4601-PR, On Balanced Sets and Cores, 1965 (PDF; record, DOI 10.7249/RM4601), which is the preprint of the paper later published as “On balanced sets and cores”, Naval Research Logistics Quarterly 14:453–460 (1967). Its own bibliography — reproduced verbatim in the sibling memorandum RM-4571, read below — gives Bondareva’s paper as “Some Applications of the Methods of Linear Programming to the Theory of Cooperative Games” (Russian), Problemy Kibernetiki 10 (1963), 119–139, which pins the volume and page range that secondary reference lists usually omit. The Bondareva original is in Russian and I could not obtain it; the attribution and citation here come from Shapley’s own reference list, which is the best primary evidence available short of the Russian journal.

The two RAND memoranda are scans with no text layer, so pdftotext returns zero words on both; everything quoted below was read from page images rendered with pdftoppm -png -r 135.

Definition (balanced weights). A vector λ assigning a weight λ_S ≥ 0 to every coalition S ⊆ N is a balanced collection if for every player i, Σ_{S : i ∈ S} λ_S = 1.

Read λ_S as “the fraction of its time coalition S operates”. Balancedness says each player is fully employed: the fractions of the coalitions containing i sum to exactly one unit of i. The obvious balanced collection is λ_N = 1 and everything else zero. The interesting ones are fractional: on three players, λ = 1/2 on each of the three pairs is balanced, because each player sits in exactly two pairs and 1/2 + 1/2 = 1.

Theorem (Bondareva–Shapley). A TU game (N, v) has a non-empty core if and only if for every balanced collection λ, Σ_S λ_S v(S) ≤ v(N).

The proof is one application of strong LP duality, and it is worth walking because it turns an infinite-looking quantifier into a finite computation.

flowchart LR
    subgraph PRIM["PRIMAL — 'cheapest way to satisfy every coalition'"]
        P1["minimise  Σ_{i∈N} xᵢ"]
        P2["s.t.  Σ_{i∈S} xᵢ ≥ v(S)<br/>for every S ⊆ N"]
        P1 --- P2
    end
    subgraph DUAL["DUAL — 'most a fractional coalition structure can promise'"]
        D1["maximise  Σ_S λ_S v(S)"]
        D2["s.t.  Σ_{S ∋ i} λ_S = 1 ∀i<br/>λ_S ≥ 0"]
        D1 --- D2
    end
    PRIM <-->|"strong duality:<br/>optima are EQUAL"| DUAL
    PRIM --> R["Core non-empty<br/>⟺ optimum = v(N)<br/>⟺ every balanced λ satisfies<br/>Σ λ_S v(S) ≤ v(N)"]
    DUAL --> R

What it shows: the primal asks how little total payout satisfies every coalition; the dual asks how much a fractional schedule of coalitions can extract. The insight: the dual constraints are the definition of balancedness — that is the entire content of the theorem. A balanced collection with Σ λ_S v(S) > v(N) is a certificate of emptiness you can check by hand.

Step by step:

  1. The primal minimum can never be less than v(N), because the constraint for S = N forces Σxᵢ ≥ v(N).
  2. The core is non-empty exactly when the primal minimum equals v(N) — i.e. when it is possible to satisfy every coalition without exceeding the grand coalition’s worth.
  3. Strong duality equates the primal minimum with the dual maximum.
  4. The dual’s feasible region is precisely the set of balanced collections.
  5. So: core non-empty ⟺ dual maximum ≤ v(N) ⟺ every balanced λ obeys Σ λ_S v(S) ≤ v(N). ∎

In the majority game, the certificate is exactly the fractional collection above: λ = 1/2 on each pair gives Σ λ_S v(S) = 3 × (1/2) × 1 = 3/2 > 1 = v(N). My solver rediscovered it independently from the dual LP — the printed {(1,2): 1/2, (1,3): 1/2, (2,3): 1/2} above is the LP’s own optimal λ, not something I supplied.

How Shapley actually states it, and why “minimal” is the operative word

The version above quantifies over every balanced collection, of which there are infinitely many (any convex combination of balanced collections is balanced). Shapley’s own formulation in RM-4601 removes that infinity, and the machinery is worth having because it is what makes the theorem checkable by hand.

Shapley’s §1 defines a balanced set as a family 𝒮 = {S₁, …, S_p} of distinct, non-empty, proper subsets of N admitting strictly positive coefficients γ₁, …, γ_p with Σ_{j : i ∈ S_j} γ_j = 1 for every i ∈ N. Note two details the textbook statement usually drops: the sets are proper (the grand coalition is excluded, it sits on the other side of the inequality) and the weights are strictly positive (a zero weight means the coalition simply is not in the family). His one-line reading of the definition is the best one there is:

“If the weights are all equal to 1, then 𝒮 is a partition of N; thus balanced sets may be regarded as generalized partitions.” — Shapley, RM-4601 §1

A minimal balanced set is one that includes no other balanced set. Shapley shows in three lines that a minimal balanced set has a unique weight vector: if γ and δ were two distinct weightings, some convex combination tγ + (1−t)δ would be non-negative but have a zero entry, exhibiting a proper balanced subfamily. Uniqueness immediately bounds the size — the n balancing equations determine p unknowns, so p ≤ n. That is what collapses the infinite quantifier: the dual LP’s vertices are exactly the minimal balanced sets, so checking the theorem means checking finitely many inequalities, one per minimal balanced set, each involving at most n coalitions.

Shapley calls a game with a non-empty core weak — his terminology, worth knowing when reading the 1960s literature — and observes that the weak games form a closed convex polyhedral cone W in the 2ⁿ − 1-dimensional space whose coordinates are the numbers v(S). Finding the balanced inequalities is then just finding the facets of that cone. His Theorem 1 is the result this note has been calling Bondareva–Shapley:

“THEOREM 1. The game v has a nonempty core if and only if it satisfies all balanced inequalities of the form γ₁v(S₁) + ⋯ + γ_p v(S_p) ≤ v(N), all γ_j > 0.” — Shapley, RM-4601 §4

The n = 3 case, in Shapley’s own worked example. He takes v({1}) = v({2}) = v({3}) = 0, v({1,2}) = a, v({1,3}) = b, v({2,3}) = c, v(N) = 1 and derives that the core is non-empty iff a + b + c ≤ 2 and a, b, c ≤ 1. When the game is superadditive the second group is automatic, so for proper (superadditive) three-player games the whole question reduces to a single inequality:

v({1,2}) + v({1,3}) + v({2,3}) ≤ 2·v({1,2,3})          (Shapley, RM-4601 eq. 8)

The three-player majority game at the top of this note is precisely the boundary violation: 1 + 1 + 1 = 3 > 2 = 2×1. Shapley even hands you a core point when the conditions hold — x₁ = 1 − c, x₂ = min(c, 1 − b), x₃ = max(0, b + c − 1) — a closed form, no LP required.

I checked both claims exhaustively over the grid a, b, c ∈ {0, ¼, ½, …, 2}: Shapley’s two conditions agreed with a brute-force core-feasibility test on 729/729 parameter triples, and his explicit point was in the core in every feasible case.

The n = 4 case, and why “not so simple” is an understatement. Shapley’s §7 reports that for four players there are 41 distinct minimal balanced sets, falling into nine equivalence classes under permutation of the players (permutations generate the other 32), and that eleven inequalities are needed to delimit the proper four-player games with non-empty cores — against the single inequality that sufficed for three. I enumerated the minimal balanced sets from scratch over exact rationals and reproduced his table exactly:

n=4: number of minimal balanced sets = 41      (Shapley RM-4601 Table 1: 41)
     equivalence classes under permutation = 9 (Shapley: nine)
     class multiplicities: 1, 1, 3, 4, 4, 4, 6, 6, 12   (sum 41; matches Table 1)
     class depths (lcd of the weights):  1,1,1,1,2,2,2,3,3   (matches Table 1)

  {123,124,134,234}  γ = 1/3,1/3,1/3,1/3   depth 3   multiplicity  1
  {1,23,24,134}      γ = 1/2,1/2,1/2,1/2   depth 2   multiplicity 12
  {12,13,14,234}     γ = 1/3,1/3,1/3,2/3   depth 3   multiplicity  4
  {1,2,3,4}          γ = 1,1,1,1           depth 1   multiplicity  1
  {12,34}            γ = 1,1               depth 1   multiplicity  3
  ...

What “depth” is: Shapley tabulates integer weights, obtained by multiplying each γ vector by its least common denominator, which he calls the collection’s depth. Depth 1 is exactly the partitions — the ordinary superadditivity inequalities. Everything of depth ≥ 2 is a genuinely fractional coalition schedule with no partition interpretation, and those are the inequalities that a naïve “check superadditivity” test misses. This is the precise sense in which balancedness is strictly stronger than superadditivity, and it is why failure mode 5 below exists.

flowchart TB
    P["Partitions of N<br/>(depth 1 balanced sets)<br/>γ ≡ 1"] --> M["Minimal balanced sets<br/>41 of them for n = 4<br/>depths 1, 2, 3"]
    M --> A["All balanced collections<br/>(infinitely many:<br/>convex hull of the minimal ones)"]
    P -.->|"the inequalities<br/>superadditivity gives you"| SA["Σ over a partition ≤ v(N)"]
    M -.->|"the inequalities<br/>Bondareva–Shapley needs"| BS["Σ_S λ_S v(S) ≤ v(N)<br/>for every minimal balanced set"]
    SA -->|"strictly weaker"| BS

What it shows: the three nested families of coalition schedules and the inequality systems each generates. The insight: superadditivity only ever tests the depth-1 members of this hierarchy; the core’s emptiness is usually certified by a fractional collection of depth 2 or more — for three players, by the depth-2 collection {12, 13, 23} with γ = ½ each, which is exactly the certificate the LP found above.

The approximate version, and why it matters computationally

Nisan et al. define the γ-core by relaxing budget balance to γ·c(A) ≤ Σαⱼ ≤ c(A) while keeping the core property, and prove the corresponding characterisation: a non-empty γ-core exists iff Σ_S λ_S c(S) ≥ γ·c(A) for every balanced λ (Theorem 15.8). Corollary 15.9 then says something genuinely surprising — for a subadditive cost function, the largest γ with a non-empty γ-core equals the integrality gap of the covering LP. Cost-sharing stability and approximation-algorithm quality turn out to be the same number. For facility location they report that gap to lie between 1/1.52 and 1/1.463.

Computing cores exactly

The whole apparatus is small enough to write from scratch. Two ingredients: exact rational arithmetic and an LP solver.

Choice of solver, stated plainly. No linear-programming library is available on this machine (glpk absent; liblpsolve55.so present but headerless; no numpy, no pip). I therefore wrote two independent exact solvers over fractions.Fraction and cross-checked them against each other:

  1. Vertex enumeration — for an LP in n variables, try every way of selecting n constraints, solve the square system by Gaussian elimination over Fraction, discard infeasible points, take the best objective. Correct whenever the optimum is attained at a vertex; complexity O(C(m, n) · n³), hopeless beyond toy sizes but trivially auditable.
  2. A two-phase simplex over Fraction with Bland’s rule (~90 lines). Bland’s rule guarantees termination without cycling; exact rationals mean there is no pivot-tolerance question at all.

They agreed on 300/300 randomly generated bounded LPs (2–3 variables, 3–6 random inequality constraints plus box bounds). The simplex is used for everything below; the enumerator exists only to keep it honest.

def core_lp(n, v):
    """min Σ x  s.t.  Σ_{i∈S} x_i ≥ v(S) for all S.
       Core is non-empty iff the optimum equals v(N)."""
    ub = []
    for S in subsets(n):                                   # all 2^n − 1 non-empty coalitions
        a = [F(-1) if i in S else F(0) for i in range(n)]   # rewrite  Σ_{i∈S} x_i ≥ v(S)
        ub.append((a, -v[S]))                              #     as  −Σ_{i∈S} x_i ≤ −v(S)
    return solve_lp(n, [F(1)] * n, ub=ub, sense="min")
 
def balanced_dual(n, v):
    """max Σ_S λ_S v(S)  s.t.  Σ_{S ∋ i} λ_S = 1 ∀i,  λ ≥ 0.
       This is the Bondareva–Shapley dual; its optimum must equal core_lp's."""
    Ss = list(subsets(n))
    eq = [([F(1) if i in S else F(0) for S in Ss], F(1)) for i in range(n)]
    ub = [([F(-1) if j == k else F(0) for j in range(len(Ss))], F(0)) for k in range(len(Ss))]
    return solve_lp(len(Ss), [v[S] for S in Ss], ub=ub, eq=eq, sense="max")

Line by line: subsets(n) yields every non-empty subset as a frozenset; the primal has n variables and 2ⁿ − 1 constraints; the dual has 2ⁿ − 1 variables and n equality constraints, so the two LPs are transposes of each other and either can be the cheaper one depending on n. Everything is Fraction, so “the optimum equals v(N)” is an exact equality test rather than a tolerance comparison — which matters, because the interesting games are exactly the degenerate ones where the optimum sits on v(N).

Measured cross-check. Over 400 randomly generated superadditive games (200 with n = 3, 200 with n = 4), the primal optimum and the dual optimum agreed in 400/400 cases. That is not a theorem test so much as a bug test — strong duality is certain, so any disagreement is a defect in my solver, and there were none.

What the same experiment measured about the solution concepts

n=3: 200 random superadditive games
   primal == dual (exact strong duality)       : 200/200
   core EMPTY                                  : 1/200 = 0.5%
   of the 199 with a non-empty core:
      Shapley value lies in the core           : 178/199 = 89.4%
      nucleolus lies in the core               : 199/199 = 100.0%
n=4: 200 random superadditive games
   primal == dual                              : 200/200
   core EMPTY                                  : 4/200 = 2.0%
   of the 196 with a non-empty core:
      Shapley value lies in the core           : 156/196 = 79.6%
      nucleolus lies in the core               : 196/196 = 100.0%

Uncertain

Verify: the 0.5% / 2.0% core-emptiness rates. Reason: they are a property of my generator, not of “random games”. I build superadditive games by taking the superadditive cover of uniform random coalition values, which pushes v(N) up until it nearly dominates every partition and thereby makes the core easy to satisfy. A different generator gives wildly different answers — see the weighted-voting measurement below, where emptiness runs at 18%. To resolve: state the generator alongside any such frequency, and never quote one as “how often the core is empty”.

The Shapley-value column is the real finding, and it does not depend on the generator in the same way: even restricted to games whose core is non-empty, the Shapley value falls outside the core roughly 10–20% of the time. The fair division and the stable division are simply different objects. Shoham and Leyton-Brown say the same thing in one sentence — “One advantage of the Shapley value is that it always exists. However, it may not be in the core, even for games that have nonempty core” — and the glove game below shows it happening in three players.

Three worked games

=== Airport (savings) game: runway costs 1, 2, 4 for cities a, b, c ===
   v(S) = Σ_{i∈S} cost_i − max_{i∈S} cost_i     (the saving from one shared runway)
   v(a)=v(b)=v(c)=0,  v(ab)=1,  v(ac)=1,  v(bc)=2,  v(abc)=3
   convex? True     core LP = 3 = v(N)  -> core NON-EMPTY
   Shapley  = (2/3, 7/6, 7/6)   sum 3   in core? True
   nucleolus = (1/2, 5/4, 5/4)

=== Glove market: players 1,2 own a LEFT glove, player 3 owns a RIGHT glove ===
   v(S) = min(#left in S, #right in S)
   v(12)=0, v(13)=1, v(23)=1, v(123)=1
   core LP = 1 = v(N)  -> core NON-EMPTY (in fact the single point (0,0,1))
   Shapley  = (1/6, 1/6, 2/3)   in core? FALSE
   nucleolus = (0, 0, 1)

=== Weighted voting [q; w] : v(S)=1 iff Σ_{i∈S} wᵢ ≥ q ===
   q=51, w=(45,25,15,15):  core EMPTY (LP = 5/3);  no veto player
                           Shapley = (1/2, 1/6, 1/6, 1/6)
   q=80, w=(45,25,15,15):  core NON-EMPTY;  veto players {A, B}
                           Shapley = (5/12, 5/12, 1/12, 1/12)

The airport game is not a toy: it is the historical origin of applied cost allocation, and its Shapley value has a closed form worth knowing. The model is due to Littlechild & Owen (1973), “A Simple Expression for the Shapley Value in a Special Case”, Management Science 20(3):370–372. In their formulation the players are aircraft movements (a take-off or a landing), aircraft come in types 1, …, |T| with runway costs 0 = c₀ ≤ c₁ ≤ ⋯ ≤ c_{|T|}, and the cost of serving a coalition is set by its largest member: c(S) = max{c_τ : S ∩ N_τ ≠ ∅} — you build the runway for the biggest plane in the group. Their result is that the Shapley value of that cost game is

Sh_i(N, c) = Σ_{t = 1}^{τ(i)}  (c_t − c_{t−1}) / |N_{≥ t}|

Symbol by symbol: τ(i) is the aircraft type of movement i; c_t − c_{t−1} is the incremental cost of extending the runway from what type t−1 needs to what type t needs; and N_{≥ t} is the set of movements of type t or larger — the movements that actually use that increment. So the rule is: divide each successive slice of runway equally among the aircraft that need it. (Saavedra-Nieves & Fiestras-Janeiro 2025, §2, which restates the Littlechild–Owen formula and its derivation.)

The savings game printed above is the sign-flipped twin of that cost game. Recomputing both from scratch over exact rationals:

runway costs (1, 2, 4) for a, b, c ; one movement each
  cost game c(S) = max cost in S
     Shapley by the definition (2^n term sum)   = (1/3, 5/6, 17/6)
     Shapley by Littlechild-Owen closed form    = (1/3, 5/6, 17/6)   MATCH
     Σ = 4 = c(N)
  savings game v(S) = Σ cost_i − max cost_i     (the version used above)
     Shapley by the definition                  = (2/3, 7/6, 7/6)
     cost_i − Sh_i(cost game)                   = (2/3, 7/6, 7/6)    MATCH

Both cross-checks pass, which is the point of running them: the savings game and the cost game are the same allocation problem and the Shapley value commutes with the transformation v(S) = Σ_{i∈S} cᵢ − c(S). If you ever get a different answer from the two routes, one of the two characteristic functions is wrong. The economically loaded reading of (1/3, 5/6, 17/6): the small aircraft pays only for the first 1 unit of runway split three ways; the largest pays that share plus half of the next unit plus all of the final two units, because nobody else needs them.

The glove market is the one to remember. Two left gloves chase one right glove; a pair is worth 1 and everything else worth 0. The core is the single allocation (0, 0, 1) — the scarce side takes the entire surplus, and the two left-glove owners are competed down to nothing. The Shapley value gives them 1/6 each on the grounds that they contribute to some orderings, which is fair and unstable: player 3 and player 1 can jointly do better by cutting player 2 out, since x₁ + x₃ = 1/6 + 2/3 = 5/6 < 1 = v({1,3}). Fairness and stability point in different directions and the game does not let you have both.

The weighted voting results reproduce the worked example in mas.pdf §12.2.1 exactly: the parliament with 45/25/15/15 seats and a 51-seat quota has Shapley values (1/2, 1/6, 1/6, 1/6), which is the book’s ($50M, $16.67M, $16.67M, $16.67M) scaled to a £1 pot. My LP additionally shows the core is empty there (optimum 5/3), and non-empty under an 80% quota where A and B become veto players — a player i with v(N \ {i}) = 0. Theorem 12.2.13 says a simple game has an empty core iff there is no veto player, and when veto players exist the core consists of exactly those vectors giving the non-veto players zero. Tested on 400 random weighted voting games with 3–5 players and random weights and quotas, the theorem held 400/400, with the core empty in 72/400 = 18.0% of them.

Convex games: the well-behaved corner

A game is convex (equivalently, v is supermodular) if for all S, T ⊆ N:

v(S ∪ T) ≥ v(S) + v(T) − v(S ∩ T)

Equivalently — and this is the reading to carry around — a player’s marginal contribution never decreases as the coalition grows: v(S ∪ {i}) − v(S) ≤ v(T ∪ {i}) − v(T) whenever S ⊆ T. Increasing returns to coalition size.

flowchart TB
    ADD["Additive (inessential)<br/>v(S∪T) = v(S)+v(T)"]
    CONV["Convex / supermodular<br/>v(S∪T) ≥ v(S)+v(T)−v(S∩T)<br/><b>core always non-empty</b><br/><b>Shapley value always in the core</b>"]
    SUP["Superadditive<br/>v(S∪T) ≥ v(S)+v(T) for disjoint S,T<br/><i>core may be empty</i>"]
    GEN["General TU games<br/><i>core usually empty</i>"]
    CS["Constant-sum<br/>v(S)+v(N\\S) = v(N)<br/><i>core empty unless additive</i>"]
    SIM["Simple<br/>v(S) ∈ {0,1}<br/><i>core empty iff no veto player</i>"]
    ADD --> CONV --> SUP --> GEN
    CS --> GEN
    SIM --> GEN

What it shows: the containment hierarchy of game classes, redrawn from Figure 12.1 of mas.pdf with the core results attached. The insight: every guarantee you get for free comes from being far left in this picture, and the majority-voting game that broke the core is constant-sum and simple — the two classes on the bottom branch, where emptiness is the rule rather than the exception.

Two theorems govern the convex corner (Theorems 12.2.14 and 12.2.15 in mas.pdf): every convex game has a non-empty core, and in every convex game the Shapley value is in the core. Both were checked exhaustively: over 4,000 random 3- and 4-player games I filtered for convexity, found 3,266 convex games, and in 3,266/3,266 the core was non-empty and the Shapley value lay inside it. Zero counterexamples, as expected — but the test is worth running because it also validates the convexity predicate, the Shapley implementation, and the core-membership check against each other.

The attribution, settled — and a textbook that gets it wrong

An earlier revision of this note flagged the citation for “in a convex game the Shapley value is in the core” as unresolved. It is now resolved, from the original: L. S. Shapley, RAND Memorandum RM-4571-PR, Notes on N-Person Games VII: Cores of Convex Games, 1965 (PDF; record, DOI 10.7249/RM4571, 32 pages), the memorandum later published as “Cores of convex games”, International Journal of Game Theory 1:11–26 (1971). Its preface dates the results: “The results in this Memorandum were presented at the Fifth Informal Conference on Game Theory at Princeton University, April 5–7, 1965.”

Shapley’s definition of convexity (his equation 3) is the intersection form, not the marginal-contribution form: v(S) + v(T) ≤ v(S∪T) + v(S∩T) for all S, T — and he immediately notes that “(1) and (3) together imply (2)”, i.e. that convexity plus v(∅) = 0 gives superadditivity for free. He also gives the differencing reading that explains the word convex: with [Δ_R v](S) = v(S ∪ R) − v(S − R), condition (3) says exactly that the second differences Δ_Q[Δ_R v] are non-negative — a discrete analogue of a non-negative second derivative. That is the cleanest justification of the name I have seen, and no textbook I read reproduces it.

The results this note relies on are four numbered theorems in that memorandum:

RM-4571Statement (Shapley’s words, abridged)
Lemma 3“The core of a convex game is not empty.”
Theorem 2“The vertices of a regular core are precisely the points a^ω” — where a^ω_i = v(S_{ω,ω(i)}) − v(S_{ω,ω(i)−1}) is player i’s marginal contribution in the ordering ω.
Theorem 3“A game is convex if and only if its core is regular.”
Theorem 4“The value of a convex game is in the core.”
Theorem 5“The core of a convex game is stable (i.e., is the unique Neumann–Morgenstern solution).”

Theorem 4’s proof is one sentence long once Theorems 2 and 3 are in hand: φ = (1/n!) Σ_ω a^ω, so the Shapley value is the centre of gravity of the extreme points of the core, and a centre of gravity of points in a convex set is in that set. This is a much sharper statement than “the Shapley value happens to lie in the core” — it says where in the core it lies. It also explains the glove-market failure earlier in this note from the other direction: in a non-convex game the marginal vectors a^ω need not be in the core at all, so their average has nothing to keep it inside.

Uncertain — a textbook misattribution

Nisan et al.’s chapter 15 notes credit the convex-games result to Shapley (1953): “In the same paper, Shapley shows that for convex games … the Shapley value is in the core.” That appears to be wrong. RM-4571 (1965) states the result as its own Theorem 4, was presented as new work at the 1965 Princeton conference, and its five-item reference list contains no 1953 Shapley value paper at all (it cites the earlier RAND memoranda RM-670 and RM-817, Bondareva 1963, and two Gillies items). Reason this is still flagged rather than asserted flatly: I have not read A Value for n-Person Games (1953) end to end in this task to confirm the absence of a convex-games theorem there, though the vault’s The Shapley Value note works from the 1953 original and records no such result. To resolve: re-read the 1953 paper’s final sections. The mathematical claim is not in doubt — it is Shapley’s Theorem 4, and the 3,266/3,266 experiment above.

Two of Shapley’s own examples, recomputed

RM-4571’s frontispiece is a drawing of the core of the four-player convex game v(S) = (Σ_{i∈S} i)² — players labelled 1 to 4, each coalition worth the square of the sum of its members’ labels. Shapley labels it “a strictly complete core for n = 4”: an (n−1)-dimensional polyhedron with exactly 2ⁿ − 2 = 14 facets. Recomputing it over exact rationals:

v(S) = (Σ_{i∈S} i)² on N = {1,2,3,4}
  convex?                                      True
  distinct marginal vectors a^ω                24  (all 4! = 24 orderings give distinct vertices)
  every a^ω in the core?                       True          [Shapley Thm 2 + Thm 3]
  Shapley value φ                              (10, 20, 30, 40)
  φ == (1/4!) Σ_ω a^ω  (centre of gravity)?    True          [Shapley Thm 4, eq. 12]
  φ in the core?                               True
  Σφ = 100 = v(N) = (1+2+3+4)²                 True

The Shapley value comes out at exactly 10i — the game is engineered so that value is linear in the label even though v is quadratic in it.

The counter-example in his §3.4 Remarks is the more instructive one, because it shows the convexity hypothesis is not decorative. Take the four-player symmetric non-convex game v(S) = 0, 0, 1, 1, 3 for |S| = 0, 1, 2, 3, 4. Shapley states its core “is a perfect cube, with vertices (1,1,1,0), (½,½,½,3/2), etc.”, that stability is easily verified, that the square faces are the sets C_S with |S| = 2, and that “the sets C_S, |S| = 3 are empty, since each three-person coalition gets at least 3/2 in the core”. Every one of those claims recomputes:

v(S) = 0,0,1,1,3 by |S|   (Shapley RM-4571 §3.4)
  convex?          False        superadditive?  True
  core vertices    8  ->  (0,1,1,1) (1,0,1,1) (1,1,0,1) (1,1,1,0)
                          (3/2,1/2,1/2,1/2) (1/2,3/2,1/2,1/2)
                          (1/2,1/2,3/2,1/2) (1/2,1/2,1/2,3/2)
  min over the core of x(S), |S| = 2  = 1   = v(S)   -> C_S is a face (the square faces)
  min over the core of x(S), |S| = 3  = 3/2 > v(S)=1 -> C_S = ∅   (core is NOT complete)

Eight vertices, in two orbits of four — a cube. The insight to take: this game is superadditive and has a large, well-behaved, stable core, and yet it is not convex, so none of the convex-game machinery applies to it. Shapley’s Theorem 5 gives stability from convexity but stability does not give convexity back; the cube is his witness. It is also a clean demonstration that a non-empty core can leave some coalitions strictly slack at every point of the core — a fact that matters computationally, because a nucleolus round that freezes constraints will never freeze those.

Refining a set that may be empty or huge: ε-core, least core, nucleolus

The core has two failure modes and one construction fixes both.

ε-core. Relax every coalition constraint by ε: Σ_{i∈S} xᵢ ≥ v(S) − ε for all S ⊊ N. Read ε as a cost of defecting — a coalition secedes only if it gains more than ε. Nothing requires ε ≥ 0; a negative ε is a bonus for defecting, so a vector in a negative-ε core is more stable than one merely in the core.

Least core. Minimise ε subject to those constraints. The value of that LP is negative exactly when the core is non-empty, and the least core is never empty because a big enough ε always works. It is simultaneously a generalisation of the core (defined even when the core is empty) and a refinement of it (it keeps only the most stable core points).

Nucleolus. The least core can still be a set. Freeze the coalitions whose constraints bind, and minimise ε again over the rest; repeat. Each round makes at least one more constraint tight, so the process terminates in at most n rounds and lands on a single point — the nucleolus (Schmeidler). Equivalently and more memorably: define the excess e(S, x) = v(S) − Σ_{i∈S} xᵢ (how much S would gain by defecting), sort all excesses in decreasing order, and pick the x whose sorted excess vector is lexicographically smallest. You are minimising the biggest grievance, then the second biggest, and so on.

flowchart TB
    R1["Round 1: minimise ε over all S ⊊ N<br/>→ ε₁ (the least core)"]
    T1{"Is x now<br/>uniquely determined?"}
    F1["Freeze every S whose constraint binds<br/>in EVERY optimum: Σ_{i∈S} xᵢ = v(S) − ε₁"]
    R2["Round 2: minimise ε over the survivors,<br/>frozen constraints held as equalities → ε₂"]
    OUT["The NUCLEOLUS<br/>unique, always exists,<br/>in the core whenever the core is non-empty"]
    R1 --> T1
    T1 -- no --> F1 --> R2 --> T1
    T1 -- yes --> OUT

What it shows: the sequential-LP construction. The insight: the phrase “in EVERY optimum” in the freeze step is not decoration — getting it wrong silently produces a wrong answer, as the next section documents.

Measured: across the 395 random games above whose core was non-empty, the nucleolus was inside the core 395/395. On the empty-core majority game the nucleolus is (1/3, 1/3, 1/3) — it exists and is unique even though the core is not.

Kohlberg’s criterion: balancedness shows up a second time

The construction above finds the nucleolus. There is a separate and much less well known result that verifies one, and it is the single most useful fact in this section because it turns a subtle iterative algorithm into a checkable certificate.

The nucleolus is due to Schmeidler (1969), “The nucleolus of a characteristic function game”, SIAM Journal on Applied Mathematics 17(6):1163–1170 — the properties that make it attractive are exactly the three used above: it always exists (given a non-empty imputation set), it is unique, and it lies in the core whenever the core is non-empty (Benedek, Fliege & Nguyen 2021, §1).

Kohlberg’s criterion (1971) gives a necessary and sufficient condition for a candidate x to be the nucleolus. Stated algorithmically, following Benedek et al. §2.2: define T₀(x) = {{i} : xᵢ = v({i})} — the players sitting exactly on their individual-rationality bound — and H₀(x) = {N}. Then repeatedly take

Tₖ(x) = argmax_{S ∉ Hₖ₋₁(x)} [ v(S) − x(S) ]        the coalitions with the k-th largest excess
Hₖ(x) = Hₖ₋₁(x) ∪ Tₖ(x)

Symbol by symbol: v(S) − x(S) is the excess already defined above — coalition S’s grievance at x. T₁(x) is the set of most aggrieved coalitions, T₂(x) the next tier down, and so on, so the excess levels strictly decrease, ε₁(x) > ε₂(x) > ⋯. Tₖ(x) is the set of tight coalitions at level k: those whose constraint is active in round k of the sequential LP. Kohlberg’s theorem is then:

x is the nucleolus if and only if for every k ≥ 1, the union T₁(x) ∪ ⋯ ∪ Tₖ(x) is T₀-balanced.

(“T₀-balanced” is the natural relaxation of balancedness in which the coalitions in T₀ may take weights of either sign, since individual rationality is a one-sided constraint.)

Why this is worth internalising: balancedness appears twice in this note, for two different reasons, and they are not the same theorem. In Bondareva–Shapley it certifies that the core is non-empty. In Kohlberg’s criterion it certifies that a candidate point is the nucleolus. Both are the same linear-algebraic condition — a family of coalitions that can be fractionally weighted to cover every player uniformly — because in both cases it is the statement “no direction of movement improves every tight constraint at once”. Once you see that, the two halves of this note stop being separate topics.

flowchart LR
    B["Balancedness<br/>Σ_{S ∋ i} γ_S = 1 ∀i"]
    B --> C1["Applied to <b>all</b> coalitions<br/>with worths v(S)"]
    B --> C2["Applied to the <b>tight</b> coalitions<br/>at a candidate point x"]
    C1 --> R1["Bondareva–Shapley:<br/>core non-empty ⟺<br/>every balanced γ obeys<br/>Σ γ_S v(S) ≤ v(N)"]
    C2 --> R2["Kohlberg criterion:<br/>x is the nucleolus ⟺<br/>every union T₁∪…∪T_k<br/>is T₀-balanced"]

What it shows: one algebraic condition serving two different solution concepts. The insight: if you have already written a balancedness test for the Bondareva–Shapley dual, you have most of a nucleolus verifier — and a verifier is what catches the bug in failure mode 1 below.

Uncertain

Verify: the claim that Kohlberg’s criterion can be reduced to checking balancedness of at most n − 1 collections. Reason: this is the headline contribution of Benedek, Fliege & Nguyen (2021, Mathematical Programming), but Meinhardt (arXiv:1706.08076) argues at length that the earlier Nguyen versions of this simplification rest on an invalid indirect proof and that “the imposed balancedness requirement on the test condition (∪ⱼ Tⱼ) within his proposed methods cannot be appropriate”. I have not been able to adjudicate the dispute, which turns on proof structure rather than on a computable claim. The original Kohlberg criterion as stated above is not in dispute and is what this note relies on. To resolve: work through Benedek et al.’s Theorem 2 and Meinhardt’s counter-argument, or test both algorithms against each other on games with known nucleoli.

Computational reality check. Verifying a candidate with the original criterion “becomes time consuming when the number of players exceeds 15, and becomes computationally extremely demanding when the number of players exceeds 20” (Benedek et al. §1), because it forms collections drawn from all 2ⁿ coalitions and tests balancedness of unions of them. Finding the nucleolus by a single LP is possible but expensive: Kohlberg’s own single-LP formulation has O(2ⁿ!) constraints, improved by Owen to O(4ⁿ) at the cost of larger coefficients, and by Puerto and Perea to O(4ⁿ) constraints and O(4ⁿ) variables with coefficients in {−1, 0, 1} (all as surveyed in Benedek et al. §1). The sequential-LP construction drawn above is the practical route precisely because it trades one monstrous LP for at most n merely exponential ones.

Complexity: everything is easy until the game gets a compact encoding

There is a trap in the complexity of coalitional games that catches everybody once. A TU game on n players is 2ⁿ − 1 numbers. If you hand the algorithm that table, then “solve the core LP” is polynomial in the input size — the input is already exponential in n. Shoham and Leyton-Brown call this out: the explicit representation “has the odd side-effect that simple brute-force approaches appear to have ‘good’ (i.e., low-order polynomial) complexity”, while in practice you can only handle a handful of agents.

The real questions appear once the game has a compact representation, and then they are hard:

RepresentationCore non-emptinessCore membershipShapley valueSource
Explicit 2ⁿ tablepoly in input (= exponential in n)poly in inputpoly in inputmas.pdf §12.3
Weighted graph game, non-negative weightsnon-empty (game is convex); membership poly via max-flowpolyφᵢ = ½ Σ_{j≠i} w(i,j), O(n²)mas.pdf Prop. 12.3.5–12.3.7
Weighted graph game, general weightscoNP-completecoNP-completestill O(n²), and equal to the (pre)nucleolusGreco et al. Fig. 2, reporting Deng & Papadimitriou 1994
Marginal contribution nets (MC-nets)coNP-complete; poly on bounded treewidthcoNP-complete; poly on bounded treewidthpoly for positive-literal conjunctionsGreco et al. Cor. 4.9
Synergy / concise superadditive representationNP-complete; in P if v(N) is suppliedpoly (Conitzer & Sandholm Lemma)NP-hardConitzer & Sandholm Thms 2, 4
Weighted voting gamespoly (core is non-empty iff a veto player exists)polyclosed form; least core and nucleolus NP-hard for binary weights, pseudo-polynomial for unaryElkind & Pasechnik Thm 1
Any NP-computable compact representationcoNP-completecoNP-complete—Greco et al. Cor. 4.9

The foundational reference is Deng & Papadimitriou, “On the complexity of cooperative solution concepts”, Mathematics of Operations Research 19(2):257–266 (1994), DOI 10.1287/moor.19.2.257. It is closed-access — Semantic Scholar’s API reports openAccessPdf: {status: CLOSED} and the INFORMS PDF URL returns a Cloudflare challenge to curl — so its results here are taken from Greco, Malizia, Palopoli & Scarcello, “On the Complexity of Core, Kernel, and Bargaining Set” (arXiv:0810.3136), which restates them twice and builds on them.

Uncertain — this note now disagrees with a textbook

Verify: whether core non-emptiness for general weighted graph games is NP-complete or coNP-complete. Reason: mas.pdf Theorem 12.3.10 states “Testing the nonemptiness of the core of a general WGG is NP-complete”, with a reduction from MAXCUT. The complexity literature says the opposite class: Greco et al. write that Deng and Papadimitriou “showed that checking whether the core is non-empty and that checking whether a payoff vector belongs to the core are co-NP-complete problems”, and repeat it in Proposition 4.3 and Corollary 4.9. The two are the same only if NP = coNP. coNP is also the class the shape of the problem predicts: the natural short certificate is for emptiness (a violated balanced inequality of at most n coalitions), not for non-emptiness. I have gone with the complexity literature and marked the textbook statement as the likely slip; the earlier revision of this note copied mas.pdf. To resolve: read Deng & Papadimitriou 1994 directly, which I could not obtain.

Two structural points that the table alone does not convey.

Why core non-emptiness is not obviously in coNP at all. Bondareva–Shapley looks like it hands you a certificate: exhibit a balanced collection violating the inequality. But as Ieong and Shoham observed, and Greco et al. quote, “the obvious certificate of non-emptiness of the core based on the Bondareva-Shapley theorem is exponential in size”, so it does not establish coNP membership. Greco et al. get membership instead from Helly’s theorem — if a finite family of convex sets in ℝⁿ has empty intersection, some subfamily of n + 1 of them already has empty intersection — which bounds the certificate to n + 1 coalition constraints regardless of how many coalitions the game has. That is a genuinely satisfying resolution: the geometry of the core, not its combinatorics, is what makes emptiness succinctly certifiable.

The synergy representation, from the primary source. mas.pdf’s Proposition 12.3.12 and Theorem 12.3.13 restate results of Conitzer & Sandholm, “Complexity of Determining Nonemptiness of the Core” (arXiv:cs/0307016), which I read. Their representation lists only the coalitions that introduce synergy, with v(S) for an arbitrary S recovered as the best partition of S into listed pieces — so evaluating v(N) is itself a set-partitioning optimisation. Their Theorem 2 shows CORE-NONEMPTY with transferable utility is NP-complete (reduction from EXACT-COVER-BY-3-SETS), and their Theorem 4 shows that if v(A) is supplied as part of the input the problem falls into P, by exactly the LP this note has been solving all along. Their Theorem 5 is the sting in the tail: for the hybrid setting where utility may be transferred only inside the grand coalition, the problem stays NP-complete even with v(A) given. They also record the historical attribution for the core itself — “It was first introduced by Gillies [Gillies, 1953]”, matching the two Gillies items in Shapley’s RM-4571 bibliography (a 1953 Princeton PhD thesis, Some Theorems on n-Person Games, and “Solutions to General Non-Zero-Sum Games”, Annals of Mathematics Study 40 (1959), 47–85).

Weighted voting games get their own story. For the class this note measured 400 random instances of, core non-emptiness is easy — the veto-player theorem is the algorithm. What is hard is the refinement: Elkind, Goldberg, Goldberg & Wooldridge (2007) showed the least core and the nucleolus are NP-hard when weights are given in binary, and Elkind & Pasechnik (arXiv:0808.0298) closed the open case with a pseudo-polynomial algorithm: the nucleolus of a weighted voting game is computable in time polynomial in n and W = maxᵢ wᵢ, via successive exponential-sized LPs solved with dynamic-programming separation oracles under the ellipsoid method. The practical reading is the one they give: in political-body applications the weights are seat counts, so W is small and the pseudo-polynomial bound is a real algorithm.

The pattern is worth internalising: the compact representation that makes the game writable is exactly what makes the solution concept hard. Weighted graph games with arbitrary signs encode MAXCUT into core-emptiness; the synergy representation hides a set-partitioning problem inside the value of the grand coalition; weighted voting games hide a subset-sum inside the least core. This is the same phenomenon as in Support Enumeration and The Lemke-Howson Algorithm on the non-cooperative side — the succinct input is where the complexity lives.

Above the core, it gets worse. Greco et al.’s main results settle two conjectures of Deng and Papadimitriou and place the neighbouring concepts higher in the polynomial hierarchy: deciding whether a payoff vector is in the kernel is Δᴾ₂-complete, and deciding whether it is in the bargaining set is Πᴾ₂-complete, on graph games and on MC-nets alike. The core is, in this precise sense, the easy member of its own family — which is one more reason it is the concept that gets deployed.

Failure Modes and Gotchas

1. Freezing the wrong constraints in the nucleolus — a bug that produces a plausible wrong answer. My first nucleolus implementation, after each round, froze every coalition whose constraint was tight at the optimal vertex the LP happened to return. That is wrong: the round’s LP typically has many optima, and only constraints tight in all of them are genuinely determined. The symptom is subtle and almost undetectable by eye — on the airport savings game the code returned (1/2, 3/2, 1) on one solver and (1/2, 1, 3/2) on another. Both look reasonable. Both are wrong: players b and c are interchangeable in that game (v(ab) = v(ac) = 1), the nucleolus is unique, and a unique concept must be symmetric under renaming — so the answer had to have x_b = x_c. The correct value is (1/2, 5/4, 5/4). The fix is to test each candidate coalition separately: after fixing ε_k, re-maximise Σ_{i∈S} xᵢ over the round’s feasible set with ε = ε_k; freeze S only if that maximum still equals v(S) − ε_k.

The regression test that catches it

The nucleolus is unique, therefore it is equivariant under permutation of the players. Generate a random game v, permute the player labels to get v∘π, compute both nucleoli, and assert nucleolus(v)ᵢ = nucleolus(v∘π)_{π(i)}. On the buggy version this fails immediately; the fixed version passes 120/120 random 3- and 4-player games. This is a good test in general: any solution concept advertised as unique must commute with relabelling, and that is far easier to check than the concept’s definition.

The principled check, if you want a proof rather than a smoke test

Symmetry testing catches this bug but does not certify correctness — a wrong answer that happens to be symmetric survives it. The certificate is Kohlberg’s criterion from the section above: compute the tiers of tight coalitions T₁(x), T₂(x), … at your candidate x and verify that every prefix union T₁ ∪ ⋯ ∪ Tₖ is T₀-balanced. That is a necessary and sufficient condition, so a candidate passing it is the nucleolus, full stop. It is also almost free to implement once the Bondareva–Shapley dual is written, since balancedness is the same linear system in both places. The cost is exponential in n and gets painful past 15 players (Benedek et al. §1) — but the games where you are debugging a freeze rule are small games.

2. Empty core reported as “infeasible”. The core LP min Σxᵢ s.t. Σ_{i∈S} xᵢ ≥ v(S) is always feasible — take xᵢ huge. Emptiness of the core shows up as the optimum exceeding v(N), not as LP infeasibility. If you instead write the LP with efficiency as an equality and ask a solver “feasible?”, you get infeasibility and no information about how far off you were. Solving the minimisation gives you the least-core gap for free.

3. Sign conventions. See the table at the top. A cost game’s core LP maximises; a payoff game’s minimises; the inequalities point opposite ways. Mixing the two mid-derivation is the standard error.

4. Floating point turns exact answers into coin flips. The interesting question is always an equality: does the optimum equal v(N)? In the facility-location example the two answers differ by 8 − 7.5 = 0.5, which is fine, but in the airport game the primal optimum is 3 and v(N) is 3 — a floating-point solver returns 2.9999999999999996 and a tolerance you now have to tune. With fractions.Fraction the comparison is just == and there is nothing to tune. This is the whole argument for exact arithmetic on small games.

5. Superadditivity does not save you. The majority-voting game is superadditive and its core is empty. Superadditivity justifies focusing on the grand coalition (it is the highest-value coalition structure); it says nothing about whether the grand coalition’s proceeds can be divided stably.

6. “The core is non-empty” is not “the core is a point”. With an 80% quota, the weighted-voting core is the whole segment of splits between the two veto players — every allocation giving C and D zero. Non-emptiness gives you stability, not prediction. If you need a single number you must go to the nucleolus, the Shapley value, or an explicit selection rule, and each answers a different question.

7. The Shapley value can be individually irrational. It is guaranteed to be a pre-imputation, not an imputation: nothing forces φᵢ ≥ v({i}) in a non-superadditive game. Check it if you are going to hand the numbers to someone.

Alternatives and When to Choose Them

ConceptAlways exists?Unique?AnswersCost to compute (explicit game)Choose it when
CoreNoNoWhich divisions are stable against group defection?one LP, 2ⁿ−1 constraintsYou need a stability guarantee and can tolerate “no answer”
ε-core / least coreLeast core: yesNoHow much defection deterrence is required?one LPThe core is empty and you want to know by how much
NucleolusYesYesWhich single division minimises the worst grievance?≤ n sequential LPsYou must ship one number and want it in the core when possible
Shapley valueYesYesWhat is each player’s average marginal contribution?closed form, 2ⁿ terms (or O(n²) in special classes)You need fairness/attribution, not stability
Nash EquilibriumYes (mixed)NoWhat will individuals do?PPAD-completeDeviations are individual, and you have an explicit strategy space
Stable Matching / Top Trading CyclesYes, constructivelyVariesWhich assignment has no blocking pair/cycle?O(n²)Utility is non-transferable and the structure is a matching
Correlated EquilibriumYesNoWhat can a mediator recommend?one LPYou have a coordination device and individual deviations

The line to hold: the core is a stability concept and the Shapley value is a fairness concept, and they routinely disagree. The glove market above is the canonical collision — the core hands everything to the scarce side, the Shapley value pays the abundant side for their orderings, and neither is “right”. Choose by what you must defend: a regulator asking “is this split fair?” wants Shapley; an engineer asking “will this coalition hold together?” wants the core.

Against Stable Matching, the contrast is Gale–Shapley’s constructive existence versus Bondareva–Shapley’s conditional existence — the same lesson the parent MOC draws about existence versus construction. Deferred acceptance always finds a stable matching; the core LP tells you whether one exists and, half the time in some game classes, the answer is no.

Production Notes

Cost sharing is the deployed form. The economically important use of the core is not coalition prediction but allocating a shared cost so nobody wants to leave — multicast trees, shared network infrastructure, facility siting. Nisan et al. devote chapter 15 to exactly this, and the connection they establish is the practically useful one: for subadditive cost functions, the best achievable budget-balance factor γ in a core-respecting allocation equals the integrality gap of the covering LP. For metric facility location the best known bounds put that gap between 1/1.52 and 1/1.463, which means you can prove in advance that no cost-sharing scheme respecting the core property can recover more than about 96% of cost. That is a hard limit on a product decision, derived from an approximation-algorithms result.

Airport landing fees are the oldest deployed instance, and they are still being extended. The Littlechild–Owen construction above is not a historical curiosity: the modern literature builds directly on it, with the Owen value handling the case where movements are grouped into airlines (Vázquez-Brage et al. 1997) and recent work extending it to code-sharing, where one movement is operated jointly by several airlines and the fee must be split among the actual beneficiaries. The solution-concept-to-airport-formula correspondence is a compact map of the whole area: Shapley value → Littlechild & Owen (1973); nucleolus → Littlechild (1974); Banzhaf value → Saavedra-Nieves (2019); τ-value → Tijs & Driessen (1986); core-center → González-Díaz et al. (2016). If you are allocating a shared fixed cost whose size is set by the largest user — a runway, a pipe diameter, a link bandwidth, a GPU with enough memory for the biggest tenant’s model — that table is your literature.

Network bargaining is the same LP wearing different clothes. Bateni, Hajiaghayi, Immorlica & Mahini (arXiv:1004.4317) study bipartite supplier–manufacturer markets where agents sign capacity-limited contracts and split the surplus, and their central technical move is a linear-programming formulation establishing “a novel connection between well-studied cooperative game theory concepts (such as core and prekernel) and the solution concepts of stable and balanced defined for the bargaining games”. Having made the connection they take the nucleolus off the shelf as their refinement, on exactly the grounds this note gives — “it is unique, always exists, and is supported by experimental data in the network bargaining literature” — and compute it by pruning and iteratively solving the natural LP. That is the sequential-LP construction from this note, applied to a market-design problem, with an experimental argument for preferring the nucleolus over the alternatives.

Group-strategyproofness pulls in the opposite direction. Nisan et al. go on to show that mechanisms which are strategyproof against coalitions need cross-monotonic cost-sharing schemes — a player’s share must never rise when the served set grows — and cross-monotonicity is strictly stronger than the core property. The chapter’s later sections are a catalogue of how much budget balance you must give up to get it (e.g. 1/2-budget-balance with a matching upper bound for Steiner forest, due to Könemann et al. 2007). Anyone building a shared-cost billing system is choosing a point on that trade-off whether or not they know it.

VCG payoffs need not be in the core. A nice concrete failure documented in mas.pdf §12.2.2: in a single-item second-price auction with truthful bidding, the payoffs are always in the core, because the seller’s revenue (the second-highest valuation) already exceeds every loser’s valuation. But VCG applied to a combinatorial auction breaks this. With two goods x, y and valuations v₁(x,y) = 90, v₂(x) = v₂(x,y) = 100, v₃(y) = v₃(x,y) = 100, the efficient allocation gives x to bidder 2 and y to bidder 3; neither is pivotal, so both pay zero, and the seller plus bidder 1 would both prefer a side deal at any price between 0 and 90. The seller’s revenue is not in the core. This is one of the concrete reasons behind Why VCG Is Rare in Practice, and it is a coalitional-game statement about a mechanism-design object.

Auctions as coalitional games are how you ask “should I exclude a bidder?” Modelling an efficient auction as a coalitional game — agents are the bidders plus the seller, v(S) is the social welfare achievable with only S participating, and any coalition without the seller has value 0 — turns “would the seller prefer to exclude some interested agents to obtain higher payments?” into a core-membership question. mas.pdf notes this can indeed occur.

Where the vault’s own systems are coalitional games. Practical Byzantine Fault Tolerance fixes a threshold at 3f+1 precisely because coalitions of size f must not be able to profit by deviating — a core condition stated as a protocol parameter. Multi-Tenancy and Fairness in LLM Serving allocates capacity among tenants who could in principle split off onto their own cluster; whether the allocation is in the core is exactly the question “will a group of tenants defect?”. Neither note frames it that way, which is the gap the parent MOC exists to close.

See Also

Primary sources read in full for this note (both are 1965 RAND scans with no text layer; page images were rendered with pdftoppm): Shapley, RM-4571-PR Notes on N-Person Games VII: Cores of Convex Games and RM-4601-PR On Balanced Sets and Cores. Between them they contain the Bondareva–Shapley theorem (RM-4601 Thm 1), the convex-game results (RM-4571 Lemma 3, Thms 2–5), the bibliographic pin for Bondareva 1963 and Gillies 1953/1959, and the two worked examples recomputed above.

Graph View

Backlinks