The Library
False-name manipulations in weighted voting games
Tools
Tools
Tools
Aziz, Haris, Bachrach, Yoram, Elkind, Edith and Paterson, Michael S. (2011) False-name manipulations in weighted voting games. Journal of Artificial Intelligence, Vol.40 . pp. 57-93. doi:10.1613/jair.3166 ISSN 1076-9757.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
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 player's 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.
| Item Type: | Journal Article | ||||
|---|---|---|---|---|---|
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Journal or Publication Title: | Journal of Artificial Intelligence | ||||
| Publisher: | A N S I Network | ||||
| ISSN: | 1076-9757 | ||||
| Official Date: | 2011 | ||||
| Dates: |
|
||||
| Volume: | Vol.40 | ||||
| Page Range: | pp. 57-93 | ||||
| DOI: | 10.1613/jair.3166 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
