Worst-case Bounds on Power vs. Proportion in Weighted Voting Games with an Application to False-name Manipulation
Pages 99 - 135
Abstract
Weighted voting games apply to a wide variety of multi-agent settings. They enable the formalization of power indices which quantify the coalitional power of players. We take a novel approach to the study of the power of big vs. small players in these games. We model small (big) players as having single (multiple) votes. The aggregate relative power of big players is measured w.r.t. their votes proportion. For this ratio, we show small constant worst-case bounds for the Shapley-Shubik and the Deegan-Packel indices. In sharp contrast, this ratio is unbounded for the Banzhaf index. As an application, we define a false-name strategic normal form game where each big player may split its votes between false identities, and study its various properties. Together, our results provide foundations for the implications of players’ size, modeled as their ability to split, on their relative power.
References
[1]
Aziz, H., Bachrach, Y., Elkind, E., & Paterson, M. (2011). False-name manipulations in weighted voting games. <italic>Journal of Artificial Intelligence Research, 40</italic>, 57-93.
[2]
Bachrach, Y., Filmus, Y., Oren, J., & Zick, Y. (2016a). Analyzing power in weighted voting games with super-increasing weights. In <italic>Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Liverpool, UK, September 19-21, 2016, Proceedings</italic>. Springer.
[3]
Bachrach, Y., Filmus, Y., Oren, J., & Zick, Y. (2016b). A characterization of voting power for discrete weight distributions. In <italic>Proceedings of the 25th International Joint Conference on Artificial Intelligence</italic>. AAAI Press.
[4]
Bachrach, Y., Zadimoghaddam, M., & Key, P. (2011). A cooperative approach to collusion in auctions. <italic>SIGecom Exch., 10</italic> (1), 17-22.
[5]
Banzhaf III, J. F. (1964). Weighted voting doesn't work: A mathematical analysis. <italic>Rutgers Law Review, 19</italic>, 317-343.
[6]
Chang, P.-L., Chua, V., & Machover, M. (2006). L.S. Penrose's limit theorem: Tests by simulation. <italic>Mathematical Social Sciences, 51</italic>, 90-106.
[7]
Coleman, J. S. (1971). Control of collectivities and the power of a collectivity to act. In Liebermann, B. (Ed.), <italic>Social Choice</italic>, pp. 269-300. Gordon and Breach.
[8]
Deegan, J., & Packel, E. (1978). A new index of power for simple n-person games. <italic>International Journal of Game Theory, 7</italic>, 113-123.
[9]
Dubey, P., & Shapley, L. S. (1979). Mathematical properties of the Banzhaf power index. <italic>Mathematics of Operations Research, 4</italic> (2), 99-131.
[10]
Faliszewski, P., & Hemaspaandra, L. (2009). The complexity of power-index comparison. <italic>Theoretical Computer Science, 410</italic> (1), 101 - 107.
[11]
Felsenthal, D. S., & Machover, M. (2005). Voting power measurement: a story of misrein-vention. <italic>Social Choice and Welfare, 25</italic> (2), 485-506.
[12]
Holler, M. J., & Packel, E. W. (1983). Power, luck and the right index. <italic>Zeitschrift für Nationalökonomie / Journal of Economics, 43</italic> (1), 21-29.
[13]
Jelnov, A., & Tauman, Y. (2014). Voting power and proportional representation of voters. <italic>International Journal of Game Theory, 43</italic> (4), 747-766.
[14]
Johnston, R. J. (1978). On the measurement of power: Some reactions to laver. <italic>Environment and Planning A, 10</italic> (8), 907-914.
[15]
Lasisi, R. O., & Allan, V. H. (2017). False-name manipulation in weighted voting games: Empirical and theoretical analysis. <italic>Computational Intelligence, 33</italic> (3), 478-506.
[16]
Lindner, I., & Machover, M. (2004). L.S. Penrose's limit theorem: Proof of some special cases. <italic>Mathematical Social Sciences, 47</italic>, 37-49.
[17]
Milnor, J. W., & Shapley, L. S. (1978). Values of large games ii: Oceanic games. <italic>Mathematics of Operations Research, 3</italic> (4), 290-307.
[18]
Morgenstern, O., & Von Neumann, J. (1953). <italic>Theory of games and economic behavior</italic>. Princeton university press.
[19]
Neyman, A. (1981). Singular games have asymptotic values. <italic>Mathematics of Operations Research, 6</italic> (2), 205-212.
[20]
Okamoto, M. (1959). Some inequalities relating to the partial sum of binomial probabilities. <italic>Annals of the Institute of Statistical Mathematics, 10</italic>, 29-35.
[21]
Oren, J., Filmus, Y., Zick, Y., & Bachrach, Y. (2014). Power distribution in randomized weighted voting: the effects of the quota. Retrieved from https://arxiv.org/abs/1408.0442.
[22]
Penrose, L. S. (1946). The elementary statistics of majority voting. <italic>Journal of the Royal Statistical Society, 109</italic> (1), 53-57.
[23]
Rey, A., & Rothe, J. (2014). False-name manipulation in weighted voting games is hard for probabilistic polynomial time. <italic>Journal of Artificial Intelligence Research, 50</italic> (1), 573-601.
[24]
Riker, W. H. (1986). The first power index. <italic>Social Choice and Welfare, 3</italic>, 293-295.
[25]
Shapley, L. S. (1952). A value for n-person games. Tech. rep., Rand Corp Santa Monica CA.
[26]
Shapley, L. S. (1962). Simple games: an outline of the descriptive theory. <italic>Behavioral Science</italic>, <italic>7</italic> (1), 59-66.
[27]
Shapley, L. S., & Shubik, M. (1954). A method for evaluating the distribution of power in a committee system. <italic>American political science review, 48</italic> (3), 787-792.
[28]
Storing, H. J. (2008). <italic>The complete anti-federalist</italic>, Vol. 2. University of Chicago Press.
[29]
Słomczyński, W., & Zyczkowski, K. (2006). Penrose voting system and optimal quota. <italic>Acta Physica Polonica B, 37</italic>, 3133-3143.
[30]
Słomczyński, W., & Życzkowski, K. (2007). From a toy model to the double square root voting system. <italic>Homo Oeconomicus, 24</italic> (3-4), 381-399.
[31]
Winter, E. (2002). Chapter 53 The Shapley value. Vol. 3 of <italic>Handbook of Game Theory with Economic Applications</italic>, pp. 2025 - 2054. Elsevier.
[32]
Young, H. P. (1978). Power, prices, and incomes in voting systems. <italic>Mathematical Programming, 14</italic> (1), 129-148.
[33]
Zick, Y. (2013). On random quotas and proportional representation in weighted voting games. In <italic>Proceedings of the 23rd International Joint Conference on Artificial Intelligence</italic>.
[34]
Zick, Y., Skopalik, A., & Elkind, E. (2011). The Shapley value as a function of the quota in weighted voting games. In <italic>Proceedings of the 22nd International Joint Conference on Artificial Intelligence</italic>.
Recommendations
False-name manipulations in weighted voting games
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 ...
False name manipulations in weighted voting games: splitting, merging and annexation
AAMAS '09: Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems - Volume 1An important aspect of mechanism design in social choice protocols and multiagent systems is to discourage insincere and manipulative behaviour. We examine the computational complexity of false-name manipulation in weighted voting games which are an ...
Simple Games Versus Weighted Voting Games
Algorithmic Game TheoryAbstractA simple game (N, v) is given by a set N of n players and a partition of into a set of losing coalitions L with value that is closed under taking subsets and a set of winning coalitions W with . Simple games with are exactly the weighted voting ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
AI Access Foundation
El Segundo, CA, United States
Publication History
Published: 04 January 2022
Published in JAIR Volume 72
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 127Total Downloads
- Downloads (Last 12 months)46
- Downloads (Last 6 weeks)3
Reflects downloads up to 13 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in