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).
Restricted to UT campus only : Request a copy
|Abstract:||A matching game is a cooperative game defined on a graph with an edge weighting . The player set is and the value of a coalition is defined as the maximum weight of a matching in the subgraph induced by . First we present an algorithm that tests if the core of a matching game defined on a weighted graph with vertices and 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 -player matching game with nonempty core can be computed in 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 -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)
|Link to this item:||http://purl.utwente.nl/publications/72459|
|Export this item as:||BibTeX|
Daily downloads in the past month
Monthly downloads in the past 12 months
Repository Staff Only: item control page