Computing power indices in weighted multiple majority games

The Shapley–Shubik power index in a voting situation depends on the number of orderings in which each player is pivotal. The Banzhaf power index depends on the number of ways in which each voter can effect a swing. If the input size of the problem is <F>n</F>, then the function which measures the worst case running time for computing these indices is in <F>O<FEN><CP TYPE = "lpar" STYLE="S">n2n<CP TYPE = "rpar" STYLE="S"></FEN>.</F> We present a method based on generating functions to compute these power indices efficiently for weighted multiple majority games and we study the temporal complexity of the algorithms. Finally, we apply the algorithms obtained with this method to compute the Banzhaf and the Shapley–Shubik indices under the two decision rules adopted in the Nice European Union summit. [Copyright &y& Elsevier]