On the computation of the nucleolus of a cooperative game
We consider classes of cooperative games. We show that we can efficiently compute an allocation in the intersection of the prekernel and the least core of the game if we can efficiently compute the minimum excess for any given allocation. In the case where the prekernel of the game contains exactly one core vector, our algorithm computes the nucleolus of the game. This generalizes both a recent result by Kuipers on the computation of the nucleolus for convex games and a classical result by Megiddo on the nucleolus of standard tree games to classes of more general minimum cost spanning tree games. Our algorithm is based on the ellipsoid method and Maschler's scheme for approximating the prekernel. <!--ID=""Acknowledgement. We thank the anonymous referees for their careful reading of the manuscript, which helped to improve the presentation.--> <!--ID=""1991 Mathematics Subject Classification. 90C27, 90D12.--> <!--ID=""Key words and phrases. Core, nucleolus, prekernel, kernel, computational complexity, convex games, MCST-games, ellipsoid method.-->
Year of publication: |
2001-10-10
|
---|---|
Authors: | Kuipers, Jeroen ; Faigle, Ulrich ; Kern, Walter |
Published in: |
International Journal of Game Theory. - Springer. - Vol. 30.2001, 1, p. 79-98
|
Publisher: |
Springer |
Saved in:
freely available
Saved in favorites
Similar items by person
-
On the computation of the nucleolus of a cooperative game
Faigle, Ulrich, (2001)
-
Computing the nucleolus of min-cost spanning tree games is NP-hard
Faigle, Ulrich, (1998)
-
Computing an Element in the Lexicographic Kernel of a Game
Faigle, Ulrich, (2006)
- More ...