Affiliations: [a] Department of Computer Science, Loughborough University, Loughborough, UK | [b] Department of Computer Science, University of Oxford, Oxford, UK | [c] School of Electronics and Computer Science, University of Southampton, Southampton, UK
Correspondence:
[*]
Corresponding author: Shaheen Fatima, Department of Computer Science, Loughborough University, Loughborough LE11 3TU, UK. E-mail: [email protected]
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=1 to 30% for games with k=5.
Keywords: Cooperative game theory, Banzhaf index, complexity, heuristic algorithms
