Hedonic Games with Social Context

Gianpiero Monaco, Luca Moscardelli, Yllka VelajICTCS 2018 · OpenReview

Abstract

This paper introduces Social Context Hedonic Games (SCHGs), a novel framework for coalition formation that incorporates social interdependencies among players. Unlike traditional hedonic games where players are purely self-interested, SCHGs model players who also derive utility from the well-being of their friends. We prove the existence of an exact potential function, guaranteeing convergence to a pure Nash equilibrium. While social awareness ensures stability, our analysis of the Price of Anarchy reveals that altruism does not always prevent highly inefficient outcomes, particularly when negative valuations are present.

Introduction

Coalition formation is a fundamental problem in game theory, modeling how individuals organize into groups such as political parties, social clubs, or research teams. Traditional hedonic games assume that a player's utility depends solely on the members of their own coalition. However, this "selfish" assumption overlooks the reality of social context: individuals often care about the happiness of their friends, regardless of whether they share a group.

This paper addresses this gap by introducing "Social Context" into hedonic games. By factoring in the happiness of friends (a form of altruism), the authors investigate whether stable groupings still exist and how this social awareness impacts the overall social welfare of the system.

The Social Context Hedonic Game Model

The authors define a formal model characterized by additive valuations, a social graph, and an altruism parameter. In this model, a player's basic happiness is the sum of their valuations for each person in their coalition. The social graph defines friendship ties, and an altruism parameter $\alpha \in [0, 1]$ determines the weight a player gives to their friends' happiness. A player's total utility is thus their own internal happiness plus $\alpha$ times the happiness of all their friends in the system.

Figure 1: An example of a Social Context Hedonic Game showing the underlying social graph, a sample coalition partition, and a table of pairwise valuations.

To analyze stability, the authors employ a Potential Function ($\Phi$). This mathematical tool tracks changes in utility as players move between coalitions. By demonstrating that every utility-improving move by a player corresponds to an increase in the global potential value, the authors prove that the game must eventually reach a Nash Equilibrium—a state where no individual player can improve their utility by unilaterally changing coalitions.

Key Insights and Results

The study yields several critical findings regarding the stability and efficiency of SCHGs:

  • Guaranteed Stability: Every SCHG possesses at least one pure Nash equilibrium. The existence of an exact potential function ensures that players will always converge to a stable state through a sequence of best-response moves.
  • The Impact of Altruism: The parameter $\alpha$ allows for a spectrum of behavior, from pure selfishness ($\alpha=0$) to full altruism ($\alpha=1$). In scenarios with non-negative valuations, the "Grand Coalition" (where everyone is in a single group) is both socially optimal and stable.
  • Efficiency Metrics: For non-negative valuations, the Price of Stability (PoS) is 1, meaning at least one stable state is socially optimal. However, the Price of Anarchy (PoA) is $\Theta(n)$, indicating that the worst stable outcome can be significantly less efficient than the optimum as the number of players ($n$) grows.
  • The Role of Negative Valuations: When players can have negative valuations (dislikes), the system's efficiency breaks down. Both the PoA and PoS can become unbounded, potentially leading to stable outcomes where everyone is worse off than in a non-stable alternative.

Conclusion and Future Directions

While SCHGs provide a more realistic model of human social behavior in group formation, several avenues for future research remain. The current model assumes symmetric (undirected) friendship and additive valuations. Future work could explore directed social ties or "fractional" hedonic games, where utility is normalized by coalition size to prevent excessively large groups. Additionally, investigating stronger notions of stability, such as "Strong Nash" or "Core" stability—where groups of players move together—could provide deeper insights into collective decision-making in social contexts.

Summary updated

BibTeX
@inproceedings{monaco2018hedonic,
  author = {Gianpiero Monaco and Luca Moscardelli and Yllka Velaj},
  title = {{Hedonic Games with Social Context}},
  booktitle = {ICTCS},
  year = {2018},
  url = {https://openreview.net/forum?id=wJ1c0Syc5dF},
}
Figure