Research map / Bandits and online learning / Online convex optimization and games
Online Learning of Coalition Structures by Selfish Agents
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.
Introduces online learning of Nash-stable coalition structures in additively separable hedonic games with selfish agents sharing a data platform, and proposes UCB-NS achieving polynomial-in-n, near-optimal Nash regret under semi-bandit and bandit feedback.
Problem
Agents with initially unknown symmetric preferences must learn them online while forming coalitions, and the goal is to reach approximately Nash stable partitions with low regret and sample complexity, despite exponential joint strategy spaces.
Approach
Model online coalition formation as a sequence of potential games; optimistic UCB estimates of preferences (per-coalition under bandit feedback, per-pair under semi-bandit feedback) induce a potential game each round, and an approximate better-response dynamics finds an epsilon-Nash stable strategy in polynomially many steps, avoiding dependence on the size of the joint strategy space.
Key results
- UCB-NS achieves Nash regret of O~(sqrt(T)) under semi-bandit feedback (O(sqrt(n^3 T log(n^2 T/δ)))) and bandit feedback (with an extra sqrt(n^3) factor), theoretically.
- Sample complexity O(1/ε^2) for obtaining an ε-Nash stable strategy, optimal up to logarithmic factors under both feedback models.
- epsilon-better-response dynamics converges to an epsilon-NS strategy in at most ceil(nW/ε) steps, polynomial in n, avoiding exponential dependence on joint strategy space.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use UCB-NS with bandit feedback | Online learning in symmetric ASHGs · Bandit feedback | Nash regret: O(√(n³T log(n²T/δ)(√n³ + 1))) | Helped |
| Use UCB-NS with semi-bandit feedback | Online learning in symmetric ASHGs · Semi-bandit feedback | Nash regret: O(√(n³T log(n²T/δ))) | Helped |
| Use UCB-NS under bandit or semi-bandit feedback | Online learning in symmetric ASHGs · Bandit and semi-bandit feedback | Sample complexity: O(1/ε2) | Helped |
Surprising findings
- Despite less information under bandit feedback, the Nash regret and sample complexity bounds match the optimal order up to logarithmic factors under both feedback models.
- Approximate better-response dynamics avoids the exponential-steps convergence issue of exact Nash dynamics in symmetric ASHGs, which is PLS-complete.
Limitations
- Purely theoretical; no experiments reported in the main text.
- Assumes symmetric preferences and a shared data platform; distributed setting left to future work.
Experimental setup
Metrics: Nash regret sample complexity
Baselines: Liu et al. 2021b UCB method for potential games Cui et al. 2022 congestion game UCB
Builds on: Liu et al. 2021b potential games with collective data utilization Bogomolnaia and Jackson additively separable hedonic games Ding et al. 2022 Nash regret Cohen and Agmon 2024b online learning in hedonic games
Closest papers by meaning
- Deviate or Not: Learning Coalition Structures with Multiple-bit Observations in Games (AAAI 2025 · similarity 0.89)
- Stability in Online Coalition Formation (AAAI 2024 · similarity 0.89)
- Multi-agent cooperation through learning-aware policy gradients (ICLR 2025 · similarity 0.88)
- Learning Coalition Structures with Games (AAAI 2024 · similarity 0.88)
- Impact of Decentralized Learning on Player Utilities in Stackelberg Games (ICML 2024 · similarity 0.87)
- No-regret Learning in Harmonic Games: Extrapolation in the Face of Conflicting Interests (NeurIPS 2024 · similarity 0.86)
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.