# -------
# ------- copeland - version 1.0
# ------- A simple self-contained function to compute:
# ------- * the Copeland ranking for all candidates in an election;
# ------- * the Copeland winner for an election, or winners, should a tie exist.
# ------- Note that if a Condorcet winner exists, it is the same as the Copeland winner.
# ------- 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:
# ------- Saari, Donald G. and Vincent R. Merlin (1996), "The Copeland Method I: Relationships and the Dictionary", Econ. Theory.
# ------- Available online at:
# ------- http://citeseer.ist.psu.edu/344687.html
# ------- A good introduction to voting theory can be found in:
# ------- Taylor, Alan D. (1995), "Mathematics and Politics: Strategy, Voting, Power and Proof", Springer-Verlag, New York, New York.
# -------
# ------- Program notes:
# ------- copeland(votes) takes as input:
# ------- * a list of tuples, with each tuple containing one voter's ranking of the candidates in decreasing order of preference
# ------- and returns a list containing:
# ------- * a dictionary containing candiate names as keys and Copeland scores as values
# ------- * a list of the Copeland winner(s)
# -------
# ------- Sample code notes:
# ------- To test copeland, try calling it with the following parameters:
# ------- test_votes = [('A','B','C'),('A','B','C'),('B','A','C'),('B','A','C'),('C','A','B'),('C','A','B'),('C','A','B')]
# ------- The result should be:
# ------- test_copeland = [{'A': 2, 'C': -2, 'B': 0}, ['A']]
# ------- A simple test program, illustrating a "typical" use scenario is included at the end of this file.
# -------
# ------- The copeland function
def copeland(votes):
number_votes = len(votes)
number_candidates = len(votes[0])
relative_wins = [ [0 for j in range(number_candidates)] for i in range(number_candidates) ] # Create a matrix to hold the relative wins
candidates_labels = list(votes[0]) # Create a sorted list of the candidates so as to label the matrix
candidates_labels.sort()
for i in range(number_votes): # Fill in the relative wins matrix
for j in range(number_candidates-1):
for k in range(j+1,number_candidates):
winner = candidates_labels.index(votes[i][j])
loser = candidates_labels.index(votes[i][k])
relative_wins[winner][loser] = relative_wins[winner][loser] + 1
relative_wins[loser][winner] = relative_wins[loser][winner] - 1
copeland_scores = number_candidates*[0] # Create a list to hold the Copeland scores
copeland_winners = number_candidates*[0] # Create a list to hold the Copeland winners
for i in range(number_candidates): # Find the Copeland scores
for j in range(number_candidates): # Aside from selecting a winner, these can also be used for rankings
if relative_wins[i][j] > 0:
copeland_scores[i] = copeland_scores[i] + 1
elif relative_wins[i][j] < 0:
copeland_scores[i] = copeland_scores[i] - 1
copeland_maximum = max(copeland_scores)
for i in range(number_candidates): # Find the Copeland winners
if copeland_scores[i] == copeland_maximum: # Two possibilities:
copeland_winners[i] = 1 # There is a Copeland winner (exactly one number in copeland_winners = 1)
else: # There is a Copeland tie (more than one number in copeland_winners = 1)
copeland_winners[i] = 0
copeland_winner_list = []
for i in range(number_candidates):
if copeland_winners[i] == 1:
copeland_winner_list = copeland_winner_list + [candidates_labels[i]]
copeland_rankings = dict([(candidates_labels[i],copeland_scores[i]) for i in range(number_candidates)])
results_list = [copeland_rankings,copeland_winner_list]
return results_list
# ------- End of copeland
# ------- A simple program to illustrate the use of copeland
import string
testvotes = [('c1', 'c2', 'c3'), ('c1', 'c2', 'c3'), ('c1', 'c2', 'c3'), ('c1', 'c2', 'c3'), ('c1', 'c2', 'c3'), ('c1', 'c2', 'c3'), ('c1', 'c2', 'c3'), ('c1', 'c2', 'c3'), ('c1', 'c3', 'c2'), ('c1', 'c3', 'c2'), ('c1', 'c3', 'c2'), ('c3', 'c1', 'c2'), ('c3', 'c2', 'c1'), ('c3', 'c2', 'c1'), ('c3', 'c2', 'c1'), ('c3', 'c2', 'c1'), ('c3', 'c2', 'c1'), ('c3', 'c2', 'c1'), ('c3', 'c2', 'c1'), ('c3', 'c2', 'c1'), ('c3', 'c2', 'c1'), ('c2', 'c3', 'c1'), ('c2', 'c3', 'c1'), ('c2', 'c3', 'c1'), ('c2', 'c1', 'c3'), ('c2', 'c1', 'c3'), ('c2', 'c1', 'c3')]
copeland_results = copeland(testvotes)
if len(copeland_results[1]) == 1:
print 'The Copeland winner is:', copeland_results[1][0]
else:
print 'There is a tie - the Copeland winners are:',
for i in copeland_results[1]:
print i,
print
print
print 'Ranking', 'Candidate', 'Score'
items = [(v, k) for k, v in copeland_results[0].items()]
items.sort()
items.reverse()
for i in range(len(items)):
print string.rjust(str(i+1), 4), string.rjust(items[i][1],8), string.rjust(str(items[i][0]), 7)
# -------