Bayesian Recovery for Probabilistic Coalition Structures Journal: Statistics and Probability Letters
Angshul Majumdar · 2026
Read Bayesian Recovery for Probabilistic Coalition Structures Journal: Statistics and Probability Letters by Angshul Majumdar (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-05273.txt.
Introduction
Angshul Majumdar's 2026 paper asks if stock tools from sparse signal work can find the best way to group agents. He finds they can not. The task, in which groups form with odds on their worth, is hard in the strong sense: no fast exact tool is thought to exist. It can be re-cast as a hunt for a sparse set of weights, one per group. That re-cast begs for the stock tools of signal work: loose fits and greedy picks.
Majumdar shows the tools break in a real-world case. When groups stack on top of each other, the weight grid gains near-twin rows. A key test for the loose fit then fails, and a stock greedy pick stalls in a way he can prove. The no-go steers folks who build group tools away from kit that looks sound but snaps where groups stack.
Catalog record
| CREATOR | Angshul Majumdar |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 19 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-05273
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Bayesian Recovery for Probabilistic Coalition Structures Journal: Statistics and Probability Letters Angshul Majumdar Abstract Probabilistic Coalition Structure Generation (PCSG) is NP–hard and can be recast as an ℓ 0 \ell_{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 ℓ 1 \ell_{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 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. 1 Introduction Coalition structure generation (CSG) is a fundamental optimisation problem in cooperative game theory: given a set of agents and a valuation function over coalitions, the goal is to partition the agents into coalitions so as to maximise the total value of the resulting coalition structure. It is well known that, under the standard representation, optimal CSG is NP–hard and admits no polynomial–time approximation scheme unless \mathrm{NP}=\mathrm{ZPP} [ 2 ] . The probabilistic variant, Probabilistic Coalition Structure Generation (PCSG), further complicates matters by introducing uncertainty in coalition values or agent availability, so that one seeks to maximise expected welfare rather than deterministic utility [ 1 ] . In both settings, exhaustive search over all partitions is infeasible even for moderate numbers of agents. A natural way to expose the combinatorial structure of PCSG is to embed it into a sparse optimisation framework. One may index all candidate coalitions and represent a coalition structure by a coefficient vector w^{\star} whose nonzero entries indicate the coalitions that participate in the structure. The welfare of a structure can then be expressed (or locally approximated) as a linear functional of w^{\star} , yielding a sparse linear model of the form y=Aw^{\star}+\varepsilon, where A is a coalition–incidence matrix, y encodes observed or expected valuations, and \varepsilon models noise or modelling error. In this formulation, optimal PCSG reduces to recovering the support of w^{\star} , which is an \ell_{0} –type combinatorial problem tightly linked to NP–hard subset selection. Two algorithmic paradigms are the most obvious candidates for tackling this \ell_{0} formulation. The first is to replace the \ell_{0} constraint by an \ell_{1} penalty, leading to the LASSO and related convex relaxations [ 3 ] . In classical sparse regression with suitably incoherent designs, \ell_{1} estimators enjoy sharp support recovery guarantees, provided an “irrepresentable condition” holds for the design matrix [ 6 ] . The second paradigm is greedy pursuit: Orthogonal Matching Pursuit (OMP) builds the support iteratively by adding one index at a time, guided by correlations with the current residual [ 5 ] . Under random, nearly orthogonal designs, OMP also achieves provable recovery with high probability. However, coalition incidence matrices induced by PCSG are far from incoherent. Extensive overlaps between coalitions yield highly correlated columns, including near–duplicate groups corresponding to structurally similar coalitions. In such regimes, the conditions underpinning the success of convex \ell_{1} relaxations and greedy methods are typically violated: the irrepresentable condition fails, and OMP can be misled by small noise perturbations when several coalitions have almost identical correlation with the residual. As a consequence, neither LASSO–type methods nor OMP can be expected to recover the optimal coalition structure reliably in the high–coherence regime that is most characteristic of PCSG. These observations motivate a move away from purely optimisation–based relaxations towards a fully probabilistic treatment of the sparse PCSG model. Sparse Bayesian Learning (SBL) provides such a framework by placing hierarchical Gaussian–Gamma priors over the coefficients, inducing an adaptive, concave sparsity penalty that is much closer in spirit to \ell_{0} than to \ell_{1} [ 4 ] . In this paper we adopt the SBL viewpoint for PCSG and show that, in a class of highly coherent, PCSG–inspired designs where both LASSO and OMP provably fail to achieve support consistency, the SBL maximum a posteriori estimator still recovers the true coalition structure with high probability. This yields a rigorous separation between Bayesian and non–Bayesian sparse methods in a setting that is both theoretically interesting and practically motivated by coalition formation under uncertainty. 2 PCSG-inspired sparse regression model We formalise here the sparse linear model that underlies our analysis and introduce the structural assumptions specific to PCSG. Let m denote the number of observable valuation coordinates and let p denote the number of candidate coalitions. We collect the contribution pattern of coalition j in a column vector a_{j}\in\mathbb{R}^{m} and form the coalition–incidence matrix A=[a_{1},\dots,a_{p}]\in\mathbb{R}^{m\times p}, with columns normalised so that \|a_{j}\|_{2}=1 for all j . A coalition structure is encoded by a coefficient vector w^{\star}\in\mathbb{R}^{p} , whose support S^{\star}:=\{j\in\{1,\dots,p\}:w^{\star}_{j}\neq 0\} indexes the coalitions present in the structure. We assume |S^{\star}|=k\ll p . The observed (or estimated) valuation vector y\in\mathbb{R}^{m} follows the linear–Gaussian model y=Aw^{\star}+\varepsilon,\qquad\varepsilon\sim\mathcal{N}(0,\sigma^{2}I_{m}), (2.1) with unknown noise variance \sigma^{2}>0 . Recovering the coalition structure reduces to recovering S^{\star} from (A,y) . A distinctive feature of PCSG is the presence of many highly overlapping coalitions. This induces strong correlations between the corresponding columns of A . We capture this via near-duplicate coalition groups . For each true index j\in S^{\star} we assume there exists a nonempty set G_{j}\subset\{1,\dots,p\}\setminus S^{\star} such that: 1. (Within-group coherence) For all \ell\in G_{j} , \langle a_{j},a_{\ell}\rangle\geq\rho_{\mathrm{in}}, with some \rho_{\mathrm{in}}\in(0,1) . 2. (Between-group separation) For all \ell\in G_{j} and all r\notin\{j\}\cup G_{j} , |\langle a_{\ell},a_{r}\rangle|\leq\rho_{\mathrm{out}}, where \rho_{\mathrm{out}}<\rho_{\mathrm{in}} is fixed. We are interested in a regime where near-duplicates become increasingly similar, in the sense that \rho_{\mathrm{in}}\to 1 as m grows, while \rho_{\mathrm{out}} remains bounded away from 1 . We work in a high-dimensional setting where p=p_{m} and k=k_{m} may grow with m , but sparsity is controlled: p_{m}\to\infty,\qquad k_{m}\to\infty,\qquad k_{m}\log p_{m}=o(m). Signal strength is regulated by a beta-min condition: there exists a sequence \beta_{\min}(m)>0 such that \min_{j\in S^{\star}}|w^{\star}_{j}|\geq\beta_{\min}(m),\qquad\beta_{\min}(m)\sqrt{\frac{m}{\log p_{m}}}\to\infty. We further assume a restricted eigenvalue condition on the true support: there exists \kappa>0 such that \|Au\|_{2}^{2}\;\geq\;\kappa\|u\|_{2}^{2}\quad\text{for all }u\in\mathbb{R}^{p}\text{ with }\mathrm{supp}(u)\subseteq S^{\star}. This allows strong correlations with near-duplicates while preventing exact multicollinearity among the true coalitions. All three estimators studied in this paper—the LASSO, k –step OMP, and the SBL maximum a posteriori estimator—are applied to the common model ( 2.1 ) under the structural assumptions above. Their respective support recovery properties in this PCSG-inspired regime are compared in the subsequent sections. 3 Failure of \ell_{1} and OMP in PCSG designs We now show that, under the PCSG–inspired design of Section 2 , neither (i) \ell_{1} –penalised least squares nor (ii) k –step Orthogonal Matching Pursuit (OMP) achieve support recovery consistency. The proofs rely directly on the near–duplicate coalition structure and require no assumptions beyond those stated earlier. Throughout, probabilities are taken with respect to the noise \varepsilon in ( 2.1 ), while A and w^{\star} are fixed. 3.1 \ell_{1} fails: irrepresentable condition violation Recall that \ell_{1} support recovery requires the