Population monotonic allocation schemes for vertex cover games

DOI10.1016/J.TCS.2020.07.023MaRDI QIDQ2006775zbMATH OpenOpenAlexFDO

Authors Han Xiao, Qizhi Fang, Du Ding-Zhu

Publication date 12 October 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2002.02824

zbMATH Keywords

cross-monotonic cost-sharing schemepopulation monotonic allocation schemestable matchingvertex cover

Mathematics Subject Classification ID

Applications of graph theory (05C90) Cooperative games (91A12) Games involving graphs (91A43) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Abstract: For vertex cover games (introduced by Deng et al., Math. Oper. Res., 24:751-766, 1999), we investigate population monotonic allocation schemes (introduced by Sprumont, Games Econ. Behav., 2: 378-394, 1990). We show that the existence of a population monotonic allocation scheme (PMAS for short) for vertex cover games can be determined efficiently and that a PMAS, if exists, can be constructed accordingly. We also show that integral PMAS-es for vertex cover games can be characterized with stable matchings and be enumerated by employing Gale-Shapley algorithm (introduced by Gale and Shapley, Amer. Math. Monthly, 69:9-15, 1962).

Recommendations

• Population monotonicity in matching games
• Population monotonic allocation schemes for cooperative games with transferable utility
• A combinatorial characterization for population monotonic allocations in convex independent set games
• A dual description of the class of games with a population monotonic allocation scheme
• Core stability of vertex cover games

Cites work

• Algorithmic Aspects of the Core of Combinatorial Optimization Games
• College Admissions and the Stability of Marriage
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Minimum cost spanning tree games and population monotonic allocation schemes.
• Monotonic stable solutions for minimum coloring games
• Population monotonic allocation schemes for cooperative games with transferable utility
• Population monotonic allocation schemes in bankruptcy games
• Submodularity of some classes of the combinatorial optimization games
• Totally balanced combinatorial optimization games

Cited in

(5)

• Population monotonicity in matching games
• Monotonic core allocation paths for assignment games
• A combinatorial characterization for population monotonic allocations in convex independent set games
• Population monotonic allocation schemes for the two-period economic lot-sizing games
• Assignment games with population monotonic allocation schemes

This page was built for publication: Population monotonic allocation schemes for vertex cover games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2006775)