How will New York City physically implement the ranked choice voting algorithm with thousands of unique mayoral votings possible?

Question

Politico's New Yorkers pick a new mayor after chaotic, historic primary begins:

NEW YORK — Polls have closed in New York City’s first ever ranked-choice election and, while the die has been cast, voters may not know the outcome for weeks.

[...] Further extending the ballot count is the advent of ranked-choice voting, which allows New Yorkers to select up to five candidates for each position. The system kicks in when no candidate attains 50 percent of votes on the first pass. The board plans to issue preliminary results of ranked ballots on June 29.

According to this:

More than a dozen Democrats and two Republicans will vie to replace outgoing Mayor Bill de Blasio (D). The ranked-choice election is expected to take weeks to resolve.

So the number of distinct yet valid ways a person could vote is large. I think that it's the sum of 0-, 1-, 2-, 3-, 4- and 5-from-14 possibilities, but I'm not even sure of that (see below).

I'm curious how New York City will physically and computationally implement ranked-choice vote counting.

Question: Algorithmically it can be done via several passes of a sorting function over all ranked-choice votes in a table in memory or on a hard drive, but how do they implement this with the various physical forms of votes cast in New York's mayoral election?

Will they resort to all electronic implementation of the algorithm, all physical, or some hybrid method?

---

In Python, assuming (for example) exactly 14 candidates available (in math it's number of permutations without repetitions)

from itertools import permutations
possible = []
for k in [0, 1, 2, 3, 4, 5]:
    uniques = list(permutations('abcdefghijklmn', k))
    possible.append(uniques)
    print(k, len(uniques))
all_possible = sum(possible, [])
print('total: ', len(all_possible))

 k        uniques
 0           1
 1          14
 2         182
 3        2184
 4       24024
 5      240240

total:  266645

Answer 1

How ranked choice voting ballots can be counted by hand

I think the counting can be done by hand (using several 'passes' if necessary). For example, in Canada, according to CBC.ca (on ranked voting in Canada):

"They're really simple. They're as easy as one, two three. You rank your choices in order — so who do I want to be mayor, who's my first choice, who's my second choice, and who's my third choice.

In the first round, we just add up the first choices, and if anyone has a majority, it's over. They win. But if nobody has a majority — let's say the person with the most votes only has 30 per cent — then obviously they shouldn't be the mayor necessarily.

So you eliminate the candidate with the fewest votes, and you just transfer those ballots to the second choice on each ballot until somebody has a majority.

Counting this by hand doesn't seem so difficult, you wouldn't need to account for all the possible ballot combinations in the counting process.

As the quote says, you start by dividing the ballots by first choice. If you have 14 candidates, then you have 14 piles of ballots. If there's no winner based on first choices, then you eliminate the candidate with the fewest (first choice) votes and start looking at the second choice on the ballots from that pile. Then you have only 13 candidates left in the running. this process continues until you have a winner.

This is also how NPR describes the counting process for the New York City mayoral election:

1. If someone gets 50% plus one after all the first-choice votes are counted, then the election is over and that candidate wins.

2. But if no one gets 50% plus one, it's on to Round 2.

3. The person with the lowest number of first-place votes is eliminated, and that candidate's voters' second choices get redistributed as votes for other candidates.

4. This reallocation of votes goes on until someone reaches 50% plus one.

New York's implementation

In New York's election though, the votes will be counted by machine. As CBS News reported on May 25th 2021:

New Yorkers can expect to find out who won the city's upcoming Democratic mayoral primary more quickly than they would have if the New York State Board of Elections hadn't acted Tuesday to approve software for tabulating ranked-choice voting results. The decision means the city will now avoid a lengthy hand count of the ballots cast in the race next month.

Nevertheless, results probably won't be available right away, from that same CBS News article:

Despite the software approval, it'll still be days, if not weeks, before New Yorkers know who won the June 22 primary. Unofficial results of the first-choice votes are expected to be released on primary night to show first-choice votes, but the city Board of Elections says that officials won't be able to start calculating results until at least the following week.

As for the specific implementation, that's already been covered in-depth by Zach Lipton's answer.

Answer 2

New York City did tabulate some ranked choice ballots by hand in special elections earlier this year, where the number of ballots and candidates was comparatively small and hand counting was more feasible.

However, for the Mayoral election, the state Board of Elections certified software for the counting process: The RCV Universal Tabulator, an open source package produced by a non-profit group called The Ranked Choice Resource Center.

The software is open source and can be viewed on GitHub. I imagine the physical ballots will be scanned using typical certified voting tabulation equipment to produce the input for the RCV software. If you're able to read Java, the core tabulation loop looks pretty straightforward (the software supports multiple winners, though that's clearly not being used in this election):

