Faster algorithms for computing power indices in weighted voting games

We consider weighted voting games with n players. We show how to compute the Banzhaf power index for every player within a running time of O(n2 1.415n), and how to compute the Shapley-Shubik power index within a running time of O(n 1.415n). Our result improves on the straightforward running times of O(n2 2n) and O(n 2n), respectively, that are implicit in the definitions of these power indices.