False name manipulations in weighted voting games: splitting, merging and annexation

Details False name manipulations in weighted voting games: splitting, merging and annexation False name manipulations in weighted voting games: splitting, merging and annexation

2009-05-20

arxiv.org/abs/0905.3348v1

Computer Science

Computer Science and Game Theory

Preprint of AAMAS 2009 (Eighth International Conference on Autonomous Agents and Multiagent Systems) paper

Scientific paper

An important aspect of mechanism design in social choice protocols and multiagent systems is to discourage insincere and manipulative behaviour. We examine the computational complexity of false-name manipulation in weighted voting games which are an important class of coalitional voting games. Weighted voting games have received increased interest in the multiagent community due to their compact representation and ability to model coalitional formation scenarios. Bachrach and Elkind in their AAMAS 2008 paper examined divide and conquer false-name manipulation in weighted voting games from the point of view of Shapley-Shubik index. We analyse the corresponding case of the Banzhaf index and check how much the Banzhaf index of a player increases or decreases if it splits up into sub-players. A pseudo-polynomial algorithm to find the optimal split is also provided. Bachrach and Elkind also mentioned manipulation via merging as an open problem. In the paper, we examine the cases where a player annexes other players or merges with them to increase their Banzhaf index or Shapley-Shubik index payoff. We characterize the computational complexity of such manipulations and provide limits to the manipulation. The annexation non-monotonicity paradox is also discovered in the case of the Banzhaf index. The results give insight into coalition formation and manipulation.

Affiliated with

Also associated with

No associations

Rating

False name manipulations in weighted voting games: splitting, merging and annexation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with False name manipulations in weighted voting games: splitting, merging and annexation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and False name manipulations in weighted voting games: splitting, merging and annexation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-243374