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.
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.
|Full text:||(AM) Accepted Manuscript|
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF (466Kb)
|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
|Look up in GoogleScholar|