Auditing Hamiltonian Elections

Presidential primary elections are a critical part of the United States electoral process, since they are used to select the final candidates contesting the Presidential election for each of the major parties. For that reason it is important that the result of these primaries be trustworthy. While the method used for primary elections differs by party and state, the majority of such elections use delegate allocation by proportional representation, the so-called Hamilton method, named after its inventor, Alexander Hamilton.

Risk-limiting audits (RLAs) [9] require a durable, trustworthy record of the votes, typically paper ballots marked by hand, kept demonstrably secure. RLAs end in one of two ways: either they produce strong evidence that the reported winners really won, or they result in a full manual tabulation of the paper records. If a RLA leads to a full manual tabulation, the outcome of the tabulation replaces the original reported outcome if they differ, thus correcting the reported outcome (if the paper trail is trustworthy). The probability that a RLA fails to correct a reported outcome that is incorrect before that outcome becomes official is bounded by a “risk limit.” An RLA with a risk limit of 1%, for example, has at most a 1% chance of failing to correct a reported election outcome that is wrong; equivalently, it has at least a 99% chance of correcting the reported outcome if it is wrong. RLAs are becoming the de-facto standard for post-election audits. They are required by statute in Colorado, Nevada, Rhode Island, and Virginia,¹¹1Virginia’s audit does not take place until after the outcome is certified, so it cannot limit the risk that an incorrect reported outcome will become final: technically, it is not a RLA. for some government elections (not primaries which are party elections), and have been piloted in over a dozen US states and Denmark. They are recommended by the US National Academies of Science, Engineering, and Medicine and endorsed by the American Statistical Association. Risk-limiting audits of limited scope have begun to be applied to US primary elections; our methods here would allow RLAs of the full elections.

In this paper we describe the first method that we are aware of for conducting an RLA for delegate allocation by proportional representation elections, which we call Hamiltonian elections. In addition to primary elections in some states in the USA, this type of election is used in Russia, Ukraine, Tunisia, Taiwan, Namibia and Hong Kong. We do so by adapting auditing methods designed for plurality and instant runoff voting (IRV) elections for auditing the viability of candidates, and generating a new kind of audit for proportional allocation.

A delegate allocation election by proportional representation is a complex form of election. Rather than simply electing candidates, the result of the election is to assign some number of delegates to some of the candidates. In the first stage of the election, the process determines the subset of candidates that are eligible or viable (for Democratic primaries, candidates need to receive at least 15% of the vote). In the second step, delegates are awarded to these viable candidates in approximate proportion to their vote. An RLA must determine the correctness of both the set of viable candidates and the number of delegates assigned to each viable candidate.

The first stage of the election uses either simple plurality voting, where each ballot is a vote for at most one candidate, or IRV, where each ballot is a ranking of some or all candidates. In IRV, candidates with the fewest first-choice ranks are eliminated and each ballot that ranked them first is reassigned to the next most-preferred ranked candidate on that ballot.

There is considerable work on both comparison audits and ballot-polling audits for plurality elections [6, 11], but few for more complex election types. Sarwate et al. [8] consider IRV and some other preferential elections. Kroll et al. [5] show how to audit the overall US electoral college outcome, but not the allocation of individual delegates. Stark and Teague [12] devise audits for the D’Hondt method for proportional representation, which is related to but distinct from Hamiltonian methods. Blom et al. [2, 3] describe efficient audits for IRV. As far as we know, there is no other auditing method for Hamiltonian Elections, nor any that combines a proportional representation method with IRV.

We have a set of $n$ candidates $\mathcal{C}$, a set of cast ballots²²2We do not distinguish between ballots and ballot cards; in general, ballots consist of one or more cards, of which at most one contains any given contest. $\mathcal{B}$, and a number of delegates $D$ to be awarded to the candidates based on the votes. The Hamilton or largest remainder method, invented by Alexander Hamilton in 1792, allocates the delegates in approximate proportion to the votes the candidates received.

