Ranked-Choice Tally: Ballot Rules, Runoffs and Multi-Winner Counts

Ranked-Choice Tally: Ballot Rules, Runoffs and Multi-Winner Counts

You've joined the elections-engineering team that maintains rcv, the tabulation service the county elections office runs on election night. The same code counts ranked-choice ballots for the county's single-winner contests and, as of this year, for the Harbor Pilots Association's board elections. A hand count of the association's chair race disagreed with the software (ticket HB-117), and the roadmap has four more items queued behind the fix: faster runoffs, a candidate withdrawal ruling, multi-winner contests, and the November countywide count of several hundred thousand ballots.

Codebase

lots.py and synthetic.py are known good. Convention: every candidate id in the system (config, ballots, withdrawals, reports) is first passed through marks.canonical_id.

How your code is run

run(operations) executes the operations in order against one fresh election and returns one result per operation. Errors are returned as "error: <code>" strings, never raised. Unless a Part says otherwise, operations are checked in this order: the operation is a list starting with a string name (else invalid arguments), the name is known (unknown operation), the number of arguments is right (invalid arguments), the election is configured (not configured, for everything except configure), then the operation's own checks in the order listed.

Config. {"candidates": [...], "seats": 1, "method": "irv", "max_rank": 6, "lot_seed": 0, "batch_elimination": false}. Only candidates is required (2 to 30 distinct ids after canonicalising). method is "irv" or "stv"; irv needs seats 1, seats must be less than the number of candidates, max_rank is 1 to 9, batch_elimination is a bool (not allowed with stv). Anything else is invalid config. A certified write-in candidate is listed like any other, as "w:<name>"; ids are reported in canonical form, candidates in plain string order.

Ballots. A ballot is a list of rank entries (at most 40), best rank first. An entry is null (nothing marked), a string (one mark) or a list of strings/nulls (several marks at the same rank). copies is an integer from 1 to 10 000 000 and means that many identical papers.

Reading a ballot (ballots.normalize)

A ballot becomes an order: the candidates the voter effectively ranked, best first. Look at ranks 1..max_rank (later entries are ignored) one at a time, with a counter of consecutive skipped ranks:

1. The marks at a rank that are *registered* candidates (after canonicalising; duplicates of the same candidate at one rank are one mark) are its votes. Blank, unregistered (typos, uncertified write-ins) marks are not votes.
2. Overvote: two or more *different* registered candidates at one rank. Reading stops; this rank and all later ranks are ignored, earlier ranks stand (stop = "overvote"). This is checked first, even if one of the candidates was already ranked higher.
3. Skipped rank: no vote at the rank, or a vote for a candidate already ranked higher. It adds one to the skip counter; the second skipped rank in a row stops reading (stop = "skipped").
4. Otherwise the candidate is appended to the order and the skip counter goes back to 0.

If reading ran out of entries, stop is "end". A ballot whose order is empty is unusable: it is not counted in any round or toward any quota.

["avery", "avery", null, "blake"] has order ["avery"] and stop "skipped": the repeat is a skipped rank, and the null is the second in a row.

Counting a single-winner contest (method: "irv")

Each round, every counted ballot supports the highest-ranked continuing candidate in its order; if it has none, it is exhausted. active is the number of ballots not exhausted. Then:

1. If only one candidate continues, that candidate is elected.
2. Otherwise, a candidate with more than half of active is elected.
3. Otherwise the weakest candidate is eliminated: the lowest count. A tie for lowest goes to the tied candidates' counts in earlier rounds, most recent round first (the first earlier round in which the counts differ decides, the lower count loses). Still tied, the lot decides: of those still tied, the one drawn earliest in lots.draw_order is eliminated. A round-1 tie goes straight to the lot.

The report

tally returns:

{"method": "irv", "cast": N, "counted": C, "unusable": N - C,
 "rounds": [ {"round": 1, "tallies": {id: count, ...}, "exhausted": n, "elected": [...],
              "eliminated": [...], "tie": null | {"between": [ids], "decided_by": "history" | "lot",
              "chosen": id}, "transfers": {from_id: {to_id | "exhausted": n}}}, ... ],
 "elected": [ids]}

