Subversion Repositories Remote Hare Voting

Rev

Rev 10 | Blame | Last modification | View Log | RSS feed 

#!/p/python/python
##
## Compute Hare Ballot
##
## Tim Korb (jtk@cs.purdue.edu), May 2007
##
## A few definitions and notes...
##
## tally: dictionary in which the keys are candidate names and the
## values are lists of ballots currently assigned to that candidate
##
## ballot: list of candidates in the order determined by the voter
##
## winners: list of candidates that have reached the quota of ballots
## or have remained in the running long enough to be declared a winner
##
## losers: list of candidates that have been eliminated from the running
##
## Note that plurals are generally used to indicate lists of other
## objects, e.g., ballots is a list of ballots.
##
import cgi
import string
import sys
import math 
import random

from revision import revision

formaction = string.split(sys.argv[0],"/")[-1]

fTrace = 1
fHTML = 1

def emitPreHTML(formaction):
    emitHTML("""Content-type: text/html\n
<html>
<body>
<title>Hare Ballot Calculation</title>
    <h1>Hare Ballot Calculation</h1>
    <form enctype="multipart/form-data" method=POST action=%s>
        <table>
        <tr><td>CSV file of ballots:
                <td><input type=file size=70 name=name>
        </table>
        <p>
        <input type=submit name="run1" value="Run 1 Time">
        <input type=submit name="run1000" value="Run 1000 Times">
        <input type=submit name="convert" value="Convert to BLT Format">
    </form>
    <p>
Input file format is given
<a href="http://www.bikmort.com/wiki/index.php?title=Hare_Voting_Procedure">here</a>.
Almost no error checking is done, so be sure to review the trace output.
The source code is available <a href="%s?fetch=yes">here</a>.
<p>
<small>%s</small>
<hr>
<pre>
""" % (formaction, formaction, revision))
    return

def emitPostHTML():
    emitHTML("""</pre>
</body>
</html>
""")
    return

def emitHTML(s):
    global fHTML
    if fHTML: print s
    return

def trace(s):
    global fTrace
    if fTrace: print s
    return

def findWinner(winners, losers, tally, quota, nWinners):
    for candidate in tally.keys():
        if candidate not in winners and len(tally[candidate]) >= quota:
            return candidate

    # Check to see if only enough candidates remain
    n = 0
    last = ""
    for candidate in tally.keys():
        if candidate not in winners and candidate not in losers:
            last = candidate
            n = n + 1
    if nWinners - len(winners) >= n:
        return last
    return

def redistributeWinner(winner, winners, losers, tally, quota):
    excess = len(tally[winner]) - quota
    if excess <= 0:
        trace("\tno excess ballots to redistribute")
    else:
        trace("\tredistributing %d excess ballot(s) at random from %s" %
              (excess, winner))
        while len(tally[winner]) > quota:
            i = int(random.uniform(0, len(tally[winner])))
            trace("\trandom choice = ballot %d" % (i+1))
            ballot = tally[winner][i]
            tally[winner] = tally[winner][0:i] + tally[winner][i+1:]
            redistributeBallot(ballot, winner, winners, losers, tally)
    traceTally(quota, tally)

def redistributeBallot(ballot, candidateFrom, winners, losers, tally):
    for candidateTo in ballot:
        if candidateTo not in winners and candidateTo not in losers:
            trace("\tto %s: %s" % (candidateTo, ballot))
            if not tally.has_key(candidateTo): tally[candidateTo] = []
            tally[candidateTo].append(ballot)
            ballot = ""
            break
    if ballot:
        trace("\tineffective ballot dropped: %s" % ballot)

def findLoser(losers, winners, tally):
    cMin = sys.maxint  # least number of votes for candidate loser
    lMin = []          # list of candidates with least votes
    for c in tally.keys():
        if c not in losers and c not in winners and len(tally[c]) <= cMin:
            if len(tally[c]) == cMin:
                lMin.append(c)
            else:
                lMin = [c]
                cMin = len(tally[c])
    trace("\nELIMINATING LOW CANDIDATE RANDOMLY FROM %s" % lMin)
    if len(lMin) == 0:
        return None
    else:
        return random.choice(lMin)

def redistributeLoser(loser, losers, winners, tally, quota):
    excess = len(tally[loser])
    if excess <= 0:
        trace("\tno ballots to redistribute")
    else:
        trace("\tredistributing %d ballot(s) from %s" % (excess, loser))
        while len(tally[loser]) > 0:
            ballot = tally[loser][0]
            tally[loser] = tally[loser][1:]
            redistributeBallot(ballot, loser, winners, losers, tally)
    traceTally(quota, tally)
    return

