TL;DR
This paper introduces "Social Context Additively Separable Hedonic Games" (SCASHGs), a new model that extends traditional hedonic games by incorporating players' concern for their friends' happiness. They demonstrate that these games always have stable outcomes (Nash equilibria) and provide bounds on the efficiency of these outcomes, showing that social context can significantly impact coalition formation dynamics.
What Problem Does This Paper Address?
Traditional hedonic games model how self-interested individuals form coalitions based solely on their own utility derived from coalition members. However, real-world scenarios often involve more complex social dynamics, where individuals might also care about the well-being of their friends within or outside their own coalition. This paper addresses the gap by introducing a formal model, SCASHGs, that captures this "social context" – the influence of friends' happiness on an individual's decision-making in coalition formation. This allows for a more realistic representation of how groups form in social networks, organizations, and other collective settings.
Methods
The authors build upon the framework of additively separable hedonic games. The core innovation is the introduction of a parameter $\alpha \in [0,1]$ that quantifies the player's altruism towards their friends. A player's utility is now a combination of their direct valuation of coalition members and a weighted sum of their friends' utilities from their respective coalitions.
Key methodological contributions include:
- Potential Function: They define an exact potential function for SCASHGs. This is crucial because the existence of a potential function guarantees that pure Nash equilibria always exist and that a best-response dynamic will eventually converge to one.
- Social Welfare Functions: Two social welfare functions are considered:
- $SW(C)$: Sum of players' direct valuations for their coalition members.
- $SW(C)$: Sum of players' total utilities, including the social context component.
- Price of Anarchy (PoA) and Price of Stability (PoS): These standard game theory metrics are used to evaluate the efficiency of Nash equilibria. PoA measures the ratio of the optimal social welfare to the worst Nash equilibrium welfare, while PoS measures the ratio to the best Nash equilibrium welfare.
Datasets
Not discussed in the paper. The paper focuses on theoretical modeling and analysis, using constructed examples and general graph structures rather than empirical datasets.
Key Insights and Ideas
- Altruism Matters: Even a small degree of altruism ($\alpha > 0$) can fundamentally alter coalition formation dynamics and the stability of outcomes compared to purely selfish players.
- Guaranteed Stability: The introduction of the potential function proves that SCASHGs are "potential games," ensuring that stable outcomes (Nash equilibria) always exist. This is a significant theoretical result for this class of games.
- Social Context Can Degrade Welfare: Counterintuitively, the social context can lead to worse outcomes. The paper shows examples where Nash equilibria result in negative social welfare, while the optimal outcome is positive, highlighting how concerns for friends' happiness can sometimes lead to suboptimal group formations.
- Bounds on Inefficiency: The paper provides tight or asymptotically tight bounds on the price of anarchy and price of stability, quantifying how much less efficient Nash equilibria can be compared to the social optimum. These bounds depend on the number of players ($n$) and the altruism parameter ($\alpha$).
Key Results
- Existence of Nash Equilibria: SCASHGs always possess pure Nash equilibria due to the existence of an exact potential function.
- Unbounded PoA/PoS (with negative valuations): When players can have negative valuations (e.g., disliking certain individuals), the price of anarchy can be unbounded, meaning Nash equilibria can be arbitrarily worse than the social optimum.
- Negative Social Welfare in Equilibria: For $\alpha \in (0, 1]$, there exist SCASHGs where all Nash equilibria yield negative social welfare, while an optimal outcome yields positive welfare.
- Bounded PoA/PoS (with non-negative valuations): For non-negative valuations, the price of anarchy is bounded by $O(n(1+\alpha))$, and the price of stability is 1. This indicates that when players only have positive or neutral valuations, the inefficiency of Nash equilibria is manageable and scales with the network size and altruism.
Limitations and Future Work
- Focus on Nash Equilibrium: The paper primarily analyzes Nash equilibria. Other stability concepts like strong Nash equilibria or core stability are mentioned as future research directions.
- Symmetric Friendship: The model assumes symmetric friendship relations (undirected graphs). Exploring asymmetric friendships could add further realism.
- Specific Social Graph Topologies: The current bounds are general. Investigating specific graph structures (e.g., complete graphs, paths, cycles) could yield tighter bounds on the price of anarchy.
- Other Utility Combinations: The paper uses an additive combination of friends' utilities. Exploring other ways friends' happiness might influence utility (e.g., min, max, weighted averages) is a promising avenue.
- Player-Specific Altruism: The current model uses a single altruism parameter $\alpha$. Allowing each player to have their own altruism parameter ($\alpha_i$) would increase the model's flexibility.
- Fractional and Modified Hedonic Games: Extending the social context concept to fractional and modified hedonic games is suggested as future work.
Summary updated