False name manipulations in weighted voting games: splitting, merging and annexation - Computer Science > Computer Science and Game TheoryReportar como inadecuado




False name manipulations in weighted voting games: splitting, merging and annexation - Computer Science > Computer Science and Game Theory - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: An important aspect of mechanism design in social choice protocols andmultiagent systems is to discourage insincere and manipulative behaviour. Weexamine the computational complexity of false-name manipulation in weightedvoting games which are an important class of coalitional voting games. Weightedvoting games have received increased interest in the multiagent community dueto their compact representation and ability to model coalitional formationscenarios. Bachrach and Elkind in their AAMAS 2008 paper examined divide andconquer false-name manipulation in weighted voting games from the point of viewof Shapley-Shubik index. We analyse the corresponding case of the Banzhaf indexand check how much the Banzhaf index of a player increases or decreases if itsplits up into sub-players. A pseudo-polynomial algorithm to find the optimalsplit is also provided. Bachrach and Elkind also mentioned manipulation viamerging as an open problem. In the paper, we examine the cases where a playerannexes other players or merges with them to increase their Banzhaf index orShapley-Shubik index payoff. We characterize the computational complexity ofsuch manipulations and provide limits to the manipulation. The annexationnon-monotonicity paradox is also discovered in the case of the Banzhaf index.The results give insight into coalition formation and manipulation.



Autor: Haris Aziz, Mike Paterson

Fuente: https://arxiv.org/



DESCARGAR PDF




Documentos relacionados