Information Technology Reference
In-Depth Information
can be advantageous or disadvantageous for the two power indices. In contrast to our
work, they do not consider the extent to which the agents involved in annexation or
merging may gain, which we study in this paper. Aziz et al. [2], have also considered
the computational aspects of the problem of annexation and merging in WVGs. They
show that determining if there exists a beneficial merge in a WVG is NP-hard using
both the Shapley-Shubik and Banzhaf indices. The same is also true for determining
the existence of beneficial annexation using the Banzhaf index.
8
Conclusions
We investigate the effects of manipulations (i.e., dishonest behaviors) by annexation
and merging in weighted voting games. These manipulations involve an agent or agents
misrepresenting their identities in anticipation of gaining more power in a game. We
evaluate the effects of these manipulations using two prominent power indices,
Shapley-
Shubik
and
Banzhaf
indices, to compute agents' power. We first provide visual illus-
trations of manipulation in weighted voting games to give some insights into why it
is difficult to predict how to merge. We then show that manipulators need to do only
a polynomial amount of work to find a much improved power gain, and present two
enumeration-based pseudopolynomial algorithms that manipulators can use. Further-
more, we provide a careful investigation of heuristics for annexation which provide
huge savings in computational efforts over the enumeration-based method. The benefits
achievable by manipulating agents using these heuristics also compare with those of the
enumeration-based method which serves as upper bound.
Acknowledgements.
This work is supported by NSF research grant #0812039 entitled
“Coalition Formation with Agent Leadership”.
References
1. Alonso-Meijide, J.M., Bowles, C.: Generating Functions for Coalitional Power Indices: An
Application to the IMF. Annals of Operations Research 137, 21-44 (2005)
2. Aziz, H., Bachrach, Y., Elkind, E., Paterson, M.: False-name manipulation in Weighted Vot-
ing Games. Journal of Artificial Intelligence Research 40, 57-93 (2011)
3. Aziz, H., Paterson, M.: False-name Manipulations in Weighted Voting Games: splitting,
merging and annexation. In: 8th International Conference on Autonomous Agents and Mul-
tiagent Systems, Budapest, Hungary, pp. 409-416 (2009)
4. Aziz, H., Paterson, M., Leech, D.: Classification of Computationally Tractable Weighted
Voting Games. In: Proceedings of the World Congress on Engineering, London, U.K., vol. I
(2008)
5. Bachrach, Y., Markakis, E., Procaccia, A.D., Rosenschein, J.S., Saberi, A.: Approximating
Power Indices - Theoretical and Empirical Analysis. Autonomous Agents and Multiagent
Systems 20(2), 105-122 (2010)
6. Banzhaf, J.: Weighted Voting Doesn't Work: A Mathematical Analysis. Rutgers Law Re-
view 19, 317-343 (1965)
7. Bilbao, J.M., Fernandez, J.R., Losada, A.J., Lopez, J.J.: Generating functions for computing
power indices efficiently. TOP: An official Journal of the Spanish Society of Statistics and
Operations Research 8(2), 191-213 (2000)
