Nucleolus (game theory)

Last updated January 20, 2024

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. The nucleolus was introduced by David Schmeidler.^[1]

Background

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.

Definitions

A cooperative game is represented by a value function $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 $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 $x$ for a coalition $S\subseteq N$ is the quantity $\mathrm {excess} (x,S):=\sum _{i\in S}x_{i}-v(S)$ . That is, the profit that players in coalition $S$ obtain if they remain in the grand coalition $N$ and do not deviate.^{[note 1]}

Let $\theta (x)\in \mathbb {R} ^{2^{N}}$ be the vector of excesses of $x$ , arranged in non-decreasing order: $\theta _{i}(x)\leq \theta _{j}(x),\forall ~i<j$ . For two payoff vectors $x,y$ , we say $\theta (x)$ is lexicographically smaller than $\theta (y)$ if for some index $k$ , we have $\theta _{i}(x)=\theta _{i}(y),\forall ~i<k$ and $\theta _{k}(x)<\theta _{k}(y)$ . The nucleolus of $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:

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

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

Properties

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

Relation to other solution concepts

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.)

Computation

General games

A general cooperative game among n players is characterized by 2ⁿ values - one value for each possible coalition. The nucleolus of a general game can be computed by any algorithm for lexicographic max-min optimization. These algorithms usually require to solve linear programs with one constraint for each objective value, plus some additional constraints. Therefore, the number of constraints is O(2ⁿ). The number of iterations required by the more efficient algorithms is at most n, so the run-time is O(n 2ⁿ).

If the cooperative game is given by enumerating all coalitions' values, then the input size is 2ⁿ , 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.

Weighted voting games

In a weighted voting game, each player has a weight. The weight of a coalition is the sum of weights of its members. A coalition can force a decision if its total weight is above a certain threshold. Therefore, the value of a coalition is 1 if its value is above the threshold, and 0 if its value is below the threshold. A weighted voting game can be represented by only n+1 values: a weight for each player, and the 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.

Minimum-cost spanning tree games

In a minimum-cost spanning-tree game, each player is a node in a complete graph. The graph contains an additional node s (the supply node). Each edge in the graph has a cost. The cost of each coalition S is the minimum cost of a spanning tree connecting all nodes in S to the supply node s. The value of S is minus the cost of S. Thus, a MCST game can be represented by O(n²) values.^[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]

Weighted cooperative matching games

In weighted cooperative matching games, the nucleolus can be computed in polynomial time.^[9]

Implicitly-given value function

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.^[10]

Potters, Reijnierse and Ansing^[11] present a fast algorithm for computing the nucleolus using the prolonged simplex algorithm.

Using the prekernel

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.

Mistakes in computing the nucleolus

Guajardo and Jornsten^[13] have found mistakes in the application of linear programming and duality to computing the nucleolus.

Notes

↑ Some papers define the excess of S as the value of S minus its total payment under x, that is, the profit that S could make by deviating. Under this definition, the goal is to minimize the largest excess, rather than maximizing the smallest excess.

Related Research Articles

Minmax is a decision rule used in artificial intelligence, decision theory, game theory, statistics, and philosophy for minimizing the possible loss for a worst case scenario. When dealing with gains, it is referred to as "maximin" – to maximize the minimum gain. Originally formulated for several-player zero-sum game theory, covering both the cases where players take alternate moves and those where they make simultaneous moves, it has also been extended to more complex games and to general decision-making in the presence of uncertainty.

In mathematics, tables of trigonometric functions are useful in a number of areas. Before the existence of pocket calculators, trigonometric tables were essential for navigation, science and engineering. The calculation of mathematical tables was an important area of study, which led to the development of the first mechanical computing devices.

In mathematics, the Laplace operator or Laplacian is a differential operator given by the divergence of the gradient of a scalar function on Euclidean space. It is usually denoted by the symbols $, (where is the nabla operator), or . In a Cartesian coordinate system, the Laplacian is given by the sum of second partial derivatives of the function with respect to each independent variable. In other coordinate systems, such as cylindrical and spherical coordinates, the Laplacian also has a useful form. Informally, the Laplacian Δ f (p) of a function f at a point p measures by how much the average value of f over small spheres or balls centered at p deviates from f (p) .$

In Vapnik–Chervonenkis theory, the Vapnik–Chervonenkis (VC) dimension is a measure of the size of a class of sets. The notion can be extended to classes of binary functions. It is defined as the cardinality of the largest set of points that the algorithm can shatter, which means the algorithm can always learn a perfect classifier for any labeling of at least one configuration of those data points. It was originally defined by Vladimir Vapnik and Alexey Chervonenkis.

