Core Stability in Hedonic Games among Friends and Enemies: Impact of Neutrals

Kazunori Ohta, Nathanaël Barrot, Anisse Ismaili, Yuko Sakurai, Makoto YokooIJCAI 2017 · DOI

TL;DR

This paper investigates how introducing "neutral" agents affects coalition stability in hedonic games, where agents form groups based on preferences for friends and aversion to enemies. Surprisingly, adding neutrals makes problems that were previously tractable (like finding a stable coalition structure) computationally intractable, even leading to situations where no stable coalition can exist.

What Problem Does This Paper Address?

Hedonic games model how individuals form coalitions based on their preferences for who they want to be with. In previous work, agents were typically categorized as either friends or enemies. This paper extends these models by introducing a third category: neutral agents. The core question is: does adding neutral agents simplify the problem of finding stable coalitions, or does it introduce new complexities? Specifically, the authors explore whether stable coalition structures are guaranteed to exist and how computationally difficult it is to find them or verify their stability, considering two main preference types: "enemies aversion" and "friends appreciation."

Methods

The paper uses a combination of theoretical analysis and complexity theory. They define formal models for hedonic games with friends, enemies, and neutrals. The core of their analysis involves proving theorems about the existence of stable coalition structures and establishing the computational complexity of related decision problems (like verifying stability or determining if a stable structure exists). They employ techniques like reductions from known NP-complete problems (e.g., MAXCLIQUE) and coNP-complete problems to prove hardness results for their own problems. They also use specific examples to demonstrate when stable coalitions might not exist.

Datasets

Not discussed in the paper. The paper focuses on theoretical models and proofs rather than empirical evaluation on datasets.

Key Insights and Ideas

  • Neutrals Complicate, Not Simplify: Counterintuitively, adding neutral agents, who by definition don't directly affect preferences, significantly increases the computational complexity of finding stable coalitions.
  • Core Can Be Empty: Under "enemies aversion" with neutrals, a stable coalition structure (in the core) is not guaranteed to exist. This is a departure from the no-neutrals case where a core-stable structure always exists.
  • Strict Core Vulnerability: Under "friends appreciation," the strict core (a more demanding stability concept) can be empty even without neutrals, and this vulnerability persists with the addition of neutrals.
  • Extreme Intractability: The problem of determining if a stable coalition structure exists in these extended hedonic games (specifically, the strict core under enemies aversion and friends appreciation) is shown to be NPNP-complete, placing it at a very high level of computational difficulty.

Key Results

  • Theorem 1: In hedonic games with enemies aversion and neutral agents, the core can be empty.
  • Theorem 2: In hedonic games with friends appreciation and neutral agents, the strict core can be empty.
  • Theorem 3: Verifying if a coalition structure is strictly core stable in an HG/E (enemies aversion) with neutrals is coNP-complete.
  • Theorem 4: Deciding if a strictly core stable coalition structure exists in an HG/E with neutrals is NPNP-complete.
  • Theorem 6: Deciding if a core stable coalition structure exists in an HG/E with neutrals is NPNP-complete.
  • Theorem 7: Verifying if a coalition structure is strictly core stable in an HG/F (friends appreciation) with neutrals is coNP-complete.
  • Theorem 8: Deciding if a strictly core stable coalition structure exists in an HG/F with neutrals is NPNP-complete.
  • Theorem 9: In hedonic games with friends appreciation (even with neutrals), a core-stable coalition structure is guaranteed to exist and can be found in polynomial time.

Limitations and Future Work

The authors acknowledge that their results focus on specific preference types (enemies aversion and friends appreciation) and that the symmetry of friend/enemy relations was not explored. They suggest that future work could investigate assumptions that might make verification tractable, potentially bringing existence problems down to class NP. They also propose numerical experiments as a potential avenue for future research.

Summary updated

BibTeX
@inproceedings{ohta2017core,
  author = {Kazunori Ohta and Nathanaël Barrot and Anisse Ismaili and Yuko Sakurai and Makoto Yokoo},
  title = {{Core Stability in Hedonic Games among Friends and Enemies: Impact of Neutrals}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/51},
}
Figure