Computing Power Indices in Weighted Majority Games with Formal Power Series

2025/11/19 by Kakimura, Naonori, Terai, Yoshihiko
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Artificial Intelligence in Games #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems

paper · doi:10.48550/arxiv.2511.14995

openalex publication_date 2025/11/19 · openalex created_date 2025/11/23 · openalex updated_date 2026/07/28

Abstract

In this paper, we propose fast pseudo-polynomial-time algorithms for computing power indices in weighted majority games. We show that we can compute the Banzhaf index for all players in O(n+qlog (q)) time, where n is the number of players and q is a given quota. Moreover, we prove that the Shapley--Shubik index for all players can be computed in O(nqlog (q)) time. Our algorithms are faster than existing algorithms when q=2^o(n). Our algorithms exploit efficient computation techniques for formal power series.

Citations

• Computing the Power Distribution in the IMF
• Algebraic and geometric methods in enumerative combinatorics
• On the Complexity of Cooperative Solution Concepts

Related

• Generating functions partitioning algorithm for computing power indices in weighted voting games
• The Complexity of Power-Index Comparison
• Control by Adding Players to Change or Maintain the Shapley-Shubik or the Penrose-Banzhaf Power Index in Weighted Voting Games Is Complete for NP^PP
• Computing voting power in easy weighted voting games
• Solving Weighted Voting Game Design Problems Optimally: Representations, Synthesis, and Enumeration