CRP Script

From IcehouseOrg
Jump to: navigation, search

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