Information Technology Reference
In-Depth Information
2
Related Work
Weighted voting games and power indices are widely studied [1,2,5,14,16]. WVGs
have many applications, including economics, political science, neuroscience, threshold
logic, reliability theory, distributed systems [3], and multiagent systems [4]. Prominent
real-life situations where WVGs have found applications include the United Nations
Security Council, the Electoral College of the United States and the International Mon-
etary Fund [1,14]. The study of WVGs has also necessitated the need to fairly determine
the power of players in a game. This is because the power of a player in a game pro-
vides information about the relative importance of that player when compared to other
players. To evaluate players' power, prominent power indices such as Shapley-Shubik,
Banzhaf, and Deegan-Packel indices are commonly employed [16]. These indices sat-
isfy the axioms that characterize a power index, have gained wide usage in political
arena, and are the main power indices found in the literature [10]. These power indices
have been defined on the framework of subsets of winning coalitions in the game they
seek to evaluate. A wide variation in the results they provide can be observed. Then,
comes the question of which of the power indices is the most resistant to manipulation
in a WVG. The choice of a power index depends on a number of factors, namely, the
a priori properties of the index, the axioms characterizing the index, and the context of
decision making process under consideration [10].
The three indices we consider measure the influence of voters differently. There are
many situations where their values are the same for similar games. However, there ex-
ists an important example of the US federal system in using the Shapley-Shubik and
Banzhaf indices where they do not agree [9]. According to Laruelle and Valenciano
[11], and Kirsch [8], the decision of which index to use in evaluating a voting situ-
ation is largely dependent on the assumptions about the voting behavior of the vot-
ers. When the voters are assumed to vote completely independently of each other, the
Banzhaf index has been found to be appropriate. On the other hand, Shapley-Shubik
index should be employed when all voters are influenced by a common belief affecting
their choices. Deegan-Packel index is appealing in that it assigns powers based on size
of the winning coalition, thus giving preference to smaller coalitions (which may be
easier to form).
Very little work exists on manipulation via annexation and merging in WVGs, and
the more detailed analysis of players merging into blocs, until now, has remained unex-
plored [2]. Machover and Felsenthal [15] proved that if a player annexes other players,
then the annexation is always advantageous for the annexer using the Shapley-Shubik
index. Annexation can be advantageous or disadvantageous using the Banzhaf index. For
the case of merging, in both the Shapley-Shubik and Banzhaf indices, merging can be
advantageous or disadvantageous. Aziz and Paterson [2] show that for some classes of
WVGs, for both Shapley-Shubik and Banzhaf indices, it is disadvantageous for a coali-
tion to merge, while advantageous for a player to annex. They also prove some NP-
hardness results for annexation and merging. They show that for both Shapley-Shubik
and Banzhaf indices, finding a beneficial annexation is NP-hard. Also, determining if
there exists a beneficial merge is NP-hard for the Shapley-Shubik index. Machover and
Felsentha [15], and Aziz and Paterson [2] have shown that it can be advantageous for
agents to engage in annexation or merging for Shapley-Shubik and Banzhaf indices
