Biró, P. and Kern, W. and Paulusma, D. and Wojuteczky, P. (2018) 'The stable fixtures problem with payments.', Games and economic behavior., 108 . pp. 245-268.
Abstract
We consider multiple partners matching games (G,b,w), where G is a graph with an integer vertex capacity function b and an edge weighting w. If G is bipartite, these games are called multiple partners assignment games. We give a polynomial-time algorithm that either finds that a given multiple partners matching game has no stable solution, or obtains a stable solution. We characterize the set of stable solutions of a multiple partners matching game in two different ways and show how this leads to simple proofs for a number of results of Sotomayor (1992, 1999, 2007) for multiple partners assignment games and to generalizations of some of these results to multiple partners matching games. We also perform a study on the core of multiple partners matching games. We prove that the problem of deciding if an allocation belongs to the core jumps from being polynomial-time solvable for b≤2 to NP-complete for b≡3.
Item Type: | Article |
---|---|
Full text: | (AM) Accepted Manuscript Available under License - Creative Commons Attribution Non-commercial No Derivatives. Download PDF (466Kb) |
Status: | Peer-reviewed |
Publisher Web site: | https://doi.org/10.1016/j.geb.2017.02.002 |
Publisher statement: | © 2017 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ |
Date accepted: | 08 February 2017 |
Date deposited: | 15 February 2017 |
Date of first online publication: | 10 February 2017 |
Date first made open access: | 10 August 2018 |
Save or Share this output
Export: | |
Look up in GoogleScholar |