Issue: 2021/Vol.31/No.2, Pages 123-145
COMPUTING POWER INDICES FOR WEIGHTED VOTING GAMES VIA DYNAMIC PROGRAMMING
Cite as: J. Staudacher, L. Á. Kóczy, I. Stach, J. Filipp, M. Kramer, T. Noffke, L. Olsson, J. Pichler, T. Singer. Computing power indices for weighted voting games via dynamic programming. Operations Research and Decisions 2021: 31(2), 123-145. DOI 10.37190/ord210206
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
Received: 1 November 2020 Accepted: 19 April 2021