用贝叶斯方法更可靠地恢复最优联盟结构。
Bayesian Recovery for Probabilistic Coalition Structures
- 将联盟结构建模为稀疏系数向量，利用贝叶斯学习进行恢复。
- 在重叠联盟导致近似重复列的情况下，传统方法易误选，而贝叶斯方法渐近正确。
- 适合关注联盟生成与稀疏恢复理论的读者。
概率联盟结构生成（PCSG）是NP难问题，可通过联盟-关联设计将联盟结构表示为稀疏系数向量，转化为$l_0$型稀疏恢复问题。一个自然问题是：标准稀疏方法如$l_1$松弛和贪婪算法能否在此设定下可靠恢复最优联盟结构？我们发现，在受PCSG启发的场景中，重叠联盟产生高度相关、近乎重复的列，导致设计不满足不可表示性条件，且$k$步正交匹配追踪（OMP）存在非零不可逆误选概率。相比之下，我们证明在相同结构假设下，具有高斯-伽马层级的稀疏贝叶斯学习（SBL）具有一致支持性。SBL产生的凹稀疏惩罚抑制虚假近似重复，使真实联盟支撑集恢复概率趋于1。这在凸优化、贪婪与贝叶斯稀疏方法之间建立了严格区分。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。