  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.