In statistics, Gibbs sampling or a Gibbs sampler is a Markov chain Monte Carlo (MCMC) algorithm for sampling from a specified multivariate probability distribution when direct sampling from the joint distribution is difficult, but sampling from the conditional distribution is more practical. This sequence can be used to approximate the joint distribution ; to approximate the marginal distribution of one of the variables, or some subset of the variables ; or to compute an integral. Typically, some of the variables correspond to observations whose values are known, and hence do not need to be sampled.

In game theory, a cooperative game is a game with competition between groups of players ("coalitions") due to the possibility of external enforcement of cooperative behavior. Those are opposed to non-cooperative games in which there is either no possibility to forge alliances or all agreements need to be self-enforcing.

In cooperative game theory, the core is the set of feasible allocations or imputations where no coalition of agents can benefit by breaking away from the grand coalition. One can think of the core corresponding to situations where it is possible to sustain cooperation among all agents. A coalition is said to improve upon or block a feasible allocation if the members of that coalition can generate more value among themselves than they are allocated in the original allocation. As such, that coalition is not incentivized to stay with the grand coalition.

A fully polynomial-time approximation scheme (FPTAS) is an algorithm for finding approximate solutions to function problems, especially optimization problems. An FPTAS takes as input an instance of the problem and a parameter ε > 0. It returns as output a value is at least $times the correct value, and at most times the correct value.$

In game theory, folk theorems are a class of theorems describing an abundance of Nash equilibrium payoff profiles in repeated games. The original Folk Theorem concerned the payoffs of all the Nash equilibria of an infinitely repeated game. This result was called the Folk Theorem because it was widely known among game theorists in the 1950s, even though no one had published it. Friedman's (1971) Theorem concerns the payoffs of certain subgame-perfect Nash equilibria (SPE) of an infinitely repeated game, and so strengthens the original Folk Theorem by using a stronger equilibrium concept: subgame-perfect Nash equilibria rather than Nash equilibria.

Clenshaw–Curtis quadrature and Fejér quadrature are methods for numerical integration, or "quadrature", that are based on an expansion of the integrand in terms of Chebyshev polynomials. Equivalently, they employ a change of variables $and use a discrete cosine transform (DCT) approximation for the cosine series. Besides having fast-converging accuracy comparable to Gaussian quadrature rules, Clenshaw-Curtis quadrature naturally leads to nested quadrature rules, which is important for both adaptive quadrature and multidimensional quadrature (cubature).$

In game theory, an epsilon-equilibrium, or near-Nash equilibrium, is a strategy profile that approximately satisfies the condition of Nash equilibrium. In a Nash equilibrium, no player has an incentive to change his behavior. In an approximate Nash equilibrium, this requirement is weakened to allow the possibility that a player may have a small incentive to do something different. This may still be considered an adequate solution concept, assuming for example status quo bias. This solution concept may be preferred to Nash equilibrium due to being easier to compute, or alternatively due to the possibility that in games of more than 2 players, the probabilities involved in an exact Nash equilibrium need not be rational numbers.

In fully cooperative games players will opt to form coalitions when the value of the payoff is equal to or greater than if they were to work alone. The focus of the game is to find acceptable distributions of the payoff of the grand coalition. Distributions where a player receives less than it could obtain on its own, without cooperating with anyone else, are unacceptable - a condition known as individual rationality. Imputations are distributions that are efficient and are individually rational.

Linear production game is a N-person game in which the value of a coalition can be obtained by solving a linear programming problem. It is widely used in the context of resource allocation and payoff distribution. Mathematically, there are m types of resources and n products can be produced out of them. Product j requires $amount of the kth resource. The products can be sold at a given market price while the resources themselves can not. Each of the N players is given a vector of resources. The value of a coalition S is the maximum profit it can achieve with all the resources possessed by its members. It can be obtained by solving a corresponding linear programming problem as follows.$

Exact division, also called consensus division, is a partition of a continuous resource ("cake") into some k pieces, such that each of n people with different tastes agree on the value of each of the pieces. For example, consider a cake which is half chocolate and half vanilla. Alice values only the chocolate and George values only the vanilla. The cake is divided into three pieces: one piece contains 20% of the chocolate and 20% of the vanilla, the second contains 50% of the chocolate and 50% of the vanilla, and the third contains the rest of the cake. This is an exact division (with k = 3 and n = 2), as both Alice and George value the three pieces as 20%, 50% and 30% respectively. Several common variants and special cases are known by different terms:

Quantum complexity theory is the subfield of computational complexity theory that deals with complexity classes defined using quantum computers, a computational model based on quantum mechanics. It studies the hardness of computational problems in relation to these complexity classes, as well as the relationship between quantum complexity classes and classical complexity classes.

