On the population monotonicity of independent set games

An independent set game is a cooperative game dealing with profit sharing in the maximum independent set problem. A population monotonic allocation scheme is a rule specifying how to share the profit of each coalition among its participants such that every participant is better off when the coalition expands. In this paper, we provide a necessary and sufficient characterization for independent set games admitting population monotonic allocation schemes. Moreover, our characterization can be verified efficiently. (c) 2022 Elsevier B.V. All rights reserved.

Automated summary

In this paper, we study profit sharing in independent set games and provide a necessary and sufficient characterization for population monotonic allocation schemes, which can be efficiently verified.