Bayesian Recovery for Probabilistic Coalition Structures

• URL: http://arxiv.org/abs/2601.05273v1
• Date: Thu, 25 Dec 2025 13:03:07 GMT
• Title: Bayesian Recovery for Probabilistic Coalition Structures
• Abstract summary: Probabilistic Coalition Structure Generation (PCSG) is NP-hard and can be recast as an $l_0$-type sparse recovery problem.<n>We show that the answer is negative in a PCSG-inspired regime where overlapping coalitions generate highly coherent, near-duplicate columns.<n>We prove that Sparse Bayesian Learning with a Gaussian-Gamma hierarchy is support consistent under the same structural assumptions.
• Score: 11.62669179647184
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• The Expressivity Boundary of Probabilistic Circuits: A Comparison with Large Language Models [49.67598869075125]
  In autoregressive language modeling, Probabilistic Circuits (PCs) lag behind Transformer-based large language models (LLMs)<n>We show that structured-decomposable PCs can match Transformer separation rank on vtree-aligned partitions, but that this capacity is limited to partitions aligned with the fixed routing structure.<n>We further prove that decomposable PCs are strictly more expressive than structured-decomposable ones, though effectively optimizing them remains an open challenge.
  arXiv  Detail & Related papers  (2026-05-13T03:22:10Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• Anchored Policy Optimization: Mitigating Exploration Collapse Via Support-Constrained Rectification [14.911955979675772]
  We propose Anchored Policy Optimization (APO) to shift the paradigm from global Shape Matching to Support Coverage.<n>APO breaks the accuracy-diversity trade-off, significantly improving Pass@1 while restoring the Pass@K diversity typically lost by standard policy gradient methods.
  arXiv  Detail & Related papers  (2026-02-05T14:41:57Z)
• Sparse Probabilistic Coalition Structure Generation: Bayesian Greedy Pursuit and $\ell_1$ Relaxations [11.62669179647184]
  We study coalition structure generation (CSG) when coalition values are not given but must be learned from episodic observations.<n>We model each episode as a sparse linear regression problem, where the realised payoff (Y_t) is a noisy linear combination of a small number of coalition contributions.<n>This yields a probabilistic CSG framework in which the planner first estimates a sparse value function from (T) episodes, then runs a CSG solver on the inferred coalition set.
  arXiv  Detail & Related papers  (2026-01-01T12:50:56Z)
• Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities (II) [51.320599504997745]
  We show that when the number $K$ of communities remains smaller than $sqrtn$, non-trivial community recovery is possible in time above the Kesten--Stigum threshold.<n>We also show that, in moderately sparse settings, the optimal algorithms appear to be fundamentally different from spectral methods.
  arXiv  Detail & Related papers  (2025-11-26T15:54:17Z)
• Structured Prediction with Abstention via the Lovász Hinge [0.24578723416255752]
  We show that the Lov'asz hinge is inconsistent with its desired target unless the set function used for evaluation is modular.<n>We show that one can combine the binary encoding construction of Ramaswamy et al. with our link construction to achieve an efficient consistent surrogate for a natural multiclass of the structured abstain problem.
  arXiv  Detail & Related papers  (2025-05-09T21:29:22Z)
• Sparse PCA with Oracle Property [115.72363972222622]
  We propose a family of estimators based on the semidefinite relaxation of sparse PCA with novel regularizations. We prove that, another estimator within the family achieves a sharper statistical rate of convergence than the standard semidefinite relaxation of sparse PCA.
  arXiv  Detail & Related papers  (2023-12-28T02:52:54Z)
• Exploiting hidden structures in non-convex games for convergence to Nash equilibrium [62.88214569402201]
  A wide array of modern machine learning applications can be formulated as non-cooperative Nashlibria. We provide explicit convergence guarantees for both deterministic and deterministic environments.
  arXiv  Detail & Related papers  (2023-12-27T15:21:25Z)
• $\varepsilon$-fractional Core Stability in Hedonic Games [13.576268908412338]
  Hedonic Games (HGs) are a framework for modeling coalitions of strategic agents guided by their individual preferences. We propose the notion of $varepsilon$-fractional core-stability, where at most an $varepsilon$-fraction of all possible coalitions is allowed to formation core-block. Specifically, we design efficient algorithms returning an $varepsilon$-fractional core-stable partition, with $varepsilon$ exponentially decreasing in the number of agents.
  arXiv  Detail & Related papers  (2023-11-18T15:30:29Z)
• GCS-Q: Quantum Graph Coalition Structure Generation [0.0]
  This paper proposes GCS-Q, a novel quantum-supported solution for Induced Subgraph Games (ISGs) in coalition structure generation. We show that GCS-Q outperforms the currently best classical solvers with its runtime in the order of $n2$ and an expected worst-case approximation ratio of $93%$ on standard benchmark datasets.
  arXiv  Detail & Related papers  (2022-12-21T21:22:06Z)
• Will My Robot Achieve My Goals? Predicting the Probability that an MDP Policy Reaches a User-Specified Behavior Target [56.99669411766284]
  As an autonomous system performs a task, it should maintain a calibrated estimate of the probability that it will achieve the user's goal. This paper considers settings where the user's goal is specified as a target interval for a real-valued performance summary. We compute the probability estimates by inverting conformal prediction.
  arXiv  Detail & Related papers  (2022-11-29T18:41:20Z)
• Exact Recovery in the General Hypergraph Stochastic Block Model [92.28929858529679]
  This paper investigates fundamental limits of exact recovery in the general d-uniform hypergraph block model (d-HSBM) We show that there exists a sharp threshold such that exact recovery is achievable above the threshold and impossible below it.
  arXiv  Detail & Related papers  (2021-05-11T03:39:08Z)
• Preventing Posterior Collapse with Levenshtein Variational Autoencoder [61.30283661804425]
  We propose to replace the evidence lower bound (ELBO) with a new objective which is simple to optimize and prevents posterior collapse. We show that Levenstein VAE produces more informative latent representations than alternative approaches to preventing posterior collapse.
  arXiv  Detail & Related papers  (2020-04-30T13:27:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.