USRSE / USRSE/usrse.github.io

feat(elections): IRV tabulation engine with test fixtures

Open
#1,943 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
HTML
Stars
33
Forks
104
Avg merge
12h 3m
Merged PRs (30d)
10

Description

Summary

Implement an Instant Runoff Voting tabulation engine that elects a single winner by iteratively eliminating the lowest-ranked candidate and redistributing those ballots.

Part of #1933.

Requirements

  • Pure function: `tabulateIRV(ballots, candidates) → { rounds[], winner, exhaustedBallots }`
  • Each round records: first-preference counts per candidate, eliminated candidate, ballots transferred
  • Handle ties on elimination using a documented, deterministic tie-break (e.g., previous-round counts, then seeded random with election ID)
  • Handle exhausted ballots (all ranked candidates eliminated) explicitly — count them, don't silently drop
  • Majority threshold: winner must have > 50% of continuing ballots
  • Edge cases covered: empty ballots, single-candidate race, all-same-ranking tie, every-ballot-exhausted scenario
  • Property-based tests: monotonicity violations are known in IRV — document them, don't try to fix them
  • Golden fixture tests against hand-calculated example elections
  • Tabulation runs server-side only (Convex action), never in the client

Context

  • Epic: #1933
  • Depends on schema issue
  • IRV handles single-winner races (Chair, President-elect, etc.)

Implementation notes

  • Implement as a pure TS module in `packages/tabulation/` so it can be tested with vitest independent of Convex
  • Compare output against a known reference implementation (e.g., `rcv` npm package) for at least 3 test cases

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the schema issue dependency and the implementation notes for packages/tabulation/. Define the pure TypeScript tabulation API and its tie-break and exhaustion behavior, then add Vitest property-based and golden fixture tests. Done means the edge cases are covered, results match the rcv reference for three cases, and tabulation runs only in the server-side Convex action.

Written by the indexing model from the issue text.

Assessment

Tech stack
typescript
Domain
backend, testing
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.