def traceTally(quota, tally):
    global fTrace
    if not fTrace: return
    trace("\nCURRENT ASSIGNMENT OF BALLOTS (%d needed to win)" % quota)
    for candidate in tally.keys():
        trace("\t%s:" % candidate)
        for ballot in tally[candidate]:
            trace("\t\t%s" % ballot)
    return

# The basic Single Transferable Vote algorithm with Hare quota
#
# while winners < nWinners:
#   if a candidate has more than quota votes:
#       redistribute excess votes to next priority candidate
#   else:
#       eliminate lowest ranking candidate
#       redistribute wasted votes to next priority candidate
#
def dotally(nWinners, ballots):
    nBallots = len(ballots)
    quota = int(math.ceil((nBallots + 1.0)/(nWinners + 1)))

    trace("INPUT SUMMARY")
    trace("\t%d ballots" % nBallots)
    trace("\tChoosing %s winners" % nWinners)
    trace("\tNeed ceil((%d + 1)/(%d + 1)) = %d ballots to win" %
          (nBallots, nWinners, quota))

    # Create initial tally
    #
    tally = {}
    for ballot in ballots:
        candidate = ballot[0]
        if not tally.has_key(candidate):
            tally[candidate] = []
        tally[candidate].append(ballot)
    traceTally(quota, tally)
    
    winners = []
    losers = []

    while len(winners) < nWinners:
        winner = findWinner(winners, losers, tally, quota, nWinners)
        if winner:
            winners.append(winner)
            trace("\nSELECTION #%d: %s" % (len(winners), winner))
            redistributeWinner(winner, winners, losers, tally, quota)
        else:
            loser = findLoser(losers, winners, tally)
            if loser:
                losers.append(loser)
                trace("\nELIMINATED: %s" % loser)
                redistributeLoser(loser, losers, winners, tally, quota)
            else:
                trace("Not enough chosen candidates to fill all positions")
                break

    return winners

# Parse input file
#
# input: lines of comma-separated values
#       nWinners, ...ignored fields...
#       candidate1, ballot1rank, ballot2rank, ...
#       candidate2, ballot1rank, ballot2rank, ...
#
# output: list of lists of ballots
#       [[1stcandbal1, 2ndcandbal1, ...], [1stcandbal2, 2ndcandbal2, ...], ...]

def parsecontents(contents):
    lines = string.split(contents, "\r\n")
    fields = string.split(lines[0], ",")
    nWinners = int(fields[0])

    votes = []
    for line in lines[1:]:
        fields = string.split(line, ",")
        candidate = fields[0]
        positions = fields[1:]
        ballotnumber = 0
        for position in positions:
            if position:
                votes.append([ballotnumber, int(position), candidate])
            ballotnumber = ballotnumber + 1

    votes.sort()

    ballots = []
    ballotnumber = ""
    ballot = ""
    for triple in votes:
        if ballotnumber == triple[0]:
            ballot.append(triple[2])
        else:
            if ballot:
                ballots.append(ballot)
            ballot = [triple[2]]
            ballotnumber = triple[0]

    ballots.append(ballot)
    return nWinners, ballots

def main():
    global fTrace
    emitPreHTML(formaction)

    form = cgi.FieldStorage()

    if not form:
        emitHTML("Enter file name and press a button to see results.")
    elif form.has_key("fetch"):
        source = open(formaction).read()
        print cgi.escape(source)
    elif not form.has_key("name"):
        emitHTML("Error: no file received")
    elif not form["name"].filename:
        emitHTML("Error: file name missing")
    else:
        name = form["name"].filename
        contents = form["name"].value

        trace("INPUT FILE")
        trace(contents)

        nWinners, ballots = parsecontents(contents)
        if form.has_key("run1"):
            results = dotally(nWinners, ballots)
            print "\nFINAL RESULTS"
            for winner in results:
                print "\t%s" % winner
        elif form.has_key("run1000"):
            print "RUNNING 1000 TIMES"
            fTrace = 0
            summary = {}
            for i in range(1000):
                results = str(dotally(nWinners, ballots))
                # print "Run %2d: %s" % (i+1, results)
                if not summary.has_key(results):
                    summary[results] = 0
                summary[results] = summary[results] + 1
            print "\nSUMMARY"
            l = summary.items()
            l.sort(lambda x,y: cmp(y[1], x[1]))
            for pair in l:
                print "%2d %s" % (pair[1], pair[0])
        elif form.has_key("convert"):
            print "Convert feature not supported yet"
        else:
            print "UNEXPECTED SUBMIT BUTTON: %s" % form
                
    emitPostHTML()
    return

main()