Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Banzhaf power index calculation
# -------
# ------- banzhaf - version 1.1
# -------
# ------- 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
# -------
# ------- This is a slight modification (mainly vectorization) of the code by
# ------- Ruben R. Puentedura (http://www.hippasus.com/resources/socialsoftware/index.html)
# ------- which was published under CC-License in 2004
# -------
# ------- 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]
# -------
def banzhaf(weight, quota):
max_order = sum(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<weight[i]):
swings[j] = polynomial[j]
else:
swings[j] = polynomial[j] - swings[j-weight[i]]
for k in range(weight[i]): # fill the Banzhaf Power vector
banzhaf_power[i] = banzhaf_power[i] + swings[quota-1-k]
# Normalize Index
total_power = float(sum(banzhaf_power))
banzhaf_index = map(lambda x: x / total_power, banzhaf_power)
return banzhaf_index
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment