  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{(\frac{n}{k})}^k)$) algorithm to compute the Banzhaf indices in weighted
voting games in which the number of weight values is bounded by $k$.

Computer Science and Game Theory;Computational Complexity;Data Structures and Algorithms