Manipulating the quota in weighted voting games

摘要

Weighted voting games provide a simple model of decision-making in human societies and multi-agent systems. Such games are described by a set of players, a list of playersʼ weights, and a quota; a coalition of the players is said to be winning if the total weight of its members meets or exceeds the quota. The power of a player in a weighted voting game is traditionally identified with her Shapley–Shubik index or her Banzhaf index, two classic power measures that reflect the playerʼs marginal contribution under different coalition formation scenarios. In this paper, we investigate by how much one can change a playerʼs power, as measured by these indices, by modifying the quota. We give tight bounds on the changes in the individual playerʼs power that can result from a change in quota. We then describe an efficient algorithm for determining whether there is a value of the quota that makes a given player a dummy, i.e., reduces her power (as measured by both indices) to 0. We also study how the choice of quota can affect the relative power of the players. Finally, we investigate scenarios where oneʼs choice in setting the quota is constrained. We show that optimally choosing between two values of the quota is complete for the complexity class PP, which is believed to be significantly more powerful than NP. On the other hand, we empirically demonstrate that even small changes in quota can have a significant effect on a playerʼs power.