Abstract
A matching game is a cooperative game (N, v) defined on a graph G = (N, E) with an edge weighting \({w: E\to {\mathbb 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 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Abraham DJ, Biró P, Manlove DF (2006) “Almost stable” matchings in the roommates problem. In: Proceedings of WAOA 2005: the 3rd workshop on approximation and online algorithms. Lecture Notes in Computer Science, vol 3879. pp 1–14
Balinski ML (1965) Integer programming: methods, uses, computation. Manag Sci 12: 253–313
Bilbao JM (2000) Cooperative games on combinatorial structures. Kluwer Academic, Norwell
Biró P (2007) The stable matching problem and its generalizations: an algorithmic and game theoretical approach. PhD Thesis, Budapest University of Technology and Economics, Budapest
Deng X, Ibaraki T, Nagamochi H (1999) Algorithmic aspects of the core of combinatorial optimization games. Math Oper Res 24: 751–766
Egerváry J (1931) Matrixok kombinatorius tulajdonságairól. Matematikai és Fizikai Lapok 38: 16–28
Eriksson K, Karlander J (2001) Stable outcomes of the roommate game with transferable utility. Int J Game Theory 29: 555–569
Faigle U, Kern W, Fekete S, Hochstättler W (1998) The nucleon of cooperative games and an algorithm for matching games. Math Program 83: 195–211
Faigle U, Kern W, Kuipers J (2001) On the computation of the nucleolus of a cooperative game. Int J Game Theory 30: 79–98
Gabow HN (1990) Data structures for weighted matching and nearest common ancestors with linking. In: Proceedings of SODA 1990: the 1st annual ACM-SIAM symposium on discrete algorithms, pp 434–443
Garey MR, Johnson DS, Stockmeyer L (1976) Some simplified NP-complete graph problems. Theor Comput Sci 1: 237–267
Kern W, Paulusma D (2003) Matching games: the least core and the nucleolus. Math Oper Res 28: 294–308
Khachiyan LG (1979) A polynomial algorithm in linear programming. Sov Math Dokl 20: 191–194
Klaus B, Nichifor A (2010) Consistency for one-sided assignment problems. Soc Choice Welf 35: 415–433
Maschler M, Peleg B, Shapley LS (1979) Geometric properties of the kernel, nucleolus, nd related solution concepts. Math Oper Res 4: 303–338
Matsui T (1998) A note on the nucleolus of assignment games, In: 5th International conference on nonlinear analysis and convex analysis. World Scientific, Singapore, pp 253–260
Micali S, Vazirani VV (1980) An \({O(\sqrt{|V|}\,\cdot\,|E|)}\) algorithm for finding maximum matching in general graphs. In: Proceedings of FOCS 1980: the 21st annual symposium on foundations of computer science, pp 17–27
Nemhauser GL, Trotter LE (1975) Vertex packings: structural properties and algorithms. Math Program 8: 232–248
Owen G (1995) Game theory. Academic Press, San Diego
Paulusma D (2001) Complexity aspects of cooperative games. PhD Thesis, University of Twente, Enschede
Schmeidler D (1969) The nucleolus of a characteristic function game. SIAM J Appl Math 17: 1163–1170
Schrijver A (2003) Combinatorial optimization. Polyhedra and efficiency, vol A, algorithms and combinatorics, vol 24. Springer-Verlag, Berlin
Shapley LS, Shubik M (1971) The assignment game I: the core. Int J Game Theory 1: 111–130
Solymosi T, Raghavan TES (1994) An algorithm for finding the nucleolus of assignment games. Int J Game Theory 23: 119–143
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version of this paper has been presented at TAMC 2010.
Rights and permissions
About this article
Cite this article
Biró, P., Kern, W. & Paulusma, D. Computing solutions for matching games. Int J Game Theory 41, 75–90 (2012). https://doi.org/10.1007/s00182-011-0273-y
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00182-011-0273-y