Research map / Learning theory and algorithms / Submodular and game algorithms
Learning Coalition Structures with 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.
Introduces Coalition Structure Learning (CSL), recovering hidden coalitions by designing games and observing single-bit Nash equilibrium checks, with the Iterative Grouping algorithm achieving near-optimal sample complexity in normal-form, congestion, graphical games and auctions.
Problem
Agents in multi-agent systems form unknown coalitions that change equilibrium behavior; the goal is to recover the coalition structure by designing games and observing whether a pre-specified strategy profile is a Nash equilibrium, with low sample complexity.
Approach
Use normal-form gadgets (a Prisoner's-Dilemma-like game whose default profile is a NE iff two agents are in different coalitions) and products of gadgets to test many agent pairs in one game, combined with binary search to find coalition members, matching an information-theoretic lower bound of n log2 n up to low-order terms; extend to auctions via reserve-price gadgets and random valuations.
Key results
- AuctionIG empirical sample complexity at n=1000 with 99% correctness is 19510 (m~U[n]) and 7915 (m=n), versus a theoretical Markov-based bound of 4145767.
- Theoretical sample complexity of IG for normal-form, congestion, and graphical games is n log2 n + 3n, matching a lower bound of (1-o(1)) n log2 n.
- AuctionIG expected sample complexity is bounded by (4.16+o(1)) n log2 n for random valuations and exactly nH_n when m=n.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use AuctionIG instead of the Markov-inequality PAC bound | AuctionCSL with n = 1000 and m = 1 · 50% probability of correctness | sample complexity: 82916 -> 11306 | Helped |
| Use AuctionIG instead of the Markov-inequality PAC bound | AuctionCSL with n = 1000 and m = n · 90% probability of correctness | sample complexity: 414577 -> 7294 | Helped |
| Use AuctionIG instead of the Markov-inequality PAC bound | AuctionCSL with n = 1000 and m sampled from \mathcal U[n] · 99% probability of correctness | sample complexity: 4145767 -> 19510 | Helped |
| Use AuctionIG when m = n rather than the general random-valuation setting | AuctionCSL · m = n | expected sample complexity upper bound: (4.16 + o(1))n \log_2 n -> (0.70 + o(1))n \log_2 n | Helped |
Surprising findings
- Empirical AuctionIG sample complexity is far below the Markov-inequality-based PAC bound, which is very loose.
- Products of auctions are not auctions in general, so the normal-form gadget product approach cannot be directly reused for auctions.
Experimental setup
Metrics: sample complexity (number of auctions) expected sample complexity PAC sample complexity at 50%/90%/99% correctness
Baselines: pairwise testing over all agent pairs (n(n-1)/2 games)
Builds on: Empirical Game-Theoretic Analysis Braess's paradox graphical games second-price auctions with personalized reserves
Closest papers by meaning
- Deviate or Not: Learning Coalition Structures with Multiple-bit Observations in Games (AAAI 2025 · similarity 0.94)
- Online Learning of Coalition Structures by Selfish Agents (AAAI 2025 · similarity 0.88)
- DualGFL: Federated Learning with a Dual-Level Coalition-Auction Game (AAAI 2025 · similarity 0.87)
- Learning in Online Principal-Agent Interactions: The Power of Menus (AAAI 2024 · similarity 0.86)
- Optimizing the coalition gain in Online Auctions with Greedy Structured Bandits (NeurIPS 2024 · similarity 0.86)
- Stability in Online Coalition Formation (AAAI 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.