Testing stability properties in graphical hedonic games

Hendrik Fichtenberger, Anja ReyAuton. Agents Multi Agent Syst 2021 · OpenReview

Abstract

In hedonic games, players form coalitions based on individual preferences over the group of players they could belong to. Several concepts to describe the stability of coalition structures in a game have been proposed and analysed in the literature. However, prior research focuses on algorithms with time complexity that is at least linear in the input size. In the light of very large games that arise from, e.g., social networks and advertising, we initiate the study of sublinear time property testing algorithms for existence and verification problems under several notions of coalition stability in a model of hedonic games represented by graphs with bounded degree. In graph property testing, one shall decide whether a given input has a property (e.g., a game admits a stable coalition structure) or is far from it, i.e., one has to modify at least an $\epsilon$-fraction of the input (e.g., the game’s preferences) to make it have the property. In particular, we consider verification of perfection, individual rationality, Nash stability, (contractual) individual stability, and core stability. While there is always a Nash-stable coalition structure (which also implies individually stable coalitions), we show that the existence of a perfect coalition structure is not tautological but can be tested. All our testers have one-sided error and time complexity that is independent of the input size.

Introduction

Hedonic games are a fundamental framework in cooperative game theory used to model how players partition themselves into disjoint coalitions. In these games, a player's utility depends solely on the members of their own coalition. Common applications include social network grouping, committee formation, and advertising markets. However, as the number of players $n$ grows, determining or even verifying the stability of a coalition structure becomes computationally prohibitive, often reaching NP-hard or even higher complexity levels. This paper addresses the challenge of scale by introducing sublinear-time property testing algorithms that can decide stability properties by examining only a constant number of players, regardless of the total population size.

The FEN Model and Stability Concepts

The authors focus on the FEN-encoding (Friends, Enemies, Neutrals) model. In this representation, players are nodes in a graph $G = (V, E)$. An edge between two players indicates a "friendship" (positive preference), while the absence of an edge or a specific "enemy" edge indicates negative or neutral preference. In the bounded-degree model, each player has at most $d$ friends or enemies.

A graphical representation of a hedonic game (Graph H) where solid green lines denote friends and dashed red lines denote enemies.

Stability concepts like Nash stability (where no player wants to move to another existing coalition) or Core stability (where no group of players wants to deviate together) are central to these models. Finding these structures is typically hard, but the authors leverage the fact that stability is often a "local" property.

Sublinear-Time Property Testing

Property testing allows for ultra-efficient decision-making by relaxing the requirement for absolute precision. A tester must accept if the game satisfies a property and reject with high probability if the game is $\epsilon$-far from it. Being $\epsilon$-far means that one would need to modify at least an $\epsilon$-fraction of the preferences (edges in the FEN graph) to satisfy the property.

Graph G demonstrates how a small modification—changing the edge between players $c$ and $f$ from 'friend' to 'enemy'—can alter the stability landscape of the game, illustrating the concept of being 'far' from a property.

Key Algorithmic Results

The research provides testers for several stability concepts with the following highlights:

  • Verification of Stability: For undirected graphs with bounded degree $d$, verifying perfection, individual rationality, and Nash stability takes $O(d/\epsilon)$ queries. This complexity is independent of the total number of players $n$.
  • Core Stability: Verifying core stability is more complex but remains testable in constant time provided the maximum coalition size $c$ is bounded: $O(c^2 \cdot d^{c^2+1} \cdot e^c / \epsilon)$.
  • Existence of Perfection: While Nash-stable structures always exist, "perfect" structures (where every player gets their absolute favorite group) do not. The authors provide a tester to detect if a perfect partition exists.
  • One-Sided Error: All proposed testers feature one-sided error, meaning they never accidentally reject a truly stable game.

Conclusion and Future Work

A critical insight is the "Directed Graph Wall": in directed graphs where relationships are asymmetric, testing for the existence of perfect structures requires nearly linear time, breaking the sublinear advantage. Future research may look into Local Computation Algorithms (LCAs) to construct stable partitions locally or explore two-sided error testers that might offer even greater efficiency for complex stability notions.

Summary updated

Abstract

In hedonic games, players form coalitions based on individual preferences over the group of players they could belong to. Several concepts to describe the stability of coalition structures in a game have been proposed and analysed in the literature. However, prior research focuses on algorithms with time complexity that is at least linear in the input size. In the light of very large games that arise from, e.g., social networks and advertising, we initiate the study of sublinear time property testing algorithms for existence and verification problems under several notions of coalition stability in a model of hedonic games represented by graphs with bounded degree. In graph property testing, one shall decide whether a given input has a property (e.g., a game admits a stable coalition structure) or is far from it, i.e., one has to modify at least an \(\epsilon\)-fraction of the input (e.g., the game’s preferences) to make it have the property. In particular, we consider verification of perfection, individual rationality, Nash stability, (contractual) individual stability, and core stability. While there is always a Nash-stable coalition structure (which also implies individually stable coalitions), we show that the existence of a perfect coalition structure is not tautological but can be tested. All our testers have one-sided error and time complexity that is independent of the input size.
BibTeX
@inproceedings{fichtenberger2021testing,
  author = {Hendrik Fichtenberger and Anja Rey},
  title = {{Testing stability properties in graphical hedonic games}},
  booktitle = {Auton. Agents Multi Agent Syst},
  year = {2021},
  url = {https://openreview.net/forum?id=mEOqa0To2a},
}
Figure