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)
36 Downloads (Pure)

Abstract

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
PublisherSpringer
Pages40-63
Number of pages24
ISBN (Print)1611-3349
DOIs
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
Volume9224
ISSN (Print)1611-3349

Workshop

Workshop41st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2015
Abbreviated titleWG
CountryGermany
CityMunich
Period17/06/1519/06/15

    Fingerprint

Cite this

Biró, P., Kern, W., Paulusma, D., & Wojuteczky, P. (2016). The stable fixtures problem with payments. In E. W. Mayr (Ed.), Graph Theoretic Concepts in Computer Science, 41st International Workshop (pp. 40-63). (Lecture Notes in Computer Science; Vol. 9224). Berlin: Springer. https://doi.org/10.1007/978-3-662-53174-7_4