从少量观测中学习稀疏联盟收益，自动找出最优合作结构。
Sparse Probabilistic Coalition Structure Generation: Bayesian Greedy Pursuit and $\ell_1$ Relaxations
- 用稀疏线性回归建模每轮合作收益，只关注少数关键联盟。
- 当观测次数超过 $K \log m$ 时，可高概率恢复真实盈利联盟组。
- 适合联盟数量少但价值难测的场景，如资源分配、协同决策。
研究在联盟收益未知、需从有限轮次观测中学习的联盟结构生成问题。将每轮观测建模为稀疏线性回归：实际收益 $Y_t$ 是少数几个联盟贡献的带噪线性组合。提出概率化联盟结构生成框架：先从 $T$ 轮观测中估计稀疏价值函数，再基于推断出的联盟集求解最优结构。分析两种估计方法：一是贝叶斯贪婪联盟追踪（BGCP），其在相干性条件和最小信号假设下，当 $T \gtrsim K \log m$ 时能以高概率恢复真实盈利联盟集，实现福利最优；二是 $\ _1$ 正则化估计，在受限特征值条件下给出 $\ _1$ 和预测误差界，并转化为福利差距保证。对比基线方法，发现稀疏情形下该方法更优，而密集情形下传统最小二乘仍具竞争力。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。