Refine
Document Type
- Article (2)
Language
- English (2)
Has Fulltext
- yes (2)
Publication reviewed
- begutachtet (2)
Keywords
- Spieltheorie (2)
- Dynamic Programming (1)
- Dynamische Optimierung (1)
- Dynamische Programmierung (1)
- Gewichtetes Abstimmungsspiel (1)
- Machtindex (1)
- Owen value (1)
- Precoalitions (1)
- Weighted Voting Games (1)
- cooperative game theory (1)
- dynamic programming (1)
- minimal winning coalitions (1)
- power indices (1)
- weighted voting games (1)
Institute
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.
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.