In a pure Hamiltonian election, also known as the Hamilton method, delegates are directly allocated based on the proportion of the vote. But most delegate elections use some form of exclusion of some candidates before the delegates are apportioned.

A Hamiltonian election with exclusion first determines which candidates in $\mathcal{C}$ are viable—eligible to be awarded one or more delegates. Typically, exclusion involves a plurality vote. Each ballot is a vote for at most one candidate. If a candidate receives a threshold proportion $\tau$ of the valid votes, the candidate is considered viable.³³3There are more complicated alternate rules for the case where no candidate reaches $\tau$; we do not consider this case here. The votes cast for viable candidates are referred to as qualified votes. The qualified votes are used to allocate delegates, as described later in this section.

For elections with many candidates, a plurality exclusion might eliminate all of them. In an instant-runoff Hamiltonian election the viable candidates are determined by a form of IRV. Each ballot is now a partial ranking of the candidates, and the viable candidates are determined as follows:

1. 1.

   Initialize the set of candidates. Each ballot is put in the pile for the candidate ranked highest on that ballot.

2. 2.

   If every (remaining) candidate has $\geqslant\tau$ of the votes in their pile, we finish the candidate selection process. All of these remaining candidates are viable.

3. 3.

   Otherwise, the candidate with the lowest tally (fewest ballots in their pile) is eliminated, and each of their ballots is moved to the pile of the next ranked remaining candidate on the ballot. A ballot is exhausted if all further candidates mentioned on the ballot have already been eliminated.

4. 4.

   We then return to step 2.

The second stage in the process is to assign delegates to candidates on the basis of their tallies. We first compute, for each viable candidate $c$, the proportion of the qualified votes in their tally, $p_{c}$. Recall that we refer to ballots belonging to viable candidates as qualified votes. We denote the number of qualified votes as $Q$. In the context of IRV, ballots are qualified if they end up in the tally of a viable candidate. Non-qualified ballots result from exhaustion: every candidate in the ballot ranking has been eliminated (is non-viable). Where a plurality contest determines viability, all votes for a viable candidate are qualified.

We denote the set of viable candidates as $\mathcal{V}$. Delegates are awarded to viable candidates as follows:

1. 1.

   We compute for each viable candidate $c$ their delegate quota, $q_{c}=D\times p_{c}$ where $p_{c}$ is the proportion of the qualified vote given to $c$ (their final tally divided by $Q$).

2. 2.

   We assign $i_{c}=\lfloor q_{c}\rfloor$ delegates to each candidate $c\in\mathcal{V}$.

3. 3.

   At this stage, there are $r=D-\sum_{c\in\mathcal{V}}i_{c}$ remaining delegates to assign. We assign these delegates to the $r$ candidates with the largest value of the remainder $q_{c}-i_{c}$. One delegate is given to each of these $r$ candidates.

4. 4.

   At this stage, each viable candidate $c$ has received $a_{c}$ total delegates, where $a_{c}$ is $q_{c}$ rounded either up or down.

A risk-limiting audit is a statistical test of the hypothesis that the reported outcome is incorrect. (In the current context, the reported outcome is the number of delegates finally awarded to each candidate.) If that hypothesis is not rejected, there is a full hand tabulation, which reveals the true outcome. If that differs from the reported outcome, it replaces the reported outcome. The significance level of the test is called the risk limit. A risk-limiting audit of a trustworthy paper trail of votes limits the risk that an incorrect electoral outcome will go uncorrected.

Two common building blocks for audits are to compare manual interpretation of randomly selected ballots or groups of ballots with how the voting system interpreted them (a comparison audit [10]), and to use only the manual interpretation of the randomly selected ballots (a ballot-polling audit [7]). Ballot polling requires less infrastructure (some voting systems do not generate or cannot export the data required for a comparison audit) but generally requires inspecting more ballots.

