Stability in Online Coalition Formation

Martin Bullinger, René RomenAAAI 2024 · DOI

Introduction

In many real-world scenarios—such as assigning new hires to project teams or students to dormitories—decisions must be made on the fly as participants arrive. This represents the "online" version of coalition formation. This paper investigates hedonic games, where an agent's utility depends solely on the members of their assigned group. While previous research often focused on maximizing social welfare, this work shifts the focus to stability: ensuring that once agents are assigned to groups, they have no incentive to leave or move.

The primary challenge in the online setting is the lack of foresight. A group that appears stable upon formation may become unstable as new agents arrive. Furthermore, assignments are typically irrevocable, making the search for stable partitions mathematically demanding.

Stability Concepts in Hedonic Games

The authors analyze Additively Separable Hedonic Games (ASHGs), where an agent’s total utility is the sum of their preferences (positive, negative, or neutral) toward each member of their coalition. Several stability concepts are evaluated, ranging from strict individual incentives to group-sanctioned movements.

Hierarchy of stability concepts and their logical implications.

The hierarchy illustrated above defines the relationships between various stability notions:

  • Nash Stability (NS): No agent prefers moving to any other existing group.
  • Individual Stability (IS): No agent wants to move, and the receiving group must also benefit from (or be indifferent to) their arrival.
  • Contractual Stability (CNS/CIS): Similar to the above, but the group being vacated must also consent to the agent's departure.
  • Pareto Optimality (PO): No alternative grouping exists that makes at least one agent better off without making another worse off.

Algorithmic Methodology

The paper introduces two primary deterministic algorithms to address different stability requirements:

  1. Algorithm 1 (Greedy CNS): Designed for symmetric games, this approach assigns agents to groups if they have positive utility for at least one member. It prioritizes joining singletons to "lock in" stability early in the process.
  2. Algorithm 2 (Online Serial Dictatorship): This algorithm achieves Pareto Optimality in strict games. The first member of a coalition acts as a "gatekeeper" or dictator; subsequent agents are only permitted to join if the founder approves.

To establish impossibility results, the authors employ Yao’s Principle. This principle demonstrates that if no deterministic algorithm can succeed on a specific distribution of inputs, then no randomized algorithm can guarantee success either.

Key Results and Dichotomy

The research reveals a sharp dichotomy between achievable and impossible stability notions. A significant finding is the "Zero Utility Problem": the presence of neutral relationships (utility = 0) significantly complicates stability. In "Friends-Enemies-Neutrals" (FENG) games, even weak stability concepts become impossible to guarantee online.

Summary of existence results for online algorithms across different stability notions and game types.

As summarized in the table above:

  • Nash and Individual Stability are generally impossible to guarantee in online settings across most game types.
  • Contractual Nash Stability (CNS) is achievable for symmetric "friends and enemies" games (FEG/AEG) using the proposed greedy approach.
  • Pareto Optimality (PO) can be guaranteed for "Strict" games where no two agents are indifferent to one another.

The results are often "gapless," meaning that when a deterministic algorithm fails, the probability of any randomized algorithm succeeding drops to zero as the number of agents increases.

Discussion and Future Work

While the paper provides a comprehensive map of online stability, it highlights a fundamental trade-off between stability and social welfare. A partition may be stable simply because agents dislike all other options equally, even if their current utility is negative.

Future research directions include moving beyond single-agent stability to "Strong Stability," where sub-groups might defect together, and exploring non-additive utilities where agent preferences depend on group size thresholds rather than simple sums of individual relationships.

Summary updated

BibTeX
@inproceedings{bullinger2024stability,
  author = {Martin Bullinger and René Romen},
  title = {{Stability in Online Coalition Formation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i9.28809},
}
Figure