Faster algorithms for computing power indices in weighted voting games

B. Klinz, G.J. Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

11 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)111-116
JournalMathematical Social Sciences
Volume49
Issue number1
DOIs
Publication statusPublished - 2005

Fingerprint Dive into the research topics of 'Faster algorithms for computing power indices in weighted voting games'. Together they form a unique fingerprint.

  • Cite this