The multiple partners matching game is a cooperative profit-sharing game, which generalizes the classic matching game by allowing each player to have more than one partner. The core is one of the most important concepts in cooperative game theory, which consists all possible ways of allocating the total profit of the game among individual players such that the grand coalition remains intact. For the multiple partners matching game, the core may be empty in general [Deng et al., Algorithmic aspects of the core of combinatorial optimization games, Math. Oper. Res., 1999.]; even when the core is non-empty, the core membership problem is intractable in general [Biro et al., The stable fixtures problem with payments, Games Econ. Behav., 2018]. Thus we study approximate core allocations for the multiple partners matching game, and provide an LP-based mechanism guaranteeing that no coalition is paid less than $2/3$ times the profit it makes on its own. Moreover, we show that the factor $2/3$ is best possible in general, but can be improved depending on how severely constrained the players are. Our result generalizes the recent work of Vazirani [Vazirani, The general graph matching game: approximate core, arXiv, 2021] from matching games to multiple partners matching games.
翻译:多伙伴匹配游戏是一种合作分享利润的游戏,它通过允许每个玩家拥有一个以上的伙伴来概括经典匹配游戏。核心是合作游戏理论中最重要的概念之一,它包括将游戏的全部利润分配给各个玩家的所有可能方式,这样大联盟仍然完好无损。对于多个伙伴匹配游戏来说,核心一般是空的[Deng et al., 组合优化游戏核心的算法方面, Math. Oper. Res. 1999];即使核心不是空的,核心会籍问题在一般情况下也是难以解决的[Biro et al., 支付稳定固定装置问题,游戏Econ. Behav., 2018]。因此我们研究多个伙伴匹配游戏的大致核心分配,并提供基于LP的机制,保证没有联盟的薪酬比它本身的利润低2/3美元。此外,我们显示,总体的系数为2/3美元,但取决于玩家受到多大的制约,核心会籍问题是可以改进的。我们的结果是,Vaziran Global compeal compeal:Vaz common commonal commonX1, common gamegame game game game.