In cooperative game theory, the nucleolus of a cooperative game is the solution (i.e., allocation of payments to players) that maximizes the smallest excess of a coalition (where the excess is the difference between the payment given to the coalition and the value the coalition could get by deviating).
Subject to that, the nucleolus satisfies the second-smallest excess; and so on, in the leximin order.
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.
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
, which assigns a value to each possible coalition (each subset of players).
, 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.
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.
The nucleolus of a general game can be computed by any algorithm for lexicographic max-min optimization.
The number of iterations required by the more efficient algorithms is at most n, so the run-time is O(n 2n).
If the cooperative game is given by enumerating all coalitions' values, then the input size is 2n , and so the above algorithms run in time polynomial in the input size.
But when n is large, even representing such a game is computationally intensive, and there is more interest in classes of cooperative games that have a compact representation.
A coalition can force a decision if its total weight is above a certain threshold.
In a weighted voting game, the core can be computed in time polynomial in n. In contrast, the least-core is NP-hard, but has a pseudopolynomial time algorithm - an algorithm polynomial in n and the maximum weight W.[3] Similarly, the nucleolus is NP-hard,[3] but has a pseudopolynomial time algorithm.
[4] The proof relies on solving successive exponential-sized linear programs, by constructing dynamic-programming based separation oracles.
In a minimum-cost spanning-tree game, each player is a node in a complete graph.
[5] Computing the nucleolus on general MCST games is NP-hard,[6] but it can be computed in polynomial time if the underlying network is a tree.
[7][8] In weighted cooperative matching games, the nucleolus can be computed in polynomial time.
[9] In some games, the value of each coalition is not given explicitly, but it can be computed by solving a set of mathematical programming problems.
Using a constraint generation approach, it is possible to compute only the values of coalitions that are required for the nucleolus.
This allows to compute the nucleolus efficiently in practice, when there are at most 20 players.
If the prekernel of a cooperative game contains exactly one core vector, then the nucleolus can be computed efficiently.
[12] The algorithm is based on the ellipsoid method and on a scheme of Maschler for approximating the prekernel.
Guajardo and Jornsten[13] have found mistakes in the application of linear programming and duality to computing the nucleolus.