Manipulating the Quota in Weighted Voting Games
Authors: Michael Zuckerman, Piotr Faliszewski, Yoram Bachrach, Edith Elkind
Abstract:
Weighted voting games provide a popular model of decision making
in multiagent 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 such games
is traditionally identified with her Shapley--Shubik index or her
Banzhaf index, two classical power measures that reflect
the player's marginal contributions under different coalition
formation scenarios. In this paper, we investigate by how
much the central authority can change a player's power,
as measured by these indices, by modifying the quota.
We provide tight upper and lower
bounds on the changes in the individual
player's power that can result from a change in quota. We also
study how the choice of quota can affect the relative power
of the players. From the algorithmic perspective,
we provide an efficient algorithm
for determining whether there is a value of the quota that makes
a given player a {\em dummy}, i.e., reduces his power
(as measured by both indices) to 0. On the other hand, we show that
checking which of the two values of the quota makes
this player more powerful is computationally hard, namely,
complete for the complexity class PP, which is
believed to be significantly more powerful than NP.