Reference STV Rules

This section presents reference voting rules, or procedures, for counting three different versions of the single transferable vote, or STV. The methods described are:

• Meek. The Meek rule is based on a 1969 proposal by Brian Meek. The Meek rule is to be preferred if it’s practical to count all elections by computer.
• WIGM. The “weighted inclusive Gregory method” is an evolution of an STV method first described by J B Gregory in 1880. Gregory’s original method, and several of its successors, have significant flaws, and should not be considered for adoption. WIGM is countable by hand, albeit with some effort, which is the principle reason that it might be preferred today to Meek’s method.
• Andrae. The Andrae method (the name is not in general use) is a method that would be recognizable by the Thomas Wright Hill, who “invented” STV, circa 1819. I have adopted the name Andrae after Carl Andrae, who independently developed a similar STV method in 1856. The Andrae method uses whole votes only, and is relatively easy to count by hand. While it is still in use by Cambridge MA, it should probably not be considered for adoption, but it is very simple, and easy to hand-count.

In general, a counting rule should be written such that any possible implementation that complies with the rule specification will produce the same election outcome from the same election profile. That is, the rule specification must not leave any choices to the implementor that have the potential to change the outcome of an election; the rule specification must be completely deterministic, and it must not be ambiguous.

Such unambiguous determinism has the benefit that independent implementations can be used to verify each other, and that disputes over the interpretation of the rule are less likely to arise.

Writing a completely unambiguous and deterministic rule is not trivial. Perhaps the most important purpose of this document is to help achieve that result.

Certain items are left to be defined outside the rule itself. They include:

• nomination procedure
• ballot configuration
• candidate qualification procedure
• ballot validation & cleaning procedure, if any
• recount procedure
• procedure for filling casual vacancies

Definitions

Here we define terms used in the reference rules.

Candidate state. At the beginning of a count, each candidate is either in the withdrawn or hopeful state. Hopeful candidates eventually move to the defeated or elected state, possibly via the pending state according to the counting rule.

Hopeful candidate: a candidate who is not withdrawn, pending, elected, or defeated. Also called continuing. Each candidate is initially a hopeful or a withdrawn candidate. Hopeful candidates are eventually elected or defeated by the rule.

Defeated candidate: a candidate that is defeated during the count. Also called excluded or eliminated.

Elected candidate: determined by the vote-counting procedure to have been successfully elected. The election may require further action (certification, for example) to become official. Also called deemed elected or successful or winner.

Pending candidate: in WIGM rules, a candidate that has attained a quota of votes, but whose surplus (possibly zero) has not been transferred. A pending candidate may or may not be eligible to receive vote transfers, depending on the specific rule.

Qualified candidate: as determined externally. Unqualified candidates appearing on a ballot may be treated as withdrawn for purposes of the count.

Quota: The number of votes required for election (sometimes called the threshold).

Sure loser: A hopeful candidate for whom defeat is inevitable, based on the current state of the count (current vote counts, surpluses and candidate states).

Surplus: The number of votes a candidate has in excess of the quota.

Valid ballot: A ballot sequentially ranking, beginning with rank 1, one or more qualified candidates and no unqualified candidates.

Voting rule. The formal method and procedure for counting an election.

WIGM. Weighted Inclusive Gregory Method. An STV counting method used by a class of rules including Scotland and Minneapolis. WIGM is more amenable to hand-counting than Meek’s method.

Withdrawn candidate: an otherwise qualified candidate who is withdrawn before the count begins.

Existing STV implementations

The STV implementations listed below are variations on the respective methods, and do not necessarily match each other or the reference rules in every detail.

Meek STV

droop includes an implementation of the reference Meek rule.

OpenSTV, open-source counting software, has several Meek implementations, including MeekSTV, MeekNZSTV (New Zealand), and MeekQXSTV (quasi-exact arithmetic).

The New Zealand legislation, Schedule 1A, differs from the actual counting software, the NZ STV Calculator. OpenSTV’s MeekNZSTV follows the STV Calculator.

David Hill’s reference implementation was used as a basis for the NZ STV Calculator.

