Challenge: Write Ranked-Choice-Voting in Python

[Bill Bushey]

Hi PyMNtos,

It's been three days since the election, and still we do not have a certified winner for the mayoral election in Minneapolis. This delay, plus the computational nature of Ranked-Choice-Voting (RCV), has sparked a discussion among some of us over at Open Twin Cities about how RCV can be implemented as a simple computer program, what some advantages would be, and thoughts on why it hasn't yet. It's also led to two implementations of the RCV algorithm, one in Java and one in R.

Seeing folks create Java and R versions of RCV got me to wonder just how many implementations of RCV could be created by, say, the end of the weekend. Its a fun little project for anybody who's new to Python, or looking for a project to spend an hour or so on. Minneapolis has a page up with information on the process itself, and from what I know of it, the algorithm boils down to:

1. Create a data structure that represents a ballot with a 1st, 2nd, and 3rd choice for office
2. Count up the number of 1st choice votes for each candidate. If a candidate has 50% + 1 votes, declare that candidate the winner.
3. Else, select the candidate with the lowest number of 1st choice votes, pop the 1st choice off of any ballot for which that candidate was the first choice, and remove that candidate from all other ballots.
4. Goto 2

So, here is a fun challenge from Open Twin Cities: be the first person to implement RCV in Python. The person who replies to this thread first with a link to a Github repo with a working RCV implementation will get a shout-out on Twitter from Open Twin Cities, and a mention on OTC's site in a forthcoming post.

Cheers, and have fun,

Bill Bushey

Open Twin Cities

[Peter Farrell]

The time I checked the CRV data file wasn't available. The data from the MN SoS is only reported as aggregate and there for when a 1st choice candidate is eliminated we don't know what the 2nd choices are for those ballots. Has the raw data been release yet?

--
Meetings Schedule / RVSP on our Meetup at http://python.mn
---
You received this message because you are subscribed to the Google Groups "PyMNtos" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pymntos+u...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[John Trammell]

FWIW I implemented RCV in Perl some time ago, not too hard.

If anyone has access to the actual algorithm being used by Minneapolis I'd love to see it.

My understanding is that city elections is using a "physical" algorithm--moving the actual ballots around in piles--rather than digitizing the ballots and getting the results that way.  I may be wrong.  I'm curious what the process for validating a software solution would look like.

Best,
John

--

[David Fawcett]

The good news is that we apparently do officially have a mayor elect now!

Great idea Bill.  It would be awesome to have a public, open source, Python solution.  Something that could get lots of eyeballs and be run by anyone.  I cringed when I read that some of the counting work was being done in 80k line Excel spreadsheets.

There is somewhat of a controversy about the algorithm.  Joel Kramer wrote an editorial about it yesterday in MinnPost.  http://www.minnpost.com/politics-policy/2013/11/minneapolis-vote-count-process-based-faulty-logic-and-bad-arithmetic

For the TC Data Viz group, I was picturing a d3-based visualization of how each of the candidates fare through each RCV iteration. 

David.

[Peter Farrell]

Nope. The ballot information is electronic this year. In 2009, they did move physical ballots around.

What we need is the individual CRV files from each precinct to merge or the master CRV file.

[Kyle Marek-Spartz]

I heard on NPR that they were using Excel to compute the results!

-- 
Kyle Marek-Spartz

On November 8, 2013 at 9:29:02 AM, Peter Farrell (p...@maestropublishing.com) wrote:
>
>Nope. The ballot information is electronic this year. In 2009, they did
>move physical ballots around.
>
>What we need is the individual CRV files from each precinct to merge or the
>master CRV file.

>>> 1. Create a data structure that represents a ballot with a 1st, 2nd,

>>> and 3rd choice for office

>>> 2. Count up the number of 1st choice votes for each candidate. If a

>>> candidate has 50% + 1 votes, declare that candidate the winner.

>>> 3. Else, select the candidate with the lowest number of 1st choice

>>> votes, pop the 1st choice off of any ballot for which that candidate was
>>> the first choice, and remove that candidate from all other ballots.

>>> 4. Goto 2

[John Trammell]

I dug around on the city ordinances available online, and found this:

http://library.municode.com/HTML/11490/level3/COOR_TIT8.5EL_CH167MUELRUCO.html#COOR_TIT8.5EL_CH167MUELRUCO_167.10AP

I'll see if I can find the election coordinator and get a copy of the data...

