False-name manipulations in weighted voting games
From MaRDI portal
Publication:3068942
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.
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
Cited in
(20)- False-Name Manipulation in Weighted Voting Games Is Hard for Probabilistic Polynomial Time
- Merging and splitting for power indices in weighted voting games and network flow games on hypergraphs
- Control complexity in Borda elections: solving all open cases of offline control and some cases of online control
- The consequences of eliminating NP solutions
- Negotiating team formation using deep reinforcement learning
- Controlling weighted voting games by deleting or adding players with or without changing the quota
- Structural control in weighted voting games
- Structural control in weighted voting games
- Controlling weighted voting games by deleting or adding players with or without changing the quota
- False-name manipulation in weighted voting games is hard for probabilistic polynomial time
- False-name manipulation in weighted voting games: empirical and theoretical analysis
- 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
- Worst-case bounds on power vs. proportion in weighted voting games with an application to false-name manipulation
- Path-disruption games: bribery and a probabilistic model
- Analyzing power in weighted voting games with super-increasing weights
- Analyzing power in weighted voting games with super-increasing weights
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)
