Subversion Repositories Local Hare Voting

## 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
## items, e.g., ballots is a list of ballot items.
##
## To download the complete source distribution, use Subversion:
##
##      % svn co http://www.bikmort.com/hare
##
## $Id$

import sys
import math 
import random

fdOut = None
fTrace = 1
randcalls = 0

class Universe:
    id = 0                              # id of last create Universe

    def __init__(self, p, nWinners, nBallots, quota):
        Universe.id += 1
        self.id = Universe.id
        self.p = p
        self.nBallots = nBallots
        self.nWinners = nWinners
        self.quota = quota
        self.winners = []
        self.losers = []
        self.tally = {}

    def getP(self):
        print "instance p =", self.p
        print "class p =", Universe.p

def trace(s):
    global fTrace, fdOut
    if fTrace: print >>fdOut, s
    return

def findWinner(winners, losers, tally, quota, nWinners):
    global randcalls
    cWin = quota        # number of votes for highest winner
    lWin = []           # list of candidates with highest votes
    for c in tally.keys():
        if c not in losers and c not in winners and len(tally[c]) >= cWin:
            if len(tally[c]) == cWin:
                lWin.append(c)
            else:
                lWin = [c]
                cWin = len(tally[c])
    if len(lWin) == 1:
        return lWin[0]
    elif len(lWin) > 1:
        trace("\tselecting winning candidate randomly from %s" % lWin)
        randcalls += 1
        return random.choice(lWin)

    # Check to see if only enough candidates remain
    ## TODO: sort by len(tally[c]) to choose larger winners first
    ## randomize and count if some with equal votes
    n = 0
    last = ""
    for c in tally.keys():
        if c not in winners and c not in losers:
            last = c
            n = n + 1
    if nWinners - len(winners) >= n:
        trace("\tremaining winner(s) have fewer than quota (%d) ballots" %
            quota)
        return last
    return

def redistributeWinner(winner, winners, losers, tally, quota):
    global randcalls
    excess = len(tally[winner]) - quota
    if excess <= 0:
        trace("\tno excess ballots to redistribute")
    else:
        lEffective = gatherEffectiveBallots(winner, winners, losers, tally)
        nRedistribute = min(excess, len(lEffective))
        trace("\tredistributing %d effective of %d excess ballot(s) at random from %s" %
              (nRedistribute, excess, winner))
        for ballot in random.sample(lEffective, nRedistribute):
            randcalls += 1
            trace("\trandom choice = %s" % ballot)
            tally[winner].remove(ballot)
            redistributeBallot(ballot, winners, losers, tally)
            nRedistribute -= 1
    traceTally(quota, tally)

def gatherEffectiveBallots(winner, winners, losers, tally):
    lEffective = []
    for ballot in tally[winner]:
        for candidateTo in ballot:
           if candidateTo not in winners and candidateTo not in losers:
                lEffective.append(ballot)
                break
    return lEffective

def redistributeBallot(ballot, 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):
    global randcalls
    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])
    if len(lMin) == 0:
        return None
    elif len(lMin) == 1:
        return lMin[0]
    else:
        trace("\teliminating low candidate randomly from %s" % lMin)
        randcalls += 1
        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, 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):
    global randcalls
    randcalls = 0

    nBallots=len(ballots)
    quota=int(math.ceil((nBallots + 1.0)/(nWinners + 1)))

    universe = Universe(1.0, nWinners, nBallots, quota)

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

    # Create initial tally and statistics
    #
    for ballot in ballots:
        candidate = ballot[0]
        if not universe.tally.has_key(candidate):
            universe.tally[candidate] = []
        universe.tally[candidate].append(ballot)

    total1st = {}
    total2nd = {}
    totalMrk = {}

    for ballot in ballots:
        for c in ballot:
            total1st[c] = 0
            total2nd[c] = 0
            totalMrk[c] = 0

    for ballot in ballots:
        total1st[ballot[0]] += 1
        if len(ballot) > 1:
            total2nd[ballot[1]] += 1
        for c in ballot:
            totalMrk[c] += 1

    trace("\n\tBALLOT MARKS\t1ST\t2ND\tNONE")
    candidates = totalMrk.keys()
    candidates.sort()
    for c in candidates:
        trace("\t%-16s%3d\t%3d\t%4d" % (c, total1st[c], total2nd[c], len(ballots)-totalMrk[c]))
    traceTally(universe.quota, universe.tally)

    continueTally(universe)
    return universe.winners

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