Congestion games (CG) are a class of games in game theory. They represent situations which commonly occur in roads, communication networks, oligopoly markets and natural habitats. There is a set of resources ; there are several players who need resources ; each player chooses a subset of these resources ; the delay in each resource is determined by the number of players choosing a subset that contains this resource. The cost of each player is the sum of delays among all resources he chooses. Naturally, each player wants to minimize his own delay; however, each player's choices impose a negative externality on the other players, which may lead to inefficient outcomes.

The multiplicative weights update method is an algorithmic technique most commonly used for decision making and prediction, and also widely deployed in game theory and algorithm design. The simplest use case is the problem of prediction from expert advice, in which a decision maker needs to iteratively decide on an expert whose advice to follow. The method assigns initial weights to the experts, and updates these weights multiplicatively and iteratively according to the feedback of how well an expert performed: reducing it in case of poor performance, and increasing it otherwise. It was discovered repeatedly in very diverse fields such as machine learning, optimization, theoretical computer science, and game theory.

Dynamic discrete choice (DDC) models, also known as discrete choice models of dynamic programming, model an agent's choices over discrete options that have future implications. Rather than assuming observed choices are the result of static utility maximization, observed choices in DDC models are assumed to result from an agent's maximization of the present value of utility, generalizing the utility theory upon which discrete choice models are based.

In mathematics, leximin order is a total preorder on finite-dimensional vectors. A more accurate, but less common term is leximin preorder. The leximin order is particularly important in social choice theory and fair division.

A minimum-cost spanning-tree game is a kind of a cooperative game. In an MCST game, each player is a node in a complete graph. The graph contains an additional node - the supply node - denoted by s. The goal of the players is that all of them will be connected by a path to s. To this end, they need to construct a spanning tree. Each edge in the graph has a cost, and the players build the minimum cost spanning tree. The question then arises, how to allocate the cost of this MCST among the players?

References

1 2 Schmeidler, D. (1969), "The nucleolus of a characteristic function game", SIAM Journal on Applied Mathematics, 17 (6): 1163–1170, doi:10.1137/0117107.
1 2 Driessen, Theo (1988), Cooperative Games, Solutions and Applications, Kluwer Academic Publishers, ISBN 9789401577878
1 2 Elkind, Edith; Goldberg, Leslie Ann; Goldberg, Paul; Wooldridge, Michael (2007-07-22). "Computational complexity of weighted threshold games". Proceedings of the 22nd National Conference on Artificial Intelligence - Volume 1. AAAI'07. Vancouver, British Columbia, Canada: AAAI Press: 718–723. ISBN 978-1-57735-323-2.
↑ Elkind, Edith; Pasechnik, Dmitrii (2009-01-04). Computing the nucleolus of weighted voting games. Proceedings of the 2009 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics. pp. 327–335. doi:10.1137/1.9781611973068.37. hdl: 10356/93815 . ISBN 978-0-89871-680-1.
↑ Bird, C. G. (1976). "On cost allocation for a spanning tree: A game theoretic approach". Networks. 6 (4): 335–350. doi:10.1002/net.3230060404.
↑ Faigle, Ulrich; Kern, Walter; Kuipers, Jeroen (1998-12-01). "Computing the nucleolus of min-cost spanning tree games is NP-hard". International Journal of Game Theory. 27 (3): 443–450. doi:10.1007/s001820050083. ISSN 0020-7276. S2CID 46730554.
↑ Megiddo, Nimrod (August 1978). "Computational Complexity of the Game Theory Approach to Cost Allocation for a Tree". Mathematics of Operations Research . 3 (3): 189–196. doi:10.1287/moor.3.3.189. ISSN 0364-765X.
↑ Galil, Zvi (1980-01-01). "Applications of efficient mergeable heaps for optimization problems on trees". Acta Informatica. 13 (1): 53–58. doi:10.1007/BF00288535. ISSN 0001-5903. S2CID 39221796.
↑ Könemann, Jochen; Pashkovich, Kanstantsin; Toth, Justin (2020-09-01). "Computing the nucleolus of weighted cooperative matching games in polynomial time". Mathematical Programming. 183 (1): 555–581. arXiv: 1803.03249 . doi:10.1007/s10107-020-01483-4. ISSN 1436-4646. S2CID 254135686.
↑ Hallefjord, Åsa; Helming, Reidun; Jørnsten, Kurt (1995-12-01). "Computing the nucleolus when the characteristic function is given implicitly: A constraint generation approach". International Journal of Game Theory. 24 (4): 357–372. doi:10.1007/BF01243038. ISSN 1432-1270. S2CID 122124918.
↑ Potters, Jos A. M.; Reijnierse, Johannes H.; Ansing, Michel (August 1996). "Computing the Nucleolus by Solving a Prolonged Simplex Algorithm". Mathematics of Operations Research . 21 (3): 757–768. doi:10.1287/moor.21.3.757. hdl: 2066/27990 . ISSN 0364-765X.
↑ Faigle, Ulrich; Kern, Walter; Kuipers, Jeroen (2001-09-01). "On the computation of the nucleolus of a cooperative game". International Journal of Game Theory. 30 (1): 79–98. doi:10.1007/s001820100065. ISSN 1432-1270. S2CID 17702694.
↑ Guajardo, Mario; Jörnsten, Kurt (2015-03-16). "Common mistakes in computing the nucleolus". European Journal of Operational Research. 241 (3): 931–935. doi:10.1016/j.ejor.2014.10.037. hdl: 11250/194983 . ISSN 0377-2217.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[2] Some papers define the excess of S as the value of S minus its total payment under x, that is, the profit that S could make by deviating. Under this definition, the goal is to minimize the largest excess, rather than maximizing the smallest excess.

