The stable fixtures problem with payments

Arbeitspapier

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 is a subset of 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 x N implies R (real numbers) with p(i; j) + p(j; i) = w(ij) if ij set membership M and p(i; j) = p(j; i) = 0 if ij is not an element of M. The pair (M; p) is called a solution. A pair of players i; j with ij is an element of E nM 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 is congruent to 1 (Biró et al., 2012). We also characterize the set of stable solutions of a multiple partners matching game in two different ways and perform a study on the core of the corresponding cooperative game, where coalitions of any size may be formed. In particular we show that the standard relation between the existence of a stable solution and the non-emptiness of the core, which holds in the other models with payments, is no longer valid for our (most general) model.

Object Details

• ISBN: 978-615-5594-10-6
• Language: Englisch

References and Relationships

• Bibliographic citation: Series: IEHAS Discussion Papers ; No. MT-DP - 2015/45

Classification and Topics

• Classification: Wirtschaft ; Optimization Techniques; Programming Models; Dynamic Analysis ; Computational Techniques; Simulation Modeling ; Cooperative Games ; Bargaining Theory; Matching Theory
• Subject: stable solutions ; cooperative game ; core

Contributors, Places and Time

• Event: Geistige Schöpfung
• (who): Biró, Péter ; Kern, Walter ; Paulusma, Daniël ; Wojuteczky, Péter
• Event: Veröffentlichung
• (who): Hungarian Academy of Sciences, Institute of Economics
• (where): Budapest
• (when): 2015

Further information

• Handle: http://hdl.handle.net/10419/129863
• Last update: 10.03.2025, 11:45 AM CET