Stable Outcomes in Modified Fractional Hedonic Games

Gianpiero Monaco, Luca Moscardelli, Yllka Velaj

TL;DR

This paper analyzes "modified fractional hedonic games" (MFHGs), a model of coalition formation where agents' utilities depend on the average benefit from their coalition members (excluding themselves). The authors characterize the existence and performance of various stable outcomes (Nash, strong Nash, and core) in these games, providing tight bounds on efficiency metrics like the price of anarchy and stability.

What Problem Does This Paper Address?

Coalition formation is a fundamental aspect of many social and economic systems, where individuals group together to achieve common goals. Hedonic games are a class of models that capture this phenomenon by focusing on agents' preferences over different coalition structures. This paper specifically addresses Modified Fractional Hedonic Games (MFHGs), a variant where an agent's utility is calculated based on the average benefit from other members of their coalition. This differs from standard fractional hedonic games where the average includes the agent themselves. The core problem is to understand the existence, efficiency, and computational aspects of stable outcomes in MFHGs, particularly how these outcomes perform in terms of social welfare compared to the optimal possible outcome.

Methods

The authors employ a combination of theoretical analysis and algorithmic approaches. They define and analyze three key stability concepts:

  • Nash Stable Outcomes: No single agent can unilaterally improve their utility by switching coalitions.
  • Strong Nash Stable Outcomes: No subset of agents can jointly deviate to improve all their utilities.
  • Core Stable Outcomes: No subset of agents can form a new coalition that benefits all of them.

They then investigate the existence of these stable outcomes, often by constructing specific graph structures or by proving general properties. For performance, they use the price of anarchy (PoA) and price of stability (PoS), which measure the ratio of the social welfare of the optimal outcome to the worst (PoA) or best (PoS) stable outcome, respectively. They also develop polynomial-time algorithms for computing certain types of stable outcomes.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis using graph structures as input, rather than empirical evaluation on datasets.

Key Insights and Ideas

  • Distinct Behavior from Fractional Hedonic Games: MFHGs exhibit different stability properties and performance bounds compared to standard fractional hedonic games, primarily due to the exclusion of an agent from their own utility calculation.
  • Existence Guarantees: While 2-strong Nash equilibria are not guaranteed in general MFHGs, the paper shows that for unweighted graphs, k-strong Nash equilibria (for any k) always exist and can be computed efficiently. Core stable outcomes are also shown to always exist.
  • Efficiency Trade-offs: The paper provides tight bounds for the price of anarchy and stability for various stability notions. For instance, the strong price of anarchy for unweighted graphs is shown to be exactly 2, while the price of anarchy for Nash stable outcomes can grow linearly with the number of agents.
  • Algorithmic Tractability: For unweighted graphs, the paper demonstrates that optimal outcomes and strong Nash equilibria can be computed in polynomial time, leading to a strong price of stability of 1. Core stable outcomes are also efficiently computable.
  • Negative Weights Matter: The existence of Nash stable outcomes is not guaranteed in the presence of negative edge weights, highlighting the importance of non-negativity for certain stability concepts.

Key Results

  • Strong Nash Stability: For unweighted graphs, k-strong Nash equilibria always exist and are polynomially computable. The strong price of anarchy is shown to be 2 for unweighted graphs.
  • Nash Stability: For non-negative edge weights, Nash stable outcomes exist. The price of anarchy is at least $\Omega(n)$ for unweighted paths, and at most $n-1$ for general weighted graphs. The price of stability is $\Omega(n)$ for weighted graphs.
  • Core Stability: The core is always non-empty for MFHGs. A core stable outcome can be computed in polynomial time, approximating the optimal social welfare within a factor of 2. The core price of stability is 1 for unweighted graphs and at least $2-\epsilon$ for weighted graphs, while the core price of anarchy is at most 4 (and 2 for unweighted graphs).
  • Algorithmic Contributions: Polynomial-time algorithms are presented for computing optimal outcomes and strong Nash equilibria in unweighted MFHGs.

Limitations and Future Work

  • Strict Core: The paper shows that the strict core can be empty, even for simple unweighted graphs, suggesting that relaxed notions of stability might be more appropriate in some contexts.
  • Weighted Graphs: While some results are provided for weighted graphs, further research is suggested to close the gap between the lower bound of 2 and the upper bound of 4 for the core price of stability.
  • Complexity of Optimal Outcomes: The complexity of computing optimal outcomes for weighted graphs remains an open question.
  • Truthful Mechanisms: Designing truthful mechanisms for MFHGs that perform well with respect to social welfare is proposed as a future research direction.
  • Alternative Social Welfare: Exploring different social welfare definitions, such as maximizing the minimum utility among agents, is suggested.

Summary updated

Abstract

In coalition formation games self-organized coalitions are created as a result of the strategic interactions of independent agents. For each couple of agents $(i,j)$, weight $w_i,j =w_j,i $ reflects how much agents i and j benefit from belonging to the same coalition. We consider the \em modified fractional hedonic game, that is a coalition formation game in which agents' utilities are such that the total benefit of agent i belonging to a coalition (given by the sum of $w_i,j $ over all other agents j belonging to the same coalition) is averaged over all the other members of that coalition, i.e., excluding herself. Modified fractional hedonic games constitute a class of succinctly representable hedonic games. We are interested in the scenario in which agents, individually or jointly, choose to form a new coalition or to join an existing one, until a stable outcome is reached. To this aim, we consider common stability notions, leading to strong Nash stable outcomes, Nash stable outcomes or core stable outcomes: we study their existence, complexity and performance, both in the case of general weights and in the case of 0-1 weights. In particular, we completely characterize the existence of the considered stable outcomes and show many tight or asymptotically tight results on the performance of these natural stable outcomes for modified fractional hedonic games, also highlighting the differences with respect to the model of fractional hedonic games, in which the total benefit of an agent in a coalition is averaged over all members of that coalition, i.e., including herself.
BibTeX
@article{monaco2020stable,
  author = {Gianpiero Monaco and Luca Moscardelli and Yllka Velaj},
  title = {{Stable Outcomes in Modified Fractional Hedonic Games}},
  journal = {Auton. Agents Multi Agent Syst},
  year = {2020},
  doi = {10.1007/s10458-019-09431-z},
}
Figure