Skip to main content

Research Repository

Advanced Search

On solution concepts for matching games

Biro, P.; Kern, W.; Paulusma, D.

Authors

P. Biro

W. Kern



Contributors

Jan Kratochvíl
Editor

Angsheng Li
Editor

Jirí Fiala
Editor

Petr Kolman
Editor

Abstract

A matching game is a cooperative game (N,v) defined on a graph G = (N,E) with an edge weighting . The player set is N and the value of a coalition S ⊆ N is defined as the maximum weight of a matching in the subgraph induced by S. First we present an O(nm + n 2logn) 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.

Citation

Biro, P., Kern, W., & Paulusma, D. (2010). On solution concepts for matching games. In J. Kratochvíl, A. Li, J. Fiala, & P. Kolman (Eds.), Theory and applications of mdels of computation, 7th Annual Conference, TAMC 2010, 7-11 June 2010, Prague, Czech Republic ; proceedings (211-221). https://doi.org/10.1007/978-3-642-13562-0_12

Conference Name 7th Annual Conference on Theory and Applications of Models of Computation
Conference Location Prague, Czech Republic
Publication Date Jan 1, 2010
Deposit Date Oct 6, 2010
Publisher Springer Verlag
Pages 211-221
Series Title Lecture notes in computer science
Series Number 6108
Book Title Theory and applications of mdels of computation, 7th Annual Conference, TAMC 2010, 7-11 June 2010, Prague, Czech Republic ; proceedings.
DOI https://doi.org/10.1007/978-3-642-13562-0_12
Public URL https://durham-repository.worktribe.com/output/1158632


You might also like



Downloadable Citations