Dynamic Programming for Computing Power Indices for Weighted Voting Games with Precoalitions
- 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.
Author: | Jochen StaudacherORCiDGND, Felix Wagner, Jan Filipp |
---|---|
DOI: | https://doi.org/10.3390/g13010006 |
Identifier: | 2073-4336 OPAC HS OPAC extern |
Parent Title (English): | Games |
Publisher: | MDPI |
Place of publication: | Basel |
Document Type: | Article |
Language: | English |
Date of Publication (online): | 2021/12/26 |
Year of first Publication: | 2022 |
Tag: | Dynamic Programming; Owen value; Precoalitions; Weighted Voting Games |
GND Keyword: | Spieltheorie; Dynamische Optimierung |
Volume: | 2022 |
Issue: | 13 / 1 |
Number of pages: | 17 Seiten |
First Page: | 1 |
Last Page: | 17 |
Institutes: | Fakultät Informatik |
IFI - Institut für Internationalisierung | |
Dewey Decimal Classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke |
3 Sozialwissenschaften | |
Open Access: | open_access |
Research focus: | FSP4: Soziale Innovationen |
Publication Lists: | Staudacher, Jochen |
Publication reviewed: | begutachtet |
Licence (German): | Creative Commons - CC BY - Namensnennung 4.0 International |
Release Date: | 2022/01/11 |