tallies lists every candidate still continuing at the start of the round (zeros included). exhausted is the number of counted ballots that are exhausted at the start of the round. tie is set when the eliminated candidate (or, in Part 4, an elected one) was chosen among candidates sharing the extreme count; between is those candidates sorted by id and chosen is the one eliminated or elected. transfers shows, for each candidate eliminated this round, where their ballots moved (to the next continuing candidate in the ballot's order, or "exhausted"); zero entries are omitted, and a round that eliminates nobody has {}. In the final round of a single-winner count, elected holds the winner.

Worked example. Candidates avery, blake, chen, diaz and the certified write-in w:ines park, lot_seed 7.

[["configure", {"candidates": ["avery","blake","chen","diaz","w:ines park"], "lot_seed": 7}],
 ["cast", ["avery","blake","chen"], 4], ["cast", ["blake","chen"], 3],
 ["cast", ["chen","diaz","avery"], 2], ["cast", ["diaz","W:  Ines  PARK"], 2],
 ["cast", ["blake", ["avery","chen"], "diaz"]], ["cast", ["avery", null, null, "diaz"]],
 ["cast", ["chen","chen","diaz"]], ["cast", [["avery","blake"], "chen"]],
 ["cast", ["W:Ines Park","diaz"], 2], ["summary"]]

17 ballots are cast, 16 counted (the last-but-one is an overvote at rank 1). Round 1 counts avery 5, blake 4, chen 3, diaz 2, ines 2: diaz and ines tie for last, there is no history, so the lot picks diaz. Round 2: chen 3 is lowest; one of chen's ballots, chen, chen, diaz, has order chen, diaz and runs out of choices, so exhausted is 1 in round 3. Round 3: avery 7, blake 4, ines 4: blake and ines tie, round 2 is level at 4 but in round 1 ines had 2 against blake's 4, so history eliminates ines. Round 4: avery 7 of 11 active ballots is a majority. summary returns {"elected": ["avery"], "rounds": 4, "counted": 16, "tallies": {"avery": 7, "blake": 4}, "exhausted": 5}.

Part 1 — Make the tally match the hand count (HB-117)

Goal: tally must follow every rule above. The auditors' notes from the chair race:

• "Ballots with two marks at one rank are still being transferred to their later choices. We exhausted them."
• "A ballot reading *Avery, Avery, blank, Diaz* counted for Diaz. The hand count calls it exhausted."
• "The hand count declared the winner as soon as they had more than half of the live ballots. The software kept eliminating until one name was left, and its final-round numbers do not match ours."
• "Ties for last place always eliminate the candidate whose name sorts first."
• "After provisional ballots were added we asked for the count again and got different numbers than a fresh count of the same ballots."

Read the rules rather than the notes: the notes are symptoms and the rules are the contract. Check that tally may be called any number of times, interleaved with cast, and always equals a fresh count of the ballots cast so far. Two of the example tests in tests/ fail today; they are a starting point, not the full list.

Part 2 — Batch elimination (ELEC-402)

Goal: large races spend many rounds eliminating candidates who cannot possibly win. With "batch_elimination": true in the config, eliminate all of them in one round. With it false (the default) behaviour is exactly Part 1.

Rules (single-winner only)

1. After the majority check fails, sort the continuing candidates weakest first (lowest count, then the Part 1 history and lot ordering). Let v1..vn be their counts in that order and S(k) = v1 + ... + vk.
2. Find the largest k with 1 <= k < n such that S(k) < v(k+1) (strictly less). If there is one, eliminate those k candidates in this round. tie is null for a batch round.
3. If there is no such k, eliminate just the weakest, exactly as in Part 1 (including tie).
4. eliminated lists the batch weakest first. transfers has one entry per eliminated candidate that had ballots: a ballot moves to the first candidate in its order who is still continuing after the whole batch is removed, or to "exhausted"; a ballot never lands on another member of the batch.
5. Later ties use the tallies of the rounds that were actually run (a batch is one round in the history).

Example. a b c d e, lot_seed 4, batch on: a,b x9, b,a x7, c,d,a x2, c,b x1, d,c,a, d,e,b, e,d,b. Round 1 counts a 9, b 7, c 3, d 2, e 1. Sorted: e1, d2, c3, b7, a9. S(1)=1<2, S(2)=3 is not <3, S(3)=6<7, S(4)=13 is not <9, so k=3: round 1 eliminates ["e","d","c"] with transfers {"c": {"a": 2, "b": 1}, "d": {"a": 1, "b": 1}, "e": {"b": 1}}. Round 2 is a 12, b 10 and a is elected. Batch elimination never changes who is mathematically able to win: if neither run needs a tie-break to decide a round, one-at-a-time and batch elections elect the same candidate. (With ties the histories differ, so the results can legitimately differ.)

Part 3 — A candidate withdraws after ballots are cast (counsel ruling 24-09)

Goal: add ["withdraw", candidate_id], returning true. County counsel ruled that a withdrawn candidate is treated as eliminated before round 1: they stay on printed ballots but can no longer receive votes.

Rules

1. Withdrawals can arrive at any time, before or after ballots are cast. Every later tally / summary reflects them; reports already returned are history.
2. A withdrawn candidate never appears in tallies, eliminated, transfers or tie between, and their ranks are skipped over as if they were eliminated before the count started.
3. A withdrawn candidate's marks still behave as marks: they still make overvotes, still count as repeats, and a rank holding one is not a skipped rank. inspect is unchanged by withdrawals and still lists them in order.
4. A ballot with no non-withdrawn candidate in its order is unusable: it is not in counted, is in unusable, and does not count toward any quota or majority.
5. The published lot draw does not change: it was published over all certified candidates, withdrawn or not.
6. Errors, in order: argument not a string (invalid arguments), not a certified candidate after canonicalising (unknown candidate), already withdrawn (already withdrawn), or the withdrawal would leave fewer than seats + 1 candidates in the race (too few candidates). A failed withdrawal changes nothing.

Example. After the Part 1 ballots, ["withdraw", "chen"] makes round 1 avery 5, blake 4, diaz 5, ines 2: chen's three first-choice ballots count for their next choice, diaz. Ines is eliminated, then blake, and diaz is elected in round 3 with 7 of 12 active ballots. counted is still 16 and unusable still 1.

Part 4 — Multi-winner STV for the board election (ELEC-431)

Goal: tally on a config with "method": "stv" and "seats": S elects S candidates by single transferable vote with a Droop quota and the weighted inclusive Gregory method. (Until now such a tally answers error: not supported.)

Rules

1. Counted ballots, exhaustion and Part 3 withdrawals work as before. quota = counted // (S + 1) + 1 (integer division); quota is in the report.
2. Every counted ballot starts with weight 1. All amounts are multiples of 0.0001 and exact (no floating point): a candidate's tally is the sum of the weights of the ballots supporting them. In the report all STV amounts (tallies, exhausted, surplus, transfers) are strings with exactly 4 decimals, e.g. "11.0000"; quota stays an integer.
3. Each round, tally the continuing candidates, then:
4. If any continuing candidate has a tally >= quota, elect the strongest continuing candidate (highest tally, then the tied candidates' earlier-round tallies, most recent first, higher is stronger, then the lot: the one drawn *latest* is stronger). One candidate per round.
5. Otherwise, if the number of continuing candidates is no more than the seats still empty, elect all of them in one round, strongest first.
6. Otherwise eliminate the weakest (Part 1 ordering). Batch elimination does not apply.
7. Surplus. surplus = tally - quota for the candidate elected in 3.1 (shown in surplus). Unless that fills the last seat, every ballot currently supporting the elected candidate, including ballots that arrived by earlier transfers, gets new weight floor(old weight x surplus / tally) to 4 decimals (truncated, never rounded up), and then supports its next continuing candidate (or is exhausted). If this was the last seat, transfers is {}.
8. An eliminated candidate's ballots move on at their current weights. A ballot whose weight reaches 0 is ignored.
9. Round records have an extra "surplus": the string for rounds that elect by quota, otherwise null. tie is set when the chosen candidate (elected or eliminated) shared the extreme tally; exhausted is the total weight of ballots with no continuing candidate. elected lists winners in the order elected. A round that fills the empty seats (3.2) has tie null. The summary of an STV count is as before.
10. A completed count has exactly S winners. irv behaviour is unchanged.

Example. x y z u v, lot_seed 2, stv, 2 seats; x,y x6, x,z x3, x x2, y,z x3, z,y x2, u,z x2, v,u x2. 20 ballots, quota 7. Round 1: x 11 reaches the quota, surplus 4, each of x's ballots is worth floor(4/11) = 0.3636, so y gets 2.1816, z gets 1.0908 and 0.7272 is exhausted. Round 2: y 5.1816, z 3.0908, u 2, v 2, the lot picks u. The count ends in round 5 with elected: ["x", "y"].

Part 5 — The November count (ELEC-440)

Goal: the countywide contest has several hundred thousand ballots. ["generate", {"seed", "ballots", "patterns"}] (already in synthetic.py) casts ballots physical ballots spread over patterns distinct papers; hidden tests tally such electorates, with and without batch elimination, with multi-winner contests, withdrawals and repeated tallies, all in one run and within the time the whole suite has. Results must be identical to what a per-ballot count would produce, down to every transfer and tie. Papers that are the same must not be re-read for every round.

Notes

• Earlier Parts keep working exactly as specified; hidden tests re-check them after every later Part.
• You may use the AI assistant freely; you are expected to verify what it produces.
• Parts 1-3 is a strong result; 4 and 5 are the stretch.