Relaxed Core Stability in Fractional Hedonic Games

Angelo Fanelli, Gianpiero Monaco, Luca MoscardelliIJCAI 2021 · DOI

TL;DR

This paper introduces "relaxed core stability" concepts for fractional hedonic games, addressing limitations of the traditional core in large, distributed systems. By considering deviations based on coalition size (q-size core) and utility gain (k-improvement core), they establish existence and computational results, offering more practical stability notions for coalition formation.

What Problem Does This Paper Address?

Coalition formation is a fundamental problem in multi-agent systems, and the "core" is a classic stability concept. However, the traditional core has practical limitations, especially in large, distributed settings. Specifically, the core requires that no subset of agents can improve their situation by deviating. This is problematic because:

  1. Coordination Overhead: Deviating agents must coordinate, which can be difficult and costly in large systems.
  2. Tiny Gains: Agents might benefit only marginally from deviating, making the strict core condition overly sensitive.
  3. Non-Existence: Even in simplified scenarios (like Simple Symmetric Fractional Hedonic Games), core-stable outcomes are not guaranteed to exist.
  4. Computational Hardness: Deciding if a core-stable outcome exists is computationally difficult.

Fractional Hedonic Games (FHGs) are a specific model where agents have valuations for other agents, and their utility in a coalition is the sum of these valuations divided by the coalition size. FHGs are relevant for modeling social networks, political parties, and international groups. This paper aims to make stability concepts more practical for FHGs by relaxing the strict conditions of the core.

Methods

The paper introduces two novel stability concepts that relax the traditional core:

  • q-size core stability: An outcome is q-size core stable if no blocking coalition exists with a size at most q. This acknowledges that only smaller groups might be able to coordinate deviations.
  • k-improvement core stability: An outcome is k-improvement core stable if no blocking coalition exists where each member strictly increases their utility by a factor greater than k. This accounts for the magnitude of utility gain required for a deviation to be worthwhile.

The authors then investigate the existence, convergence, and computational aspects of these relaxed notions in FHGs. They use:

  • Potential Function Arguments: To prove convergence of dynamics (e.g., Theorem 3, Theorem 5).
  • Graph Representations: For SS-FHGs, they leverage graph structures (cliques, paths) to analyze blocking coalitions (e.g., Theorem 2, Theorem 4).
  • Constructive Algorithms: To demonstrate the polynomial-time computability of stable outcomes (e.g., Theorem 6).
  • Price of Anarchy Analysis: To quantify the efficiency loss of stable outcomes compared to the social optimum.

Datasets

Not discussed in the paper. The paper focuses on theoretical results for a general class of games (S-FHGs and SS-FHGs) rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Relaxation is Key: The core's strictness is its downfall in practical, large-scale systems. Relaxing conditions based on coalition size and utility gain offers a more realistic path to stable outcomes.
  • q-size Core and k-improvement Core are Related: The paper shows that 2-size core stability implies 2-improvement core stability (Theorem 1), and 3-size core stability implies 3-improvement core stability in SS-FHGs (Theorem 2). This suggests a connection between limiting deviation size and limiting utility gain.
  • Convergence is Achievable: The proposed relaxed dynamics are shown to converge to stable outcomes, which is a desirable property for practical applications. Specifically, 2-size core dynamics always converge (Theorem 3), and k-improvement core dynamics converge for k ≥ 2 (Theorem 5).
  • Computational Tractability: While the traditional core is computationally hard, these relaxed notions are often computationally tractable. For instance, k-improvement core stable outcomes can be computed in polynomial time for k ≥ 2(1-1/n) (Theorem 6).
  • Efficiency Trade-offs Exist: The paper quantifies the "price of anarchy" for these relaxed stability concepts, showing that stable outcomes can be up to 2k times worse than the social optimum for k-improvement core stability (Theorem 8). However, these bounds are shown to be tight, indicating that the relaxations are necessary to achieve stability.

Key Results

  • Existence:
    • Every S-FHG admits a 2-size core stable outcome (Theorem 3).
  • Every S-FHG admits a k-improvement core stable outcome for k ≥ 2 (Theorem 5).
  • Convergence:
    • 2-size core dynamics always converge in S-FHGs (Theorem 3).
  • k-improvement core dynamics converge for k ≥ 2 in S-FHGs (Theorem 5).
  • 3-size core dynamics converge in polynomial time for SS-FHGs (Theorem 4).
  • Computation:
    • k-improvement core stable outcomes are computable in polynomial time for k ≥ 2(1-1/n) (Theorem 6).
  • k-improvement core stable outcomes are computable in polynomial time for k ≥ 3/2 in SS-FHGs (Theorem 7).
  • Efficiency (Price of Anarchy):
    • k-IMPR CPOA(G) ≤ 2k for S-FHGs (Theorem 8).
  • 2-SIZE CPOA(G) ≤ 4 for S-FHGs (Theorem 10).
  • 3-SIZE CPOA(G) ≤ 3 for SS-FHGs (Theorem 10).
  • Lower bounds for these prices of anarchy are also established, showing tightness of the bounds.

Limitations and Future Work

  • Open Problems on Existence: The paper notes that for some games, core-stable outcomes might not exist for certain q and k values (e.g., q=11, k=100/99). A key open problem is to determine the exact thresholds for q and k that guarantee existence, efficient computation, and reachability by dynamics.
  • Generalizing Relations: While Theorems 1 and 2 show specific relationships between q-size and k-improvement core stability, a broader conjecture is proposed: any q-size core stable coalition structure is (q-1)/(q-2)-improvement core stable.
  • Efficiency Bounds: Further investigation into the q-size core price of anarchy for q ≥ 4 (S-FHGs) and q ≥ 3 (SS-FHGs) is suggested, with a conjecture that it is 2q/(q-1).
  • Price of Stability: The paper highlights that for k ≥ 2, the k-improvement core price of stability is 1 (optimal solution is stable). However, for k < 2, the price of stability is less understood, and tight bounds are sought, especially for k=1.
  • Combinations of Relaxations: The authors suggest exploring combinations of q-size and k-improvement relaxations simultaneously.
  • Broader Applicability: Investigating these relaxed notions in other game classes beyond FHGs is also proposed.

Summary updated

BibTeX
@inproceedings{fanelli2021relaxed,
  author = {Angelo Fanelli and Gianpiero Monaco and Luca Moscardelli},
  title = {{Relaxed Core Stability in Fractional Hedonic Games}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/26},
}
Figure