The stable fixtures problem with payments

• 成果类型: Article
• 署名作者: Biro, Peter; Kern, Walter; Paulusma, Daniel; Wojuteczky, Peter
• 署名单位: HUN-REN; HUN-REN Centre for Economic & Regional Studies; Institute of Economics - HAS; Hungarian Academy of Sciences; Corvinus University Budapest; University of Twente; Durham University
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2017.02.002
• 发表日期: 2018
• 页码: 245-268
• 关键词: Stable solutions; Cooperative game; core

摘要

We consider multiple partners matching games (G, b, w), where G is a graph with an integer vertex capacity function b and an edge weighting w. If G is bipartite, these games are called multiple partners assignment games. We give a polynomial-time algorithm that either finds that a given multiple partners matching game has no stable solution, or obtains a stable solution. We characterize the set of stable solutions of a multiple partners matching game in two different ways and show how this leads to simple proofs for a number of results of Sotomayor (1992, 1999, 2007) for multiple partners assignment games and to generalizations of some of these results to multiple partners matching games. We also perform a study on the core of multiple partners matching games. We prove that the problem of deciding if an allocation belongs to the core jumps from being polynomial-time solvable for b <= 2 to NP-complete for b equivalent to 3. (C) 2017 Elsevier Inc. All rights reserved.