On solution concepts for matching games

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.