Skip to main content

Research Repository

Advanced Search

The stable fixtures problem with payments

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

The stable fixtures problem with payments Thumbnail


Authors

P. Biró

W. Kern

P. Wojuteczky



Contributors

Ernst W. Mayr
Editor

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 Mar 28, 2024
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

Files





You might also like



Downloadable Citations