The stable fixtures problem with payments

Péter Biró, Walter Kern, Daniël Paulusma and Péter Wojuteczky

Games and Economic Behavior, 2018, vol. 108, issue C, 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.

Keywords: Stable solutions; Cooperative game; Core (search for similar items in EconPapers)
JEL-codes: C61 C71 C78 (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S089982561730026X
Full text for ScienceDirect subscribers only

Related works:
Working Paper: The Stable Fixtures Problem with Payments (2015)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:gamebe:v:108:y:2018:i:c:p:245-268

DOI: 10.1016/j.geb.2017.02.002

Access Statistics for this article

Games and Economic Behavior is currently edited by E. Kalai

More articles in Games and Economic Behavior from Elsevier
Bibliographic data for series maintained by Catherine Liu ().