This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Kern, W. Articles by Paulusma, D. Search for Related Content

Matching Games: The Least Core and the Nucleolus

Faculty of Mathematical Sciences, University of Twente, P.O. Box 217, 7500 AE Enschede, The Netherlands
Faculty of Mathematical Sciences, University of Twente, P.O. Box 217, 7500 AE Enschede, The Netherlands
kern{at}math.utwente.nl
paulusma{at}math.utwente.nl

A matching game is a cooperative game defined by a graph GN, E The player set is N and the value of a coalition S N is defined as the size of a maximum matching in the subgraph induced by S. We show that the nucleolus of such games can be computed efficiently. The result is based on an alternative characterization of the least core, which may be of independent interest. The general case of weighted matching games remains unsolved.

Key Words: Cooperative games; nucleolus; computational complexity; matching
History: Received: September 21, 2000; revision received: December 4, 2001;revision received: June 4, 2002;

This article has been cited by other articles:

				W. Kern and D. Paulusma On the Core and f-Nucleolus of Flow Games Mathematics of Operations Research, November 1, 2009; 34(4): 981 - 991. [Abstract] [PDF]

				D. Nace and J. B. Orlin Lexicographically Minimum and Maximum Load Linear Programming Problems Operations Research, January 1, 2007; 55(1): 182 - 187. [Abstract] [PDF]