WIGM STV

droop includes an implementation of the reference WIGM rule, as well as the Scottish and Minneapolis variants.

Variations on WIGM are used by Scotland, Minneapolis MN, and the Green Parties of the US and California.

Andrae STV

Cambridge MA has used a more elaborate variation on this method since 1940.

Supplementary Rules

The three reference counting rules describe core counting methods. Besides the counting rule itself, additional rules are required to fully describe an electoral system. We won’t address all possible election rules, but we will discuss several specific election rules that may already exist but need to be adapted for STV elections.

This section is a work in progress. Additional topics that need to be addressed include:

• Recounts
• Filling casual vacancies
• Ballot validation
• Ballot format

Ballot-file format

[to be written. ballot files constrain certain errors—for example, .blt can’t have skipped or duplicate rankings. To the extent that the file can represent ballot errors, the rule should say what’s to be done.]

Reporting

[to be written. The main point is that values should be reported from a specified point in the rule, so that different implementations report the same set of values. I’ll try to find a point in each rule that would be good for reporting, with the criterion being clarity with respect to election and defeat.]

Breaking ties

The broad subject of tie-breaking is beyond the scope of this document, but we’ll discuss some implications of the tie-breaking specification for writing counting rules.

Ties can arise in all methods when choosing a candidate to defeat. Ties can arise in WIGM and Droop methods when choosing the winner with the highest surplus to transfer.

Meek implementations typically break ties at random. This is typically done with a pseudo-random-number generator (PRNG) so that ties are broken identically on subsequent counts of identical ballots. A counting rule must specify the tie-breaking process completely, such that any implementation that follows the rules will produce the same outcome for the same ballots.

New Zealand uses a specified PRNG to put the candidates in an initial order; the order is reversed for each round. When a tie arises, the order of candidates is used to break the tie. Notice that such a tie-breaking rule can cause difficulties for optimizations that alter the number of rounds, and such optimizations must take care to preserve correct tie-breaking behavior.

In general, it’s probably best to avoid tie-breaking methods that depend on the count of rounds. If the tie-breaking order is to be changed (and it need not be), a better approach would be to change it (invert it, calculate a new order, etc) each time a candidate is elected or defeated, which should be invariant with respect to optimizations.

Ballot cleaning

A jurisdiction may choose to reinterpret ballots that would be considered invalid under the counting rule by explicitly including rules for such reinterpretation. For example, skipped rankings could be corrected by “closing up” the ballot rankings. A candidate ranked twice might be counted only at the first ranking. A ballot might be treated as valid for any rankings up to but not including a duplicate ranking (that is, two candidates with the same ranking). Depending on the ballot format, not all of these defects are possible. There are good reasons for allowing or not allowing such reinterpretation.

Auditing

[to be written. My view is that the correct approach to auditing computer-counted STV is to divide the count, and the audit, into two stages. In the first stage, the original ballots are converted to a computer-readable election profile. How this is done depends on the voting equipment. In the second stage, a computer-based implementation of the rule reads the election profile and counts the election, reporting the result. Auditing of the second stage is accomplished by comparing results of independent implementations of the rule.]

Calculators

Calculators are often used when counting a WIGM election by hand. A calculator must be tested to ensure that it conforms to the rounding specification of the rule being used. In particular, some calculators round-to-nearest, which is never correct for vote counting.

A simple test may be performed by dividing 2 by 3. A calculator that rounds down will show an answer ending in 6 and may be used; one that rounds to nearest will show an answer ending in 7, and must not be used.

Counting-Rule Considerations

Optimization

Meek

With Meek methods, multiple candidates may be defeated simultaneously when doing so is equivalent to one-at-a-time defeat. The idea is that a group of bottom-ranked candidates may be defeated together if their total votes, plus any surplus, is less than any other candidate’s vote.

The motivation is to reduce the number of rounds that need to be calculated and reported, and, potentially, to avoid needless tiebreaking.

The Meek iteration may be terminated early if and only if doing so is equivalent to carrying the iteration to its conclusion. The idea is that if the vote for the lowest-ranked candidate plus the surplus is less than the vote for the candidate with the next higher vote, then the lowest-ranked candidate can be safely defeated without completing the iteration.

