The stable fixtures problem with payments

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)
44 Downloads (Pure)


We generalize two well-known game-theoretic models by introducing multiple partners matching games, defined by a graph $G=(N,E)$, with an integer vertex capacity function $b$ and an edge weighting $w$. The set $N$ consists of a number of players that are to form a set $M\subseteq E$ of 2-player coalitions $ij$ with value $w(ij)$, such that each player $i$ is in at most $b(i)$ coalitions. A payoff is a mapping $p: N \times N \rightarrow \R$ with $p(i,j)+p(j,i)=w(ij)$ if $ij\in M$ and $p(i,j)=p(j,i)=0$ if $ij\notin M$. The pair $(M,p)$ is called a solution. A pair of players $i,j$ with $ij\in E\setminus M$ blocks a solution $(M,p)$ if $i, j$ can form, possibly only after withdrawing from one of their existing 2-player coalitions, a new 2-player coalition in which they are mutually better off. A solution is stable if it has no blocking pairs. We give a polynomial-time algorithm that either finds that no stable solution exists, or obtains a stable solution. Previously this result was only known for multiple partners assignment games, which correspond to the case where $G$ is bipartite (Sotomayor, 1992) and for the case where $b\equiv 1$ (Biro et al., 2012). We also characterize the set of stable solutions of a multiple partners matching game in two different ways and initiate a study on the core of the corresponding cooperative game, where coalitions of any size may be formed.
Original languageEnglish
Title of host publicationGraph Theoretic Concepts in Computer Science, 41st International Workshop
EditorsErnst W. Mayr
Place of PublicationBerlin
Number of pages24
ISBN (Print)1611-3349
Publication statusPublished - 2016
Event41st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2015 - Munich, Germany
Duration: 17 Jun 201519 Jun 2015
Conference number: 41

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
ISSN (Print)1611-3349


Workshop41st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2015
Abbreviated titleWG


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

Cite this