Measuring power in coalitional games with friends, enemies and allies
Measuring power in coalitional games with friends, enemies and allies
复制标题
衡量与朋友、敌人和盟友的联盟博弈中的力量
DOI：
10.1016/j.artint.2022.103792
复制
发表时间：
2022
影响因子：
14.4
通讯作者：
Yokoo Makoto
中科院分区：
文献类型：
--
作者：
Skibski Oskar;Suzuki Takamasa;Grabowski Tomasz;Sakurai Yuko;Michalak Tomasz;Yokoo Makoto
我们将由Myerson提出的著名的图约束博弈模型推广到有符号图。在我们的模型中，不仅可以明确定义一些玩家是朋友（就像Myerson的模型），还可以明确定义一些其他玩家是敌人。因此，我们的游戏可以表达更广泛的情况，例如政党之间的敌意。我们使用遵循著名的Myerson值描述的公理方法来定义有符号图形游戏的值。在此基础上，我们提出了一种计算任意半值的算法，包括我们提出的Myerson值的扩展。对于有界树宽的有符号图，我们还开发了加权投票博弈中幂指标的伪多项式算法。此外，我们考虑了玩家之间具有先验定义联盟（联盟）的签名图形游戏，并提出了计算欧文值在该设置下的扩展的算法。
We extend the well-known model of graph-restricted games due to Myerson to signed graphs. In our model, it is possible to explicitly define not only that some players are friends (as in Myerson's model) but also that some other players are enemies. As such our games can express a wider range of situations, e.g., animosities between political parties. We define the value for signed graph games using the axiomatic approach that closely follows the celebrated characterization of the Myerson value. Furthermore, we propose an algorithm for computing an arbitrary semivalue, including the extension of the Myerson value proposed by us. We also develop a pseudo-polynomial algorithm for power indices in weighted voting games for signed graphs with bounded treewidth. Moreover, we consider signed graph games with a priori defined alliances (unions) between players and propose algorithms to compute the extension of the Owen value to this setting.