Recent work [11] shows that audits of most social choice functions can be reduced to checking a set of assertions. If all the assertions are true, the reported election outcome is correct. Each assertion is checked by conducting a hypothesis test of its logical negation. To reject the hypothesis that the negation is true is to conclude that the assertion is true. Each hypothesis is tested using a statistic calculated from the audit data. Larger values of the statistic are unlikely if the corresponding assertion is false. If the statistic takes a sufficiently large value, that is statistical evidence that the assertion is true, because such a large value would be very unlikely if the assertion were false. The statistic is generally calibrated to give sequentially valid tests of the assertions, meaning that the sample of ballots can be expanded at will and the statistic can be recomputed from the expanded sample, while controlling the probability of erroneously concluding that the assertion is true if the assertion is in fact false.

The initial sample size is generally chosen so that there is a reasonable chance that the audit will terminate without examining additional ballots if the reported results are approximately correct. If the initial sample does not give sufficiently strong evidence that all the assertions are correct, the sample is augmented and the condition is checked again.⁴⁴4For sequentially valid test statistics, the sample can be augmented at will; for other methods, there may be an escalation schedule prescribing a sequence of sample sizes before conducting a full manual tabulation. The sample continues to expand until either all the assertions have been confirmed⁵⁵5In other words, the hypothesis that the assertion is false has been rejected at a sufficiently small significance level. or the sample contains every ballot, and the correct result is therefore known. At any point during the audit, the auditor can choose to conduct a full manual tabulation. If the audit leads to a full manual tabulation, the outcome of that tabulation replaces the reported outcome if they differ.

The basic assertions for Hamiltonian elections are:

(Super/sub) majority $p>t$,

where $p$ is the proportion of ballots that satisfy some condition (usually the condition is that the ballot has a vote for a particular candidate) among ballots that meet some validity condition, and $t$ is a proportion in $(0,1]$.

Pairwise majority $p_{A}>p_{B}$,

where $p_{A}$ and $p_{B}$ are the proportions of ballots that meet two mutually exclusive conditions $A$ and $B$, among ballots that meet some validity condition. (Typically, among the ballots that contain a valid vote, $A$ is a ballot with a vote for one candidate, and $B$ is a ballot with a vote for a different candidate).

Pairwise difference $p_{A}>p_{B}+d$,

where $p_{A}$ and $p_{B}$ are the proportions of ballots that meet two mutually exclusive conditions among ballots that meet some validity condition, and $d$ is a constant in the range $(-1,1)$. This is a new form of assertion not previously used, that extends pairwise majority assertions. It is necessary for auditing delegate assignment in Hamiltonian elections.

In the SHANGRLA approach to RLAs [11], each assertion is transformed into a canonical form: the mean of an assorter (which assigns each ballot a nonnegative, bounded number) is greater than 1/2. The value the assorter assigns to a ballot is generally a function of the votes on that ballot and others and the voting system’s interpretation of the votes on that ballot and others.

For majority assertions, a ballot that satisfies the condition is assigned the value $1/(2t)$; a valid ballot that does not satisfy the condition is assigned the value 0; and an invalid ballot is assigned the value 1/2. For pairwise majority assertions, a ballot for class A counts as 1 and a ballot for class B counts as 0. Ballots that fall outside both classes count as 1/2.

For pairwise difference assertions, we define the assorter $g$ which assigns ballot $b$ the value:

Let $\bar{g}$ be the mean of $g$ over the ballots. We have that $0\leqslant g(b)\leqslant 1/(1+d)$, and $\bar{g}>1/2$ iff $p_{A}>p_{B}+d$. When $d=0$ this reduces to the pairwise majority assorter if the “valid” category is the same.

The margin $m$ of an assertion $a$ is equal to 2 times the mean of its assorter (when applied to all ballots $\mathcal{B}$) minus 1. An assertion with a smaller margin will be harder to audit than an assertion with a larger margin.

The first stage of the election identifies the viable candidates. We introduce notation for the assertions we will use to audit viability, as follows:

