On solution concepts for matching games


Share/Save/Bookmark

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.

[img]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:
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

 

Repository Staff Only: item control page