False-name manipulations in weighted voting games

DOI10.1613/JAIR.3166zbMATH Open1210.91011arXiv1401.3869OpenAlexW3100107980MaRDI QIDQ3068942FDOQ3068942

Haris Aziz, Edith Elkind, Mike Paterson, Yoram Bachrach

Publication date: 21 January 2011

Published in: Journal of Artificial Intelligence Research (Search for Journal in Brave)

Abstract: 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 players power in such games is usually not directly proportional to his weight, and is measured by a power index, the most prominent among which are the Shapley-Shubik index and the Banzhaf index.In this paper, we investigate by how much a player can change his power, as measured by the Shapley-Shubik index or the Banzhaf index, by means of a false-name manipulation, i.e., splitting his weight among two or more identities. For both indices, we provide upper and lower bounds on the effect of weight-splitting. We then show that checking whether a beneficial split exists is NP-hard, and discuss efficient algorithms for restricted cases of this problem, as well as randomized algorithms for the general case. We also provide an experimental evaluation of these algorithms. Finally, we examine related forms of manipulative behavior, such as annexation, where a player subsumes other players, or merging, where several players unite into one. We characterize the computational complexity of such manipulations and provide limits on their effects. For the Banzhaf index, we describe a new paradox, which we term the Annexation Non-monotonicity Paradox.

Full work available at URL: https://arxiv.org/abs/1401.3869

zbMATH Keywords

decision-makingNP-hardShapley-Shubik indexBanzhaf indexweighted voting gamesagentsAnnexation Non-monotonicity Paradox

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cooperative games (91A12) Voting theory (91B12)

Cited In (15)

• False-Name Manipulation in Weighted Voting Games Is Hard for Probabilistic Polynomial Time
• Analyzing Power in Weighted Voting Games with Super-Increasing Weights
• Control complexity in Borda elections: solving all open cases of offline control and some cases of online control
• The consequences of eliminating NP solutions
• Worst-case Bounds on Power vs. Proportion in Weighted Voting Games with an Application to False-name Manipulation
• Negotiating team formation using deep reinforcement learning
• Structural control in weighted voting games
• Controlling weighted voting games by deleting or adding players with or without changing the quota
• Proof systems and transformation games
• Manipulating the quota in weighted voting games
• Axiomatizing the public good index via merging and new arrival properties
• Manipulation in communication structures of graph-restricted weighted voting games
• Tight incentive analysis of Sybil attacks against the market equilibrium of resource exchange over general networks
• Path-disruption games: bribery and a probabilistic model
• Analyzing power in weighted voting games with super-increasing weights

Uses Software

• TRAVOS

   Recommendations

• False-Name Manipulation in Weighted Voting Games is Hard for Probabilistic Polynomial Time 👍 👎
• False-Name Manipulation in Weighted Voting Games Is Hard for Probabilistic Polynomial Time 👍 👎
• False‐Name Manipulation in Weighted Voting Games: Empirical and Theoretical Analysis 👍 👎
• Worst-case Bounds on Power vs. Proportion in Weighted Voting Games with an Application to False-name Manipulation 👍 👎
• Manipulating the quota in weighted voting games 👍 👎

This page was built for publication: False-name manipulations in weighted voting games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3068942)