Relaxed Core Stability for Hedonic Games with Size-Dependent Utilities

Tom Demeulemeester, Jannik PetersMFCS 2023 · OpenReview

TL;DR

This paper investigates relaxed notions of stability in hedonic games, specifically "q-size core stability" and "k-improvement core stability." The authors establish general bounds relating these concepts for a broad class of hedonic games and confirm two important conjectures about fractional hedonic games, including a precise characterization of the price of anarchy for q-size stability.

What Problem Does This Paper Address?

Hedonic games are a fundamental model in multiagent systems and algorithmic game theory where agents form coalitions to maximize their own utility, based on their preferences for partners. A key concept for stability is the "core," where no coalition has an incentive to deviate. However, the core can be too restrictive, often leading to non-existent or computationally intractable solutions. To address this, researchers have introduced relaxed notions of stability. This paper focuses on two such relaxations:

  • q-size core stability: A coalition structure is q-size core stable if no coalition of size at most q can improve the utility for all its members.
  • k-improvement core stability: A coalition structure is k-improvement core stable if no coalition can improve the utility for all its members by a factor greater than k.

The problem this paper tackles is understanding the precise relationship between these two relaxed stability notions, particularly for games where an agent's utility depends on the size of their coalition. Specifically, they aim to quantify how much a coalition can improve its members' utilities in a q-size core stable outcome and to establish tight bounds for this improvement. This is crucial for understanding the trade-offs between stability and efficiency in coalition formation.

Methods

The paper introduces a new class of hedonic games called α-hedonic games. In these games, an agent's utility from being in a coalition of size m is determined by the sum of cardinal utilities from other agents in that coalition, multiplied by a factor α(m) that depends on the coalition size. This general framework encompasses several previously studied types of hedonic games, such as fractional, modified fractional, and additively separable hedonic games.

The core of their methodology involves:

  1. Deriving Upper Bounds: For a broad class of α-hedonic games, they derive upper bounds on the maximum factor by which a deviating coalition of a certain size can improve the utilities of its members, given that the original coalition structure is q-size core stable. This is achieved through a detailed analysis of blocking coalitions and their potential utility gains.
  2. Proving Asymptotic Lower Bounds: They also provide asymptotically tight lower bounds for these improvement factors, demonstrating that their derived upper bounds are often the best possible for certain classes of games.
  3. Confirming Conjectures: Using these bounds, they rigorously prove two conjectures made by Fanelli et al. (2021) regarding symmetric fractional hedonic games (S-FHGs).

The proofs often involve intricate combinatorial arguments, including the use of hypergraph matchings to analyze the structure of potential blocking coalitions.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and does not involve empirical evaluation on specific datasets.

Key Insights and Ideas

  • Unifying Framework: The introduction of α-hedonic games provides a powerful unifying framework for studying various relaxed stability concepts across different types of hedonic games. This allows for more generalizable results.
  • Quantifying the Trade-off: The paper precisely quantifies the relationship between q-size core stability and k-improvement core stability. It shows that a q-size core stable outcome implies a certain level of k-improvement core stability, where k is dependent on q and the coalition size m. This is a significant step in understanding the "cost" of relaxing core stability.
  • Confirmation of Conjectures: The paper provides formal proofs for two important conjectures concerning fractional hedonic games. This solidifies existing theoretical understanding and opens avenues for further research.
  • Price of Anarchy Characterization: A key result is the precise characterization of the price of anarchy for q-size stability in symmetric fractional hedonic games as exactly $2q/(q-1)$. This is a strong theoretical result with implications for understanding the efficiency loss due to stability requirements.
  • Tightness of Bounds: The paper not only provides bounds but also demonstrates their tightness for specific cases, indicating that the theoretical limits are often achievable in practice, which is crucial for theoretical computer science.

Key Results

  • General Bound: For any symmetric α-hedonic game, a q-size core stable coalition structure is also $(m, f(q, m))$-core stable, where $f(q, m)$ is a function of $q$, $m$, and the α-function. For fractional hedonic games, this bound simplifies to $1 + \frac{m-2}{q-1}$.
  • Conjecture Confirmation (S-FHGs):
    • Every q-size core stable outcome in an S-FHG is also $\frac{q}{q-1}$-improvement core stable.
  • The price of anarchy for q-size stability in S-FHGs is exactly $\frac{2q}{q-1}$.
  • Lower Bounds: The paper establishes asymptotically tight lower bounds for the improvement factors, showing that the derived upper bounds are often tight for hospitable α-hedonic games.
  • Specific Game Results: Tightness results are shown for various combinations of $(q, m)$ and game types, including S-FHGs and S-ASHGs.

Limitations and Future Work

  • Tightness of Bounds: While the paper provides general bounds and demonstrates tightness for specific cases, it acknowledges that the tightness of the bounds is not fully established for all combinations of $q$, $m$, and α-functions. For instance, the tightness for $q=5$ and $m=10$ in S-FHGs and S-ASHGs remains an open question. The authors used integer linear programming to find counterexamples for tightness but were unsuccessful for these specific cases.
  • Generalization of α-hedonic Games: The authors suggest that the generalization of α-hedonic games could find applications in other areas of hedonic games research.
  • Dynamics Convergence: Investigating whether certain dynamics converge for α-hedonic games is proposed as an interesting future direction.
  • Asymmetric Games: The paper primarily focuses on symmetric games, and extending the results to asymmetric games could be a valuable area for future research.

Summary updated

Abstract

We study relationships between different relaxed notions of core stability in hedonic games. In particular, we study (i) q-size core stable outcomes in which no deviating coalition of size at most q exists and (ii) k-improvement core stable outcomes in which no coalition can improve by a factor of more than k. For a large class of hedonic games, including fractional and additively separable hedonic games, we derive upper bounds on the maximum factor by which a coalition of a certain size can improve in a q-size core stable outcome. We further provide asymptotically tight lower bounds for a large class of hedonic games. Finally, our bounds allow us to confirm two conjectures by Fanelli et al. [Angelo Fanelli et al., 2021][IJCAI'21] for symmetric fractional hedonic games (S-FHGs): (i) every q-size core stable outcome in an S-FHG is also q/(q-1)-improvement core stable and (ii) the price of anarchy of q-size stability in S-FHGs is precisely 2q/q-1.
BibTeX
@inproceedings{demeulemeester2023relaxed,
  author = {Tom Demeulemeester and Jannik Peters},
  title = {{Relaxed Core Stability for Hedonic Games with Size-Dependent Utilities}},
  booktitle = {MFCS},
  year = {2023},
  url = {https://openreview.net/forum?id=GioRWVNUXH},
}
Figure