Earlier in the thread Arend said they used Javascript to tabulate the elections, so I’m assuming they wouldn’t be using my library.
Here’s a plodding description of how my deterministic tiebreaker works, including the various Python data structures and library routines I used. Sorry if any/all of this is obvious–I’m only a programmer, and I’ve barely dipped a toe in the election science world.
- Start with the following data:
- a list of all the ballots. I store ballots as a dict, mapping candidate name to vote.
- an integer representing this tiebreaker. I start with 1 for the first tiebreaker, and if I wind up needing additional tiebreakers I increment this integer by 1 each time (so it’s 1, 2, 3, 4, etc).
- a list of the candidates.
- Sort the list of candidates.
- Convert each of the ballot dicts into a ballot list: a list of tuples of (candidate name, vote). Now you have a list of ballot lists.
- Sort each ballot list.
- Sort the list of ballot lists. You now have a deterministic blob of data; for this election, with these ballots, this sorted list of sorted ballot lists will always be identical.
- Serialize the list of ballot lists into binary data. I used the Python function marshal.dumps, but pickle.dumps might be better if you care about consistent results between Python versions or across platforms. Either one will produce identical results every time when run with the same Python binary.
- Use a high-quality hash algorithm to hash the integer, followed by the serialized list of ballot lists. I used SHA3-512, because it’s awesome, and because I wanted lots of bits in the result. This produces a binary digest.
- Use the binary digest to seed a PRNG. I created a new Python’s random.Random object, passing in the digest for the seed argument to its constructor. This object uses the Mersenne Twister algorithm.
- Shuffle the sorted list of candidates, using a random shuffle algorithm, using the PRNG I just created above. I called the shuffle method on my Random object, passing in the list of candidates.
- (Actually, I shuffled it three times, just for fun. This shouldn’t be necessary. I guess I have a misguided sense of fun.)
- When breaking a tie, you have a set C of tied candidates of length |C|, and you want to choose M of them, where M < |C|. I iterate over the shuffled list and select the first M candidates I see that are members of C. For example, if the shuffled list is [ Z X G Q R E ], and there’s a three-way tie between Z Q and E, and we need to choose two candidates to break the tie, I’d pick Z and Q, because those are the two candidates of C that appear earliest in the shuffled list. In Python you could express that as
[ candidate for candidate in shuffled_sorted_candidates if candidate in C ][:M].