On the computation of the nucleolus of a cooperative game

Jeroen Kuipers (), Ulrich Faigle () and Walter Kern ()
Additional contact information
Jeroen Kuipers: Department of Mathematics, Maastricht University, P.O.Box 616, 6200 MD Maastricht, The Netherlands. E-mail address: kuipers@math.unimaas.nl
Walter Kern: Department of Applied Mathematics, University of Twente, P.O.Box 217, 7500 AE Enschede, The Netherlands. E-mail address: kern@math.utwente.nl

International Journal of Game Theory, 2001, vol. 30, issue 1, 79-98

Abstract: 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.

Date: 2001-10-10
Note: Received February 2000/Final version April 2001
References: Add references at CitEc
Citations: View citations in EconPapers (20)

Downloads: (external link)
http://link.springer.de/link/service/journals/00182/papers/1030001/10300079.pdf (application/pdf)
Access to the full text of the articles in this series is restricted

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jogath:v:30:y:2001:i:1:p:79-98

Ordering information: This journal article can be ordered from
http://www.springer. ... eory/journal/182/PS2

Access Statistics for this article

International Journal of Game Theory is currently edited by Shmuel Zamir, Vijay Krishna and Bernhard von Stengel

More articles in International Journal of Game Theory from Springer, Game Theory Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().