We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

The stable fixtures problem with payments.

Biró, P. and Kern, W. and Paulusma, D. and Wojuteczky, P. (2016) 'The stable fixtures problem with payments.', in Graph-theoretic concepts in computer science : 41st international workshop, WG 2015, Garching, Germany, June 17-19, 2015 ; revised papers. Berlin: Springer, pp. 49-63. Lecture notes in computer science. (9224).


We generalize two well-known game-theoretic models by introducing multiple partners matching games, defined by a graph G=(N,E)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⊆EM⊆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×N→Rp:N×N→R with p(i,j)+p(j,i)=w(ij)p(i,j)+p(j,i)=w(ij) if ij∈Mij∈M and p(i,j)=p(j,i)=0p(i,j)=p(j,i)=0 if ij∉Mij∉M. The pair (M, p) is called a solution. A pair of players i, j with ij∈E∖Mij∈E∖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≡1b≡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.

Item Type:Book chapter
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:The final publication is available at Springer via
Date accepted:12 August 2015
Date deposited:21 August 2015
Date of first online publication:05 August 2016
Date first made open access:05 August 2017

Save or Share this output

Look up in GoogleScholar