The two optimizations may be combined, such that multiple candidates may be defeated before an iteration is complete.

WIGM

Four variations exist for the “defeat sure losers” step of a WIGM rule:

1. Never defeat sure losers.
2. Defeat hopeful candidates with zero votes if the current surplus is zero.
3. Defeat all candidates who are certain to be defeated (their vote, plus the votes from all other candidates being considered for defeat, plus the surplus, is insufficient to overtake the next-higher hopeful candidate), with the further limitation that the total of the votes from all candidates to be defeated plus the surplus is not enough to elect the highest hopeful candidate.
4. Defeat all candidates who are certain to be defeated (their vote, plus the votes from all other candidates being considered for defeat, plus the surplus, is insufficient to overtake the next-higher hopeful candidate).

Variations 1–3 lead to identical outcomes, and a rule may choose to make them optional. Variation 4, however, can alter the order of election, which can alter its outcome. Consequently, if variation 4 is to be used, it must be mandatory, so that the outcome is fully determined by the rule (Minneapolis MN mandates variation 4). If variation 4 is made mandatory, there is no reason in principle not to use it; the potential difference in outcome stems from an underlying weakness in WIGM (but not Meek), and there is no reason to prefer the outcome of variations that are equivalent to one-at-a-time defeats (that is, variations 1–3).

The motivation for batch defeats with WIGM-based rules is the same as for Meek-based rules, plus one additional motivation. If an election is to be counted by hand, performing a batch defeat before transferring a surplus can avoid needless surplus transfers to candidates who will inevitably be defeated.

Arithmetic precision

WIGM STV: arithmetic precision

For WIGM STV, the arithmetic precision chosen will determine how small a difference in vote count between two candidates can be resolved; smaller difference will be treated as ties.

For hand-counting WIGM STV with a calculator, it’s desirable to be able to see the full precision of a product of two values, in order to perform proper rounding. For most hand calculators, four digits of precision is a practical upper limit, so that eight digits of precision in the product can be seen.

The reference WIGM rule specifies four digits of precision, as does Minneapolis MN. Scotland specifies five digits.

Meek STV: arithmetic precision and omega

Various Meek implementations use different values of omega, the surplus value below with the Meek iteration is terminated. When iterating, candidates whose vote differs by less than omega are treated as tied. Consequently, omega must be small enough to resolve differences that we care about (are not prepared to treat as ties).

Arithmetic precision and omega must be considered together. A large omega can result in causing candidates separated by a very small count to be treated as if they were tied. A small omega (relative to precision) can lead to a stable state in which the total surplus never falls below omega, in which case the iteration does not terminate unless the stable state is explicitly detected.

• NZ uses 0.0001 (10⁻⁴), in the context of 9-digit precision.
• OpenSTV’s MeekSTV uses the smallest value greater than 0 that can be represented at the specified precision, by default, 0.000001 (10⁻⁶) with 6-digit precision.
• OpenSTV’s MeekQXSTV (quasi-exact arithmetic) effectively iterates the surplus to 0.

The reference Meek rule uses 0.000001 (10⁻⁶), together with with 9-digit precision.

Meek STV and stable-state detection

When iterating with limited precision, it’s possible for the iteration to reach a stable state, where the surplus converges on a value greater than omega, resulting in an infinite loop.

• OpenSTV’s MeekSTV detects a stable state and terminates the iteration if all the keep factors are identical in two successive iterations.
• OpenSTV’s MeekNZSTV can end up in a stable state that flips between two different states, due to its different approach to rounding. Its stable-state detector looks for the same condition as OpenSTV’s MeekSTV, or for any candidate’s keep factor to increase from one iteration to the next.
• NZ Schedule 1A mentions a stable-state detector, but does not specify how it functions. This is a problem with the rule.

If an implementation requires a stable-state detector, it must be completely specified, because differences in stable-state detection can lead to differences in outcome.

Rounding

Meek rounding

