A heuristic approximation method for the Banzhaf index for voting games
OA Location
Author(s)
Fatima, S
Wooldridge, M
Jennings, NR
Type
Journal Article
Abstract
The Banzhaf index is a well known and widely used index for measuring the power a player has in a voting game. However, the problem of computing this index is computationally hard. To overcome this problem, a number of approximation methods were developed for one majority voting games. While it may be possible to extend some of these to k-majority games (which are generalized versions of one majority games), to date, there has been no performance analysis of these methods in the context of the Banzhaf index for k-majority games. In this paper, we fill this gap, by first presenting an approximation method for the Banzhaf index for k-majority games. This is a heuristic method that uses randomization to estimate an approximate. We then show that this method is computationally feasible. Finally, we evaluate its performance by analyzing its error of approximation, and show how the error varies with k. Specifically, we show that the average percentage error increases from 15% for games with k=1k=1 to 30% for games with k=5k=5.
Date Issued
2012-10-24
Date Acceptance
2012-10-24
Citation
Multiagent and Grid Systems, 2012, 8 (3), pp.257-274
ISSN
1875-9076
Publisher
IOS Press
Start Page
257
End Page
274
Journal / Book Title
Multiagent and Grid Systems
Volume
8
Issue
3
Copyright Statement
© 2012 IOS Press and the authors. All rights reserved. The final publication is available at IOS Press through http://dx.doi.org/10.3233/MGS-2012-0194
Identifier
http://eprints.soton.ac.uk/343615/
Subjects
0801 Artificial Intelligence And Image Processing
1702 Cognitive Science