2008/11/15 by Haris Aziz, Aziz, Haris, Mike Paterson +1
Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Computational Complexity (cs.CC) #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 · pdf · doi:10.48550/arxiv.0811.2497
openalex publication_date 2008/11/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Weighted voting games are ubiquitous mathematical models which are used in economics, political science, neuroscience, threshold logic, reliability theory and distributed systems. They model situations where agents with variable voting weight vote in favour of or against a decision. A coalition of agents is winning if and only if the sum of weights of the coalition exceeds or equals a specified quota. The Banzhaf index is a measure of voting power of an agent in a weighted voting game. It depends on the number of coalitions in which the agent is the difference in the coalition winning or losing. It is well known that computing Banzhaf indices in a weighted voting game is NP-hard. We give a comprehensive classification of weighted voting games which can be solved in polynomial time. Among other results, we provide a polynomial (O(k((n)/(k))k)) algorithm to compute the Banzhaf indices in weighted voting games in which the number of weight values is bounded by k.