Computing solutions for matching games

Biró, Péter and Kern, Walter and Paulusma, Daniël (2012) Computing solutions for matching games. International journal of game theory, 41 (1). pp. 75-90. ISSN 0020-7276

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

Abstract:	A matching game is a cooperative game (N, v) defined on a graph G = (N, E) with an edge weighting $w: E \rightarrow R_+$ The player set is N and the value of a coalition $S \subseteq NSN$ 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 member if the core is nonempty. This algorithm improves previous work based on the ellipsoid method and can also be used to compute stable solutions for instances of the stable roommates problem with payments. Second we show that the nucleolus of an n-player matching game with a nonempty core can be computed in $O(n^4)$ time. This generalizes the corresponding result of Solymosi and Raghavan for assignment games. Third we prove that is NP-hard to determine an imputation with minimum number of blocking pairs, even for matching games with unit edge weights, whereas the problem of determining an imputation with minimum total blocking value is shown to be polynomial-time solvable for general matching games.
Item Type:	Article
Copyright:	© 2012 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/79991
Official URL:	http://dx.doi.org/10.1007/s00182-011-0273-y
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 289776