Sparse Probabilistic Coalition Structure Generation: Bayesian Greedy Pursuit and $\ell_1$ Relaxations

• URL: http://arxiv.org/abs/2601.00329v1
• Date: Thu, 01 Jan 2026 12:50:56 GMT
• Title: Sparse Probabilistic Coalition Structure Generation: Bayesian Greedy Pursuit and $\ell_1$ Relaxations
• Abstract summary: 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.
• Score: 11.62669179647184
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study coalition structure generation (CSG) when coalition values are not given but must be learned from episodic observations. 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. 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. We analyse two estimation schemes. The first, Bayesian Greedy Coalition Pursuit (BGCP), is a greedy procedure that mimics orthogonal matching pursuit. Under a coherence condition and a minimum signal assumption, BGCP recovers the true set of profitable coalitions with high probability once \(T \gtrsim K \log m\), and hence yields welfare-optimal structures. The second scheme uses an \(\ell_1\)-penalised estimator; under a restricted eigenvalue condition, we derive \(\ell_1\) and prediction error bounds and translate them into welfare gap guarantees. We compare both methods to probabilistic baselines and identify regimes where sparse probabilistic CSG is superior, as well as dense regimes where classical least-squares approaches are competitive.

Related papers

• CRPS-Optimal Binning for Conformal Regression [0.0]
  We propose a method for non-parametric conditional distribution estimation based on partitioning co-sorted observations into contiguous bins.<n>We form two complementary predictive objects: the Venn prediction band and a conformal prediction set based on CRPS as the nonconformity score.
  arXiv  Detail & Related papers  (2026-03-23T14:07:09Z)
• 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)
• Almost Asymptotically Optimal Active Clustering Through Pairwise Observations [59.20614082241528]
  We propose a new analysis framework for clustering $M$ items into an unknown number of $K$ distinct groups using noisy and actively collected responses.<n>We establish a fundamental lower bound on the expected number of queries needed to achieve a desired confidence in the accuracy of the clustering.<n>We develop a computationally feasible variant of the Generalized Likelihood Ratio statistic and show that its performance gap to the lower bound can be accurately empirically estimated.
  arXiv  Detail & Related papers  (2026-02-05T14:16:47Z)
• Bayesian Recovery for Probabilistic Coalition Structures [11.62669179647184]
  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.
  arXiv  Detail & Related papers  (2025-12-25T13:03:07Z)
• Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities [51.320599504997745]
  Predictions from statistical physics postulate that recovery of the communities in Block Model (SBM) is possible in time above, and only above, the KestenStigum (KS) threshold.<n>Chin et al.(2025) recently prove that, in a sparse regime, community recovery in time is possible below the KS threshold by counting nonbacktracking paths.
  arXiv  Detail & Related papers  (2025-09-19T09:53:56Z)
• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  We study the problem of clustering $T$ trajectories of length $H$, each generated by one of $K$ unknown ergodic Markov chains over a finite state space of size $S$.<n>We derive an instance-dependent, high-probability lower bound on the clustering error rate, governed by the weighted KL divergence between the transition kernels of the chains.<n>We then present a novel two-stage clustering algorithm.
  arXiv  Detail & Related papers  (2025-06-02T05:10:40Z)
• Convergence Rates of Constrained Expected Improvement [11.79168261900291]
  Constrained expected improvement (CEI) is a commonly used CBO method for black-box optimization with constraints.<n>We study the convergence rate of CEI by analyzing its simple regret upper bound.<n>We show that when $f$ and $c$ are assumed to be sampled from Gaussian processes, CEI achieves the same convergence rates with a high probability.
  arXiv  Detail & Related papers  (2025-05-16T14:44:13Z)
• Beyond likelihood ratio bias: Nested multi-time-scale stochastic approximation for likelihood-free parameter estimation [49.78792404811239]
  We study inference in simulation-based models where the analytical form of the likelihood is unknown.<n>We use a ratio-free nested multi-time-scale approximation (SA) method that simultaneously tracks the score and drives the parameter update.<n>We show that our algorithm can eliminate the original bias $Obig(sqrtfrac1Nbig)$ and accelerate the convergence rate from $Obig(beta_k+sqrtfracalpha_kNbig)$.
  arXiv  Detail & Related papers  (2024-11-20T02:46:15Z)
• $\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)
• QuACS: Variational Quantum Algorithm for Coalition Structure Generation in Induced Subgraph Games [0.0]
  We propose a novel hybrid quantum classical algorithm for Coalition Structure Generation in Induced Subgraph Games (ISGs) We show that the proposed algorithm outperforms existing approximate classical solvers with a runtime of $mathcalO(n2)$ and an expected approximation ratio of $92%$. It requires a significantly lower number of qubits and allows experiments on medium-sized problems compared to existing quantum solutions.
  arXiv  Detail & Related papers  (2023-04-14T16:01:27Z)
• 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)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  We introduce the expected co-coercivity condition, explain its benefits, and provide the first last-iterate convergence guarantees of SGDA and SCO. We prove linear convergence of both methods to a neighborhood of the solution when they use constant step-size. Our convergence guarantees hold under the arbitrary sampling paradigm, and we give insights into the complexity of minibatching.
  arXiv  Detail & Related papers  (2021-06-30T18:32:46Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  This paper analyzes the trajectories of gradient descent (SGD) We show that SGD avoids saddle points/manifolds with $1$ for strict step-size policies.
  arXiv  Detail & Related papers  (2020-06-19T14:11: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.