Abstract
In hedonic games, altruism is typically modeled by assuming players care about the average well-being of their friends. This paper introduces a novel "egalitarian" approach, focusing instead on the happiness of the unhappiest friend—the "weakest link." By analyzing this minimization-based altruism, we determine the conditions under which social structures remain stable and evaluate the computational complexity of finding popular coalitions.
Introduction: The "Weakest Link" in Social Groups
Hedonic games explore how individuals form coalitions based on personal preferences. Traditional models of altruism assume a "utilitarian" perspective, where players seek to maximize the average utility of their friends. However, in many real-world groups, collective satisfaction is often dictated by the most dissatisfied member. This paper formalizes minimization-based altruism, shifting the focus from the average to the minimum utility within a player's social circle.
Formalizing Minimization-Based Altruism
The authors define three distinct degrees of altruism based on how players weight their own happiness against that of their friends:
- Minimum Selfish-First (
minSF): Players prioritize their own utility, using the unhappiest friend's utility only as a tie-breaker. - Minimum Equal-Treatment (
minEQ): Players treat themselves and their friends equally, seeking to maximize the minimum utility in the entire group. - Minimum Altruistic-Treatment (
minAL): Players prioritize the unhappiest friend's utility first, using their own utility as a tie-breaker.
The research methodology is purely theoretical, employing game theory to prove the existence of stable structures and computational complexity analysis to categorize the difficulty of decision problems.
Key Insights: Stability and Social Welfare
The shift from average to minimum utility fundamentally alters the stability of coalitions:
- Nash Stability is Robust: For all three types of minimization-based altruism, a Nash stable coalition structure—where no single player wants to move—is guaranteed to exist.
- Core Stability is Fragile: While "selfish-first" players can always find a strictly core stable structure (where no group wants to deviate), this is not guaranteed for the "equal-treatment" or "altruistic-treatment" models. In these cases, the needs of the unhappiest friend can create cycles of dissatisfaction.
- Complexity of Popularity: Determining if a coalition structure is "strictly popular" (preferred by a majority over any other structure) is highly complex—specifically coNP-complete. As the number of players grows, it becomes exponentially harder to verify if a social arrangement is truly the most popular one.
Key Results
- Existence Proofs: The authors prove that Nash stable, individually stable, and contractually individually stable structures always exist for all three altruism types.
- Strict Core Stability: Existence is proven for
minSF, but counterexamples are provided forminEQandminAL, showing that a stable core is not guaranteed when altruism is high. - Computational Hardness: The verification of "strict popularity" is proven to be coNP-complete, and the existence problem for such structures is coNP-hard.
- Algorithmic Efficiency: Despite general hardness, the authors provide a polynomial-time algorithm (Algorithm 1) to calculate the utility of the unhappiest friend in a player's most preferred coalition for the
minEQcase.
Limitations and Future Work
The study focuses strictly on friend-oriented preferences (friends vs. enemies). Future work may include:
- Investigating if coNP-completeness for strict popularity holds for average-based models.
- Extending minimization-based altruism to more general coalition formation games.
- Resolving the complexity of the "Most Preferred Coalition" problem, which is suspected to be coNP-complete.
Summary updated