Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/98888
Title: Manipulating the quota in weighted voting games
Authors: Zuckerman, Michael
Faliszewski, Piotr
Bachrach, Yoram
Elkind, Edith
Issue Date: 2012
Source: Zuckerman, M., Faliszewski, P., Bachrach, Y.,& Elkind, E. (2012). Manipulating the quota in weighted voting games. Artificial Intelligence, 180-181, 1-19.
Series/Report no.: Artificial intelligence
Abstract: 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.
URI: https://hdl.handle.net/10356/98888
http://hdl.handle.net/10220/12585
ISSN: 0004-3702
DOI: http://dx.doi.org/10.1016/j.artint.2011.12.003
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SPMS Journal Articles

Google ScholarTM

Check

Altmetric

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.