2021/05/03 by Han Xiao, Xiao, Han, Qizhi Fang +1
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #05C57 #91A12 #91A43 #91A46 #Auction Theory and Applications #Complexity and Algorithms in Graphs #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Voting Systems #cs.GT #msc:05C57 #msc:91A12 #msc:91A43 #msc:91A46
paper · pdf · doi:10.48550/arxiv.2105.00621
arxiv created 2021/05/03 · openalex publication_date 2021/05/03 · arxiv updated 2021/05/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.