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...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2013
|
| Online Access: | https://hdl.handle.net/10356/98888 http://hdl.handle.net/10220/12585 |
| _version_ | 1811687886481784832 |
|---|---|
| author | Zuckerman, Michael Faliszewski, Piotr Bachrach, Yoram Elkind, Edith |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Zuckerman, Michael Faliszewski, Piotr Bachrach, Yoram Elkind, Edith |
| author_sort | Zuckerman, Michael |
| collection | NTU |
| description | 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. |
| first_indexed | 2024-10-01T05:23:26Z |
| format | Journal Article |
| id | ntu-10356/98888 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T05:23:26Z |
| publishDate | 2013 |
| record_format | dspace |
| spelling | ntu-10356/988882020-03-07T12:34:44Z Manipulating the quota in weighted voting games Zuckerman, Michael Faliszewski, Piotr Bachrach, Yoram Elkind, Edith School of Physical and Mathematical Sciences 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. 2013-07-31T04:03:24Z 2019-12-06T20:00:50Z 2013-07-31T04:03:24Z 2019-12-06T20:00:50Z 2012 2012 Journal Article Zuckerman, M., Faliszewski, P., Bachrach, Y.,& Elkind, E. (2012). Manipulating the quota in weighted voting games. Artificial Intelligence, 180-181, 1-19. 0004-3702 https://hdl.handle.net/10356/98888 http://hdl.handle.net/10220/12585 10.1016/j.artint.2011.12.003 en Artificial intelligence |
| spellingShingle | Zuckerman, Michael Faliszewski, Piotr Bachrach, Yoram Elkind, Edith Manipulating the quota in weighted voting games |
| title | Manipulating the quota in weighted voting games |
| title_full | Manipulating the quota in weighted voting games |
| title_fullStr | Manipulating the quota in weighted voting games |
| title_full_unstemmed | Manipulating the quota in weighted voting games |
| title_short | Manipulating the quota in weighted voting games |
| title_sort | manipulating the quota in weighted voting games |
| url | https://hdl.handle.net/10356/98888 http://hdl.handle.net/10220/12585 |
| work_keys_str_mv | AT zuckermanmichael manipulatingthequotainweightedvotinggames AT faliszewskipiotr manipulatingthequotainweightedvotinggames AT bachrachyoram manipulatingthequotainweightedvotinggames AT elkindedith manipulatingthequotainweightedvotinggames |