Stable and Envy-free Partitions in Hedonic Games

Nathanaël Barrot, Makoto YokooIJCAI 2019 · DOI

TL;DR

This paper investigates fairness and stability in hedonic games, where agents form coalitions based on their preferences. The authors show that achieving both individual stability and envy-freeness is surprisingly difficult, even in simplified game settings, and often leads to NP-complete decision problems. They also introduce an algorithm that guarantees Pareto optimal, individually stable, and envy-free partitions in a specific class of games.

What Problem Does This Paper Address?

In many real-world scenarios, individuals form groups (coalitions) to achieve common goals. In "hedonic games," agents have preferences over the coalitions they join, but not necessarily over the coalitions others join. A key question is how these agents will form stable partitions (sets of disjoint coalitions covering all agents). Beyond mere stability, fairness is crucial. Envy-freeness is a fairness notion where no agent prefers another agent's coalition to their own. While the grand coalition (everyone together) is always envy-free, it's often not the most relevant outcome. This paper explores the challenging intersection of stability and envy-freeness in hedonic games, specifically asking when partitions exist that are both stable (no agent has an incentive to unilaterally change their coalition) and envy-free. They focus on specific types of hedonic games: additively separable (where utility is the sum of values for coalition members), and top/bottom responsive games, which model more realistic preference structures.

Methods

The paper analyzes the existence and complexity of stable and envy-free partitions in different classes of hedonic games.

  • Theoretical Analysis: The core of the work involves proving theoretical results about the existence of partitions satisfying various combinations of stability and fairness criteria. This includes demonstrating NP-completeness for decision problems and proving the guaranteed existence of certain types of partitions.
  • Algorithm Design: The authors propose the "Extended Top Covering Algorithm" for top-responsive hedonic games. This algorithm is designed to construct a partition that is simultaneously Pareto optimal, individually stable, and envy-free.
  • Counterexamples and Reductions: To prove NP-completeness, the authors construct specific counterexamples of hedonic games where desired partitions do not exist. They also use reductions from known NP-complete problems (like EXACTCOVERBY3SETS) to show that deciding the existence of such partitions is computationally hard.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and algorithmic design, using constructed examples rather than real-world datasets.

Key Insights and Ideas

  • Envy-freeness is Tricky: Even in simplified settings like symmetric additively separable hedonic games, finding a partition that is both individually stable and envy-free is not guaranteed and deciding its existence is NP-complete. This highlights that fairness considerations significantly complicate coalition formation.
  • Top Responsiveness is Powerful: For games with "top responsiveness" (a condition on how preferences over subsets influence preferences over larger coalitions), the authors provide a constructive algorithm (Extended Top Covering) that guarantees the existence of a partition that is Pareto optimal, individually stable, and envy-free. This is a significant positive result.
  • Bottom Responsiveness is Less Forgiving: In contrast, "bottom responsiveness" (a condition related to agents' worst-case coalition members) does not guarantee envy-free partitions, even when combined with strong stability notions. Deciding the existence of individually stable and envy-free partitions remains NP-complete in this setting.
  • Justified Envy-freeness: The paper introduces and analyzes "justified envy-freeness," a stronger notion than basic envy-freeness, and shows that even this stronger fairness criterion can be considered in conjunction with stability, often leading to similar complexity results.

Key Results

  • Symmetric ASHGs: Deciding the existence of an individually stable and justified envy-free partition is NP-complete. A Pareto optimal and justified envy-free partition may not exist.
  • Top Responsive Games: The "Extended Top Covering Algorithm" guarantees the existence of a Pareto optimal, individually stable, and envy-free partition, and can compute it in polynomial time.
  • Bottom Responsive Games: Deciding the existence of an individually stable and envy-free partition is NP-complete. However, a Pareto optimal and justified envy-free partition is always guaranteed.
  • Top Responsive & Mutual Games: Guarantees the existence of strict strong Nash stable and envy-free partitions.

Limitations and Future Work

  • Complexity: The paper identifies several NP-complete problems related to finding stable and envy-free partitions, suggesting that for many scenarios, finding such partitions is computationally intractable.
  • Specific Game Classes: The results are specific to additively separable, top-responsive, and bottom-responsive hedonic games. Extending these findings to more general hedonic games could be a future direction.
  • Algorithm Adaptability: The authors note that their positive result for top responsiveness might not extend to weaker forms of responsiveness.
  • Future Directions: The paper suggests future work on studying complexity issues related to core stability and Pareto optimality, which could lead to "NPNP difficult problems" (problems whose complexity is even higher than NP-complete). Investigating algorithms for more general classes of games and exploring other fairness notions are also potential avenues.

Summary updated

BibTeX
@inproceedings{barrot2019stable,
  author = {Nathanaël Barrot and Makoto Yokoo},
  title = {{Stable and Envy-free Partitions in Hedonic Games}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/10},
}
Figure