Stability in Minimization-Based Altruistic Hedonic Games

Alessandra Wiechers, Jörg RotheSTAIRS@ECAI 2020 · OpenReview

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.

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:

  1. Minimum Selfish-First (minSF): Players prioritize their own utility, using the unhappiest friend's utility only as a tie-breaker.
  2. Minimum Equal-Treatment (minEQ): Players treat themselves and their friends equally, seeking to maximize the minimum utility in the entire group.
  3. Minimum Altruistic-Treatment (minAL): Players prioritize the unhappiest friend's utility first, using their own utility as a tie-breaker.
Table 1: Comparison of utility values for player 1 across different altruism models in a sample graph.

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.
Figure 1: An example of a social network graph with potential coalition structures A and B.
  • 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 for minEQ and minAL, 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 minEQ case.

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

BibTeX
@inproceedings{wiechers2020stability,
  author = {Alessandra Wiechers and Jörg Rothe},
  title = {{Stability in Minimization-Based Altruistic Hedonic Games}},
  booktitle = {STAIRS@ECAI},
  year = {2020},
  url = {https://openreview.net/forum?id=VD85vRiSm6},
}
Figure