If exact arithmetic is not employed, then rounding must be specified. With limited-precision Meek’s method, rounding is required at three points: quota calculation, distribution of surpluses, and the calculation of keep factors.

Arithmetic precision is typically specified in decimal places, with calculations performed with fixed-point decimal arithmetic. The number of digits of precision is generally in the range of 4 to 9. We’ll use 6 decimal digits of precision as an example.

Rounding down is the floor function, or truncation. Rounding up is the ceiling function. In both cases, the rounded result is equal to the exact result if the exact result can be represented at the specified precision, otherwise the nearest representable value lower (rounding down) or higher (rounding up), than the exact result.

Quota. Calculate the quota q to 6 decimal places, rounding down, and then add 0.000001. The election test becomes (v ≥ q), since q is now always greater than the exact quota.

Keep factors. The keep factor is updated by multiplying a candidate’s previous keep factor by the quota, and then dividing by the candidate’s vote count. Several variations are possible.

• Perform the multiplication to 12 digits of precision (no rounding required). Round the result of the division down to 6 digits of precision, and add 0.000001. (OpenSTV’s MeekSTV)
• Round the result of the multiplication down to 6 digits of precision and add 0.000001. Round the result of the division down to 6 digits of precision and add 0.000001. (NZ, Hill)

Surplus distribution. Here we multiply the the ballot weight by the first-ranked candidate’s keep factor (adding the result to that candidate’s vote total v), reduce the ballot’s weight by the same amount, and continue down the ranked candidates on the ballot until the ballot weight is reduced to 0 or until there are no more candidates ranked on the ballot.

In the following descriptions, the keep value is the value to be added to the current candidate’s vote total; the residual value becomes the new ballot weight, to be used for the next-ranked candidate.

We have three variations.

• Keep value = ballot weight times current candidate’s keep factor, rounding down. 
Residual value = ballot weight times (one minus the current candidate’s keep factor), rounding down. 
(OpenSTV’s MeekSTV)
• Keep value = ballot weight times current candidate’s keep factor, rounding up. 
Residual value = 1 – new keep value. 
(NZ Calculator, Hill)
• Keep value = ballot weight times current candidate’s keep factor, rounding up. 
Residual value = ballot weight times (one minus the current candidate’s keep factor), rounding up. 
(NZ Schedule 1A)

WIGM rounding

Rounding with WIGM is required for quota calculation and in calculating surplus transfers.

Quota rounding is identical to Meek, above.

Surplus-transfer weights are

w' = w * s / v

where w' is the new ballot weight, w is the old ballot weight, v is the candidate’s total vote, and s is the surplus v – q.

The options are whether to round the intermediate product w * s at all, and if so how (up or down), and whether to round the result of the final division up or down. The usual choices are to round down in both cases. Retaining the full intermediate precision is an option, but notice that if a count is made by hand, many calculators will not provide enough precision for this calculation, so if the ability to count by hand is desirable, the intermediate product should be rounded down.

Equality of preference

[to be written. brief discussion.]

Quota

For all practical purposes, the Droop quota, nominally votes divided by one more than the number of seats to be filled,

is universally used for STV elections, though historically the Hare quota (nominally v/s) has also seen use. The quota is generally rounded, to allow for finite (non-exact) arithmetic. The rounded value is usually

where v/(s+1) is calculated to some specified number of digits, with any remainder discarded, and ε is the smallest value needed to make the quota strictly greater than the exact v/(s+1). For example, if calculations are made to 4 decimal places, ε is 0.0001.

In this case (non-exact arithmetic), a candidate whose vote is equal to or greater than the quota is elected.

When only whole (not fractional) votes are used, such as in the method used by Cambridge MA, the quota is also calculated as a whole number:

with any fractional remainder discarded.

In some rules, apparently from historical habit, the whole-number quota is specified for methods that otherwise employ fractional values. This practice is less than ideal, though it does relatively little harm when the number of votes is large.

With exact arithmetic, the quota is exactly v / (s+1), and a candidate whose vote is strictly greater than the quota is elected, guaranteeing that we cannot elect more candidates than seats.