Path-Disruption Games: Bribery and a Probabilistic Model
Path-Disruption Games: Bribery and a Probabilistic Model
复制标题
路径破坏博弈：贿赂和概率模型
DOI：
10.1007/s00224-016-9669-1
复制
发表时间：
2017
影响因子：
0.5
通讯作者：
A. Marple
中科院分区：
文献类型：
--
作者：
A. Rey;J. Rothe;A. Marple
路径中断博弈（Path-disruption games）是最近由Bachrach和Porat提出的一种在图上进行的联盟博弈，其中一个或多个对手每个都试图从给定的源顶点到达给定的目标顶点，而代理联盟则试图通过阻止每个对手从源到目标的每条路径来防止这种情况发生。例如，这些联盟游戏模拟了计算机网络中的安全问题。受投票中贿赂的启发，我们引入了贿赂的概念，路径中断游戏。我们分析了这样一个问题，即决定对手是否可以贿赂一些代理人，从而不会形成阻止他们所有路径的联盟，这有多难。我们表明，这个问题是NP-完全的一个单一的对手和完整的，第二层次的多项式，多个对手的情况下。我们还通过允许目标的不确定性来扩展模型：在概率路径中断游戏中，我们为每个顶点分配对手想要到达它的概率，并且我们研究了与常见解决方案概念（例如核心和ε-核心）相关的问题的复杂性以及此类游戏的其他属性。
Path-disruption games, recently introduced by Bachrach and Porat, are coalitional games played on graphs where one or multiple adversaries each seeks to reach a given target vertex from a given source vertex, while a coalition of agents seeks to prevent that from happening by blocking every path from the source to the target for each adversary. These coalitional games model, for instance, security issues in computer networks. Inspired by bribery in voting, 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 will form that blocks all paths for them. We show that this problem is NP-complete for a single adversary and complete for, the second level of the polynomial hierarchy, for the case of multiple adversaries. We also expand the model by allowing uncertainty about the targets: In probabilistic path-disruption games, we assign to each vertex the probability that an adversary wants to reach it, and we study the complexity of problems related to common solution concepts (such as the core and theε-core) and other properties of such games.
登录
查看更多内容
巴克林的操纵、贿赂和竞选管理的复杂性以及后备投票
影响因子：
1.9
作者：
P. Faliszewski;Y. Reisch;J. Rothe;L. Schend
通讯作者：
L. Schend
路径破坏游戏中的贿赂
DOI：
10.1007/978-3-642-24873-3_19
发表时间：
2011
期刊：
ArXiv
影响因子：
--
作者：
Anja Rey;J. Rothe
通讯作者：
J. Rothe
迷宫识别自动机和非确定性磁带复杂性
DOI：
10.1016/s0022-0000(73)80031-5
发表时间：
1973
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
W. Savitch
通讯作者：
W. Savitch
批准驱动的投票规则下的竞选管理
影响因子：
1.1
作者：
Ildikó Schlotter;Piotr Faliszewski;Edith Elkind
通讯作者：
Edith Elkind
面向敌人的享乐博弈中存在极稳定分区和严格核心稳定联盟结构的复杂性
影响因子：
1.2
作者：
Anja Rey;J. Rothe;Hilmar Schadrack;Lena Schend
通讯作者：
Lena Schend