[Peter Farrell]

Great. If you get it, please put it on GitHub.

[John Trammell]

Hello elec...@minneapolismn.gov:

I'm a member of a local Minnesota software user group (see www.python.mn) and former election judge in ward 11.  A number of other group members and I are curious about the RCV evaluation process for this year's municipal races.  Is there any chance we could get a copy of the original ballot data you're using to decide the winners?  We're discussing the feasability of implementing a software solution in parallel with the solution you're using.

I understand that you're very busy at the moment, so please prioritize this request as you see fit.

Thanks for all your hard work, we do appreciate it.

Best,
John Trammell

[Peter J. Farrell]

John Trammell said the following on 11/08/2013 10:10 AM:

> I dug around on the city ordinances available online, and found this:
>
> http://library.municode.com/HTML/11490/level3/COOR_TIT8.5EL_CH167MUELRUCO.html#COOR_TIT8.5EL_CH167MUELRUCO_167.10AP
>
> I'll see if I can find the election coordinator and get a copy of the
> data...
>
>

After quickly reading the municode, it sounds like only the voting
equipment needs to be certified. Certainly Excel has not gone through
that certification.

Let's get that data!

--
Peter J. Farrell
Principal Technologist - Maestro Publishing, LLC
http://blog.maestropublishing.com
Identi.ca / Twitter: @maestrofjp

* Learn about VSRE. I prioritize emails with VSRE in the subject! http://vsre.info/
* Please do not send me Microsoft Office/Apple iWork documents. Send OpenDocument instead! http://fsf.org/campaigns/opendocument/

[Mike Hicks]

They do list the output of each round here, and it would be possible to walk backwards through it to determine many of the original ballots, though the result of that would be missing vote combinations where a voter's second- or third-choice candidate had been eliminated in a previous round.

http://vote.minneapolismn.gov/results/2013/2013-mayor-tabulation

--
Mike Hicks | mul...@gmail.com

[Jim Cummins]

Hello all,

I am looking to work on this on Github. I was hoping to keep it CSV and D3 / Javascript as I'm not really up to snuff on my Python. 

Anyhow I am looking at this CSV file and was wondering if this was the same data you all are looking at?

http://vote.minneapolismn.gov/www/groups/public/@clerk/documents/webcontent/2013-mayor-final-rvc.xlsx

Jim

[Peter J. Farrell]

Jim Cummins said the following on 11/11/2013 04:42 PM:

> Hello all,
>
> I am looking to work on this on Github. I was hoping to keep it CSV
> and D3 / Javascript as I'm not really up to snuff on my Python.
>
> Anyhow I am looking at this CSV file and was wondering if this was the
> same data you all are looking at?
>
> http://vote.minneapolismn.gov/www/groups/public/@clerk/documents/webcontent/2013-mayor-final-rvc.xlsx

Nah, this is just details the each round of vote for the RCV. We
actually need the original ballot information --- so if 1st choice
Candidate X is eliminated, we need to know what that particular person's
2nd choice is. Right now the data posted is in aggregate...

An example might be -- each line is a "ballot" with up to three choices:

Joe,Jane,Gordon
Jane,Gordon,Randy
Jane
Gordon,Randy
Joe,Randy

[Bill Bushey]

Hi Everybody,

Sorry I've been silent all this time since posting the challenge. Friday, Saturday, and Sunday I was busy preparing for and helping to run the CityCampMN unconference and hackathon. Yesterday I finally slept :p

I was definitely unclear about one bit of this challenge. We are not asking for folks to count the actual Minneapolis Mayoral election. Instead, the challenge is focused on implementing the process of Ranked Choice Voting in Python. Because data on actual ballots are not yet available, you do not have to worry about matching a spec regarding ballots. All we are asking for is a simple Python script that could (with some modification) decide a RCV election, once ballot data becomes available.

I'm awake and not running an event, so I'm available to answer questions.

Cheers,

Bill

[Bill Bushey]

Congratulations to William Cannon for creating the Python implementation of RCV. And might I add, one of the most sophisticated implementations I've seen in any language.

Twitter Shoutout: https://twitter.com/OpenTwinCities/status/402816789807390722

Blog Post: http://www.opentwincities.org/2013/11/15/ranked-choice-voting-and-civic-tech-in-minneapolis/

Thanks to everybody who discussed and participated.

Cheers,

Bill