Bayesian Recovery for Probabilistic Coalition Structures
This work addresses a theoretical bottleneck in coalition formation for multi-agent systems, establishing a rigorous separation between sparse recovery methods, which is incremental as it builds on existing PCSG and sparse recovery frameworks.
The paper tackled the problem of recovering optimal coalition structures in Probabilistic Coalition Structure Generation (PCSG), showing that standard sparse methods like $l_1$ relaxations and greedy pursuits fail under high coherence conditions, while Sparse Bayesian Learning (SBL) achieves support consistency with probability tending to one.
Probabilistic Coalition Structure Generation (PCSG) is NP-hard and can be recast as an $l_0$-type sparse recovery problem by representing coalition structures as sparse coefficient vectors over a coalition-incidence design. A natural question is whether standard sparse methods, such as $l_1$ relaxations and greedy pursuits, can reliably recover the optimal coalition structure in this setting. We show that the answer is negative in a PCSG-inspired regime where overlapping coalitions generate highly coherent, near-duplicate columns: the irrepresentable condition fails for the design, and $k$-step Orthogonal Matching Pursuit (OMP) exhibits a nonvanishing probability of irreversible mis-selection. In contrast, we prove that Sparse Bayesian Learning (SBL) with a Gaussian-Gamma hierarchy is support consistent under the same structural assumptions. The concave sparsity penalty induced by SBL suppresses spurious near-duplicates and recovers the true coalition support with probability tending to one. This establishes a rigorous separation between convex, greedy, and Bayesian sparse approaches for PCSG.