# -------
# ------- banzhaf - version 1.0
# ------- A simple self-contained function to compute the Banzhaf Power Index given:
# ------- * a list of integer weights for all voters in the system, sorted in ascending order
# ------- * the quota for the voting system
# ------- Copyright 2004 Ruben R. Puentedura
# -------
# ------- This software is released under a Creative Commons 2.0 Attribution License:
# ------- You are free:
# ------- * to copy, distribute, display, and perform the work
# ------- * to make derivative works
# ------- * to make commercial use of the work
# ------- Under the following conditions:
# ------- * Attribution. You must give the original author credit.
# ------- * For any reuse or distribution, you must make clear to others the license terms of this work.
# ------- * Any of these conditions can be waived if you get permission from the copyright holder.
# ------- The full legal text for this license is available at:
# ------- http://creativecommons.org/licenses/by/2.0/legalcode
# -------
# ------- Background notes:
# ------- The algorithm used here is based upon the description in:
# ------- Leech, Dennis (2002), "Computation of Power Indices", Warwick Economic Research Papers, Number 644, University of Warwick.
# ------- Available online at:
# ------- http://www.warwick.ac.uk/~ecrac/twerp644.pdf
# ------- A good introduction to the Banzhaf Power Index can be found in:
# ------- Taylor, Alan D. (1995), "Mathematics and Politics: Strategy, Voting, Power and Proof", Springer-Verlag, New York, New York.
# -------
# ------- Program notes:
# ------- banzhaf(weight, quota) returns a list containing the Banzhaf Power Index for all voters in the system
# ------- * weight is a list of integer weights for all voters in the system, sorted in ascending order
# ------- * quota is an integer which designates the number of votes needed for a coalition to win
# ------- The program will run in a few seconds for "reasonable" scenarios:
# ------- * total number of voters on the order of up to a thousand or so;
# ------- * maximum number of votes per voter on the order of up to a hundred or so.
# ------- Even many "unreasonable" scenarios will run quickly.
# ------- For scenarios that take too long to run using this code, a Monte Carlo approach may work best - see Leech (2002) for more info.
# -------
# ------- Sample code notes:
# ------- To test banzhaf, try calling it with the following parameters:
# ------- test_weight = [1,2,2,4,4,4]
# ------- test_quota = 12
# ------- These parameters correspond to the EEC in 1958 - the members (ordered by increasing voting weight) were:
# ------- Luxembourg, Netherlands, Belgium, Italy, Germany, France
# ------- The result should be:
# ------- test_index = [0.0, 0.14285714285714285, 0.14285714285714285, 0.23809523809523808, 0.23809523809523808, 0.23809523809523808]
# ------- A simple test program, illustrating a "typical" use scenario is included at the end of this file.
# -------
# ------- The banzhaf function
def banzhaf(weight, quota):
max_order = 0 # compute the maximum order for our polynomial
for each_weight in weight:
max_order = max_order + each_weight
polynomial = [1] + max_order*[0] # create a list to hold the polynomial coefficients
current_order = 0 # compute the polynomial coefficients
aux_polynomial = polynomial[:]
for i in range(len(weight)):
current_order = current_order + weight[i]
offset_polynomial = weight[i]*[0]+polynomial
for j in range(current_order+1):
aux_polynomial[j] = polynomial[j] + offset_polynomial[j]
polynomial = aux_polynomial[:]
banzhaf_power = len(weight)*[0] # create a list to hold the Banzhaf Power for each voter
swings = quota*[0] # create a list to compute the swings for each voter
for i in range(len(weight)): # compute the Banzhaf Power
for j in range(quota): # fill the swings list
if (j