Open AccessComputing power indices for weighted voting games via dynamic programming
Author(s) -
Jochen Staudacher,
László Á. Kóczy,
Izabella Stach,
Jan Filipp,
Marcus Kramer,
Till Noffke,
Linus Olsson,
Jonas Pichler,
Tobias Singer
Publication year - 2021
Publication title -
badania operacyjne i decyzje/operations research and decisions
Language(s) - English
Resource type - Journals
eISSN - 2081-8858
pISSN - 1230-1868
DOI - 10.37190/ord210206
Subject(s) - computer science , voting , computation , index (typography) , weighted voting , implementation , dynamic programming , power (physics) , power index , software , theoretical computer science , point (geometry) , software implementation , state (computer science) , mathematical optimization , algorithm , mathematics , programming language , mathematical economics , physics , geometry , quantum mechanics , politics , political science , law
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 smallest size, as well as a very first method for computing 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.