PrefVote is a project to promote preference voting. It supports several ranked-choice voting methods and algorithms. It was originally derived from the Vote::STV software written by Ian Kluft in Perl in 1999, with periodic maintenance over the years.
Since the project’s original language Perl has strengths in prototyping, that’s the reference implementation in this project for multiple language implementations. With translations to multiple programming languages, the library is designed with a common test suite among the different implementations to verify proper functioning.
The original Vote::STV software implemented the single transferable vote algorithm, which is a subset of ranked-choice voting, also called preference voting. PrefVote has expanded into a library of multiple voting method implementations all based on ranked choice.
STV was the first implemented voting method in PrefVote since it was the original implementation as Vote::STV back to 1998. But STV has largely fallen out of favor because studies of voting methods found it lacking on some desirable characteristics. STV was retained while modernizing the code to develop testing infrastructure.
No voting method can be perfect, due to a long list of desirable properties, some of which turn out to be in conflict. Given that there is no perfect voting method, it’s important to have agreement among a community on which method it uses. Methods which meet Condorcet requirements make comparisons between each pair of candidates and, if one exists, always pick a winner who beats all other candidates in pairwise comparisons. Condorcet methods differ in how to handle cases where there isn’t a clear Condorcet winner.
The second voting method implemented in PrefVote was the Schulze algorithm (see full definition paper). The method was designed by Marcus Schulze in 1997 to compute a graph out of voter preferences among candidates and pick the ones preferred over all others. An ordering of all the candidates can be computed over multiple rounds after removing the previous round’s winner(s).
Next was Ranked Pairs. It was designed by Nicolaus Tideman in 1987. It tallies ranked choice ballots into pairwise comparisons among all choices/candidates. The pairs are sorted by margin of victory from largest margin down to ties at zero. Pairs are “locked” in for consideration of the final order of candidates if they do not conflict with locked pairs with larger margins. Candidates are then ordered starting who beats all other candidates, then each who beat all remaining candidates.
After the reference implementation in Perl, next up for language implementations will be Rust.
The original and primary input file format of PrefVote is YAML with a predefined data structure. There is documentation for the data format. Also, when PrefVote is used as a library any data can be submitted by calling functions directly.
In support of a proposed Open Source standard for preference voting systems, PrefVote also supports the Condorcet Election Format (CEF), or CEF. There is documentation for PrefVote’s support for CEF input files.
PrefVote modifies all the algorithms in one way. It adds a tie-breaking factor using the average ballot-position ranking of a choice/candidate. It started as experimentation with intuition that the average ranking of a choice was indicative of the will of the voters. Though it wouldn’t be acceptable as a primary factor because averages don’t have quantitative data - and quantitative data is paramount to meeting the expectation that the candidate with the most votes must be the winner. Test runs show that it approximates Condorcet results fairly well and converges with Condorcet by around 100 random ballots. It didn’t even need to be that close to Condorcet to convey meaning about voter’s preferences. So this tie-breaking method restores ballot-position ordering information which Condorcet lacks.
PrefVote’s Core module from which all the voting methods inherit common code is not a voting method itself. But in performing the counting of average choice ranking (ACR) for other methods to use for tie-breaking, it contains results which can be displayed for testing purposes. Since it only uses average ranking, it really must not be used for actual voting. There is a principle in voting that every vote counts. That means quantitative factors must be the primary ordering for results. But ACR turns out to be surprisingly well-suited to be a second sorting factor for tie-breaking.
This is an example result from Single Transferable Vote (STV), Schulze and Ranked Pairs using the same file in the test suite with each algorithm. 250 ballots were randomly generated. So there’s no actual meaning to the result except testing the software.
Notes about all the following examples:
Candidate names are fictitious, just to get names that start with A, B, C, D, E and F as used universally throughout the test suite. The names are whimsical based on the difficult dilemma voters sometimes feel they are choosing between in real candidates.
Even for a relatively small set of test data, this shows the importance of algorithm definition to handling of ranked-choice votes. The various algorithms can lead to different results which are valid by the definition of how each method does its counting. Following the procedures of each method, they can vary in behavior when vote counts are close. Typically they won’t vary when results are not close. This example was one where a close race came out differently.
Results: Test Vote 004
1 seat available ∣ 250 ballots
Abbreviation Name/description Result FACTIOUS factious/divisive 1/selected EVIL evil villain 2/placed CHAOTIC chaotic unpredictable 3/eliminated ABNORMAL abnormal and antisocial 4/eliminated BORING boring as anything 5/eliminated DYSFUNCTIONAL dysfunctional incompetent 6/eliminated
Round # Quota FACTIOUS EVIL CHAOTIC ABNORMAL BORING DYSFUNCTIONAL 1 125 68 54 36 31 33 28 ❌ 2 124.5 75 58 45 36 35 ❌ ❌ 3 122 78 69 51 46 ❌ ❌ ❌ 4 118.5 90 81 66 ❌ ❌ ❌ ❌ 5 114 118 ✅ 110 ❌ ❌ ❌ ❌ 6 56.50847 ✅ 113.01695 ✅ ❌ ❌ ❌ ❌
Notes about the STV example:
In the Single Transferable Vote (STV) method used in this example, each round proceeds by either selecting winners who are above the quota of available votes, or eliminating the last-place candidate(s) and transferring those votes to the next choice on each ballot that had them. When a candidate wins, the fraction of their votes beyond the quota necessary to win also transfer to other candidates.
The “Result” column shows a numerical place and disposition. The disposition will be one of
“selected” if the candidate/choice placed high enough to win an available seat
“tied” if a tie exists between multiple candidates and spans through at least one available seat and more than can be filled. It is the software’s role to report this, not to decide what to do. Ties can and do happen. So an organization must have procedures to deal with them.
“placed” if the candidate placed after the last available seat, and therefore was not selected/elected.
“eliminated” if the candidate was eliminated from counting. A place number reflects order where the first or strongest elimination is ordered last.
Results: Test Vote 004
1 seat available ∣ 250 ballots
Abbreviation Name/description Result FACTIOUS factious/divisive 1/selected EVIL evil villain 2/placed CHAOTIC chaotic unpredictable 3/placed DYSFUNCTIONAL dysfunctional incompetent 4/placed ABNORMAL abnormal and antisocial 5/placed BORING boring as anything 6/placed Margin-of-victory matrix
FACTIOUS EVIL CHAOTIC DYSFUNCTIONAL ABNORMAL BORING FACTIOUS 🛇 7 ✅ 57 ✅ 67 ✅ 74 ✅ 79 ✅ EVIL -7 ❌ 🛇 48 ✅ 68 ✅ 68 ✅ 64 ✅ CHAOTIC -57 ❌ -48 ❌ 🛇 16 ✅ 5 ✅ 15 ✅ DYSFUNCTIONAL -67 ❌ -68 ❌ -16 ❌ 🛇 13 ✅ 5 ✅ ABNORMAL -74 ❌ -68 ❌ -5 ❌ -13 ❌ 🛇 11 ✅ BORING -79 ❌ -64 ❌ -15 ❌ -5 ❌ -11 ❌ 🛇
Notes about the Schulze example:
The Schulze method is a Condorcet voting method. So it aggregates the ranked preferences from each ballot into pairwise preference of each of the candidates. In all Condorcet methods, if one candidate is preferred over all others then it is considered the Condorcet winner. The Schulze method also considers paths of preferences in a graph to pick between candidates when there isn’t a single Condorcet winner.
As with the STV results, the first table in the example is the final ranking order of the voting results. It indicates selected, tied, and placed candidates as above. There is no concept of eliminated candidates in the Schulze method. After the winner is found in each round, the vote is re-run for as many rounds as needed until all the candidates are ordered in the result.
The margin-of-victory matrix shows the voting results with how much each candidate on the row labels are preferred over candidates on the column labels. Negative numbers mean the other candidate is more preferred. There is a “not applicable” icon in each cell diagonally down the middle where each candidate cannot be compared to themselves. The matrix always has an inverse symmetry because the same pair of candidates compared on the other side of the diagonal will be opposite - with A-B vs B-A, one of them must negative and opposite of the other. A Condorcet winner is easily visible as having all positive numbers (and check-mark icons) compared against all other candidates.
Results: Test Vote 004
1 seat available ∣ 250 ballots
Abbreviation Name/description Result FACTIOUS factious/divisive 1/selected EVIL evil villain 2/placed CHAOTIC chaotic unpredictable 3/placed DYSFUNCTIONAL dysfunctional incompetent 4/placed ABNORMAL abnormal and antisocial 5/placed BORING boring as anything 6/placed Margin-of-victory matrix
FACTIOUS EVIL CHAOTIC DYSFUNCTIONAL ABNORMAL BORING FACTIOUS 🛇 7 ✅🔒 57 ✅🔒 67 ✅🔒 74 ✅🔒 79 ✅🔒 EVIL -7 ❌ 🛇 48 ✅🔒 68 ✅🔒 68 ✅🔒 64 ✅🔒 CHAOTIC -57 ❌ -48 ❌ 🛇 16 ✅🔒 5 ✅🔒 15 ✅🔒 DYSFUNCTIONAL -67 ❌ -68 ❌ -16 ❌ 🛇 13 ✅🔒 5 ✅🔒 ABNORMAL -74 ❌ -68 ❌ -5 ❌ -13 ❌ 🛇 11 ✅🔒 BORING -79 ❌ -64 ❌ -15 ❌ -5 ❌ -11 ❌ 🛇
Notes about the Ranked Pairs example:
Ranked Pairs is also a Condorcet method, like Schulze. So there are fewer differences between them. And in this example there are no differences at all. Though other files in the test suite do have some modest differences between them when breaking ties.
The lock icon (🔒) in the results indicate candidate majority pairings which were “locked” and accepted for use in the result order because they did not conflict with pairs with larger margins of victory. Table entries without a lock icon would be because they were a loss or tie, or a conflict with larger majorities. For example if A>B and B>C then C>A is not locked due to a conflict.
I modified the Ranked Pairs implementation in the case of tie-breaking. Rather than select a random ballot to count a second time as Tideman recommended in his 1987 paper, I used average ballot-position ranking as a second priority sorting field. This was then retrofitted as a tie-breaker in STV and Schulze and adopted as a design feature of PrefVote::Core.