• •

  $\mbox{\emph{Viable}}(c,E,t)$: Candidate $c$ has at least proportion $t$ of the vote after the candidates in set $E$ have been eliminated. This amounts to a simple majority assertion $p_{c}>t$ after candidates in $E$ are eliminated.

• •

  $\mbox{\emph{NonViable}}(c,E,t)$: Candidate $c$ has less than proportion $t$ of the vote after candidates $E$ have been eliminated. This amounts to a simple majority assertion $\bar{p}_{c}>1-t$ where $\bar{p}_{c}$ is the proportion of valid votes for candidates other than $c$ after candidates $E$ are eliminated.

• •

  $\mbox{\emph{IRV}}(c,c^{\prime},E)$: Candidate $c$ has more votes than candidate $c^{\prime}$ after candidates $E$ have been eliminated. This amounts to a pairwise majority assertion.

If the first stage is a plurality vote, $E\equiv\emptyset$: the elimination in the first stage only occurs for IRV.

Consider an election $\mathcal{E}=\langle\mathcal{C},\mathcal{B},\tau\rangle$ with candidates $\mathcal{C}$, cast ballots $\mathcal{B}$, and viability threshold $\tau$ ($\tau=0.15$ for the primary elections we will examine). The outcome of this election is a set of viable candidates, $\mathcal{V}\subseteq\mathcal{C}$, together with, in the case of instant runoff Hamiltonian elections, a sequence of eliminated candidates, $\pi$. To check that the set of candidates reported to be viable really are the viable candidates, we test assertions that rule out all all other possibilities. Consider the subset $\mathcal{V}^{\prime}\subseteq\mathcal{C}$, where $\mathcal{V}^{\prime}\neq\mathcal{V}$. We can demonstrate that $\mathcal{V}^{\prime}$ is not the true set of viable candidates by showing that some candidate $c\in\mathcal{V}^{\prime}$ does not belong there. We can also rule out $\mathcal{V}^{\prime}$ as an outcome by showing that there is a candidate $c\notin\mathcal{V}^{\prime}$ that does in fact belong in the viable set. We aim to find the ‘least effort’ set of assertions $\mathcal{A}$ that, if shown to hold in a risk-limiting audit, confirm that (i) each candidate in $\mathcal{V}$ is viable, and (ii) no candidate $c^{\prime}\notin\mathcal{V}$ is viable.

The Hamilton method for proportional representation is used to assign delegates to viable candidates. It might appear that auditing the Hamilton method requires checking some delicate results, for instance, whether candidate $A$ received at least 2 delegate quotas when candidate $A$ actually received 2.001 delegate quotas. However, this is not necessary, because candidate $A$ can receive 2 delegates without having at least 2 delegate quotas. For example, if $A$ receives 1.999 quotas $A$ may still end up with 2 delegates. Our auditing method avoids checking such things.

The audit instead examines all pairs of viable candidates, including those receiving no delegates. For each pair of viable candidates $n$ and $m$ we check whether $(q_{n}-(a_{n}-1))<1+(q_{m}-(a_{m}-1))$ which requires that the quota of $n$ is not 1 more than the quota for $m$, after removing all received delegates but the last. This can be equivalently rewritten as

In the case that $q_{m}$ was rounded up and $q_{n}$ was rounded down, this captures that the remainder for $m$ was greater than the remainder for $n$: $p_{m}D-(a_{m}-1)>p_{n}D-a_{n}$.

We show that if the delegates are wrong with respect to the true votes, then one of these assertions is violated.

We consider the set of Hamiltonian elections conducted as part of the selection process for the 2020 Democratic National Convention (DNC) presidential nominee. Most of these primaries determine candidate viability via a plurality vote. Several states, including Wyoming and Alaska, use IRV. We estimate the number of ballots we would need to check in a comparison audit of these primaries. For each of these primaries, we audit the viability of candidates on the basis of the statewide vote, and that each viable candidate deserved the delegates that were awarded to them. We consider only the delegates that are awarded on the basis of statewide vote totals (PLEO⁸⁸8Party Leaders and Elected Officials and at-large) as these are readily available.⁹⁹9Data for plurality-based primaries was obtained from www.thegreenpapers.com/P20. Data for IRV-based primaries we consider was provided by the relevant state-level Democrats. In each proportional DNC primary, viable candidates must attain at least 15% of the total votes cast.

