Software:Nucleolus (game theory)

From HandWiki
Short description: Solution in cooperative games

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 [math]\displaystyle{ v : 2^N \to \mathbb{R} }[/math], which assigns a value to each possible coalition (each subset of players). A solution to a cooperative game is a vector [math]\displaystyle{ x \in \mathbb{R}^N }[/math], 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 [math]\displaystyle{ x }[/math] for a coalition [math]\displaystyle{ S \subseteq N }[/math] is the quantity [math]\displaystyle{ \mathrm{excess}(x,S) := \sum_{ i \in S } x_i - v(S) }[/math]. That is, the profit that players in coalition [math]\displaystyle{ S }[/math] obtain if they remain in the grand coalition [math]\displaystyle{ N }[/math] and do not deviate.[note 1]

Let [math]\displaystyle{ \theta(x) \in \mathbb{R}^{ 2^N } }[/math] be the vector of excesses of [math]\displaystyle{ x }[/math], arranged in non-decreasing order: [math]\displaystyle{ \theta_i(x) \leq \theta_j(x), \forall~ i \lt j }[/math]. For two payoff vectors [math]\displaystyle{ x, y }[/math], we say [math]\displaystyle{ \theta(x) }[/math] is lexicographically smaller than [math]\displaystyle{ \theta(y) }[/math] if for some index [math]\displaystyle{ k }[/math], we have [math]\displaystyle{ \theta_i(x) = \theta_i(y), \forall~ i \lt k }[/math] and [math]\displaystyle{ \theta_k(x) \lt \theta_k(y) }[/math]. The nucleolus of [math]\displaystyle{ v }[/math] 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: [math]\displaystyle{ \begin{align} \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{align} }[/math]where k = 2N = 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 2n 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(2n). 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.

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(n2) 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

  1. ↑ 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.

See also

  • Contested garment rule

References

  1. ↑ 1.0 1.1 Schmeidler, D. (1969), "The nucleolus of a characteristic function game", SIAM Journal on Applied Mathematics 17 (6): 1163–1170, doi:10.1137/0117107. 
  2. ↑ 2.0 2.1 Driessen, Theo (1988), Cooperative Games, Solutions and Applications, Kluwer Academic Publishers, ISBN 9789401577878, https://books.google.com/books?id=1yDtCAAAQBAJ&q=%22cooperative+games%22 
  3. ↑ 3.0 3.1 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. https://dl.acm.org/doi/abs/10.5555/1619645.1619761. 
  4. ↑ Elkind, Edith; Pasechnik, Dmitrii (2009-01-04). "Computing the nucleolus of weighted voting games" (in en). 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. ISBN 978-0-89871-680-1. https://epubs.siam.org/doi/10.1137/1.9781611973068.37. 
  5. ↑ Bird, C. G. (1976). "On cost allocation for a spanning tree: A game theoretic approach" (in en). Networks 6 (4): 335–350. doi:10.1002/net.3230060404. https://onlinelibrary.wiley.com/doi/10.1002/net.3230060404. 
  6. ↑ 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. https://doi.org/10.1007/s001820050083. 
  7. ↑ Megiddo, Nimrod (August 1978). "Computational Complexity of the Game Theory Approach to Cost Allocation for a Tree" (in en). Mathematics of Operations Research 3 (3): 189–196. doi:10.1287/moor.3.3.189. ISSN 0364-765X. https://pubsonline.informs.org/doi/10.1287/moor.3.3.189. 
  8. ↑ 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. https://doi.org/10.1007/BF00288535. 
  9. ↑ Könemann, Jochen; Pashkovich, Kanstantsin; Toth, Justin (2020-09-01). "Computing the nucleolus of weighted cooperative matching games in polynomial time" (in en). Mathematical Programming 183 (1): 555–581. doi:10.1007/s10107-020-01483-4. ISSN 1436-4646. https://doi.org/10.1007/s10107-020-01483-4. 
  10. ↑ Hallefjord, Åsa; Helming, Reidun; Jørnsten, Kurt (1995-12-01). "Computing the nucleolus when the characteristic function is given implicitly: A constraint generation approach" (in en). International Journal of Game Theory 24 (4): 357–372. doi:10.1007/BF01243038. ISSN 1432-1270. https://doi.org/10.1007/BF01243038. 
  11. ↑ Potters, Jos A. M.; Reijnierse, Johannes H.; Ansing, Michel (August 1996). "Computing the Nucleolus by Solving a Prolonged Simplex Algorithm" (in en). Mathematics of Operations Research 21 (3): 757–768. doi:10.1287/moor.21.3.757. ISSN 0364-765X. https://pubsonline.informs.org/doi/10.1287/moor.21.3.757. 
  12. ↑ Faigle, Ulrich; Kern, Walter; Kuipers, Jeroen (2001-09-01). "On the computation of the nucleolus of a cooperative game" (in en). International Journal of Game Theory 30 (1): 79–98. doi:10.1007/s001820100065. ISSN 1432-1270. https://doi.org/10.1007/s001820100065. 
  13. ↑ 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. ISSN 0377-2217. https://www.sciencedirect.com/science/article/pii/S0377221714008595. 




Retrieved from "https://handwiki.org/wiki/index.php?title=Software:Nucleolus_(game_theory)&oldid=3467004"