The stable fixtures problem with payments

Péter Biró* (Corresponding Author), Walter Kern (Corresponding Author), Daniël Paulusma (Corresponding Author), Péter Wojuteczky (Corresponding Author)

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

6 Citations (Scopus)
36 Downloads (Pure)

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

Original languageEnglish
Pages (from-to)245-268
Number of pages24
JournalGames and economic behavior
Volume108
DOIs
Publication statusPublished - 1 Mar 2018

Keywords

  • Core
  • Stable solutions
  • Cooperative game

Fingerprint Dive into the research topics of 'The stable fixtures problem with payments'. Together they form a unique fingerprint.

Cite this