Unknown Agents in Friends Oriented Hedonic Games: Stability and Complexity

Nathanaël Barrot, Kazunori Ota, Yuko Sakurai, Makoto YokooAAAI 2019 · DOI

Abstract

This research investigates the impact of "unknown agents"—individuals who are neither friends nor enemies—on the stability of coalition formation in hedonic games. By extending the standard friends-oriented model to include extraverted (liking unknowns) and introverted (disliking unknowns) personality traits, the authors demonstrate a significant shift in computational complexity. While introversion guarantees stable outcomes and efficient solutions, extraversion leads to inherent instability and $NP^{NP}$-complete decision problems.

Introduction

In social and economic settings, individuals frequently form groups such as project teams, clubs, or political parties. Hedonic games provide a formal framework for modeling these scenarios, assuming that a player's utility depends entirely on the composition of their coalition. A classic approach is the "friends appreciation" model, where players seek to maximize friends and minimize enemies. However, traditional models often overlook the role of "unknown" agents—those with whom a player has no prior relationship. This paper addresses this gap by exploring how different personality traits regarding strangers affect the existence and findability of stable group structures.

Modeling Personality Traits

The authors extend the standard friends-oriented hedonic game by categorizing agents based on their attitude toward unknown agents ($\perp$):

  1. Neutral (HG/F): Unknown agents have zero impact on an agent's preference between two coalitions.
  2. Extraverted (HG/F+): Agents prefer coalitions with more unknown agents when the number of friends and enemies is otherwise equal.
  3. Introverted (HG/F-): Agents prefer coalitions with fewer unknown agents in the event of a tie between friends and enemies.
A friendship graph illustrating friends (F), enemies (E), and unknown agents (\perp).

These preferences are modeled using a lexicographic approach, where friendship and enmity take precedence over the number of unknown agents.

Stability and Computational Complexity

The study evaluates two primary types of stability: Core Stability, where no subgroup has an incentive to deviate and form a new coalition, and Individual Stability (IS), where no single player can move to another group without making someone in that group unhappy or decreasing their own utility.

To determine the difficulty of finding these stable structures, the researchers employ computational complexity theory, utilizing reductions from known hard problems such as MAXCLIQUE and MINMAXCLIQUE.

Complexity reduction from the MinMaxClique problem to the hedonic game model.

Key Results and Insights

The research yields several counter-intuitive findings regarding social dynamics:

  • Extraversion as a Destabilizing Force: Paradoxically, a population of extraverts is less likely to reach a stable arrangement. Their constant drive to seek out unknown agents can lead to cycles of instability. Deciding if a stable core exists for extraverts is $NP^{NP}$-complete, and determining individual stability is NP-complete.
  • The "Safety" of Introversion: In contrast, if all agents are introverted, a stable core is guaranteed to exist. Furthermore, this stable structure can be identified efficiently in polynomial time using the strongly connected components of the friendship graph.
  • Neutrality is Not a Middle Ground: The authors disprove the assumption that neutral agents behave like simpler "friends-only" models. They provide a counter-example showing that even when unknowns are ignored, an individually stable structure may not exist.
  • Symmetry Matters: If friendship is symmetric (i.e., if agent A considers B a friend, B also considers A a friend), stability is much easier to achieve and is always guaranteed for both extraverts and introverts.

Conclusion

By incorporating attitudes toward unknown agents, this work reveals that social openness can significantly complicate the achievement of societal stability. While introverts naturally gravitate toward stable, known groups, extraverts' preference for the unknown introduces high levels of computational and structural complexity. Future research may explore mixed populations of introverts and extraverts or additive utility models where different categories of agents are assigned specific numerical weights.

Summary updated

BibTeX
@inproceedings{barrot2019unknown,
  author = {Nathanaël Barrot and Kazunori Ota and Yuko Sakurai and Makoto Yokoo},
  title = {{Unknown Agents in Friends Oriented Hedonic Games: Stability and Complexity}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33011756},
}
Figure