Divide and Conquer: False-Name Manipulations in Weighted Voting Games
Authors: Yoram Bachrach, Edith Elkind
Abstract:
In this paper, we study false-name manipulations in weighted
voting games. Weighted voting is a well-known model of cooperation
among agents in decision-making domains. In such games, each of the
players has a weight, and a coalition of players wins the game if its
total weight exceeds a certain quota. While a player's ability to
influence the outcome of the game is related to its weight, it is not
always directly proportional to it.
This observation has led to the concept of a power index, which is a
measure of an agent's ``real power'' in this domain. One prominent power
index is the Shapley--Shubik index, which has been widely used to
analyze political power.
This index is equal to the Shapley value of the player in the game. If
an agent can alter the game so that his Shapley--Shubik index
increases, this will mean that he has gained power in the game.
Moreover, the Shapley value is often used to distribute the gains of
the grand coalition. In this case, this alteration will also
increase the agent's payoffs.
One way in which an agent can change the game (and hence his payoffs)
is by distributing his weight among several false identities. We call
this behavior a false-name manipulation. We show that such
manipulations can indeed increase an agent's power, as determined by
the Shapley--Shubik power index, or his payoffs, as given by the
Shapley value. We provide upper and lower bounds on the effects of
such manipulations. We then study this issue from the computational
perspective, and show that checking whether a beneficial split exists
is NP-hard. We also discuss efficient algorithms for restricted cases
of this problem, as well as randomized algorithms for the general
case.