# Bayesian Recovery for Probabilistic Coalition Structures

arXiv: https://arxiv.org/abs/2601.05273 · HTML: https://mlsanity.com/paper/2601.05273/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 0 of its 6 references that are in the map.
- First posted on arXiv 25 Dec 2025.

## Abstract (arXiv)

Probabilistic Coalition Structure Generation (PCSG) is NP-hard and can be recast as an l0-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 l1 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.