// At each iteration, we'll either a) identify one or more
// winners and transfer their votes to the remaining candidates (if we still need to find more
// winners), or b) eliminate one or more candidates and gradually transfer votes to the
// remaining candidates.

They'll eventually release the full cast vote record as well, which will allow anyone to perform their own version of the algorithm if they wish.

Answer 3

I think you're misunderstanding how the ranked choice voting works. If, as was the case, no candidate crosses 50% of the vote, the last-place candidate is eliminated. Their ballots are now all allocated to the second-choice candidates from their voters. So the only votes that need to be re-counted are the last-place candidate's.

We then go back to the beginning and pretend that those recategorized votes have the second-choice candidate as their first-choice candidate, third-choice as second-choice etc. and again look to see if anyone has crossed 50%. If not, we repeat the process with the new last-place candidate. Note that it's possible that the threshold for 50% will go down as the process continues if anyone doesn't pick a second- or third- etc. candidate.

The process is described here: https://vote.nyc/page/ranked-choice-voting

I'd add also, that (a) they're not going to start the process until next week and (2) some of the early round reallocations will go really fast since there are very small numbers for the most minor candidates.

Answer 4

I'm curious how New York City will physically and computationally implement ranked-choice vote counting.

Physically, voters received a tabular ballot (see this NYC government page) where rows are candidates and columns are order of preference, and the ballots are scanned to obtain varying length records (the voter can express 1÷5 choices) containing the voted candidates in order of preference.

Computationally, NYC has a more fail-safe version of this (relatively) simple Python script

from random import seed, shuffle
from timeit import default_timer as dt
seed(20210622)
n_candidates, n_choices, n_ballots = 14, 5, 10**6    
# ##### generate the ballots
start_generation = dt()
candidates = list(range(n_candidates))+[0] # introducing a bias for candidate 0
ballots = [candidates[:n_choices] for _ in range(n_ballots)
           if not shuffle(candidates)]
print("\nGeneration of %d ballots required %.2f s"%(
        n_ballots, dt()-start_generation))

# ##### process the ballots
start_count = dt()
while True:
    counts = {candidate:0 for candidate in candidates}
    # count 1st choices
    for ballot in ballots: counts[ballot[0]] += 1
    # sort candidates according to 1st choices
    ranks = sorted(list(counts.items()), key=lambda t:t[1])
    # max no. of 1st choices
    max_1st = ranks[-1][1]
    # if there is a winner, stop counting
    if max_1st > len(ballots)//2: break
    
    # who is the loser?
    loser = ranks[0][0]
    
    # remove loser from ballots and from list of candidates
    for ballot in ballots:
        if loser in ballot: ballot.remove(loser)
    candidates.remove(loser)

    # remove any empty ballot from list of ballots
    # (copying not empty ballots is WAY FASTER than deleting void ballots)
    ballots = [ballot for ballot in ballots if ballot]

# we have a winner
print(*reversed(ranks), sep='\n')
print("Counting %d ballots required %.2f s"%(
        n_ballots, dt()-start_count))

When I ran it on my old, low end notebook I got the following output

Generation of 1000000 ballots required 9.29 s
(0, 490711)
(12, 245897)
Counting 1000000 ballots required 6.08 s

Even in this simulation it is apparent that the real problem is preparing the data in a format that is suitable for counting, then it's a matter of seconds…

---

As a foot note, initially I thought I had to optimize the script using vector math libraries but it turned out it is not necessary.