Bribery in Path-Disruption Games
Bribery in Path-Disruption Games
复制标题
路径破坏游戏中的贿赂
DOI：
10.1007/978-3-642-24873-3_19
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
J. Rothe
中科院分区：
文献类型：
--
作者：
Anja Rey;J. Rothe
Bachrach和Porat [1]在这些联盟游戏中引入了路径干扰游戏。这样做，如果代理商成功地阻止了对手的所有路径，我们会赢得联盟的胜利。它是为了确定对手是否可以贿赂某些代理，从而使对手的所有路径都无法构成。 ，我们通过证明相应的问题在多项式层次结构的第二级中提供了上限，并且我们怀疑这是该类别的完整。
Bachrach and Porat [1] introduced path-disruption games. In these coalitional games, agents are placed on the vertices of a graph, and one or more adversaries want to travel from a source vertex to a target vertex. In order to prevent them from doing so, the agents can form coalitions, and a coalition wins if it succeeds in blocking all paths for the adversaries. In this paper, we introduce the notion of bribery for path-disruption games. We analyze the question of how hard it is to decide whether the adversaries can bribe some of the agents such that no coalition can be formed that blocks all paths for the adversaries. We show that this problem is NP-complete, even for a single adversary. For the case of multiple adversaries, we provide an upper bound by showing that the corresponding problem is in Σ2p, the second level of the polynomial hierarchy, and we suspect it is complete for this class.