The Stable Fixtures Problem with Payments

Péter Biró, Walter Kern (), Daniel Paulusma () and Peter Wojuteczky ()
Additional contact information
Walter Kern: Faculty of Electrical Engineering - Mathematics and Computer Science - University of Twente
Daniel Paulusma: School of Engineering and Computing Sciences, Durham University, Science Laboratories
Peter Wojuteczky: Institute of Economics - Centre for Economic and Regional Studies - Hungarian Academy of Sciences

No 1545, CERS-IE WORKING PAPERS from Institute of Economics, Centre for Economic and Regional Studies

Abstract: We generalize two well-known game-theoretic models by introducing multiple partners matching games, de ned 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 E of 2-player coalitions ij with value w(ij), such that each player i is in at most b(i) coalitions. A payo is a mapping p : N N ! R with p(i; j) + p(j; i) = w(ij) if ij 2 M and p(i; j) = p(j; i) = 0 if ij =2 M. The pair (M; p) is called a solution. A pair of players i; j with ij 2 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 o . A solution is stable if it has no blocking pairs. We give a polynomial-time algorithm that either nds 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 1 (Biro et al., 2012). We also characterize the set of stable solutions of a multiple partners matching game in two di erent 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.

Keywords: stable solutions; cooperative game; core (search for similar items in EconPapers)
JEL-codes: C61 C63 C71 C78 (search for similar items in EconPapers)
Pages: 21 pages
Date: 2015-09
New Economics Papers: this item is included in nep-gth
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://econ.core.hu/file/download/mtdp/MTDP1545.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 500 Can't connect to econ.core.hu:80 (A connection attempt failed because the connected party did not properly respond after a period of time, or established connection failed because connected host has failed to respond.)

Related works:
Journal Article: The stable fixtures problem with payments (2018)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:has:discpr:1545

Access Statistics for this paper

More papers in CERS-IE WORKING PAPERS from Institute of Economics, Centre for Economic and Regional Studies Contact information at EDIRC.
Bibliographic data for series maintained by Nora Horvath ( this e-mail address is bad, please contact ).