Research map / Learning theory and algorithms / Sample complexity
Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size
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 formation with bounded coalition size (C-Coalition Formation) in additively separable hedonic games, giving FPT algorithms for treewidth+C and vertex cover, W[1]-hardness results, and tight ETH lower bounds.
Problem
Maximizing utilitarian social welfare when partitioning agents (graph vertices) into coalitions of bounded maximum size C, in additively separable hedonic games; the problem is NP-hard even for C=3 and needs parameterized analysis.
Approach
Dynamic programming over nice tree decompositions that stores, per bag, one important C-partition per type (coloring of bag vertices plus coalition sizes), giving (tw·C)^O(tw) time; a vertex-cover algorithm with polynomial dependence on C; and matching ETH lower bounds and kernel/hardness results for the unweighted and weighted variants.
Key results
- Weighted C-Coalition Formation solvable in (tw·C)^O(tw) n^O(1) time via dynamic programming over nice tree decompositions.
- C-Coalition Formation is W[1]-hard parameterized by treedepth, and W[1]-hard parameterized by twin-cover number.
- Weighted C-Coalition Formation solvable in vc^O(vc) n^O(1) time; unless ETH fails, no (C·vc)^o(vc+C) algorithm exists for the unweighted problem.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Parameterize C-Coalition Formation by treewidth+C via bottom-up DP over nice tree decomposition (running time (tw·C)^O(tw) n^O(1)) | Weighted C-Coalition Formation · theoretical, parameterized by treewidth and C | running time (FPT membership) | Helped |
| Parameterize by treedepth alone (no bound on C) | C-Coalition Formation (unweighted) · theoretical, parameterized by treedepth | W[1]-hardness | Hurt |
| Parameterize by vertex cover number (polynomial dependence on C) | Weighted C-Coalition Formation · theoretical, parameterized by vertex cover number | running time (FPT membership) | Helped |
| Polynomial kernel parameterized by vertex cover number and C | C-Coalition Formation (unweighted) · theoretical, parameterized by vc and C | kernel size | Helped |
| Weights (weighted instead of unweighted edges) under vc+C parameterization | C-Coalition Formation · theoretical, parameterized by vc + C | polynomial kernel existence | Hurt |
Surprising findings
- Weighted version admits no polynomial kernel parameterized by vertex cover + C unless the polynomial hierarchy collapses, while the unweighted version does admit a polynomial kernel.
Limitations
- Tree-depth and twin-cover hardness results rule out FPT in tw alone and in twc, so the algorithms need the C dependence or vc-based structure.
- Weighted variant has no polynomial kernel, a barrier for kernelization.
- Results are theoretical; no empirical evaluation is reported.
Experimental setup
Builds on: additively separable hedonic games max utilitarian coalition formation FPT algorithm (treewidth) general factors W[1]-hardness
Closest papers by meaning
- Anytime Heuristic and Monte Carlo Methods for Large-Scale Simultaneous Coalition Structure Generation and Assignment (AAAI 2021 · similarity 0.87)
- Stability in Online Coalition Formation (AAAI 2024 · similarity 0.87)
- Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures (AAAI 2025 · similarity 0.87)
- Individually Stable Dynamics in Coalition Formation over Graphs (AAAI 2025 · similarity 0.86)
- Adaptive Manipulation for Coalitions in Knockout Tournaments (AAAI 2025 · similarity 0.84)
- The Complexity of Two-Team Polymatrix Games with Independent Adversaries (ICLR 2025 · similarity 0.84)
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.