Scholarlink

<p>The multiple partners matching game generalizes the matching game by allowing each player to have more than one possibly repeated partner up to their capacity. We study approximate core allocations for multiple partners matching games, since the core may be empty (Deng et al., Math Oper Res 24(3):751–766, 1999) and the core membership problem is generally intractable (Biró et al., Games Econ Behav 108:245–268, 2018). We provide an LP-based mechanism guaranteeing that no coalition is paid less than <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\frac{2}{3}\)</EquationSource> <EquationSource Format="MATHML"><math> <mfrac> <mn>2</mn> <mn>3</mn> </mfrac> </math></EquationSource> </InlineEquation> times the profit it makes on its own by seceding from the grand coalition. We also show that <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\frac{2}{3}\)</EquationSource> <EquationSource Format="MATHML"><math> <mfrac> <mn>2</mn> <mn>3</mn> </mfrac> </math></EquationSource> </InlineEquation> is the best possible factor relative to the LP-relaxation of the underlying problem. Our result generalizes the work of Vazirani (Games Econ Behav 132:478–486, 2022) from matching games to multiple partners matching games.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Approximate Core Allocations for Multiple Partners Matching Games

  • 期刊论文

  • 发表日期：

    2025年11月26日

查看全文
  • Han Xiao,
  • Yi-Han Li,
  • Tian-Hang Lu,
  • Qi-Zhi Fang

摘要

The multiple partners matching game generalizes the matching game by allowing each player to have more than one possibly repeated partner up to their capacity. We study approximate core allocations for multiple partners matching games, since the core may be empty (Deng et al., Math Oper Res 24(3):751–766, 1999) and the core membership problem is generally intractable (Biró et al., Games Econ Behav 108:245–268, 2018). We provide an LP-based mechanism guaranteeing that no coalition is paid less than \(\frac{2}{3}\) 2 3 times the profit it makes on its own by seceding from the grand coalition. We also show that \(\frac{2}{3}\) 2 3 is the best possible factor relative to the LP-relaxation of the underlying problem. Our result generalizes the work of Vazirani (Games Econ Behav 132:478–486, 2022) from matching games to multiple partners matching games.