# ------- # ------- 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) # -------