Population monotonicity in matching games
From MaRDI portal
Publication:2136163
DOI10.1007/S10878-021-00804-3zbMATH Open1492.91035arXiv2105.00621OpenAlexW3201170906MaRDI QIDQ2136163FDOQ2136163
Authors: Han Xiao, Qizhi Fang 
Publication date: 10 May 2022
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Abstract: A matching game is a cooperative profit game defined on an edge-weighted graph, where the players are the vertices and the profit of a coalition is the maximum weight of matchings in the subgraph induced by the coalition. A population monotonic allocation scheme is a collection of rules defining how to share the profit among players in each coalition such that every player is better off when the coalition expands. In this paper, we study matching games and provide a necessary and sufficient characterization for the existence of population monotonic allocation schemes. Our characterization also implies that whether a matching game admits population monotonic allocation schemes can be determined efficiently.
Full work available at URL: https://arxiv.org/abs/2105.00621
Recommendations
- Population monotonic allocation schemes for vertex cover 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
- Matching Games: The Least Core and the Nucleolus
Cooperative games (91A12) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)
Cites Work
- An algorithm for finding the nucleolus of assignment games
- Totally balanced combinatorial optimization games
- The assignment game. I: The core
- Population monotonic allocation schemes for cooperative games with transferable utility
- Incremental cost sharing: Characterization by coalition strategy-proofness
- Strategyproof sharing of submodular costs: budget balance versus efficiency
- Characterization of the extreme core allocations of the assignment game.
- Algorithmic Aspects of the Core of Combinatorial Optimization Games
- Generalized Ramsey theory for graphs, X: Double stars
- Assignment games with stable core
- Computing solutions for matching games
- Limitations of cross-monotonic cost-sharing schemes
- Matching Games: The Least Core and the Nucleolus
- An axiomatization of the nucleolus of assignment markets
- Axiomatization of the core of assignment games
- The nucleon of cooperative games and an algorithm for matching games
- Stable outcomes of the roommate game with transferable utility
- Computing the nucleolus of weighted cooperative matching games in polynomial time
- Consistency in one-sided assignment problems
- The general graph matching game: approximate core
Cited In (10)
- Title not available (Why is that?)
- The mask game with multiple populations
- Population monotonic solutions on convex games
- Regular population monotonic allocation schemes
- Monotone Matching in Perfect and Imperfect Worlds
- Population monotonic path schemes for simple games
- A dual description of the class of games with a population monotonic allocation scheme
- Population monotonic allocation schemes on externality games
- Assignment games with population monotonic allocation schemes
- On the population monotonicity of independent set games
This page was built for publication: Population monotonicity in matching games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2136163)
