On solution concepts for matching games

Peter Biro, Walter Kern, Daniël Paulusma

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)


A matching game is a cooperative game $(N,v)$ defined on a graph $G = (N,E)$ with an edge weighting $\omega : E \to {\Bbb R}_+$ . The player set is $N$ and the value of a coalition $S \subseteq  N$ is defined as the maximum weight of a matching in the subgraph induced by $S$. First we present an $O(nm + n {}^2\log n)$ algorithm that tests if the core of a matching game defined on a weighted graph with $n$ vertices and $m$ edges is nonempty and that computes a core allocation if the core is nonempty. This improves previous work based on the ellipsoid method. Second we show that the nucleolus of an $n$-player matching game with nonempty core can be computed in $O(n^4)$ time. This generalizes the corresponding result of Solymosi and Raghavan for assignment games. Third we show that determining an imputation with minimum number of blocking pairs is an $NP$-hard problem, even for matching games with unit edge weights.
Original languageUndefined
Title of host publicationTheory and Applications of Models of Computation, Proceedings 7th Annual Conference, TAMC 2010
EditorsJ. Kratochvil, A. Li, J. Fiala, P. Kolman
Place of PublicationBerlin
Number of pages11
ISBN (Print)978-3-642-13561-3
Publication statusPublished - Jun 2010
Event7th Annual Conference on Theory and Applications of Models of Computation, TAMC 2010 - Prague, Czech Republic
Duration: 7 Jun 201011 Jun 2010

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference7th Annual Conference on Theory and Applications of Models of Computation, TAMC 2010
Other7-11 June, 2010


  • EWI-18180
  • IR-72459
  • METIS-270926

Cite this