The Core

The Shapley value asks how to divide the value of a coalition fairly. It says nothing about whether the players will accept that division. This chapter studies the core, the set of allocations that are stable in the sense that no group of players can do better by breaking away. Fairness and stability are different demands, and as we will see they need not agree.

Motivating Example: Will the party stick together?¶

Recall the D&D battle from the previous chapter, in which Ren, Azel, and Quinn divide 1,000 gold coins. The Shapley value divides the hoard fairly, giving

This is a fair split: each character receives their average marginal contribution. But is it stable? Recall that Ren and Azel together can secure 900 coins on their own, since $v(\{\text{Ren}, \text{Azel}\}) = 900$. Under the Shapley value they receive only $350 + 450 = 800$ between them. The two of them would do better to walk away from Quinn and split the 900 they can earn alone.

The fair allocation is therefore not stable: a sub-group is being short-changed relative to what it could guarantee itself. If the party is to stay together, the division must give every coalition at least what it could secure on its own. The set of allocations meeting that demand is the subject of this chapter.

Theory¶

Definition: Imputation¶

Given a characteristic function game $G = (N, v)$, a payoff vector $x \in \mathbb{R}^N$ is an imputation if it is:

• efficient: $\sum_{i \in N} x_i = v(N)$, the whole value of the grand coalition is shared out; and

• individually rational: $x_i \geq v(\{i\})$ for every player $i$, so that no player receives less than they could secure alone.

Individual rationality is the weakest possible stability requirement: it asks only that no single player wishes to leave. The core strengthens this to every coalition.

Example: Imputations of the D&D battle¶

For the D&D battle the grand coalition is worth $v(N) = 1000$ and each player alone is worth $v(\{i\}) = 0$, so a payoff vector is an imputation precisely when it sums to 1000 and gives every player a non-negative amount. The Shapley value $(350, 450, 200)$ is an imputation, and so is the lopsided split $(1000, 0, 0)$ in which Ren takes everything. The vector $(1100, -100, 0)$ is not an imputation: it is efficient, but Azel receives $-100 < v(\{\text{Azel}\}) = 0$, less than they could secure alone. Individual rationality alone permits a great many allocations; the core will cut them down.

Definition: The Core¶

The core of a characteristic function game $G = (N, v)$ is the set of efficient payoff vectors on which no coalition can improve:

The defining inequalities are the coalitional rationality constraints: every coalition $C$ must receive, in total, at least the value $v(C)$ it could secure by itself. A coalition for which $\sum_{i \in C} x_i < v(C)$ is said to block the allocation $x$; the core is exactly the set of efficient, unblocked allocations. Since the singleton constraints $x_i \geq v(\{i\})$ are among the coalitional ones, every core allocation is an imputation, but the converse need not hold.

Example: The core of the D&D battle¶

For the D&D battle, an allocation $x = (x_{\text{Ren}}, x_{\text{Azel}}, x_{\text{Quinn}})$ is in the core if it is efficient, $x_{\text{Ren}} + x_{\text{Azel}} + x_{\text{Quinn}} = 1000$, and no coalition can block it:

The Shapley value $(350, 450, 200)$ violates the first inequality, since $350 + 450 = 800 < 900$, confirming that it is not in the core. A stable allocation must give the strong pair $\{\text{Ren}, \text{Azel}\}$ at least 900 between them. The allocation $(350, 600, 50)$ satisfies every inequality ($950 \geq 900$, $400 \geq 400$, $650 \geq 600$) and so lies in the core: the party will stay together under it. The core here is not empty, but the fair allocation lies outside it.

Definition: Convex game¶

A characteristic function game $G = (N, v)$ is convex (or supermodular) if

Equivalently, a game is convex when the marginal contribution of a player to a coalition never decreases as the coalition grows: players become more valuable as more of the others join. Convexity is stronger than superadditivity, which is the special case where $S$ and $T$ are disjoint.

Example: The D&D battle is not convex¶

In the D&D battle, adding Quinn to the coalition $\{\text{Ren}\}$ raises its value by $v(\{\text{Ren}, \text{Quinn}\}) - v(\{\text{Ren}\}) = 400$, while adding Quinn to the larger coalition $\{\text{Ren}, \text{Azel}\}$ raises it by only $v(N) - v(\{\text{Ren}, \text{Azel}\}) = 100$. Quinn’s marginal contribution falls as the coalition grows, so the game is not convex. This is exactly why, as the next theorem makes precise, its fair and stable allocations can come apart.

Theorem: Convex games have a non-empty core¶

If $G = (N, v)$ is convex, then its core is non-empty and contains the Shapley value.

We state this result without proof; it is due to Shapley Shapley, 1971. Convexity is therefore a convenient sufficient condition: for a convex game the fair allocation and a stable allocation coincide, because the Shapley value is itself in the core. The D&D battle shows that without convexity the two can come apart: it is not convex, as the example above shows, and its Shapley value lies outside its core.

Theorem: The Bondareva–Shapley theorem¶

The core may be empty, and there is an exact condition for when it is not. A collection of weights $(\lambda_C)_{C \subseteq N,\, C \neq \emptyset}$ with $\lambda_C \geq 0$ is balanced if, for every player $i$, $\sum_{C \,:\, i \in C} \lambda_C = 1$. The game is balanced if for every such balanced collection $\sum_{C} \lambda_C v(C) \leq v(N)$.

