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$):
- Neutral (HG/F): Unknown agents have zero impact on an agent's preference between two coalitions.
- Extraverted (HG/F+): Agents prefer coalitions with more unknown agents when the number of friends and enemies is otherwise equal.
- Introverted (HG/F-): Agents prefer coalitions with fewer unknown agents in the event of a tie between friends and enemies.
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.
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