The full code used to generate the assertions for each DNC primary, and estimate the ASN for each audit, is located at:

https://github.com/michelleblom/primaries

Table 1 reports the expected number of ballot samples required to perform three levels of audit in each plurality and IRV-based primary conducted for the 2020 DNC.¹⁰¹⁰10A small number of DNC 2020 primaries that did not use proportional allocation of delegates were not considered, in addition to those for which we could not obtain data. Level 1 checks only that the reportedly viable candidates have at least 15% of the vote, and all other candidates do not. Level 2 checks candidate viability and that each viable candidate $c$, with $a_{c}$ allocated delegates, deserved at least $a_{c}-1$ of them. We introduce this level because, as the table shows, sometimes the complete auditing of the final delegate counts is difficult. Level 3 checks candidate viability and that each viable candidate deserved all of their allocated delegates. The assertions required to check the allocation of a candidate’s final delegate are the hardest to audit.

Of the primaries in Table 1, Maine (ME), New Hampshire (NH), Washington (WA), Texas (TX), Idaho (ID), Massachusetts (MA), California (CA), and Minnesota (MN), were considered to be close with differences of less than 10% in the statewide vote between the two leading candidates. In Maine, the difference in the statewide vote for Biden and Sanders was less than 1% of the cast vote. Auditing the Maine primary, however, is expected to require only a sample of 189 ballots. The Rhode Island (RI) primary, in contrast, requires a full manual recount. In RI, Sanders narrowly falls below the 15% threshold with 14.93% of the vote to Biden’s 76.67%. The margins that determine the complexity of these audits are the extent to which a candidates’ vote falls below or exceeds the relevant threshold, and the relative size of the remainders in candidates’ delegate quotas as a proportion of the number of delegates available.

Table 2 contrasts several of the hardest primaries of Table 1 to audit with some of the easiest. We record, for each of these primaries: the number of at-large delegates being awarded; the delegate quotas computed for each viable candidate; the difference between the decimal portion of these quotas (the remainder) divided by the number of available delegates; and the estimated auditing effort (ASN) for the primary. For the first four primaries in the table, the last awarded at-large delegate is the hardest to audit.

The use of IRV for determining candidate viability does not make a Hamiltonian election more difficult to audit. While more assertions are created to audit an IRV-based primary, the difficulty of any audit is based on the cost (ballot samples required) of its most expensive assertion. Since all assertions are tested on each ballot examined, the principle cost is retrieving the correct ballot. The audit specifications generated for the Wyoming and Alaskan primaries contain 78 and 89 assertions, respectively. The number of assertions formed for a plurality-based primary is proportional to the number of candidates. NH, involving the most candidates at 34, has 48 assertions to audit.

The computational cost of generating these audit specifications is not significant. On a machine with an Intel Xeon Platinum 8176 chip (2.1GHz), and 1TB of RAM, the generation of an audit specification for Wyoming and Alaska takes 0.3s and 0.4s, respectively. The time required to generate an audit for each of the plurality-based primaries in Table 1 ranges from 0.2ms to 0.24s (and 0.03s on average).

We provide an effective method for auditing delegate allocation by proportional representation (the Hamilton method), the first we know of for elections of this kind. Usually the audit only requires examining a small number of ballots. This could be used for primary elections in the USA and other elections in Russia, Ukraine, Tunisia, Taiwan, Namibia and Hong Kong.

We provide a version suitable for Democratic primaries in Alaska, Hawaii, Kansas, and Wyoming, which use a modified form where viability is decided using IRV.

To audit these elections we defined a new assertion for pairwise differences and corresponding assorter, which may be useful for auditing other methods.