Subversion Repositories Remote 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

## objects, e.g., ballots is a list of ballots.

##

import math 

import random

from revision import revision

fTrace = 1

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

    global fTrace