Computing Power Indices in Weighted Majority Games with Formal Power Series

Abstract

In this paper, we propose fast pseudo-polynomial-time algorithms for computing power indices in weighted majority games. We show that we can compute the Banzhaf index for all players in $O(n+q\log (q))$ time, where $n$ is the number of players and $q$ is a given quota. Moreover, we prove that the Shapley--Shubik index for all players can be computed in $O(nq\log (q))$ time. Our algorithms are faster than existing algorithms when $q=2^{o(n)}$. Our algorithms exploit efficient computation techniques for formal power series.