The core of $G = (N, v)$ is non-empty if and only if the game is balanced.

We state the theorem, due independently to Bondareva Bondareva, 1963 and Shapley Shapley, 1967, without proof. Its practical content is that core non-emptiness is a linear programming question. The core is non-empty precisely when the linear program

has optimal value equal to $v(N)$; the balancedness condition is exactly the statement that the dual of this program never exceeds $v(N)$. When the optimum equals $v(N)$, the optimal $x$ is itself a point of the core.

Definition: The nucleolus¶

When the core is non-empty it is usually not a single point, and we may want to select one allocation from it. For a payoff vector $x$ and coalition $C$, the excess $e(C, x) = v(C) - \sum_{i \in C} x_i$ measures how dissatisfied $C$ is with $x$: a positive excess means $C$ is blocking. The nucleolus is the imputation that lexicographically minimises the vector of excesses sorted from largest to smallest, that is, it first makes the most dissatisfied coalition as satisfied as possible, then the next, and so on.

The nucleolus always exists, is unique, and whenever the core is non-empty it lies in the core. It can be read as the most stable allocation of all: it pushes every coalition as far from blocking as the game allows.

Example: The nucleolus of the D&D battle¶

For the D&D battle the singleton coalitions have excess $e(\{i\}, x) = -x_i \leq 0$ and so are never the most dissatisfied; the binding coalitions are the three pairs. Using efficiency $x_{\text{Ren}} + x_{\text{Azel}} + x_{\text{Quinn}} = 1000$, their excesses are

These three excesses always sum to $1000 - 1100 = -100$, so the largest of them is at least the average $-100/3$, with equality only when all three are equal. The nucleolus makes the largest excess as small as possible, and so equalises them, giving

This allocation lies in the core, and it differs from both the Shapley value $(350, 450, 200)$ and the core allocation $(350, 600, 50)$ met earlier: the nucleolus is the single division that holds every coalition as far from blocking as the game permits.

Exercises¶

Programming¶

The coopgt library can check whether a payoff vector is an imputation or lies in the core, and whether a game is convex. We continue with the D&D battle.

import coopgt.core
import coopgt.shapley_value

characteristic_function = {
    (): 0,
    (1,): 0,
    (2,): 0,
    (3,): 0,
    (1, 2): 900,
    (1, 3): 400,
    (2, 3): 600,
    (1, 2, 3): 1000,
}

shapley = coopgt.shapley_value.calculate(characteristic_function)
print(f"Shapley value: {shapley}")

Shapley value: [350. 450. 200.]

The Shapley value is fair, but it is not in the core, because the coalition $\{1, 2\}$ can block it:

print(f"Shapley value in the core? {coopgt.core.is_in_core(characteristic_function, shapley)}")

Shapley value in the core? False

The game is not convex, which is why fairness and stability come apart:

print(f"Game convex? {coopgt.core.is_convex(characteristic_function)}")

Game convex? False

By the Bondareva–Shapley theorem the core is non-empty exactly when the game is balanced. coopgt finds a point of the core by solving the associated linear program, returning None when the core is empty:

core_point = coopgt.core.find_core_point(characteristic_function)
print(f"A point in the core: {core_point}")

A point in the core: [400. 600.  -0.]

An allocation is returned rather than None, so the core is non-empty, and we can confirm that the allocation it found is indeed a point of the core:

print(f"Found allocation in the core? {coopgt.core.is_in_core(characteristic_function, core_point)}")

Found allocation in the core? True

Notable Research¶

The core was introduced by Gillies Gillies, 1959 as part of his study of stable allocations in cooperative games, building on the stable-set ideas of von Neumann and Morgenstern. The exact condition for the core to be non-empty was established independently by Bondareva Bondareva, 1963 and Shapley Shapley, 1967 in the balancedness theorem that now bears both their names, tying core non-emptiness to linear programming duality.

Shapley Shapley, 1971 showed that convex games always have a non-empty core whose extreme points are the marginal-contribution vectors, and that the Shapley value is their barycentre and hence always in the core. The nucleolus was introduced by Schmeidler Schmeidler, 1969, who proved that it always exists, is unique, and lies in the core whenever the core is non-empty.

Cooperative solution concepts of this kind underpin practical cost-sharing and resource-allocation schemes, from apportioning the cost of shared infrastructure to allocating gains in collaborative logistics, where stability is what keeps a coalition of firms or municipalities from walking away.

Conclusion¶

In this chapter we studied the core, the set of allocations that no coalition can improve upon. Where the Shapley value answers the question of fairness, the core answers the question of stability, and the D&D battle shows that the two can disagree: the fair allocation left the strong pair worse off than they could be alone.

We saw that the core is a polytope, that it can be empty, and that the Bondareva–Shapley theorem characterises non-emptiness through balancedness, turning the question into a linear program. Convex games are a well-behaved class for which the core is always non-empty and contains the Shapley value, so that fairness and stability coincide. Finally the nucleolus selects a single, maximally stable allocation from the core whenever one exists.

Table 1 summarises the concepts of this chapter.

Solutions¶