Manipulation of Weighted Voting Games via Annexation and Merging - Agents and Artificial Intelligence - page 370

however, this heuristic requires smaller computational effort compared to that of the
enumeration-based method and thus makes it more useful in practice. We can even do
better using the idea in the following heuristic:

MaximalWeights Heuristic:
Given :AWVGof n agents with a distinguished annexer i .
Procedure : Since agents' weights are given in ascending order, let agent i annex
the last k − 1 agents from the remaining n − 1 agents in the game.

As before, let A ( G ) be the pseudopolynomial running time of Shapley-Shubik or Banzhaf
power index of an agent according to [7,9]. The running time of the MaximalWeights
heuristic is O ( n + A ( G )) . Here is a brief analysis. We just need to sum the weights of
the last k 1 agents to that of the annexer at a cost of

O ( k ) . In the worst case, it takes O ( n ) to sum the weights when k = n , i.e., the annexer
is able to annex all the remaining n

− 1 agents from the remaining n −

1 agents. Computing the power of the annexer in
each of the original and altered games takes O ( A ( G )) . Therefore, the total running time
of the heuristic is O ( n + A ( G )) . Now, apart from the fact that this heuristic appears to
find the most improved gain, its running time is by far less than the O ( n k

−

· A ( G )) run-
ning times of the manipulation algorithm for annexation of Subsection 4.3 and the above
heuristic especially when k is large. Thus, the MaximalWeights heuristic is more useful
in practice for the annexer.

7 Related Work

Weighted voting games and power indices are widely studied [8,12,17]. Prominent real-
life situations where WVGs have found applications include the United Nations Secu-
rity Council, the International Monetary Fund [1,20], the Council of Ministers, and
the European Community [12]. The need to compensate agents from jointly derived
payoff in WVGs has also necessitated the assignment of power to players. A widely
accepted method for measuring power of agents in WVGs uses power indices. Fair-
ness in the assignment of power to players in a game is also a concern of most of the
power indices. The two most prominent and widely used power indices are Shapley-
Shubik [23] and Banzhaf [6] power indices. Other power indices found in the liter-
ature include Deegan-Packel [10], Johnsoton [16], and Holler-Packel [15] power in-
dices. Computing the Shapley-Shubik and Banzhaf power indices of players in WVGs
is NP-hard [22]. The power indices of voters using any of Shapley-Shubik and Banzhaf
power indices can be computed in pseudo-polynomial time using dynamic program-
ming [21]. Efficient exact algorithms using generating functions [7,9] also exist for
both the Shapley-Shubik and Banzhaf power indices for WVGs where the weights of
all agents are restricted to integers. There are also approximation algorithms [5,11] for
computing the Shapley-Shubik and Banzhaf power indices in WVGs.
Felsenthal and Machover [12,13] originally studied annexation and alliance (or merg-
ing) in WVGs. They consider when the blocs formed by annexation or merging are
advantageous or disadvantageous. They show that using the Shapley-Shubik index, it
is always advantageous for a player to annex some other players in the game. How-
ever, this is not true for Banzhaf power index. Furthermore, they show that merging