Information Technology Reference
In-Depth Information
Fig. 1.
Six permutations of three agents and corresponding power indices of the agents for various
values of quota from
q
=1
to
q
=6
Fig. 2.
Manipulation by merging between Agent 1 and Agent 3 (from Figure 1) to form a new
Agent X. The power indices of Agent X and Agent 2 as computed by Shapley-Shubik index after
the merging for various values of the quota is also shown.
shown that annexation is never disadvantageous for an annexer using the Shapley-
Shubik power index. However, that is not the case when the annexer uses the Banzhaf
power index. This they have dubbed the bloc paradox.
4
Manipulation Algorithms for Annexation and Merging
4.1
Overview
We propose an enumeration approach for manipulation by annexation and merging in
WVGs using the two power indices to compute agents' power. To begin with, we re-
call that the problem of calculating the Shapley-Shubik and Banzhaf indices is NP-
hard and admit pseudopolynomial algorithms using generating functions or dynamic
