Nucleolus (game theory)

In a cooperative game, there is a set N of players, who can cooperate and form coalitions. Each coalition S (subset of players) has a value, which is the profit that S can make if they coopereate on their own, ignoring the other players in N. The players opt to form the grand coalition - a coalition containing all players in N. The question then arises, how should the value of the grand coalition be allocated among the players? Each such allocation of value is called a solution or a payoff vector.

The excess of any coalition S from a given payoff-vector x is the difference between the total payoff to members of S under x, and the value of S. Note that the excess can be positive, negative or zero. Intuitively, a solution in which all coalitions have a higher excess is more stable, since coalitions are less incentivized to deviate from the grand-coalition.

The nucleolus is a single solution, for which the vector of excesses of all coalitions is largest in the leximin order. Intuitively, the nucleolus maximizes the stability of the solution by minimizing the incentives of coalitions to deviate.

A cooperative game is represented by a value function ${\displaystyle v:2^{N}\to \mathbb {R} }$, which assigns a value to each possible coalition (each subset of players). A solution to a cooperative game is a vector ${\displaystyle x\in \mathbb {R} ^{N}}$, which assigns a payoff to each player in N. A solution should satisfy the basic requirement of efficiency: the sum of payoffs should exactly equal v(N) -- the value of the grand coalition. A payoff solution satisfying this condition is called an imputation.

The excess of a payoff-vector ${\displaystyle x}$ for a coalition ${\displaystyle S\subseteq N}$ is the quantity ${\displaystyle excess(x,S):=\sum _{i\in S}x_{i}-v(S)}$. That is, the profit that players in coalition ${\displaystyle S}$ obtain if they remain in the grand coalition ${\displaystyle N}$ and do not deviate.[note 1]

Let ${\displaystyle \theta (x)\in \mathbb {R} ^{2^{N}}}$ be the vector of excesses of ${\displaystyle x}$, arranged in non-decreasing order: ${\displaystyle \theta _{i}(x)\leq \theta _{j}(x),\forall ~i<j}$. For two payoff vectors ${\displaystyle x,y}$, we say ${\displaystyle \theta (x)}$ is lexicographically smaller than ${\displaystyle \theta (y)}$ if for some index ${\displaystyle k}$, we have ${\displaystyle \theta _{i}(x)=\theta _{i}(y),\forall ~i<k}$ and ${\displaystyle \theta _{k}(x)<\theta _{k}(y)}$. The nucleolus of ${\displaystyle v}$ is the lexicographically largest imputation, based on this ordering. In other words, the nucleolus is an imputation whose excesses-vector is largest in the leximin order. It can be represented by the following optimization problem:

$${\displaystyle {\begin{aligned}\operatorname {lex} \max \min &&excess(x,S_{1}),excess(x,S_{2}),\ldots ,excess(x,S_{k})\\{\text{subject to}}&&x~{\text{is an imputation}}\end{aligned}}}$$

where k = 2^N = the number of possible coalitions.

• The nucleolus is always unique. See [1] and Section II.7 of [2] for a proof.

• The core is, by definition, the set of all imputations in which the excess of each coalition is at least 0. Therefore, if the core is non-empty, the nucleolus is in the core.

• When the core is empty, it is natural to consider an approximation: the ε-core is the set of all imputations in which the excess of each coalition is at least -ε. For every ε, if the ε-core is non-empty, then the nucleolus is in the ε-core.
• The least-core is the smallest nonempty ε-core (for the smallest ε for which the ε-core is non-empty). The nucleolus is always in the least-core. In fact, the nucleolus can be seen as a refinement of the least-core. Starting with the least-core, record the coalitions for which the excess is exactly -ε. Find a subset of the least-core in which the smallest excess of the other coalitions is as large as possible. Repeat this process as many times as necessary until all coalitions have been recorded. The resulting payoff vector is the nucleolus.
• The nucleolus is always in the kernel, and since the kernel is contained in the bargaining set, it is always in the bargaining set (see [2] for details.)

• Contested garment rule