Dynamic Programming for Computing Power Indices for Weighted Voting Games with Precoalitions

Jochen Staudacher, Felix Wagner and Jan Filipp
Additional contact information
Jochen Staudacher: Fakultät Informatik, Hochschule Kempten, 87435 Kempten, Germany
Felix Wagner: Fakultät Informatik, Hochschule Kempten, 87435 Kempten, Germany
Jan Filipp: Fakultät Informatik, Hochschule Kempten, 87435 Kempten, Germany

Games, 2021, vol. 13, issue 1, 1-17

Abstract: We study the efficient computation of power indices for weighted voting games with precoalitions amongst subsets of players (reflecting, e.g., ideological proximity) using the paradigm of dynamic programming. Starting from the state-of-the-art algorithms for computing the Banzhaf and Shapley–Shubik indices for weighted voting games, we present a framework for fast algorithms for the three most common power indices with precoalitions, i.e., the Owen index, the Banzhaf–Owen index and the symmetric coalitional Banzhaf index, and point out why our new algorithms are applicable for large numbers of players. We discuss implementations of our algorithms for the three power indices with precoalitions in C++ and review computing times, as well as storage requirements.

Keywords: cooperative game theory; power indices; weighted voting games; dynamic programming; precoalitions; Shapley value; Owen value; Banzhaf index (search for similar items in EconPapers)
JEL-codes: C C7 C70 C71 C72 C73 (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2073-4336/13/1/6/pdf (application/pdf)
https://www.mdpi.com/2073-4336/13/1/6/ (text/html)

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:gam:jgames:v:13:y:2021:i:1:p:6-:d:711371

Access Statistics for this article

Games is currently edited by Ms. Susie Huang

More articles in Games from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().