Near-Optimal Coalition Structures in Polynomial Time
This provides a rigorous probabilistic separation for anytime algorithms in coalition formation, which is incremental but offers practical efficiency gains for applications like multi-agent systems.
The paper tackles the coalition structure generation problem by comparing three algorithmic paradigms, proving that sparse relaxations achieve near-optimal welfare in polynomial time with high probability under a random model, while dynamic programming and MILP methods require exponential time for similar quality.
We study the classical coalition structure generation (CSG) problem and compare the anytime behavior of three algorithmic paradigms: dynamic programming (DP), MILP branch-and-bound, and sparse relaxations based on greedy or $l_1$-type methods. Under a simple random "sparse synergy" model for coalition values, we prove that sparse relaxations recover coalition structures whose welfare is arbitrarily close to optimal in polynomial time with high probability. In contrast, broad classes of DP and MILP algorithms require exponential time before attaining comparable solution quality. This establishes a rigorous probabilistic anytime separation in favor of sparse relaxations, even though exact methods remain ultimately optimal.