- 简介在合作博弈理论中，主要关注的是代理人之间的公平分配收益或成本。然而，在合作博弈的实际应用中，准确地表示游戏是具有挑战性的。在这种情况下，使用对游戏中微小扰动敏感的分配方法可能会导致各种问题，包括代理人的不满和代理人寻求最大化自己利益的操纵可能性。因此，分配方法必须对游戏扰动具有鲁棒性。 在本研究中，我们探讨了优化博弈，其中特征函数的值作为优化问题的最优值提供。为了评估分配方法的鲁棒性，我们使用了Lipschitz常数，该常数量化了分配向量在对基础问题的权重向量进行单位扰动的响应中的变化程度。然后，我们提供了一个匹配博弈的算法，该算法返回属于$\left(\frac{1}{2}-\epsilon\right)$-近似核心的分配，并具有Lipschitz常数$O(\epsilon^{-1})$。此外，我们提供了一种最小生成树博弈的算法，该算法返回属于$4$-近似核心的分配，并具有一个常数Lipschitz常数。 Shapley值是一种流行的分配方法，满足几个理想属性。因此，我们研究了Shapley值的鲁棒性。我们证明了最小生成树的Shapley值的Lipschitz常数是常数，而匹配博弈的Lipschitz常数为$\Omega(\log n)$，其中$n$表示顶点数。
- 图表
- 解决问题研究优化博弈中的分配问题的鲁棒性，特别是对于游戏扰动的敏感性
- 关键思路使用Lipschitz常数评估分配方法的鲁棒性，并提出了适用于匹配游戏和最小生成树游戏的算法
- 其它亮点提出了用于优化博弈的分配问题的新的评估方法，并探讨了Shapley值的鲁棒性。对于最小生成树游戏，Shapley值的Lipschitz常数是常数级别的，而对于匹配游戏，则是对数级别的。
- 相关论文包括：'On the Robustness of Shapley Values', 'The Core of a Matching Game with Interdependent Preferences', 'The Approximate Core of Large Games and an Algorithmic Framework for Cooperative Games'
提问交流