Research map / Multi-agent systems and games / Games and equilibria
Stability in Online Coalition Formation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies online additively separable hedonic games where agents arrive sequentially and must be irrevocably assigned to coalitions, characterizing which stability and Pareto-optimality notions can be guaranteed by deterministic or randomized online algorithms.
Problem
Online coalition formation: agents arrive one at a time and must be irrevocably placed into coalitions, and the goal is to guarantee stable (or Pareto-optimal) partitions rather than maximize social welfare.
Approach
Shifts the online coalition formation objective from social welfare to stability concepts (Nash, individual, contractual, core, strict core) and Pareto optimality, giving a dichotomy: deterministic algorithms that maintain CNS on symmetric {-y,x}-ASHGs and PO on strict ASHGs, and Yao-principle impossibility results for randomized algorithms under other restrictions.
Key results
- Deterministic online algorithm always outputs contractually Nash-stable partitions for symmetric {-y,x}-ASHGs (includes FEGs and AEGs).
- Deterministic online serial-dictatorship algorithm always outputs Pareto-optimal partitions for strict ASHGs, hence also contractually individually stable partitions.
- No randomized online algorithm achieves nonzero guarantee for individual stability, core, or strict core on symmetric {-y,x}-ASHGs/AFGs/AEGs, and for CNS on symmetric AFGs; no deterministic algorithm achieves CIS on symmetric FENGs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the online algorithm for symmetric {-y,x}-ASHGs with y ≥ x > 0 | CNS online coalition formation · Symmetric {-y,x}-ASHGs, y ≥ x > 0 | CNS guarantee: always outputs a CNS partition | Helped |
| Restrict utility values to {-y,x}, with y ≥ x > 0, instead of symmetric AFG utilities | Online CNS coalition formation · Symmetric games | CNS guarantee: always outputs a CNS partition | Helped |
| Use online serial dictatorship for strict ASHGs | Pareto-optimal coalition formation · Strict ASHGs | Pareto-optimality guarantee: always outputs a PO partition | Helped |
| Allow utility value 0, moving from strict ASHGs to symmetric FENGs | Online CIS coalition formation · Symmetric FENGs | CIS guarantee: always outputs a CIS partition -> no deterministic online algorithm | Hurt |
| Allow symmetric AFGs as the input class for CNS | Online CNS coalition formation · Symmetric AFGs | CNS guarantee: always outputs a CNS partition -> W_CNS(ALG) = 0 | Hurt |
| Require individual stability rather than the guaranteed online CNS result | Online coalition formation in symmetric {-y,x}-ASHGs · Symmetric {-y,x}-ASHGs, x,y > 0 | IS guarantee: W_IS(ALG) = 0 | Hurt |
| Require core or strict-core stability online | Online coalition formation in symmetric AFGs · Symmetric AFGs | Core and strict core guarantee: W_CR(ALG) = 0; W_SCR(ALG) = 0 | Hurt |
| Use an online algorithm for strict ASHGs to obtain Pareto-optimal partitions | Online coalition formation · Strict ASHGs | CIS guarantee: always outputs a CIS partition | Helped |
Surprising findings
- Pareto optimality and contractual individual stability, which always exist offline, cannot be guaranteed online once zero utilities are allowed (symmetric FENGs).
- Negative results hold even though all constructed instances contain stable partitions in the relevant solution concept.
Limitations
- Positive results hold only for restricted utility classes (symmetric {-y,x}-ASHGs, strict ASHGs); many negative results for randomized algorithms.
- Algorithms may output partitions with negative social welfare, giving no welfare approximation guarantee.
Experimental setup
Metrics: worst-case probability of outputting a stable partition (gua
Builds on: additively separable hedonic games online matching ranking algorithm Yao's principle serial dictatorship
Closest papers by meaning
- Reaching Individually Stable Coalition Structures in Hedonic Games (AAAI 2021 · similarity 0.93)
- Single-Agent Dynamics in Additively Separable Hedonic Games (AAAI 2022 · similarity 0.92)
- Online Learning of Group-Stable Coalition Structures (NeurIPS 2026 · similarity 0.91)
- Individually Stable Dynamics in Coalition Formation over Graphs (AAAI 2025 · similarity 0.89)
- Online Learning of Coalition Structures by Selfish Agents (AAAI 2025 · similarity 0.89)
- Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size (AAAI 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.