Computer Algorithms for Power Indices

Notation and Definitions

A legislature that uses weighted voting and has n members is represented by a set N = {1, 2, … , n} whose voting weights are w1, w2, …, wn. Members vote for or against an action. The combined weight of a subset of members voting “for,” and represented by the subset T ⫅ (N), is denoted by . The decision rule is defined in terms of a quota, q, by which T is winning if w(T) > q and losing if w(T) < q. The weights and the quota are real numbers in general; although in most applications they are integers, this is not essential to the theory, but it is relevant to certain methods of computation, particularly the method of generating functions.

Frequently a voting body is represented using the notation {q; w1, w2, …, wn}. In this definition, there is a single decision rule and one set of weights. In some applications, it is necessary to generalize this: [Page 130]for example, the system of qualified majority voting in the European Union (EU) Council is formally a triple-majority rule in which three conditions must be satisfied in weighted votes, population, and number of member countries. But allowing for multiple majority rules is a minor complication that we can ignore for the present purpose of discussing algorithms.

Each member has a power index measuring the relative number of times that member can be the “swing” member. Formally, a swing for member i can be defined as a pair of subsets, (Ti, Ti+{i}), where Ti ⫅ N − {i}, such that Ti is losing, but Ti+ {i} is winning, that is, q — wi ≤ w(Ti) < q.

The Penrose-Banzhaf power index for member i, βi′, is the number of swings, ηi, expressed as a fraction of the total number of subsets of N, which is equal to 2n-1. It measures the probability of i being the swing voter assuming all swings Ti to be equiprobable.

The normalized Banzhaf index, βi uses the total number of swings for all players as the denominator to measure relative voting power among players,

This is a trivial normalization, so it is necessary to consider only the details of computing equation (1).

James S. Coleman's power indices are related to the Penrose-Banzhaf indices and require, in addition, the number of voting outcomes that lead to a positive decision, ω, that is, the number of subsets S (S ⫅ N) where w(S) ≥q. This imposes an extra computing requirement but enables us to calculate the three

...