The Stable Fixtures Problem with Payments

Biró, P.; Kern, W.; Paulusma, D.; Wojuteczky, P.

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.

Citation

Biró, P., Kern, W., Paulusma, D., & Wojuteczky, P. (2018). The Stable Fixtures Problem with Payments. Games and Economic Behavior, 108, 245-268. https://doi.org/10.1016/j.geb.2017.02.002

• Journal Article Type: Article
• Acceptance Date: Feb 8, 2017
• Online Publication Date: Feb 10, 2017
• Publication Date: Mar 1, 2018
• Deposit Date: Feb 14, 2017
• Publicly Available Date: Aug 10, 2018
• Journal: Games and Economic Behavior
• Print ISSN: 0899-8256
• Electronic ISSN: 1090-2473
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 108
• Pages: 245-268
• DOI: https://doi.org/10.1016/j.geb.2017.02.002
• Public URL: https://durham-repository.worktribe.com/output/1394395