Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10480456 | Mathematical Social Sciences | 2005 | 6 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Bettina Klinz, Gerhard J. Woeginger,