Return to search

Experimental Analysis of the Effects of Manipulations in Weighted Voting Games

Weighted voting games are classic cooperative games which provide compact representation for coalition formation models in human societies and multiagent systems. As useful as weighted voting games are in modeling cooperation among players, they are, however, not immune from the vulnerability of manipulations (i.e., dishonest behaviors) by strategic players that may be present in the games. With the possibility of manipulations, it becomes difficult to establish or maintain trust, and, more importantly, it becomes difficult to assure fairness in such games. For these reasons, we conduct careful experimental investigations and analyses of the effects of manipulations in weighted voting games, including those of manipulation by splitting, merging, and annexation . These manipulations involve an agent or some agents misrepresenting their identities in anticipation of gaining more power or obtaining a higher portion of a coalition's profits at the expense of other agents in a game. We consider investigation of some criteria for the evaluation of game's robustness to manipulation. These criteria have been defined on the basis of theoretical and experimental analysis. For manipulation by splitting, we provide empirical evidence to show that the three prominent indices for measuring agents' power, Shapley-Shubik, Banzhaf, and Deegan-Packel, are all susceptible to manipulation when an agent splits into several false identities. We extend a previous result on manipulation by splitting in exact unanimity weighted voting games to the Deegan-Packel index, and present new results for excess unanimity weighted voting games. We partially resolve an important open problem concerning the bounds on the extent of power that a manipulator may gain when it splits into several false identities in non-unanimity weighted voting games. Specifically, we provide the first three non-trivial bounds for this problem using the Shapley-Shubik and Banzhaf indices. One of the bounds is also shown to be asymptotically tight. Furthermore, experiments on non-unanimity weighted voting games show that the three indices are highly susceptible to manipulation via annexation while they are less susceptible to manipulation via merging. Given that the problems of calculating the Shapley-Shubik and Banzhaf indices for weighted voting games are NP-complete, we show that, when the manipulators' coalitions sizes are restricted to a small constant, manipulators need to do only a polynomial amount of work to find a much improved power gain for both merging and annexation, and then present two enumeration-based pseudo-polynomial algorithms that manipulators can use. Finally, we argue and provide empirical evidence to show that despite finding the optimal beneficial merge is an NP-hard problem for both the Shapley-Shubik and Banzhaf indices, finding beneficial merge is relatively easy in practice. Also, while it appears that we may be powerless to stop manipulation by merging for a given game, we suggest a measure, termed quota ratio, that the game designer may be able to control. Thus, we deduce that a high quota ratio decreases the number of beneficial merges.

Identiferoai:union.ndltd.org:UTAHS/oai:digitalcommons.usu.edu:etd-2746
Date01 August 2013
CreatorsLasisi, Ramoni Olaoluwa
PublisherDigitalCommons@USU
Source SetsUtah State University
Detected LanguageEnglish
Typetext
Formatapplication/pdf
SourceAll Graduate Theses and Dissertations
RightsCopyright for this work is held by the author. Transmission or reproduction of materials protected by copyright beyond that allowed by fair use requires the written permission of the copyright owners. Works not in the public domain cannot be commercially exploited without permission of the copyright owner. Responsibility for any use rests exclusively with the user. For more information contact Andrew Wesolek (andrew.wesolek@usu.edu).

Page generated in 0.0015 seconds