False-Name Manipulations in Weighted Voting Games
False-Name Manipulations in Weighted Voting Games
复制标题
DOI：
10.1613/jair.3166
复制
发表时间：
2011-01-01
影响因子：
5
通讯作者：
Paterson, Mike
中科院分区：
文献类型：
--
作者：
Aziz, Haris;Bachrach, Yoram;Paterson, Mike
加权投票是决策领域中多个智能体之间合作的经典模型。在这样的游戏中，每个玩家都有一个重量，如果一个玩家联盟的总重量达到或超过给定的配额，就会赢得比赛。在这类游戏中，玩家的力量通常与他的体重不成正比，而是由权力指数来衡量，其中最突出的是Shapley-Shubik指数和Banzhaf指数。在本文中，我们调查了玩家通过假名操纵，即在两个或多个身份之间分割他的权重，可以在多大程度上改变他的力量，通过Shapley-Shubik指数或Banzhaf指数来衡量。对于这两个指标，我们给出了权重拆分效果的上下界。然后，我们证明了检查是否存在有益分裂是NP难的，并讨论了该问题的受限情况下的有效算法，以及一般情况下的随机算法。我们还提供了对这些算法的实验评估。最后，我们检查了相关形式的操纵行为，如吞并，即一个玩家吞并其他玩家，或合并，其中多个玩家联合为一个。我们描述了这种操作的计算复杂性，并对它们的影响提供了限制。对于Banzhaf指数，我们描述了一个新的悖论，我们称之为吞并非单调性悖论。
Weighted voting is a classic model of cooperation among agents in decision-making domains. In such games, each player has a weight, and a coalition of players wins the game if its total weight meets or exceeds a given quota. A player's power in such games is usually not directly proportional to his weight, and is measured by a power index, the most prominent among which are the Shapley-Shubik index and the Banzhaf index.In this paper, we investigate by how much a player can change his power, as measured by the Shapley-Shubik index or the Banzhaf index, by means of a false-name manipulation, i.e., splitting his weight among two or more identities. For both indices, we provide upper and lower bounds on the effect of weight-splitting. We then show that checking whether a beneficial split exists is NP-hard, and discuss efficient algorithms for restricted cases of this problem, as well as randomized algorithms for the general case. We also provide an experimental evaluation of these algorithms.Finally, we examine related forms of manipulative behavior, such as annexation, where a player subsumes other players, or merging, where several players unite into one. We characterize the computational complexity of such manipulations and provide limits on their effects. For the Banzhaf index, we describe a new paradox, which we term the Annexation Non-monotonicity Paradox.