Instant-runoff Voting

Recently, I had a conversation with a friend in Australia who told me about the voting system used in most of their elections: instant-runoff voting.

Instead of voting for a single candidate, you rank candidates in the order of preference. This ranking system is used to choose a best candidate.

1. Count each person's most preferred candidate.
2. The winning candidate must have more than 50% of the votes.
3. Otherwise, remove the candidate with the least number of overall votes, and try again.

Let's implement a voting system like this in Factor.

Assuming voters provide an ordered list of candidates, we can count everyone's top candidate:

: count-votes ( votes -- total )
    [ first ] histogram-by sort-values ;

A candidate wins the election if he has a simple majority (more than 50%) of the votes:

: choose-winner ( votes total -- winner/f )
    last first2 rot length 2/ > [ drop f ] unless ;

If the candidate with the most votes did not achieve a majority of the votes, we remove all votes for the candidate with the least number of votes:

: remove-loser ( votes total -- newvotes )
    first first swap [ remove ] with map ;

The full implementation of our instant-runoff voting system:

: instant-runoff ( votes -- winner )
    dup count-votes 2dup choose-winner
    [ 2nip ] [ remove-loser instant-runoff ] if* ;

One improvement we could make would be to support versions of this model that do not require voters to rank all the candidates (an assumption that the code above makes).

The code for this is on my GitHub.