Information Technology Reference
In-Depth Information
factor of increment. Finally, for the case of manipulation by annexation and for both the
Shapley-Shubik and Banzhaf indices, the impovement in power achieved by manipulat-
ing agents using the enumeration method is by far more than those achieved using the
best-of-three method.
6
Heuristics for Annexation and Merging in WVGs
Unlike the manipulation algorithms for annexation and merging of Section 4 where we
have
n
and
k
as the number of agents and the number of assimilated agents in a WVG,
manipulating agents may not be interested in achieving the most improved power gain
among the
O
(
n
k
)
polynomial coalitions described before. This is because the number
of these coalitions may be large even for small values of
n
and
k
. Thus, we propose
heuristics that agents may use for annexation in WVGs. Considering the basic require-
ments for a good heuristic as its ease of computation and to be as informative as possible
[14], the heuristics we propose are designed to first avoid the enumeration approach of
the manipulation algorithms in Section 4. Second, we avoid the unintelligent simple
random approach of [18] to ensure that our heuristics provide good information for
manipulating agents to make decisions on how to annex in WVGs.
6.1
Annexation Heuristics
We recall the definition of annexation in Section 2 and from [2,13], the power of the
assimilated bloc in an altered WVG is compared to the power of the annexer in the
original game. By this definition, intuition suggests that annexation should always be
advantageous. This intuition is indeed true using the Shapley-Shubik index to compute
agents' power. However, there exist situations where annexation is disadvantageous
for the annexer using the Banzhaf index. See [2,3,13] for examples of WVGs where
annexation is disadvantageous for the annexer using the Banzhaf index. This case where
annexation results in power decrease for the annexer is refer to as the
bloc paradox
[13].
Again, recall from Equation 4 that an annexer needs to examine a polynomial num-
ber of assimilated coalitions of size at most
k
1
to find the most improved power
gain among these coalitions whose sizes we have restricted to
k
. We note also that the
assimilated coalitions with maximal weights among these coalitions are those of sizes
k
−
1
. Thus, it is enough for a particular annexer to check only the assimilated coali-
tions of size exactly
k
−
1
in order for the annexer to find the coalition with the most
improved benefit using the two power indices. This indeed is the case for the Shapley-
Shubik index. For the case of Banzhaf index, we conduct a test to check the highest
factor of increment among all the coalitions of
2
,
000
different WVGs. We found that
the coalitions with maximal weights (i.e., those having sizes of
k
−
1
) yield the highest
possible factor of increment in over
82%
of the games. The remaining highest factor of
increment are archieved by manipulators' blocs with lower number of agents in them. In
none of these two situations do we experience the bloc paradox. This suggests that the
bloc paradox for the Banzhaf power index may be a rare phenomenon in practice.
−
such assimilated coalitions to be considered by this an-
nexer. As seen, the amount of work carried out by the annexer is still polynomial,
There are only
n −
1
k −
1
