On solution concepts for matching games

Biro, Peter and Kern, Walter and Paulusma, Daniël (2010) On solution concepts for matching games. In: 7th Annual Conference on Theory and Applications of Models of Computation, TAMC 2010, 7-11 June, 2010, Prague, Czech Republic.

PDF
Restricted to UT campus only: Request a copy
215Kb

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.
Item Type:	Conference or Workshop Item
Copyright:	© 2010 Springer
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/72459
Official URL:	http://dx.doi.org/10.1007/978-3-642-13562-0_12
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page