@inproceedings{8210928b450a4da899f760146e8c0cf3,

title = "On solution concepts for matching games",

abstract = "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.",

keywords = "EWI-18180, IR-72459, METIS-270926",

author = "Peter Biro and Walter Kern and Dani{\"e}l Paulusma",

note = "10.1007/978-3-642-13562-0_12 ; null ; Conference date: 07-06-2010 Through 11-06-2010",

year = "2010",

month = jun,

doi = "10.1007/978-3-642-13562-0_12",

language = "Undefined",

isbn = "978-3-642-13561-3",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "117--127",

editor = "J. Kratochvil and A. Li and J. Fiala and P. Kolman",

booktitle = "Theory and Applications of Models of Computation, Proceedings 7th Annual Conference, TAMC 2010",

}