Research map / Multi-agent systems and games / Games and equilibria
Deviate or Not: Learning Coalition Structures with Multiple-bit Observations in Games
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 coalition structure learning under a multiple-bit deviation oracle, designing game sequences (normal-form, congestion, graphical, auction) that recover the hidden coalition structure in near-optimal numbers of rounds.
Problem
Learning a hidden coalition structure among n strategic agents by actively designing games and observing which agents would deviate from specified strategies; prior single-bit oracle methods need Theta(n log n) rounds.
Approach
Replace the single-bit NE oracle with an n-bit deviation oracle and design products of directed prisoner's dilemmas (or Braess's paradoxes, auction gadgets) so that many agents' bits are informative in parallel, enabling simultaneous binary search that matches an information-theoretic lower bound.
Key results
- Normal-form games: simultaneous binary search learns the coalition structure in log2 n + 2 rounds, matching the log2 n - O(log log n) lower bound up to small terms.
- Graphical degree-d games: algorithm uses 2n/d + 2 log2 d + 1 rounds, matching the ceil((n-1)/d) lower bound up to a constant factor.
- Second-price auctions with personalized reserves: (1 + log2 n)(1 + c) + 1 rounds, where c is the largest coalition size, close to the lower bound when coalitions are small.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use multiple-bit observations with simultaneous binary search in normal-form games | Coalition Structure Learning · Normal-form games | rounds: \Theta(n \log n) -> \log_2 n + 2 | Helped |
| Use directed Braess's paradoxes with simultaneous binary search | Coalition Structure Learning · Congestion games | rounds: \log_2 n + 2 | Helped |
| Use block decomposition with simultaneous binary search | Coalition Structure Learning · Degree-d graphical games | rounds: 2n/d+2\log_2 d + 1 | Helped |
| Use bitwise search with auction gadgets | Coalition Structure Learning · Auctions | rounds: (1+\log_2n)(1+c)+1 | Helped |
| Use iterative location with auction gadgets instead of bitwise search | Coalition Structure Learning · Auctions | rounds: n - 1 vs. (1+\log_2n)(1+c)+1 | Mixed |
Limitations
- Assumes agents coordinate perfectly within coalitions and are rational; agents' full behavior model is not modeled
- Auction result only near-optimal for small coalitions; gap to lower bound when coalitions are large
- Does not consider dynamic coalitions, strategic awareness of the algorithm, noisy observations, or partial observation of agents
Experimental setup
Metrics: number of query rounds information-theoretic lower bound matching
Baselines: single-bit CSL algorithm (Theta(n log n) rounds)
Builds on: Coalition structure learning with single-bit observation (prior CSL work) Inverse game theory
Closest papers by meaning
- Learning Coalition Structures with Games (AAAI 2024 · similarity 0.94)
- Online Learning of Coalition Structures by Selfish Agents (AAAI 2025 · similarity 0.89)
- Learning in Online Principal-Agent Interactions: The Power of Menus (AAAI 2024 · similarity 0.87)
- Aligning Individual and Collective Objectives in Multi-Agent Cooperation (NeurIPS 2024 · similarity 0.86)
- Playing Markov Games Without Observing Payoffs (NeurIPS 2026 · similarity 0.86)
- Multi-agent cooperation through learning-aware policy gradients (ICLR 2025 · 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.