Information Technology Reference
In-Depth Information
Fig. 4.
The average factor of increment for merging for the enumeration and best-of-three meth-
ods using various values of size of bloc divided by the number of agents in the games
We have used a total of
500
original WVGs for each experiment and compute the
average factor of increments over the entire set of games for the two power indices. The
evaluation is carried out for the proportion of agents in manipulators' blocs and the
variance of the weights of agents in the WVGs. We have implemented efficient exact
polynomial methods of computing the Shapley-Shubik and Banzhaf indices for integer
weights using generating functions [7,9] which can be exponential-time in complexity
in the worst case.
We first present the results of the case of manipulation by merging and then provide
discussion on the results of manipulation by annexation. Figure 4 shows the benefits
from merging for both the best-of-three and enumeration-based methods using the two
indices. The
x
-axes indicates the proportion of agents in the manipulators' bloc (i.e.
|S|
|
=
n
) whose factor of increment were reported while the
y
-axes are the average fac-
tor of increment achieved by manipulating agents in those coalitions. For the Shapley-
Shubik power index, Figure 4
(
a
)
shows that manipulating agents achieved improved
power using the enumeration approach than using the best-of-three method. There are
cases where the manipulators achieved more than
2
.
4
times as much as the original
power for the enumeration method, and in general the average factor of increment
I
|
