The Shapley value for cooperative games under precedence constraints
The Shapley value for cooperative games under precedence constraints
复制标题
DOI：
10.1007/bf01258278
复制
发表时间：
1992-09
影响因子：
0.6
通讯作者：
U. Faigle;W. Kern
中科院分区：
文献类型：
--
作者：
U. Faigle;W. Kern
在合作博弈中，只有那些尊重特定优先级结构的玩家联盟才是可行的。在经典对称公理的基础上，我们得到了在该模型中产生唯一Shapley值的三个公理。Shapley值反映了参与者对可行随机联盟的期望边际贡献，这使得我们可以不确定地评估Shapley值。我们证明了Shapley值的每个精确算法都需要在经典情况下的指数数量的操作，即使是对简单游戏的限制通常也是#P-hard。此外，我们还概述了Hsiao和Raghavan的多选择合作博弈在我们的背景下是如何处理的，这导致Shapley值不依赖于预先分配的权重。最后，讨论了Shapley值与Gilles、Owen和van den Brink的许可值之间的关系。两者都涉及合作博弈的形式上相似的模型，但反映了对优先约束的互补解释，因此产生了根本不同的解决方案概念。
Cooperative games are considered where only those coalitions of players are feasible that respect a given precedence structure on the set of players. Strengthening the classical symmetry axiom, we obtain three axioms that give rise to a unique Shapley value in this model. The Shapley value is seen to reflect the expected marginal contribution of a player to a feasible random coalition, which allows us to evaluate the Shapley value nondeterministically. We show that every exact algorithm for the Shapley value requires an exponential number of operations already in the classical case and that even restriction to simple games is #P-hard in general. Furthermore, we outline how the multi-choice cooperative games of Hsiao and Raghavan can be treated in our context, which leads to a Shapley value that does not depend on pre-assigned weights. Finally, the relationship between the Shapley value and the permission value of Gilles, Owen and van den Brink is discussed. Both refer to formally similar models of cooperative games but reflect complementary interpretations of the precedence constraints and thus give rise to fundamentally different solution concepts.