Tim Korb's Home Page

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
~~NOTOC~~





====== Hare Voting Procedure ======

The [[http://sof.uchicago.edu/hare|Hare System of Proportional Representation]] is a procedural description of the [[http://en.wikipedia.org/wiki/Single_transferable_vote|Single Transferable Vote (STV)]] preferential voting system.  It is "preferential" in the sense that voters rank the order of their chosen candidates (using, say, numbers 1-5), rather than using an unranked mark (e.g., one or more "X"s).  A common application is in the selection of committees, in which multiple winners must be chosen from a set of available candidates.  

(Note: The quota calculation described in this document and used in the associated software is actually based on the [[http://en.wikipedia.org/wiki/Droop_quota|Droop Quota]], not the [[http://en.wikipedia.org/wiki/Hare_quota|Hare Quota]].  The term //Hare// is retained here as the common name for //Single Transferable Vote// despite this inaccurate characterization.)

====== Background ======

I have written a simple [[http://www-cgi.cs.purdue.edu/cgi-bin/jtk/vote/vote.py|web-based program]] to determine winners in a Hare vote.  The input is a comma-separated value (CSV) file, typically generated from a spreadsheet.  The first cell is the number of winners to be chosen.  In the left column are the candidates; each subsequent column represents a ballot, with numbers giving the preferred rank for that candidate (with 1 being highest).  See example below, with candidates ''A-E'' and ballots ''B1-B7''.  The CSV file input format is very rigid: //no blanks are allowed in names or in the comma-separated rows of votes//, for example.  

^Sample Input (without comma separation)^^^^^^^^
|3|B1|B2|B3|B4|B5|B6|B7 
|A|1|3|4|1|5|1|2 
|B|2|2|3|2|2|3|1
|C|3|1|2|3|4|3|3
|D|4|4|5|4|3|2|5
|E|5|5|1|5|1|5|4

Because STV systems use randomization to redistribute excess ballots and to eliminate candidates with few votes, different runs can produce different results.  The program includes a "Run 500 Times" button that repeats the selection procedure 500 times and summarizes the results.

The program also includes a "Run All Ways" button that maintains a probabilistic analysis at each decision point in the algorithm.  The result is to compute probabilities of outcomes, rather than actually counting the outcomes.  To manage the potentially explosive growth of possibilities, the program automatically discards outcomes that have a very low probability of contributing to the final result.

Very little input checking is done, although the program will crash and give a (perhaps gibberish) diagnostic for some errors (e.g., using non-numeric ranks).  The input lines are split on commas, so names cannot contain commas, even if surrounded by quotes.  Please report any errors to [[mailto:jtk@cs.purdue.edu|me]].

//[[http://www-cgi.cs.purdue.edu/cgi-bin/jtk/vote/vote.py|Go to the Hare Voting Site]]//

====== Hare Voting and Computer Science/College of Science ======

The Hare Voting Procedure is the College of Science procedure to select small, representative groups, e.g., committees, boards, and councils.  The procedure is designed to prevent a single voting block from electing all candidates.

The procedure used by the College of Science is described in this [[http://www.science.purdue.edu/faculty_staff/policies/PP2006_11_16.pdf|document]], starting at page 35.  The procedure implemented above does not follow the CoS procedure in the following case: If there is a tie for weakest candidate, the CoS procedure chooses the candidate who had fewer votes in the previous round, if one exists; otherwise, a candidate is chosen at random.  The procedure implemented here always chooses a candidate at random from among those tied for last place, regardless of the status during the previous round.  (This procedure is consistent with the University of Chicago [[http://sof.uchicago.edu/hare/rules.html|rules]].)

====== How to Cast a Hare Ballot ======

Voters are given a list of candidates (a ballot), which they rank in order of preference: //c1//, //c2//, //c3//, ..., etc.  While it may appear that voters are selecting multiple individuals to fill the positions on the committee, they are not: Each voter's ballot will ultimately be cast for only //one// candidate.  The Hare Procedure moves ballots among candidates following rules that are intended to reflect the preferences of the voters.  The process stops when all (or nearly all) ballots have been assigned to the most popular candidates, who then make up the committee.   

A simple way for the voter to consider the process:

  * My first choice is for candidate //c1// to be selected to serve on the committee.
    * But, if //c1// is
      * so popular as to not need my vote, or
      * so unpopular as to not stand a chance,
    * then use my ballot to cast a vote for //c2// instead.
  * Repeat for all //ci//.

====== Hare Process ======

===== Initial Step =====

The first step in the process is to divide the ballots into sets based on the first candidate listed on each ballot.


===== Selection Step ====

In order to be selected, a candidate must have a minimum number of votes, called the //quota//, which is roughly the number of votes cast divided by the number of positions to be filled.  More precisely, the College of Science defines the //quota// to be //(votes cast + 1)/(number of positions + 1)// rounded up.  (As a side note, this quota calculation is actually closer to the "Droop" quota than the "Hare" quota, but we retain the older terminology to apply to the entire Single-Transferable-Vote process.)

  while there is a candidate that has the minimum number of votes
    select that candidate
    if the selected candidate has more than the minimum number of votes
      randomly choose excess ballot(s) and move each ballot to the candidate that is the next choice

At this point, no remaining candidate has enough votes to be selected, so low-ranking candidates are eliminated and their ballots reassigned.

===== Elimination Step =====

  choose a candidate randomly from those with the least number of votes
    redistribute ballot(s) to the next choice candidate(s)

Now, continue with the //Selection Step//, repeating both steps until all positions are filled.