[schmeidler-1] 1 2 Schmeidler, D. (1969), "The nucleolus of a characteristic function game", SIAM Journal on Applied Mathematics, 17 (6): 1163–1170, doi:10.1137/0117107.

[driessen-3] 1 2 Driessen, Theo (1988), Cooperative Games, Solutions and Applications, Kluwer Academic Publishers, ISBN 9789401577878

[:0-4] 1 2 Elkind, Edith; Goldberg, Leslie Ann; Goldberg, Paul; Wooldridge, Michael (2007-07-22). "Computational complexity of weighted threshold games". Proceedings of the 22nd National Conference on Artificial Intelligence - Volume 1. AAAI'07. Vancouver, British Columbia, Canada: AAAI Press: 718–723. ISBN 978-1-57735-323-2.

[5] Elkind, Edith; Pasechnik, Dmitrii (2009-01-04). Computing the nucleolus of weighted voting games. Proceedings of the 2009 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics. pp. 327–335. doi:10.1137/1.9781611973068.37. hdl: 10356/93815 . ISBN 978-0-89871-680-1.

[:1-6] Bird, C. G. (1976). "On cost allocation for a spanning tree: A game theoretic approach". Networks. 6 (4): 335–350. doi:10.1002/net.3230060404.

[7] Faigle, Ulrich; Kern, Walter; Kuipers, Jeroen (1998-12-01). "Computing the nucleolus of min-cost spanning tree games is NP-hard". International Journal of Game Theory. 27 (3): 443–450. doi:10.1007/s001820050083. ISSN 0020-7276. S2CID 46730554.

[8] Megiddo, Nimrod (August 1978). "Computational Complexity of the Game Theory Approach to Cost Allocation for a Tree". Mathematics of Operations Research . 3 (3): 189–196. doi:10.1287/moor.3.3.189. ISSN 0364-765X.

[9] Galil, Zvi (1980-01-01). "Applications of efficient mergeable heaps for optimization problems on trees". Acta Informatica. 13 (1): 53–58. doi:10.1007/BF00288535. ISSN 0001-5903. S2CID 39221796.

[10] Könemann, Jochen; Pashkovich, Kanstantsin; Toth, Justin (2020-09-01). "Computing the nucleolus of weighted cooperative matching games in polynomial time". Mathematical Programming. 183 (1): 555–581. arXiv: 1803.03249 . doi:10.1007/s10107-020-01483-4. ISSN 1436-4646. S2CID 254135686.

[11] Hallefjord, Åsa; Helming, Reidun; Jørnsten, Kurt (1995-12-01). "Computing the nucleolus when the characteristic function is given implicitly: A constraint generation approach". International Journal of Game Theory. 24 (4): 357–372. doi:10.1007/BF01243038. ISSN 1432-1270. S2CID 122124918.

[12] Potters, Jos A. M.; Reijnierse, Johannes H.; Ansing, Michel (August 1996). "Computing the Nucleolus by Solving a Prolonged Simplex Algorithm". Mathematics of Operations Research . 21 (3): 757–768. doi:10.1287/moor.21.3.757. hdl: 2066/27990 . ISSN 0364-765X.

[13] Faigle, Ulrich; Kern, Walter; Kuipers, Jeroen (2001-09-01). "On the computation of the nucleolus of a cooperative game". International Journal of Game Theory. 30 (1): 79–98. doi:10.1007/s001820100065. ISSN 1432-1270. S2CID 17702694.

[14] Guajardo, Mario; Jörnsten, Kurt (2015-03-16). "Common mistakes in computing the nucleolus". European Journal of Operational Research. 241 (3): 931–935. doi:10.1016/j.ejor.2014.10.037. hdl: 11250/194983 . ISSN 0377-2217.

[1]

[note 1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]