Structural Control in Weighted Voting Games: (Extended Abstract)
Authors: 
Anja Rey, Jörg RotheAuthors Info & Claims
Pages 1371 - 1372
Abstract
Inspired by the study of control scenarios in elections and complementing manipulation and bribery settings in cooperative games with transferable utility, we introduce the notion of structural control in weighted voting games. We model two types of influence, adding players to and deleting players from a game, with goals such as increasing a given player's Shapley--Shubik power index in relation to the original game. We study the complexity of the problems of whether such structural changes can achieve the desired effect.
References
[1]
H. Aziz, Y. Bachrach, E. Elkind, and M. Paterson. False-name manipulations in weighted voting games. Journal of Artificial Intelligence Research, 40:57--93, 2011.
[2]
F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. Procaccia, editors. Handbook of Computational Social Choice. Cambridge University Press, 2016. To appear.
[3]
G. Chalkiadakis, E. Elkind, and M. Wooldridge. Computational Aspects of Cooperative Game Theory. Morgan & Claypool, 2011.
[4]
P. Dubey and L. Shapley. Mathematical properties of the Banzhaf power index. Mathematics of Operations Research, 4(2):99--131, 1979.
[5]
E. Elkind, D. Pasechnik, and Y. Zick. Dynamic weighted voting games. In Proc.\ AAMAS'13, pages 515--522. IFAAMAS, 2013.
[6]
P. Faliszewski and L. Hemaspaandra. The complexity of power-index comparison. Theoretical Computer Science, 410(1):101--107, 2009.
[7]
R. Myerson. Conference structures and fair allocation rules. International Journal of Game Theory, 9(3):169--182, 1980.
[8]
T. Rahwan, T. Michalak, and M. Wooldridge. A measure of synergy in coalitions. Technical Report arXiv: 1404.2954.v1 {cs.GT}, CoRR, Apr. 2014.
[9]
A. Rey and J. Rothe. False-name manipulation in weighted voting games is hard for probabilistic polynomial time. Journal of Artificial Intelligence Research, 50:573--601, 2014.
[10]
A. Rey, J. Rothe, and A. Marple. Path-disruption games: Bribery and a probabilistic model. Theory of Computing Systems. To appear.
[11]
J. Rothe, editor. Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division. Springer-Verlag, 2015.
[12]
L. Shapley and M. Shubik. A method of evaluating the distribution of power in a committee system. American Political Science Review, 48(3):787--792, 1954.
[13]
M. Zuckerman, P. Faliszewski, Y. Bachrach, and E. Elkind. Manipulating the quota in weighted voting games. Artificial Intelligence, 180--181:1--19, 2012.
Index Terms
- Structural Control in Weighted Voting Games: (Extended Abstract)
Recommendations
Classic Nintendo games are (computationally) hard
We prove NP-hardness results for five of Nintendo's largest video game franchises: Mario, Donkey Kong, Legend of Zelda, Metroid, and Pokémon. Our results apply to generalized versions of Super Mario Bros. 1-3, The Lost Levels, and Super Mario World; ...
Monotone cooperative games and their threshold versions
AAMAS '10: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1 - Volume 1Cooperative games provide an appropriate framework for fair and stable resource allocation in multiagent systems. This paper focusses on monotone cooperative games, a class which comprises a variety of games that have enjoyed special attention within AI,...
NPPP-Completeness of Control by Adding Players to Change the Penrose-Banzhaf Power Index in Weighted Voting Games
AAMAS '24: Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent SystemsWeighted voting games are an important class of simple games that can be compactly represented and have many real-world applications. Rey and Rothe [14] introduced the notion of structural control by adding players to or deleting them from weighted ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
May 2016
1580 pages
ISBN:9781450342391
- General Chairs:
- Catholijn M. Jonker,
- Stacy Marsella,
- Program Chairs:
- John Thangarajah,
- Karl Tuyls
Sponsors
- IFAAMAS
In-Cooperation
Publisher
International Foundation for Autonomous Agents and Multiagent Systems
Richland, SC
Publication History
Published: 09 May 2016
Check for updates
Author Tags
Qualifiers
- Extended-abstract
Funding Sources
- DFG
Conference
AAMAS '16
Sponsor:
AAMAS '16: International Conference on Agents and Multiagent Systems
May 9 - 13, 2016
Singapore, Singapore
Acceptance Rates
AAMAS '16 Paper Acceptance Rate 137 of 550 submissions, 25%;
Overall Acceptance Rate 1,155 of 5,036 submissions, 23%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 41Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)0
Reflects downloads up to 21 Nov 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