Skip to main content

Research Repository

Advanced Search

The Stable Fixtures Problem with Payments

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

The Stable Fixtures Problem with Payments Thumbnail


Authors

P. Biró

W. Kern

P. Wojuteczky



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
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

Files





You might also like



Downloadable Citations