Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2512.21657 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909975939383296 |
|---|---|
| author | Majumdar, Angshul |
| author_facet | Majumdar, Angshul |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_21657 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Near-Optimal Coalition Structures in Polynomial Time Majumdar, Angshul Computer Science and Game Theory Artificial Intelligence 91A12, 68T42, 90C27 G.1.6; F.2.2 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. |
| title | Near-Optimal Coalition Structures in Polynomial Time |
| topic | Computer Science and Game Theory Artificial Intelligence 91A12, 68T42, 90C27 G.1.6; F.2.2 |
| url | https://arxiv.org/abs/2512.21657 |