Divide and conquer

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Divide and conquer: false-name manipulations in weighted voting games

Full text

Pdf (348 KB)

Source

International Conference on Autonomous Agents archive
Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 2 table of contents

Estoril, Portugal

SESSION: Economic paradigms table of contents

Pages 975-982

Year of Publication: 2008

ISBN:978-0-9817381-1-6

Authors

Yoram Bachrach	Hebrew University, Jerusalem, Israel
Edith Elkind	University of Southampton, Southampton, United Kingdom

Sponsors

AAAI : Association for the Advancement of Artifical Intelligence
ACM: Association for Computing Machinery

Publisher

International Foundation for Autonomous Agents and Multiagent Systems Richland, SC

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 34, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

ABSTRACT

In this paper, we study false-name manipulations in weighted voting games. Weighted voting is a well-known model of cooperation among agents in decision-making domains. In such games, each of the players has a weight, and a coalition of players wins the game if its total weight exceeds a certain quota. While a player's ability to influence the outcome of the game is related to its weight, it is not always directly proportional to it. This observation has led to the concept of a power index, which is a measure of an agent's "real power" in this domain. One prominent power index is the Shapley--Shubik index, which has been widely used to analyze political power. This index is equal to the Shapley value of the player in the game. If an agent can alter the game so that his Shapley--Shubik index increases, this will mean that he has gained power in the game. Moreover, the Shapley value is often used to distribute the gains of the grand coalition. In this case, this alteration will also increase the agent's payoffs.

One way in which an agent can change the game (and hence his payoffs) is by distributing his weight among several false identities. We call this behavior a false-name manipulation. We show that such manipulations can indeed increase an agent's power, as determined by the Shapley-Shubik power index, or his payoffs, as given by the Shapley value. We provide upper and lower bounds on the effects of such manipulations. We then study this issue from the computational perspective, and show that checking whether a beneficial split exists is NP-hard. We also discuss efficient algorithms for restricted cases of this problem, as well as randomized algorithms for the general case.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	J. F. Banzhaf. Weighted voting doesn't work: a mathematical analysis. Rutgers Law Review, 19:317--343, 1965.
	2	V. Conitzer and T. Sandholm. Computing Shapley values, manipulating value division schemes, and checking core membership in multi-issue domains. In Proc. AAAI'04, pp. 219--225, 2004.
	3	Xiaotie Deng , Christos H. Papadimitriou, On the complexity of cooperative solution concepts, Mathematics of Operations Research, v.19 n.2, p.257-266, May 1994 [doi>10.1287/moor.19.2.257]
	4	P. Dubey and L. Shapley. Mathematical properties of the Banzhaf power index. Mathematics of Operations Research, 4(2):99--131, 1979.
	5	Shaheen S. Fatima , Michael Wooldridge , Nicholas R. Jennings, A randomized method for the shapley value for the voting game, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329316]
	6	A. Laruelle. On the choice of a power index. Papers 99--10, Valencia --- Instituto de Investigaciones Economicas, 1999.
	7	D. Leech. Voting power in the governance of the international monetary fund. Annals of Operations Research, 109(1--4):375--397, 2002.
	8	M. Machover and D. S. Felsenthal. The treaty of Nice and qualified majority voting. Social Choice and Welfare, 18(3):431--464, 2001.
	9	I. Mann and L. S. Shapley. Values of large games, IV: Evaluating the electoral college by Monte-Carlo techniques. Technical report, The Rand Corporation, Santa Monica, CA, 1960.
	10	I. Mann and L. S. Shapley. Values of large games, VI: Evaluating the electoral college exactly. Technical report, The Rand Corporation, Santa Monica, CA, 1962.
	11	Y. Matsui and T. Matsui. A survey of algorithms for calculating power indices of weighted majority games. Journal of the Operations Research Society of Japan, 43, 2000.
	12	Y. Matsui and T. Matsui. NP-completeness for calculating power indices of weighted majority games.
	13	G. Owen. Multilinear extensions and the Banzhaf Value. Naval Research Logistics Quarterly, 22(4):741--750, 1975.
	14	L. S. Shapley. A value for n-person games. Contributions to the Theory of Games, pp. 31--40, 1953.
	15	L. S. Shapley and M. Shubik. A method for evaluating the distribution of power in a committee system. American Political Science Review, 48:787--792, 1954.
	16	P. Straffin. Homogeneity, independence and power indices. Public Choice, 30:107--118, 1977.
	17	M. Yokoo, V. Conitzer, T. Sandholm, N. Ohta, A. Iwasaki. Coalitional games in open anonymous environments. In Proc. AAAI'05, pp. 509--515, 2005.
	18	Makoto Yokoo , Yuko Sakurai , Shigeo Matsubara, Robust combinatorial auction protocol against false-name bids., Artificial Intelligence, v.130 n.2, p.167-181, 08/01/2001 [doi>10.1016/S0004-3702(01)00077-7]
	19	M. Yokoo, Y. Sakurai, S. Matsubara. The effect of false-name bids in combinatorial auctions: New fraud in Internet auctions. Games and Economic Behavior, 46(1):174.188, 2004.