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

### 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 language English Graph Theoretic Concepts in Computer Science, 41st International Workshop Ernst W. Mayr Berlin Springer 40-63 24 1611-3349 https://doi.org/10.1007/978-3-662-53174-7_4 Published - 2016 41st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2015 - Munich, GermanyDuration: 17 Jun 2015 → 19 Jun 2015Conference number: 41

### Publication series

Name Lecture Notes in Computer Science Springer Verlag 9224 1611-3349

### Workshop

Workshop 41st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2015 WG Germany Munich 17/06/15 → 19/06/15

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