Computing power indices for weighted voting games via dynamic programming

Jochen Staudacher (), László Kóczy (), Izabella Stach, Jan Filipp, Marcus Kramer, Till Noffke, Linuss Olsson, Jonas Pichler and Tobias Singer

Operations Research and Decisions, 2021, vol. 31, issue 2, 123-145

Abstract: We study the efficient computation of power indices for weighted voting games using the paradigm of dynamic programming. We survey the state-of-the-art algorithms for computing the Banzhaf and Shapley-Shubik indices and point out how these approaches carry over to related power indices. Within a unified framework, we present new efficient algorithms for the Public Good index and a recently proposed power index based on minimal winning coalitions of the smallest size, as well as a very first method for computing the Johnston indices for weighted voting games efficiently. We introduce a software package providing fast C++ implementations of all the power indices mentioned in this article, discuss computing times, as well as storage requirements.

Keywords: cooperative game theory; power indices; weighted voting games; dynamic programming; minimal winning coalitions (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://ord.pwr.edu.pl/assets/papers_archive/1576%20-%20published.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wut:journl:v:31:y:2021:i:2:p:61-76:id:1576

DOI: 10.37190/ord210206

Access Statistics for this article

More articles in Operations Research and Decisions from Wroclaw University of Science and Technology, Faculty of Management Contact information at EDIRC.
Bibliographic data for series maintained by Adam Kasperski ().