On the Population Monotonicity of Independent Set Games

Han Xiao, Libing Wang, Donglei Du, Dachuan XuarXiv 2022 · DOI · arXiv

Abstract

This paper provides a complete structural characterization of graphs whose independent set games admit a Population Monotonic Allocation Scheme (PMAS). By classifying edges based on their proximity to pendant vertices, the authors establish necessary and sufficient conditions for dynamic stability in profit sharing. These conditions ensure that as the group of players grows, individual payoffs remain stable or improve. Furthermore, the authors demonstrate that these conditions can be verified in polynomial time using standard graph algorithms.

Introduction

In cooperative game theory, the "core" is a fundamental concept representing stable ways to distribute profits such that no subgroup has an incentive to break away. However, the core is inherently static; it does not guarantee that as a coalition expands, the individual payoffs for existing members will be preserved or enhanced. To address this limitation, researchers utilize Population Monotonic Allocation Schemes (PMAS). A PMAS ensures that every participant is better off (or at least not worse off) when the coalition grows, providing a robust framework for dynamic cooperation.

This research focuses on a specific class of problems known as Independent Set Games. In these games, players are represented as edges in a graph. The value of a coalition is defined by the size of the maximum independent set—a set of vertices where no two are connected—within the subgraph formed by those edges. This model is particularly relevant for project management and resource allocation, where participants (edges) connect various tasks (vertices), and the objective is to maximize the number of independent tasks completed.

Structural Methodology

The authors employ structural graph theory and combinatorial optimization to identify the specific graph architectures that support PMAS. A central element of their analysis is the role of pendant vertices (vertices with a degree of one). They categorize edges into three distinct types based on their relationship to these pendant vertices:

  1. Pendant Edges: Edges directly incident to a pendant vertex.
  2. Type I Non-Pendant Edges: Edges that are not incident to any pendant edges.
  3. Type II Non-Pendant Edges: Edges that are incident to at least one pendant edge.

By examining how these edge types contribute to the maximum independent set of a subgraph, the authors derive the necessary conditions for profit-sharing stability. They propose a specific allocation rule—a mathematical formula for distributing the value of the independent set—and prove that it satisfies PMAS requirements if and only if the underlying graph meets specific structural criteria.

The Characterization of Population Monotonicity

The paper’s primary contribution is the formalization of the structural requirements for an independent set game to be population monotonic. Two critical rules emerged from their analysis:

The Distance-2 Rule

The authors discovered that for a game to maintain stability as the population grows, every vertex in the graph must be within a distance of at most two from a pendant vertex. If a vertex is too "distant" from these essential pendant edges, the stability of the profit-sharing scheme collapses when new edges are added to the coalition.

Isolation of Type I Edges

Even if the distance rule is satisfied, the game may still fail to be population monotonic if certain edges are positioned incorrectly. Specifically, the authors prove that Type I non-pendant edges (those further from pendant edges) must not be incident to one another. In other words, they cannot share a vertex. This isolation ensures that the addition of new players does not disrupt the existing allocation logic.

Main Results and Algorithmic Efficiency

The culmination of this research is Theorem 9, which states that an independent set game is population monotonic if and only if the graph satisfies both the Distance-2 Rule and the isolation of Type I edges.

Beyond the theoretical characterization, the authors address the practical implementation of these findings. They demonstrate that determining whether a graph supports a PMAS is computationally efficient. Because the conditions rely on simple distance and adjacency metrics, a standard Breadth-First Search (BFS) algorithm can verify a graph's eligibility in polynomial time. This makes the result highly applicable for analyzing large-scale networks and complex cooperative structures.

Furthermore, the paper broadens the understanding of the relationship between convexity and population monotonicity. While it was previously known that convex games are population monotonic, this work identifies a significantly larger and more flexible class of graphs that satisfy population monotonicity without necessarily being convex.

Conclusion and Future Directions

While this research provides a definitive characterization for independent set games, the authors acknowledge that these findings are specific to this model. Many real-world cooperative scenarios, such as flow games or matching games, operate under different combinatorial rules.

Future research may involve characterizing PMAS for other types of combinatorial optimization games or investigating alternative stability concepts. Potential areas of interest include "link monotonic allocation schemes" or "monotonic core allocation paths," which explore different dimensions of how payoffs evolve over time in dynamic networks.

Summary updated

Abstract

An independent set game is a cooperative game defined on graphs and dealing with profit-sharing in maximum independent set problems. 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 population monotonic allocation schemes in independent set games. Moreover, our characterization can be verified efficiently.
BibTeX
@misc{xiao2022population,
  author = {Han Xiao and Libing Wang and Donglei Du and Dachuan Xu},
  title = {{On the Population Monotonicity of Independent Set Games}},
  year = {2022},
  eprint = {2203.17041},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2203.17041},
}
Figure