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 (pp. pp. 117-127).

[img] PDF
Restricted to UT campus only
: Request a copy
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
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/72459
Official URL:https://doi.org/10.1007/978-3-642-13562-0_12
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page