The stable fixtures problem with payments

Biró, P.; Kern, W.; Paulusma, D.; Wojuteczky, P.

Abstract

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.

Citation

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, WG 2015, Garching, Germany, June 17-19, 2015 ; revised papers (49-63). https://doi.org/10.1007/978-3-662-53174-7_4

• Conference Name: 41 International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015)
• Conference Location: Munich, Germany
• Start Date: Jun 17, 2015
• End Date: Jun 19, 2015
• Acceptance Date: Aug 12, 2015
• Online Publication Date: Aug 5, 2016
• Publication Date: Aug 5, 2016
• Deposit Date: Aug 12, 2015
• Publicly Available Date: Aug 5, 2017
• Pages: 49-63
• Series Title: Lecture notes in computer science
• Series Number: 9224
• Series ISSN: 0302-9743,1611-3349
• Book Title: Graph-theoretic concepts in computer science : 41st international workshop, WG 2015, Garching, Germany, June 17-19, 2015 ; revised papers.
• ISBN: 9783662531730
• DOI: https://doi.org/10.1007/978-3-662-53174-7_4
• Public URL: https://durham-repository.worktribe.com/output/1152736
• Additional Information: Conference dates: 17-19 June 2015