Nucleolus, Stable Coalitions, and Matching Theory

When the Core Is Insufficient

The core is an attractive concept, but it has two drawbacks: it can be empty (no stable allocation exists) and non-unique (many stable allocations). The nucleolus and stable sets are alternative concepts, each with its own logic.

Nucleolus: Minimizing Dissatisfaction

For an allocation x and coalition S, define the excess $e(S, x) = v(S) - \sum_{i \in S} x_i$. Positive excess: coalition S can "do better" for itself if it breaks off. Negative: the coalition "loses out" by breaking off.

The nucleolus is the allocation x that lexicographically minimizes the vector of excesses for all coalitions, ordered in descending order. First, we minimize the maximal excess; then, among allocations with the maximally "satisfied" ones fixed, we minimize the next one, and so on.

Schmeidler (1969): the nucleolus exists and is unique for any game. If the core is non-empty, the nucleolus lies within it.

Numerical example: $N = {1,2,3}, v({1,2}) = 60, v({1,3}) = 80, v({2,3}) = 40, v(N) = 100, v({i}) = 0.$

Step 1. From efficiency: $x_1 + x_2 + x_3 = 100$. Core conditions: $x_1 + x_2 \geq 60$, $x_1 + x_3 \geq 80$, $x_2 + x_3 \geq 40$. From $x_1 + x_2 \geq 60$ and $x_1 + x_3 \geq 80$: adding, $2x_1 + x_2 + x_3 \geq 140$, that is, $x_1 \geq 40$. Also, $x_2 + x_3 = 100 - x_1 \leq 60$. But we also need $x_2 + x_3 \geq 40$ ✓. Core: $x_1 \geq 40$, $x_1 + x_2 \geq 60$, $x_1 + x_3 \geq 80$.

To find the nucleolus: with $x_1 + x_2 + x_3 = 100$, minimize $\max(60 - x_1 - x_2,\ 80 - x_1 - x_3,\ 40 - x_2 - x_3)$. Equalizing the first two: $60 - x_1 - x_2 = 80 - x_1 - x_3 \rightarrow x_3 - x_2 = 20$. Using $x_1 + x_2 + x_3 = 100$ and equality of excesses: nucleolus $\approx (50, 20, 30)$. Check: $e({1,2}, \nu) = 60 - 70 = -10$; $e({1,3}, \nu) = 80 - 80 = 0$; $e({2,3}, \nu) = 40 - 50 = -10$.

von Neumann–Morgenstern Stable Sets

Von Neumann and Morgenstern (1944) proposed the concept of a stable set V:

• Internal stability: No allocation $x \in V$ dominates $y \in V$ (via some coalition S: $\sum_{i \in S} x_i \leq v(S)$ and $x_i > y_i$ for all $i \in S$)
• External stability: For each $x \notin V$, there exists $y \in V$ that dominates x

A stable set is interpreted as a "social norm": within it there is no conflict, but for outsiders there is always an alternative from V. Drawbacks: V can be uncountable, non-unique, or not exist (Lucas's example, 1969).

Matching Theory: Markets Without Prices

A matching is an allocation of agents of two types: employers–employees, students–universities. No explicit prices—only preferences.

The Stable Marriage Problem (Gale–Shapley, 1962): N men, N women, strict preferences. A matching $\mu$ is stable if there is no "blocking pair" $(m, w)$: m prefers w to his partner AND w prefers m to her partner.

DA Algorithm (Deferred Acceptance): 1. Men propose to their top choices. 2. Each woman "defers" the best proposal, rejects all others. 3. Rejected men propose to their next candidate. 4. Repeat until stabilization.

Theorem: DA always ends with a stable matching. The outcome with proposals from men is M-optimal (best for all men among stable matchings) and W-pessimal.

Numerical example: 3 men ($m_1$, $m_2$, $m_3$) and 3 women ($w_1$, $w_2$, $w_3$).

Men's preferences: $m_1$: $w_1 > w_2 > w_3$; $m_2$: $w_1 > w_3 > w_2$; $m_3$: $w_2 > w_1 > w_3$. Women's preferences: $w_1$: $m_2 > m_1 > m_3$; $w_2$: $m_1 > m_2 > m_3$; $w_3$: $m_1 > m_2 > m_3$.

Round 1: $m_1 \rightarrow w_1$ (accepts, holds); $m_2 \rightarrow w_1$ (accepts, holds $m_2$ instead of $m_1$! since $w_1$: $m_2 > m_1$); $m_1$ rejected.

Round 2: $m_1 \rightarrow w_2$ (accepts, holds); $m_3 \rightarrow w_2$ ($w_2$: $m_1 > m_3$ $\rightarrow$ $w_2$ holds $m_1$, rejects $m_3$).

Round 3: $m_3 \rightarrow w_1$ ($w_1$ holds $m_2$, $w_1$: $m_2 > m_3$ $\rightarrow$ rejects $m_3$).

Round 4: $m_3 \rightarrow w_3$ (accepts). Final: ${m_1-w_2, m_2-w_1, m_3-w_3}$.

Application: NRMP (placement of medical residents in US hospitals since 1952) and school assignments in NYC and Boston — the DA algorithm by Alvin Roth (Nobel 2012). Stable matchings provide systemic stability: with unstable allocation, blocking pairs "break" official assignments — this was observed before the DA mechanism was introduced. Stability is a key property making the Gale–Shapley algorithm practically applicable to real markets with two-sided preferences.

The Core and Nucleolus in Cost Allocation and Merger Negotiations

The concepts of the core and nucleolus are directly applied in negotiation processes and cost allocation. In building joint infrastructure (water supply, road, power line) among several users, the core sets the range of acceptable cost allocations: no subgroup of users should pay more than it would cost them to build the facility on their own. The nucleolus minimizes the maximum "dissatisfaction" of coalitions and provides a unique solution even when the core is empty. In corporate merger negotiations, the core delineates the range of fair allocation of synergies between the merging parties: an offer outside the core will be rejected, since one party can achieve more without merging. In international trading blocs, the nucleolus is used to set quotas and compensatory payments among member countries. The question of non-emptiness of the core (the core exists if and only if the game is balanced, by the Bondareva–Shapley theorem) determines whether stable cooperation is possible or it will inevitably fall apart. Simplex programming is used to compute the nucleolus in large games.

The core and nucleolus are computed via linear programming: the core is a set of solutions to a system of inequalities (by the number of coalitions), the nucleolus is a minimax vector of excesses, found through lexicographic minimization. The software package gambit and Python libraries (nashpy, pycmptgame) implement these algorithms and are used in academic and practical pricing calculations for infrastructure projects.

Exercise: For the game $N = {1,2,3}: v({1,2}) = 60, v({1,3}) = 80, v({2,3}) = 40, v(N) = 100$. Find the core and nucleolus. Do they coincide?