CRP Script
This is Zarf's Condorcet Ranked Pairs solution script which is also available at http://eblong.com/zarf/ftp/rpvote.py.
It must be copied to a local file named rpvote.py and run using a local votes file in the format specified in the script header.
#!/usr/bin/env python """ Ranked Pairs Vote Resolver Written by Andrew Plotkin (erkyrath@eblong.com). This program is in the public domain. This is an implementation of the Condorcet Ranked-Pairs system. See <http://condorcet.org/rp/index.shtml>. This is not a *perfect* Condorcet implementation. I've made one modification to the system, added one hack, and left one bug. Sorry! They were all for pragmatic reasons. I will describe them all further down. To use this, create a vote file in the following format: ----------------------- * AAA BBB CCC DDD # The first line should begin with a *. This defines the list of # candidates in the contest. (All on one line, separated by whitespace.) # The remaining lines define ballots -- one line per voter. DDD CCC BBB AAA # This is a complete ballot. The voter ranked all four candidates, # from DDD (best) to AAA (worst). DDD AAA BBB # This is an incomplete ballot. The voter only ranked three candidates; # he didn't have any opinion about CCC at all. (This neither helps nor # hurts CCC.) DDD AAA/CCC BBB # This ballot contains a tie. The voter liked DDD best, BBB least, # and AAA and CCC tied for middle place. This is not the same as the # previous ballot, because the voter *did* express opinions about CCC; # he says CCC is better than BBB and worse than DDD. CCC AAA/DDD/BBB # This voter likes CCC best, but sees the other candidates as all # equally bad. This ballot *does* hurt AAA, BBB, and DDD. AAA # This voter says AAA is... well, he isn't saying anything about AAA. # This is legal, but pointless. It doesn't express any preferences # at all, so it's the same as not voting. AAA/DDD # This voter ranked AAA and DDD as equal and ignores the others. This # is also pointless; it doesn't favor any candidate over another. ----------------------- To run the script: python rpvote.py VOTEFILE You will see two charts and a final tally. The first chart looks like this: ----------------------- Margins: AAA BBB CCC DDD AAA ` 1 -2 -3 BBB -1 ` -3 -3 CCC 2 3 ` -1 DDD 3 3 1 ` ----------------------- For any two candidates, this lists the margin between the people who preferred one and the people who preferred the other. In our example, two voters preferred AAA over BBB, and one preferred the reverse; the difference is 1. So AAA's margin over BBB is 1. (And BBB's margin over AAA is -1.) The margin of DDD over AAA is 3, because three voters preferred DDD over AAA (and none the reverse). Ties might appear as 0, or (if nobody expressed a preference at all) a blank entry. The second chart: ----------------------- Outrankings: AAA BBB CCC DDD AAA ` + - - BBB - ` - - CCC + + ` - DDD + + + ` ----------------------- This expresses which candidates beat which others, once everything is worked out. In our example, AAA beats BBB, but loses to CCC and to DDD. ----------------------- Place: Name (wins, losses, unresolved) 1: DDD (3, 0, 0) 2: CCC (2, 1, 0) 3: AAA (1, 2, 0) 4: BBB (0, 3, 0) ----------------------- This is the final tally. Each entry simply reads off a row of the previous chart; CCC scored two wins (+) and one loss (-), so its standing is 2, 1, and 0. The tally is sorted in order of the final standing. Ties will show up as a " mark in the first column. This code includes a tiebreaker rule -- see below -- but there can still be genuine ties. For example, if nobody votes at all, you'd see this tally: ----------------------- Place: Name (wins, losses, unresolved) 1: AAA (0, 0, 3) ": BBB (0, 0, 3) ": CCC (0, 0, 3) ": DDD (0, 0, 3) ----------------------- This indicates that all four candidates were tied for the first (and only) place. ----------------------- The caveats: My modification to Condorcet is to accept incomplete ballots. (All the sample ballots above which list fewer than four candidates are incomplete.) An ideal Condorcet system only accepts complete ballots. If you want to run the election this way, simply reject all incomplete ballots. Alternatively, you can add missing entries as a tie for last place. So if a voter offers you "AAA BBB", you would record it as "AAA BBB CCC/DDD". If you do this, be sure to explain that an incomplete ballot *does* hurt the missing candidates! My hack is a tiebreaker rule. An election with few voters will tend to produce ties. That is, a pair of candidates will be indeterminate -- neither beats the other according to the Condorcet rules. I resolve these in favor of whichever candidate beat the most other candidates overall. If that doesn't help, I pick whichever candidate lost to the fewest others overall. The bug is in a particular corner case: when a set of pairs have the same margin, are not contradicted by higher-margin pairs, but contradict each other. My code tries to resolve this, but not in a very smart way. """ import sys class Contest: def __init__(self, ents): self.entries = ents self.count = len(ents) self.colwidth = max([ len(key) for key in ents ]) self.colwidth = max(self.colwidth, 3) self.keydict = {} for key in ents: self.keydict[key] = True self.ballots = [] self.margins = {} def iskey(self, key): return self.keydict.has_key(key) def addballot(self, ls): self.ballots.append(ls) def printballots(self): print len(self.ballots), 'ballots:' for ballot in self.ballots: for ls in ballot: if (len(ls) == 1): print ls[0], else: print '(' + '/'.join(ls) + ')', print print def computemargins(self): for ballot in self.ballots: ranks = len(ballot) for ix in range(ranks): for row in ballot[ix]: for jx in range(ranks): if (jx == ix): continue for col in ballot[jx]: self.applymargin(row, col, (ix<jx)) def applymargin(self, row, col, rowwins): val = self.margins.get( (row,col), 0) if (rowwins): val += 1 else: val -= 1 self.margins[(row,col)] = val def printmargins(self): print 'Margins:' wid = self.colwidth print ''.rjust(wid), for col in self.entries: print col.rjust(wid), print for row in self.entries: print row.rjust(wid), for col in self.entries: if (col == row): val = '`' else: val = self.margins.get((row,col), '') print str(val).rjust(wid), print print def compute(self): dic = {} for tup in self.margins.keys(): val = self.margins.get(tup, 0) if (val <= 0): continue ls = dic.get(val) if (not ls): dic[val] = [tup] else: ls.append(tup) outcome = Outcome(self) if (not dic): return outcome maxmargin = max([ val for val in dic.keys() ]) for level in range(maxmargin, 0, -1): ls = dic.get(level) if (not ls): continue compatls = [ tup for tup in ls if outcome.compatible(*tup) ] try: newout = outcome.clone() for tup in compatls: newout.accept(*tup) outcome = newout continue except: #print 'WARNING: Contradiction at level', level, '('+str(len(compatls)), 'pairs)' pass notguilty = [] for avoid in compatls: try: newout = outcome.clone() for tup in compatls: if (tup == avoid): continue newout.accept(*tup) except: notguilty.append(avoid) if (len(notguilty) == 0 or len(notguilty) == len(compatls)): #print '...all pairs eliminated.' continue #print '...', len(notguilty), ' pairs remain.' try: newout = outcome.clone() for tup in notguilty: newout.accept(*tup) outcome = newout continue except: #print 'WARNING: Contradiction at level', level, 'still exists' pass return outcome class Outcome: def __init__(self, contest): self.contest = contest self.entries = contest.entries self.higher = {} self.lower = {} def printout(self): print 'Outrankings:' wid = self.contest.colwidth print ''.rjust(wid), for col in self.entries: print col.rjust(wid), print for row in self.entries: print row.rjust(wid), for col in self.entries: if (col == row): val = '`' else: val = '' dic = self.higher.get(row) if (dic and dic.get(col)): val += '-' dic = self.lower.get(row) if (dic and dic.get(col)): val += '+' print str(val).rjust(wid), print print def result(self): total = self.contest.count - 1 res = {} for row in self.entries: wins = 0 losses = 0 for col in self.entries: if (col == row): continue dic = self.higher.get(row) if (dic and dic.get(col)): losses += 1 dic = self.lower.get(row) if (dic and dic.get(col)): wins += 1 res[row] = (wins, losses, total-(wins+losses)) return res def printresult(self): res = self.result() ls = list(self.entries) def func(key1, key2): (w1,l1,t1) = res[key1] (w2,l2,t2) = res[key2] val = cmp((w2,t2), (w1,t1)) return val ls.sort(func) print 'Place: Name (wins, losses, unresolved)' wid = self.contest.colwidth ix = 1 lastkey = None for key in ls: (wins, losses, ties) = res[key] if ((not lastkey) or func(lastkey, key)): place = str(ix)+':' else: place = '":' print place.rjust(4), key.rjust(wid), (wins, losses, ties) ix += 1 lastkey = key def clone(self): res = Outcome(self.contest) for key in self.higher.keys(): res.higher[key] = self.higher[key].copy() for key in self.lower.keys(): res.lower[key] = self.lower[key].copy() return res def known(self, winner, loser): dic = self.higher.get(loser) if (dic and dic.get(winner)): return True return False def compatible(self, winner, loser): if (winner == loser): raise Exception('Entry cannot beat itself.') dic = self.higher.get(winner) if (dic and dic.get(loser)): return False dic = self.lower.get(loser) if (dic and dic.get(winner)): return False return True def accept(self, winner, loser): facts = [(winner,loser)] while facts: (winner,loser) = facts.pop(0) if (not self.compatible(winner, loser)): raise Exception('Contradiction.') if (self.known(winner, loser)): continue dic = self.lower.get(winner) if (not dic): self.lower[winner] = { loser:True } else: dic[loser] = True dic = self.higher.get(loser) if (not dic): self.higher[loser] = { winner:True } else: dic[winner] = True dic = self.higher.get(winner) if (dic): for key in dic.keys(): if (not self.known(key, loser)): facts.append( (key, loser) ) dic = self.lower.get(loser) if (dic): for key in dic.keys(): if (not self.known(winner, key)): facts.append( (winner, key) ) def derive(self, winner, loser): res = self.clone() res.accept(winner, loser) return res def read_file(file): contents = None ballots = [] while True: ln = file.readline() if (not ln): break ln = ln.strip() if (not ln): continue if (ln.startswith('#')): continue if (ln.startswith('*')): if (contents): raise Exception('More than one line in the input file begins with *.') contents = ln else: ballots.append(ln) if (not contents): raise Exception('No line in the input file begins with *.') entries = contents[1:].split() if (not entries): raise Exception('The * line has no contents.') dic = {} for val in entries: dic[val] = True if (len(dic) != len(entries)): raise Exception('Duplicate entry in * line.') contest = Contest(entries) for ln in ballots: ls = ln.split() ls = [ val.split('/') for val in ls ] dic = {} for subls in ls: for val in subls: if (not contest.iskey(val)): raise Exception('Unknown key in ballot: ' + val) if (dic.has_key(val)): raise Exception('Repeated key in ballot: ' + val) dic[val] = True contest.addballot(ls) return contest if (len(sys.argv) > 1): file = open(sys.argv[1], 'rU') else: file = sys.stdin try: contest = read_file(file) except Exception, ex: print ex sys.exit(1) if (file != sys.stdin): file.close() #contest.printballots() contest.computemargins() contest.printmargins() outcome = contest.compute() outcome.printout() outcome.printresult()