Improving the Security of United States Elections with Robust Optimization

1. Introduction

Computerized voting machines are widely used to scan ballots and determine election outcomes throughout the United States and around the world. Voting machines are used instead of hand counting because voters are often invited to participate in a large number of contests in an election—including political offices from the President to local school boards—which causes hand counting to be impractically costly and time consuming. In this paper, we develop a low-cost approach to reducing the security risks of voting machines and improving public trust in democratic institutions by drawing on techniques from the field of robust optimization.

1.1. Background

For voting machines that scan ballots to count votes accurately, they must be configured with correct mappings between the voting targets on the ballot—that is, the boxes or ovals that voters mark—and the candidates who should receive the votes. If a voting machine is configured with an incorrect mapping, then the machine may count votes for the wrong candidates. As illustrated by the following examples, voting machines misconfigurations can produce dramatically wrong vote totals and damage public trust in elections:

• During the 2020 election, voting machines in Antrim County, Michigan were accidentally misconfigured with mappings that caused votes for Republicans to be tallied for Democrats and votes for Democrats to go uncounted (Halderman 2022). The erroneous vote totals announced as a result of this flaw received widespread media coverage (AP 2020, Bowden and Teague 2021), and this incident served as the basis for a draft executive order, later obtained by the Congressional committee investigating the events of January 6, 2021, that would have directed the Secretary of Defense to seize voting machines (Swan 2022).

• Similar accidental misconfigurations affected announced election results in Pennsylvania (Corasaniti 2019) and Georgia (Georgia Voter Registration & Elections-DeKalb County 2022) in the past five years. Although the errors were quickly caught and corrected, they similarly resulted in the initial publication of incorrect vote totals and generated significant negative publicity for the affected jurisdictions. In a particularly recent example, an accidental misconfiguration in Northampton County, Pennsylvania, during their November 2023 election caused votes to be swapped across two judge contests, leading to voter confusion and long lines on election day (Sakellariadis 2023, Walker 2024).

• Misconfigurations could also be induced deliberately by adversaries with very little technical expertise. Indeed, a group that contends the outcome of the 2020 presidential election was fraudulent recently released a video that demonstrates exactly how one could strategically induce these misconfigurations to manipulate future election outcomes (DePerno Law Office 2023). Such deliberate manipulations would allow an adversary to sow doubt in election systems, influence who wins prominent political offices, and—in at least 24 states (National Conference of State Legislators 2022)—directly affect the passage of laws on matters ranging from environmental policy to abortion rights.

Past work has sought to address the potential dangers of compromised voting machines through postelection interventions such as risk-limiting audits and cryptographic systems that make announced results publicly verifiable (Lindeman and Stark 2012, Bernhard et al. 2017). These postelection procedures are increasingly being implemented in the United States and have received attention in popular media (Oliver 2019). However, no prior work has developed a procedure that is guaranteed to detect important classes of possible attacks before an election takes place. Such a procedure could help safeguard election integrity and public confidence by detecting attacks before they affect reported vote totals. Our paper develops a rigorous and low-cost pre-election defense against misconfiguration-based cyberattacks by applying robust optimization to a widely used testing procedure called logic and accuracy testing (LAT).

1.2. Logic and Accuracy Testing

For more than a century, election officials throughout the United States have used LAT to inspect voting machines prior to elections. The idea behind LAT is simple: Officials prepare a set of ballots with known votes—dubbed a test deck—then cast the ballots through each voting machine and confirm that the machine outputs the expected tallies for all candidates (Figure 1). Any discrepancy indicates a potential malfunction, which can be addressed before the machine is used to count real votes. LAT was initially developed in the early 1900s to protect against breakdowns of mechanical lever-based voting machines and is today required by law before each election in all fifty states (Jones and Simons 2012, Walker et al. 2022).

Despite the widespread use of LAT, no prior work has used LAT for detecting attacks on modern computerized voting machines. In fact, LAT is not an obvious candidate for securing modern elections; it cannot, for example, detect malicious alterations to a voting machine’s software that cause the voting machine to operate fraudulently only after testing has concluded.¹ Nonetheless, LAT has a number of properties that make it potentially attractive for election security. First, the legally mandated use of LAT across the United States means that repurposing this procedure as a modern security tool would require little investment on already-overburdened election administrators. Second, the fact that LAT is performed prior to elections means that it is well-situated to detect cyberattacks before they affect the public. Third, developing sophisticated cyberattacks that cannot be detected by LAT requires technical capabilities that are out of reach for many would-be adversaries. In particular, we show in this paper that LAT has the potential to be an effective defense against less sophisticated (yet still practically significant) classes of attacks that are based on deliberate misconfiguration of voting machines.

The set of misconfigurations which would be detected by LAT hinges on the design of the test deck, that is, the decision of which voting targets to fill out on each ballot. Until now, test decks throughout the United States have been designed following simple heuristics that are based on human intuition (Walker et al. 2022). For example, Figure 2 shows an example of a test deck constructed by a common heuristic that gives each candidate within each contest a different number of votes. However, Figure 3 shows the output of voting machines using the test deck from Figure 2 under three examples of misconfigured mappings between voting targets and candidates, including one misconfiguration which this test deck would not detect. This demonstrates that this simple heuristic is not guaranteed to secure the voting machine from misconfiguration attacks. If each candidate on the ballot received a different number of votes, then all misconfigured mappings between voting targets and candidates would be detected, but this strategy for designing test decks is not used in practice because it requires impractically many ballots for real-world elections (see Online Appendix A). The difficulty of marking and scanning test decks scales with the number of ballots included, so short test decks are imperative for practical implementation.

1.3. Contributions

We bring a scientific perspective to LAT by introducing the first formal approach to designing test decks for LAT with rigorous security guarantees. Specifically, our approach employs mathematical optimization—rather than heuristics—to find test decks that are guaranteed to detect any misconfiguration that swaps votes between candidates. Moreover, out of all the test decks that are guaranteed to detect these swaps, our approach yields a test deck with the minimum number of ballots, thereby minimizing implementation difficulties for election officials.

In greater detail, our approach to designing test decks consists of constructing and solving a robust optimization problem (Ben-Tal et al. 2009, Bertsimas et al. 2011). The input to the robust optimization problem is a “ballot style,” which for our purposes means the set of contests that appear on a given ballot, the set of candidates who are running in each of those contests, the maximum number of candidates that a voter is allowed to select in each contest, and the correct mapping of voting targets to candidates.² The output of the robust optimization problem is the design of a minimum-length test deck that is guaranteed to detect whether a voting machine has an incorrect bijective mapping from candidates to voting targets for the ballot style in question. The robust optimization problem is stated formally in Section 3.3.

One of the key difficulties in solving our robust optimization problem lies in the large number of incorrect bijective mappings from candidates to voting targets. In a ballot style with N candidates and voting targets, there are $N!-1$ possible ways that voting targets can be swapped, one swap for each bijection over candidates less the single correct bijection. In U.S. elections, the number of candidates across the contests of a ballot style is often greater than 100. Consequently, formulating our robust optimization problem often requires more than $100!-1\approx {10}^{157}$ constraints, a number far greater than the estimated number of particles in the observable universe (Whittaker 1945). An optimization problem that explicitly encodes all possible swaps thus cannot be represented nor solved on any extant computer for many real-world elections. It is currently unknown whether the robust optimization problem is NP-hard, and it is unknown whether there exists a mixed-integer linear programming reformulation of the robust optimization problem of size that is polynomial in the number of candidates N.

We contend with the above computational challenge by developing an exact algorithm for the robust optimization problem inspired by the cutting plane method (see Section 4.1). The cutting plane method is a classical technique for solving optimization problems with many constraints by solving a sequence of optimization problems with small numbers of constraints. In our setting, each iteration of the cutting plane method solves a relaxation of the robust optimization problem that contains a small subset of the $N!-1$ swaps. If the optimal test deck of the relaxed optimization problem detects all the $N!-1$ swaps of the original problem, then the algorithm terminates. Otherwise, the algorithm finds a swap that is undetected by the optimal test deck of the relaxed problem, adds the undetected swap into the relaxed problem, and then solves the relaxed problem again. This process repeats until a feasible solution for the original robust optimization problem is obtained.

To make the cutting plane method terminate in practical computation times in real-world elections, we make a number of novel algorithmic developments. First, we reformulate the relaxed optimization problem as well as the problem of finding an undetected swap as mixed-integer linear optimization problems (see Section 4.2). These reformulations enable the cutting plane method to be easily implemented using widely available open-source and commercial optimization software such as Gurobi and Mosek. Second, we offer a variety of theoretically-justified improvements to our mixed-integer linear optimization formulations (see Section 5) that aim to decrease the number of iterations and decrease the per-iteration computation time of the cutting plane method. These improvements include dynamically identifying and removing unnecessary decision variables from the mixed-integer linear optimization problems (Section 5.1), adding constraints that impose the structure of optimal test decks into the mixed-integer linear optimization problems (Sections 5.2 and 5.3), developing a combinatorial framework for identifying which swap to add to the relaxed optimization problem in each iteration (Section 5.4), and combining all contests that are not competitive (Section 5.5). In Online Appendix C, we demonstrate via experiments on synthetic elections that each of our improvements yields significant decreases in the computation time and number of iterations of the cutting plane method.

We conclude by showcasing the value of our robust optimization approach in application to real world elections. In partnership with the Michigan Bureau of Elections, we applied our approach to each of the state’s 6,928 ballot styles from the November 2022 general election. Our results for this election (see Section 6) reveal that our approach only required a 1.2% average increase in the number of test ballots compared with current practice across the state’s 6,928 ballot styles. Hence, our approach can be deployed with minimal financial cost or operational overhead while providing significant security benefits to election jurisdictions. Moreover, our cutting plane method for solving the robust optimization problems enabled our approach to obtain optimal test decks for all 6,928 ballot styles in less than seven hours. These findings demonstrate that our cutting plane method can find optimal test decks for all of the ballot styles across a state in computation times that are practical from the perspective of election officials. Our approach described in this paper has been piloted by the Michigan Bureau of Elections in real-world elections during the summer of 2023, and we hope that our approach will be adopted by more states and countries in upcoming elections as a low-cost tool to improving the security and increasing public confidence in election outcomes.

An open source portion of the code from this paper is available at https://github.com/ballotiq/deck-checker.

2. Vulnerabilities of Existing Heuristics for Designing Test Decks

Our proposed approach to designing test decks with rigorous security guarantees is presented in Section 3. To motivate our approach, we begin in this section by describing three examples of misconfiguration attacks against U.S. voting machines. We show in each of the three examples how the attack could be strategically deployed by an adversary to undermine public trust or change the outcome of an election. Finally, we show how the examples of attacks could evade detection by LAT when test decks are designed by commonly used heuristics.

2.1. Swaps of Individual Candidates

Suppose that the goal of an adversary is to decrease the number of votes received by a specific candidate in a high-stakes contest near the top of the ballot (such as a presidential contest). In this case, an example of a misconfiguration that would be appealing to the adversary is one that swaps the voting target of the specific candidate with the target of a candidate from a contest that is lower on the ballot (such as the contest to elect a sanitation commissioner). Because fewer people vote in downballot contests (Kimball and Kropf 2008), this misconfiguration could result in the adversary’s disfavored presidential candidate receiving fewer votes than they should. Moreover, if the test deck for LAT is designed using a common heuristic in which a single ballot contains votes for the first candidate in each contest, two ballots contain votes for the second candidate in each contest, and so on, then LAT would not detect any misconfiguration that swaps the targets for two candidates at corresponding indices in their respective contests. An example of a test deck constructed by this common heuristic is shown in Figure 2, and the misconfiguration depicted in Figure 3(c) is an example of such a swap that goes undetected, because it swaps the second candidate in the presidential contest with the second candidate in the senatorial contest.

2.2. Swaps of Entire Contests

In many states, elections put certain yes-or-no questions—commonly called initiatives, proposals, or referendums—directly to voters. The effect of these contests range from modifying a state’s constitution on matters such as abortion rights (Slevin 2023) and environmental policy (Kollipara 2016, Barron 2022) to recalling sitting politicians from their office (Mai-Duc 2021). If an adversary wished to swap the outcome of two such contests, they could misconfigure the voting machine to swap the voting targets for yes and for no between the two contests. Moreover, if LAT is conducted with a test deck that includes the same number of votes for yes and the same number of votes for no in each of the two contests—which is the case under every common heuristic for test deck preparation used today (Walker et al. 2022)—then this misconfiguration would not be detected by LAT (see Section 5.3). This attack could thus be used to ensure a favored proposal passes or a disfavored proposal fails, and would allow an adversary to directly influence the laws or constitution of a jurisdiction.

2.3. Deliberately Flawed Test Decks

It is common for jurisdictions to contract outside vendors to configure their voting machines as well as design the test decks used to conduct LAT. If this vendor is untrustworthy, they could misconfigure the machine according to their own preference, and then deliberately construct a test deck which would fail to detect the modification. Indeed, we show in Online Appendix B that a vendor has significant freedom in the misconfiguration they choose, even when the test deck they produce is constrained by some of the most stringent legal requirements in use by states today.

In the following section, we introduce an approach to designing test decks that enables LAT to become a rigorous pre-election defense against an important class of misconfiguration attacks. This class includes, among many others, the three examples of attacks described above.

3. Robust Logic and Accuracy Testing

In this section, we introduce robust logic and accuracy testing (RLAT), an optimization-based framework for designing test decks in LAT with rigorous security guarantees. This section has the following organization. Section 3.1 develops the terminology and mathematical notation that will be used throughout the paper. Section 3.2 presents a general formulation of RLAT and discusses its value from the perspective of various stakeholders in U.S. elections. Section 3.3 uses the RLAT framework to derive our robust optimization problem (RO-$\mathrm{\Sigma }$) for finding a minimum-length test deck that will detect whether a voting machine is misconfigured to swap votes between candidates. Section 3.4 establishes the fundamental structural properties of test decks that are feasible for the robust optimization problem (RO-$\mathrm{\Sigma }$).

3.1. Preliminaries

A ballot style is composed of a set of contests $\mathcal{C}\triangleq \{1,\dots ,C\}$ and a set of candidates $\mathcal{N}\triangleq \{1,\dots ,N\}$. For each contest $c\in \mathcal{C}$, we let ${\mathcal{N}}_c\subseteq \mathcal{N}$ denote the subset of candidates that appear in contest c, and we let $v_c$ denote the maximum number of candidates in that contest that may be legally selected by a voter. For example, for a contest that corresponds to the senatorial election, the set ${\mathcal{N}}_c$ would contain the indices of the candidates that are running for senator, and the equality $v_c=1$ would denote that each voter is permitted to select at most one candidate in the contest. In a contest for a local school board with five vacancies, we would alternatively have the equality $v_c=5$. We assume that each candidate $i\in \mathcal{N}$ appears in exactly one contest. We say that a contest c is noncompetitive if the maximum number of votes $v_c$ is equal to the number of candidates $|{\mathcal{N}}_c|$ in the contest.³ In real-world elections such as those from Michigan (Figure 4), the number of contests in each ballot style typically satisfies $15\le C\le 40$, and the number of candidates in each ballot style typically satisfies $60\le N\le 120$.

A ballot refers to a physical document that contains a box or oval beside each candidate, termed targets, that are used by voters to record their choices. With a slight abuse of notation, we denote the targets on a ballot by $\mathcal{N}\triangleq \{1,\dots ,N\}$, where each target $i\in \mathcal{N}$ refers to the box or oval that is beside candidate $i\in \mathcal{N}$. A filled-out ballot is represented by a subset of targets $\beta \subseteq \mathcal{N}$, with the interpretation that the filled-out ballot satisfies $i\in \beta$ if and only if the filled-out ballot selected target i. It follows that the number of targets beside candidates in contest $c\in \mathcal{C}$ that are selected by a filled-out ballot $\beta \subseteq \mathcal{N}$ is equal to $|{\mathcal{N}}_c\cap \beta |$. A deck refers to any finite-length sequence of filled-out ballots $({\beta }_1,\dots ,{\beta }_B)$.

When a voting machine operates correctly, the machine will receive a deck of filled-out ballots as its input, and the machine will output the total number of targets that are selected for each candidate in the filled-out ballots that do not have an overvote in that candidate’s contest. For any input deck $({\beta }_1,\dots ,{\beta }_B)$, we denote the output of a voting machine that operates correctly by the vector-valued function

with the output for each candidate $i\in {\mathcal{N}}_c$ in each contest $c\in \mathcal{C}$ defined as

In the above definition, and throughout the rest of this paper, we let $\mathbb{I}\{·\}$ represent the indicator function that is equal to one if $·$ is true and is equal to zero if $·$ is false. The inclusion $i\in {\beta }_b$ holds if and only if filled-out ballot ${\beta }_b$ has selected the target that is beside candidate i, and the inequality $|{\mathcal{N}}_c\cap {\beta }_b|\le v_c$ holds if and only if filled-out ballot ${\beta }_b$ has selected at most $v_c$ of the targets that are beside the candidates in contest c. In other words, the inequality $|{\mathcal{N}}_c\cap {\beta }_b|\le v_c$ holds if and only if filled-out ballot ${\beta }_b$ is interpreted by the voting machine that operates correctly as not containing an overvote in contest c. For notational convenience, we denote the set of ballots that do not overvote any contest by $ℬ\triangleq \{\beta \subseteq \mathcal{N}:|{\mathcal{N}}_c\cap \beta |\le v_c\hspace{0.17em}\forall c\in \mathcal{C}\}.$

Remark 1.

If the filled-out ballots in an input deck do not contain overvotes, then the output of the voting machine that operates correctly will equal the number of filled-out ballots that select the target associated with each candidate. In other words, if ${\beta }_1,\dots ,{\beta }_B\in ℬ$, then the equality $T_i^{*}({\beta }_1,\dots ,{\beta }_B)=|\{b\in \{1,\dots ,B\}:i\in {\beta }_b\}|$ holds for each candidate $i\in \mathcal{N}$.

To represent the output of a specific voting machine that may or may not be operating correctly, we use the vector-valued function

This function represents the output of the voting machine for any input deck of filled-out ballots $({\beta }_1,\dots ,{\beta }_B)$. We say that the voting machine represented by the vector-valued function $\widehat{T}(·)$ is not operating correctly if there exists a deck $({\beta }_1,\dots ,{\beta }_B)$ and a candidate $i\in \mathcal{N}$ such that ${\widehat{T}}_i({\beta }_1,\dots ,{\beta }_B)\ne T_i^{*}({\beta }_1,\dots ,{\beta }_B)$. If the voting machine is not operating correctly, and if the voting machine is used to count votes in an actual election, then it could produce results inconsistent with the actual ballots cast and change the outcome of the election.

3.2. Formulation of RLAT

We now introduce the mathematical description of RLAT, an optimization-based framework for designing test decks in LAT with rigorous security guarantees. Specifically, given an uncertainty set $\mathcal{U}$ of possible ways that a voting machine might be operating incorrectly, RLAT designs the test deck by solving the following optimization problem:

The optimization problem (RO) yields a minimum-length test deck that is guaranteed to detect whether a voting machine is operating incorrectly in any of the ways specified by the uncertainty set.

In greater detail, the decision variables of the optimization problem (RO) consist of the length of the test deck, $B\in \mathbb{N}$, as well as the test deck of filled-out ballots without any overvotes, ${\beta }_1,\dots ,{\beta }_B\in ℬ$. The constraints of the optimization problem (RO) ensure that if the test deck is cast into a voting machine, and if the voting machine is operating incorrectly in any of the ways specified by the uncertainty set, then the output of the voting machine will be different from the output of a voting machine that is operating correctly. In other words, if $(B,{\beta }_1,\dots ,{\beta }_B)$ is an optimal solution for the optimization problem (RO), then we have a guarantee that the output of a voting machine $\widehat{T}({\beta }_1,\dots ,{\beta }_B)$ will be different from the output of a voting machine that operates correctly $T^{*}({\beta }_1,\dots ,{\beta }_B)$ whenever the voting machine $\widehat{T}(·)$ is operating incorrectly in any of the ways specified by the uncertainty set $\mathcal{U}$. We elaborate on the construction of the uncertainty set in Section 3.3. The objective of the optimization problem (RO) is to find a test deck that satisfies the constraints that consists of the fewest number of ballots.

The optimization problem (RO) for designing test decks in LAT can be viewed as attractive from the perspective of the relevant stakeholders including election administrators, policy makers, voters, and the computer security community. We elaborate below on the attractiveness and the design of the optimization problem (RO) through the perspectives of these various stakeholders:

3.2.1. Election Administrators.

The administration of U.S. elections is a complicated endeavor, conducted in parallel by thousands of local officials across the country. Across so diverse and decentralized a system, even marginal increases to the difficulty or complexity of election procedures carry a very high administrative cost. This cautions against testing procedures that are substantially more difficult or resource intensive than those already in use.

From an implementation standpoint, RLAT aims to minimize the burden the solution confers to election administrators. By finding a test deck that minimizes the number of ballots, the optimization problem (RO) yields a suitable test deck that minimizes the time it takes to fill out and insert the decks into a machine. Moreover, a computer algorithm for solving the optimization problem (RO) can be integrated seamlessly at many stages, like in the vendor provided Election Management System (EMS) or by third-party ballot-printing companies that are often contracted to prepare test decks under current practice. This means we can implement RLAT through the operational processes that election administrators already have in place, with minimal change to the official’s direct experience. Finally, using a computer algorithm can relieve election workers from the arduous task of manually designing test decks.

3.2.2. Policy Makers and Voters.

RLAT is attractive for policy makers and voters because it enables LAT to provide strong and interpretable guarantees regarding the security of an election and the legitimacy of its outcome. Indeed, the optimization problem (RO) provides policy makers with the flexibility to specify the uncertainty set of possible ways that a voting machine may operate incorrectly. Policy makers can make this decision based on their evaluation of the cost-security tradeoffs for their own state or jurisdiction and based on factors like the known traits of the voting machines that are used in their elections (see Remark 2 in Section 3.3). The optimization problem (RO) can also easily integrate minimum legal requirements on test decks that are specified by policy makers, as we elaborate in Online Appendix D. Moreover, given a defined uncertainty set $\mathcal{U}$ and a test deck $({\beta }_1,\dots ,{\beta }_B)$, any voter can verify that the test deck satisfies the constraints of the optimization problem (RO). This can enhance voter confidence that testing is being conducted fairly and provides concrete and voter-verifiable assurances that the outcome of the election has not been accidentally or maliciously altered in ways similar to those from the examples given in Section 2.

3.2.3. Computer Security Community.

In the election security community, and in the computer security community more broadly, risk is defined and minimized by considering a hypothetical adversary. This adversary aims to interfere with a system and is constrained by a threat model that specifies the scope of their capabilities. This allows for the development of security interventions that have a definite effect with respect to certain assumptions about the options available to an adversary. The optimization problem (RO) thus works constructively with the computer security mindset. Indeed, the uncertainty set $\mathcal{U}$ is in essence a formalization of the threat model—It describes the potential modifications to the machine, which the adversary is able to choose between. By changing the uncertainty set, this formulation can flexibly substitute threat models as needed.

3.3. RLAT with the Swap Uncertainty Set

The key to achieving strong and interpretable security guarantees through RLAT is selecting an appropriate uncertainty set $\mathcal{U}$ in the optimization problem (RO). If the uncertainty set accounts for only a small number of possible misconfigurations or errors, then the security guarantees afforded by RLAT will be limited. On the other hand, if the uncertainty set is overly expansive, then (RO) might yield a test deck comprised of an impractically large number of ballots. Naturally, the task of choosing an uncertainty set that strikes an appropriate balance between the expressiveness and conservatism is a central challenge when constructing robust optimization problems such as (RO).

We focus throughout this paper on solving the optimization problem (RO) with a specific construction of the uncertainty set that we henceforth refer to as the swap uncertainty set. The swap uncertainty set consists of all of the voting machines that have an incorrect bijective mapping from candidates to voting targets. Hence, the optimization problem (RO) with the swap uncertainty set will yield the shortest test deck that is guaranteed to detect whether a voting machine is swapping votes across candidates. The optimization problem (RO) with the swap uncertainty set is stated formally at the end of this section as the optimization problem (RO-$\mathrm{\Sigma }$).

The swap uncertainty set is attractive from a security standpoint because it encompasses a general class of misconfigurations that would be difficult to detect for a well-implemented voting machine. The premise of the swap uncertainty set when scanning hand-marked ballots is that a voting machine is configured with a $(x,y)$ coordinate for each candidate, which specifies the location of that candidate’s voting target on the physical ballot. A well-implemented voting machine’s software should perform two basic sanity checks of this configuration. First, the voting machine should not allow any candidate to be associated with multiple targets. Second, the voting machine should not allow different candidates’ targets to overlap. This ensures a bijective mapping between candidates and targets. The premise of the swap uncertainty set when scanning ballots produced with a ballot-marking device (BMD) is that the BMD and optical scanner may be configured with inconsistent data representations of the candidates (Georgia Voter Registration & Elections-DeKalb County 2022), such that votes encoded by the BMD as corresponding to one candidate may be read by the scanner as corresponding to another. Well-implemented software should enforce that each candidate has precisely one data representation, so this mismatch must also be a bijection. The swap uncertainty set is thus a natural choice for the RLAT problem under either of these models, since it describes each possible mapping from candidates to targets.

The formal definition of the swap uncertainty set requires the following additional notation. Let $\mathrm{\Sigma }$ denote the set of all nonidentity bijections of the form $\sigma :\mathcal{N}\to \mathcal{N}$, where we say that the function $\sigma (·)$ is a nonidentity bijection if and only if the function satisfies the following two criteria:

1. For every target $j\in \mathcal{N}$, there exists one candidate $i\in \mathcal{N}$ that satisfies $\sigma (i)=j$.

2. There exists $i\in \mathcal{N}$ that satisfies $\sigma (i)\ne i$.

Each nonidentity bijection can be understood as an incorrect mapping from candidates to targets.⁴ The output of a voting machine whose mapping from candidates to targets is the bijection $\sigma :\mathcal{N}\to \mathcal{N}$ is given for each candidate $i\in {\mathcal{N}}_c$ in each contest $c\in \mathcal{C}$ by

To make sense of the above definition, we remark that the inclusion $\sigma (i)\in {\beta }_b$ holds if and only if the bth filled-out ballot in the test deck is interpreted by a voting machine with mapping $\sigma$ to contain a vote for candidate i. Similarly, we observe that the inequality $|\{\sigma (j)\in {\beta }_b:j\in {\mathcal{N}}_c\}|\le v_c$ holds if and only if the bth filled-out ballot in the test deck is interpreted by a voting machine with mapping $\sigma$ as containing votes for at most $v_c$ candidates in contest c.

In view of the above notation, we define the swap uncertainty set as the set of the voting machines that correspond to each of the nonidentity bijections:

Hence, we conclude that a test deck comprised of filled-out ballots ${\beta }_1,\dots ,{\beta }_B\in ℬ$ will satisfy the constraints of the optimization problem (RO) with the swap uncertainty set if and only if the test deck is guaranteed to detect whether a voting machine has been misconfigured to swap votes across candidates.

Equipped with the swap uncertainty set, we are ready to formally state the key optimization problem of this paper, that is, the optimization problem of finding a minimum-length test deck that is guaranteed to detect whether a voting machine has been misconfigured to swap votes across candidates. This optimization problem (RO) with the swap uncertainty set is stated below as (RO-$\mathrm{\Sigma }$):

Having established that the test decks obtained by (RO-$\mathrm{\Sigma }$) offer attractive and rigorous security guarantees, we show in the rest of this paper that (RO-$\mathrm{\Sigma }$) leads to test decks that can be practically deployed in real world elections. In Sections 4 and 5, we develop an exact algorithm for solving the optimization problem (RO-$\mathrm{\Sigma }$). In Section 6, we show that our exact algorithm scales to Michigan’s November 2022 elections and that the test decks obtained by (RO-$\mathrm{\Sigma }$) in those elections are not much longer than the test decks produced according to the heuristics Michigan currently uses. Hence, RLAT with the swap uncertainty set strikes a balance between producing test decks that account for a large number of possible voting machine misconfigurations and producing test decks with a practically small number of ballots.

Remark 2.

Although this paper focuses on solving (RO-$\mathrm{\Sigma }$), we note that RLAT offers election officials the flexibility to use uncertainty sets that include a more expansive or narrow model of the ways in which a voting machine could be wrong. For instance, in states that currently use weaker heuristics than Michigan’s to prepare their test decks, election officials may be accustomed to using very short test decks and thus might balk at the lengths of test decks produced by (RO-$\mathrm{\Sigma }$). To accommodate election officials in such states, one can solve (RO) with an uncertainty set that is a subset of the swap uncertainty set to obtain shorter test decks with weaker, albeit still rigorous defined, security guarantees (e.g., by opting to ignore the possibility of swaps between candidates in noncompetitive contests). Conversely, the swap uncertainty set can be made more expansive (e.g., by considering cases where the mapping of targets to candidates need not be bijective for voting machines whose software implementation allows the same target to be associated with multiple candidates, or vice versa). That being said, we emphasize that the algorithms presented in this paper are designed for solving (RO-$\mathrm{\Sigma }$), i.e., the specific case of (RO) in which the uncertainty set is the swap uncertainty set.

3.4. Discussion

We conclude Section 3 by characterizing the key structural properties of test decks that satisfy the constraints of the optimization problem (RO-$\mathrm{\Sigma }$). Specifically, the main contribution of this section is a technical result, denoted by Theorem 1, that characterizes the situations in which the output of a voting machine that operates correctly will be different from the output of a voting machine whose mapping from candidates to targets is a nonidentity bijection. The characterization established by the following theorem will be used extensively for designing algorithms in the rest of the sections.

Theorem 1.

Let ${\beta }_1,\dots ,{\beta }_B\in ℬ$ and $\sigma \in \mathrm{\Sigma }$. Then $T^{\sigma }({\beta }_1,\dots ,{\beta }_B)\ne T^{*}({\beta }_1,\dots ,{\beta }_B)$ if and only if at least one of the following two conditions hold:

• There exists a candidate $i\in \mathcal{N}$ that satisfies

  $$|\{b\in \{1,\dots ,B\}:i\in {\beta }_b\}|\ne |\{b\in \{1,\dots ,B\}:\sigma (i)\in {\beta }_b\}|.$$

• There exist a contest $c\in \mathcal{C}$ and a filled-out ballot ${\beta }_b$ for some $b\in \{1,\dots ,B\}$ that satisfy

  $$|\left\{\sigma (j)\in {\beta }_b:j\in {\mathcal{N}}_c\right\}|>v_c.$$

The proof of this theorem and all other technical proofs in this paper can be found in Online Appendix F.

In words, the above theorem establishes that the output of a voting machine that operates correctly will not equal the output of a voting machine whose mapping from candidates to targets is a nonidentity bijection $\sigma \in \mathrm{\Sigma }$ if and only if the test deck comprised of filled-out ballots ${\beta }_1,\dots ,{\beta }_B\in ℬ$ satisfies at least one of two conditions. The first condition is that there exists a candidate $i\in \mathcal{N}$ such that the number of filled-out ballots that selected target i, $|\{b\in \{1,\dots ,B\}:i\in {\beta }_b\}|$, is different from the number of filled-out ballots that selected target $\sigma (i)$, $|\{b\in \{1,\dots ,B\}:\sigma (i)\in {\beta }_b\}|$. The second condition is that there exists a contest $c\in \mathcal{C}$ in one of the ballots $b\in \{1,\dots ,B\}$ that is interpreted as overvoted by the voting machine whose mapping from candidates to targets is $\sigma$. As an immediate corollary of Theorem 1, we obtain the following characterization of the test decks that are feasible for the optimization problem (RO-$\mathrm{\Sigma }$).

Corollary 1.

A tuple $(B,{\beta }_1,\dots ,{\beta }_B)$ is feasible for the optimization problem (RO-$\mathrm{\Sigma }$) if and only if $B\in \mathbb{N}$, ${\beta }_1,\dots ,{\beta }_B\in ℬ$, and for every $\sigma \in \mathrm{\Sigma }$, at least one of the following two conditions hold:

• There exists a candidate $i\in \mathcal{N}$ that satisfies

  $$|\{b\in \{1,\dots ,B\}:i\in {\beta }_b\}|\ne |\{b\in \{1,\dots ,B\}:\sigma (i)\in {\beta }_b\}|.$$

• There exist a contest $c\in \mathcal{C}$ and a filled-out ballot ${\beta }_b$ for some $b\in \{1,\dots ,B\}$ that satisfy

  $$|\left\{\sigma (j)\in {\beta }_b:j\in {\mathcal{N}}_c\right\}|>v_c.$$

Corollary 1 implies that the optimization problem (RO-$\mathrm{\Sigma }$) always has a feasible solution. Specifically, it follows from Corollary 1 that any test deck that gives a distinct total number of votes to each of the candidates across all of the contests is a feasible solution for the optimization problem (RO-$\mathrm{\Sigma }$) (a formal proof of this can be found in the proof of Proposition EC.1 from Online Appendix A). We note that, although Corollary 1 implies that a feasible solution for optimization problem (RO-$\mathrm{\Sigma }$) can be obtained by simply giving every candidate across every contest a distinct number of votes, we show in Online Appendix A using real-world data that heuristics based on assigning a distinct number of votes to each candidate will result in test decks that contain too many ballots to be implementable in practice. Thus motivated, we proceed in Section 4 to develop an exact algorithm that solves the optimization problem (RO-$\mathrm{\Sigma }$) in order to find test decks that are feasible solutions for (RO-$\mathrm{\Sigma }$) with the fewest possible number of ballots.

4. Exact Algorithm

In this section, we present our exact algorithm for solving the optimization problem (RO-$\mathrm{\Sigma }$).

4.1. Overview of Exact Algorithm

To begin our discussion of our exact algorithm, we recall from Section 1.1 that one of the key challenges in solving the optimization problem (RO-$\mathrm{\Sigma }$) is that the problem contains an enormous number of constraints. Indeed, we observe that the number of constraints in the optimization problem (RO-$\mathrm{\Sigma }$) is driven by the cardinality of the set of nonidentity bijections $\mathrm{\Sigma }$, and it follows readily from Section 3.3 that the number of nonidentity bijections satisfies $|\mathrm{\Sigma }|=N!-1$ for a ballot style with N candidates. Because the number of candidates in real-world ballot styles often satisfies $N\ge 100$, an optimization problem that explicitly encodes all possible nonidentity bijections thus cannot be represented nor solved on any extant computer for many real-world elections. It is currently unknown whether (RO-$\mathrm{\Sigma }$) is NP-hard, and it is unknown whether there exists a mixed-integer linear programming reformulation of (RO-$\mathrm{\Sigma }$) of size that is polynomial in the number of candidates N.

To contend with the computational challenge of solving the optimization problem (RO-$\mathrm{\Sigma }$), we draw inspiration from an algorithmic strategy known as the cutting plane method (Kelley 1960, Gilmore and Gomory 1961). The goal of the cutting plane method is to circumvent the need to solve an optimization problem with a large number of constraints by solving a sequence of optimization problems with small numbers of constraints. The application of the cutting plane method to the optimization problem (RO-$\mathrm{\Sigma }$) takes the form of an iterative algorithm that is described below and visualized in Figure 5.

In each iteration of our algorithm, we start with a subset of nonidentity bijections $\widehat{\mathrm{\Sigma }}\subseteq \mathrm{\Sigma }$, and we solve the following variant of the optimization problem (RO-$\mathrm{\Sigma }$):

To make sense of the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$), let us reflect on the relationship between (RO-$\widehat{\mathrm{\Sigma }}$) and (RO-$\mathrm{\Sigma }$). We observe that the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$) is nearly identical to the optimization problem (RO-$\mathrm{\Sigma }$), with the only difference being that the former only has a constraint for each $\sigma \in \widehat{\mathrm{\Sigma }}$ instead of a constraint for each $\sigma \in \mathrm{\Sigma }$. The optimization problem (RO-$\widehat{\mathrm{\Sigma }}$) can thus be viewed as a relaxation of the optimization problem (RO-$\mathrm{\Sigma }$), in the sense that the optimal objective value of the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$) is less than or equal to the optimal objective value of the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$), but an optimal solution for the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$) might not be a feasible solution for the optimization problem (RO-$\mathrm{\Sigma }$). The potential attractiveness of the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$) can be attributed to practical tractability: If the cardinality of $\widehat{\mathrm{\Sigma }}$ is significantly less than the cardinality of $\mathrm{\Sigma }$, then it will be possible to solve the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$) much faster by a computer compared with the optimization problem (RO-$\mathrm{\Sigma }$).

After computing an optimal solution for the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$), the next step of the current iteration of our algorithm is determining whether the optimal solution for the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$) is a feasible solution for the optimization problem (RO-$\mathrm{\Sigma }$). This step is performed by solving the optimization problem

where $(B,{\beta }_1,\dots ,{\beta }_B)$ denotes the optimal solution of the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$). The optimization problem (CUT) has two possible outputs. First, if the optimization problem (CUT) outputs an optimal solution $\sigma \in \mathrm{\Sigma }$, then we conclude that $(B,{\beta }_1,\dots ,{\beta }_B)$ is not a feasible solution of the optimization problem (RO-$\mathrm{\Sigma }$) because the constraint $T^{\sigma }({\beta }_1,\dots ,{\beta }_B)\ne T^{*}({\beta }_1,\dots ,{\beta }_B)$ in the optimization problem (RO-$\mathrm{\Sigma }$) is violated by the test deck $({\beta }_1,\dots ,{\beta }_B)$. Second, if the optimization problem (CUT) does not have any optimal solution, then we conclude that $(B,{\beta }_1,\dots ,{\beta }_B)$ is a feasible solution for the optimization problem (RO-$\mathrm{\Sigma }$).

The final step of each iteration of the algorithm depends on the output of the optimization problem (CUT). If that optimization problem does not have a feasible solution, then we observe that $(B,{\beta }_1,\dots ,{\beta }_B)$ must be a feasible solution for the optimization problem (RO-$\mathrm{\Sigma }$). Moreover, because $(B,{\beta }_1,\dots ,{\beta }_B)$ was an optimal solution for the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$) and because the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$) is a relaxation of the optimization problem (RO-$\mathrm{\Sigma }$), it must be the case that $(B,{\beta }_1,\dots ,{\beta }_B)$ is also an optimal solution for the optimization problem (RO-$\mathrm{\Sigma }$). Hence, if the optimization problem (CUT) does not have a feasible solution, then we have found an optimal solution to the optimization problem (RO-$\mathrm{\Sigma }$), and the algorithm terminates. Otherwise, if the optimization problem (CUT) outputs $\sigma \in \mathrm{\Sigma }$, then we conclude the current iteration by updating $\widehat{\mathrm{\Sigma }}\leftarrow \widehat{\mathrm{\Sigma }}\cup \{\sigma \}$ and starting a new iteration of the algorithm.

It follows from straightforward arguments that the algorithm described above will terminate at an optimal solution for the optimization problem (RO-$\mathrm{\Sigma }$) after finitely many iterations, regardless of the choice of the subset $\widehat{\mathrm{\Sigma }}\subseteq \mathrm{\Sigma }$ in the first iteration. Indeed, the finite convergence of the algorithm follows from the fact that $\mathrm{\Sigma }$ is a finite set and from the fact that the optimization problem (CUT) will never output a nonidentity bijection $\sigma \in \mathrm{\Sigma }$ that is an element of $\widehat{\mathrm{\Sigma }}$ when the test deck $({\beta }_1,\dots ,{\beta }_B)$ satisfies the constraints of the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$). Therefore, the number of iterations of the algorithm is always upper bounded by $|\mathrm{\Sigma }|=N!-1$. In our numerical experiments throughout this paper, we initialize $\widehat{\mathrm{\Sigma }}$ in the first iteration to be the empty set.

In order for the algorithm described above to be practically efficient in real-world elections, three important properties must hold. First, it must be possible to quickly solve the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$) when $|\widehat{\mathrm{\Sigma }}|\ll |\mathrm{\Sigma }|$. Second, the algorithm must terminate after a relatively small number of iterations, as this property is essential for ensuring that the cardinality of $\widehat{\mathrm{\Sigma }}$ remains much smaller than the cardinality of $\mathrm{\Sigma }$. Third, it must be possible to have a fast implementation of the optimization problem (CUT) for finding a constraint that is violated by the test deck obtained by solving the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$). In Sections 4.2 and 5, we show that these three important properties for obtaining a practically efficient algorithm can be achieved simultaneously.

4.2. Mixed-Integer Reformulations

In each iteration of the cutting plane method from Section 4.1, we are tasked with solving the optimization problems (RO-$\widehat{\mathrm{\Sigma }}$) and (CUT). Here, we show that optimal solutions for these two optimization problems can be obtained by solving mixed-integer linear optimization problems. In doing so, this section enables the cutting plane method from Section 4.1 to be easily implementable using widely available open-source and commercial optimization software such as Gurobi and Mosek. Improvements to the mixed-integer linear optimization reformulations from the present section are proposed and analyzed in Section 5.

4.2.1. Mixed-Integer Reformulation of (RO-$\widehat{\mathrm{\Sigma }}$).

At a high level, our procedure for solving the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$) consists of the following steps. First, we fix B to be an integer that is less than or equal to the optimal objective value of the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$). We then solve the following optimization problem:

If the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$-B) does not have any feasible solutions, then we observe that B must be strictly less than the optimal objective value of the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$). In that case, we update $B\leftarrow B+1$ and resolve the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$-B) with the new value for the parameter B. We repeat this loop until the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$-B) is feasible, at which point (RO-$\widehat{\mathrm{\Sigma }}$-B) will yield an optimal solution for the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$).

Remark 3.

We use the above procedure to solve the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$) because the number of decision variables in the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$) depends on the integer B, where the integer B is itself a decision variable in the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$). In contrast, the number of decision variables in the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$-B) is known because the integer B is fixed externally. Because the number of decision variables is known a priori, the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$-B) can be reformulated as a mixed-integer linear optimization problem.

Remark 4.

The above procedure requires B to be initialized to an integer that is less than or equal to the optimal objective value of the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$). In our implementation of the procedure, we initialize the integer to $B\leftarrow 1$ in the first iteration of the cutting plane method. In all subsequent iterations of the cutting plane method, we initialize B to the optimal objective value of the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$) from the previous iteration of the cutting plane method.⁵

In the remainder of Section 4.2.1, we show that the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$-B) can be reformulated as a mixed-integer linear optimization problem. Indeed, let $\mathcal{B}\triangleq \{1,\dots ,B\}$ and ${\mathcal{B}}_0\triangleq \{0\}\cup \mathcal{B}$. With this notation, we first observe that the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$-B) can be rewritten equivalently as the following intermediary optimization problem:

The optimization problem (1) can be interpreted as follows. Each binary decision variable ${\beta }_{b,i}\in \{0,1\}$ is equal to one if and only if target i is selected in the bth filled-out ballot in the test deck. Hence, each vector ${\beta }_b\equiv ({\beta }_{b,1},\dots ,{\beta }_{b,N})\in {\{0,1\}}^{\mathcal{N}}$ serves as a binary encoding of the targets that are selected in the bth filled-out ballot. Constraint (1b) ensures that each filled-out ballot in the test deck is feasible, that is, there does not exist a filled-out ballot that contains more votes for candidates in a contest than are allowed. Constraint (–) says that the output of a voting machine whose mapping from candidates to targets is $\sigma \in \widehat{\mathrm{\Sigma }}$ must be different from the output of a correctly operating voting machine when using the test deck ($\{i:{\beta }_{1,i}=1\},\dots ,\{i:{\beta }_{B,i}=1\}$).

We observe from inspection that the above optimization problem (1) consists exclusively of binary decision variables. Moreover, the objective function (1a) and the constraints (1b) are linear functions of the decision variables. Therefore, the final step in our reformulation of the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$-B) as a mixed-integer linear optimization problem is to reformulate the constraint (–). This can be done through the introduction of new decision variables $\gamma$, y, and p, resulting in the following mixed-integer linear optimization problem:

The decision variables of the above optimization problem can be interpreted as follows.

First, we observe that Constraints (1c) and (1d) together enforce that each decision variable ${\gamma }_{i,g}\in \{0,1\}$ will be equal to one if and only if candidate i appears in exactly g ballots.

Second, Constraint (1e) requires that $y_{i,j}$ must be greater than or equal to one if candidates i and j receive the same number of votes across $\mathcal{B}$, and may be as low as zero if they receive a different number of votes. Similarly, Constraint (1f) requires that $p_{b,c}^{\sigma }$ must be equal to one if contest c receives $v_c$ or fewer votes on ballot b under swap $\sigma$ and may be zero if the contest is instead overvoted.

Finally, Constraint (1g) ensures that a feasible solution for the optimization problem (1) exists if and only if at least one $y_{i,\sigma (i)}$ or $p_{b,c}^{\sigma }$ is zero for each $\sigma \in \widehat{\mathrm{\Sigma }}$. In other words, the problem has a feasible solution if and only if, for each swap in $\widehat{\mathrm{\Sigma }}$, there exists at least one candidate that is mapped to a target with a different number of votes or there exists at least one ballot that is unexpectedly interpreted as containing an overvote. This ensures that any feasible solution to this optimization problem corresponds to a deck of ballots that will detect every swap in our subset.

In summary, we have shown in this section that the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$) can be solved by a procedure that consists of fixing the integer B to a lower bound on the optimal objective value of the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$) and then incrementing B until the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$-B) has a feasible solution. Moreover, for each fixed choice of the integer B, we showed that the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$-B) can be reformulated as the mixed-integer linear optimization problem (1). Thus, we have shown that an optimal solution for the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$) can be obtained by a procedure that consists of solving one or more mixed-integer linear optimization problems.

4.2.2. Mixed-Integer Reformulation of (CUT).

We conclude Section 4.2 by reformulating the optimization problem (CUT) as a mixed-integer linear optimization problem.⁶ Given any test deck $({\beta }_1,\dots ,{\beta }_B)$, our mixed-integer linear optimization reformulation of the optimization problem (CUT) is the following:

The Constraints (2a)–(2c) enforce that the decision variables $x\in {\{0,1\}}^{\mathcal{N}\times \mathcal{N}}$ are a binary encoding of a nonidentity bijection $\sigma \in \mathrm{\Sigma }$. Indeed, Constraints (2a) and (2b) ensure that each feasible solution of (2) can be transformed into a bijection $\sigma :\mathcal{N}\to \mathcal{N}$ using the rule that $\sigma (i)=j$ if and only if $x_{i,j}=1$ for each $i,j\in \mathcal{N}$. Constraint (2c) enforces that there exists $i\in \mathcal{N}$ that satisfies $\sigma (i)\ne i$.

The last two constraints (2d) and (2e) enforce that the nonidentity bijection $\sigma \in \mathrm{\Sigma }$ corresponding to the decision variables $x\in {\{0,1\}}^{\mathcal{N}\times \mathcal{N}}$ satisfies the equality $T^{\sigma }({\beta }_1,\dots ,{\beta }_B)=T^{*}({\beta }_1,\dots ,{\beta }_B)$. To see why this is the case, we first observe that Constraint (2d) enforces that the inequality $|\{\sigma (j)\in {\beta }_b:j\in {\mathcal{N}}_c\}|\le v_c$ holds for all contests $c\in \mathcal{C}$ and $b\in \mathcal{B}$. Moreover, Constraint (2e) enforces that the equality $|\{b\in \{1,\dots ,B\}:i\in {\beta }_b\}|=|\{b\in \{1,\dots ,B\}:\sigma (i)\in {\beta }_b\}|$ holds for all candidates $i\in \mathcal{N}$. Therefore, it follows from Theorem 1 in Section 3.4 that Constraints (2d) and (2e) are satisfied if and only if the nonidentity bijection $\sigma \in \mathrm{\Sigma }$ corresponding to the decision variables $x\in {\{0,1\}}^{\mathcal{N}\times \mathcal{N}}$ satisfies the equality $T^{\sigma }({\beta }_1,\dots ,{\beta }_B)=T^{*}({\beta }_1,\dots ,{\beta }_B)$.

5. Improvements to Exact Algorithm

In this section, we present five improvements to the mixed-integer linear optimization reformulations from Section 4.2 that significantly increase the practical efficiency of the cutting plane method from Section 4.1. Our five improvements to the mixed-integer linear optimization reformulations are presented and analyzed in Sections 5.1 to 5.5. In Online Appendix C, we demonstrate via numerical experiments on synthetic elections that each of the five improvements from this section, when applied in isolation, generates between a 20× and 3,000× speedup to the cutting plane method.

5.1. Improvement 1: Reducing Number of Decision Variables and Constraints

As our first step in increasing the practical efficiency of the cutting plane method from Section 4.1, we show that a number of the decision variables and constraints in the mixed-integer linear optimization problem (1) from Section 4.2.1 can be removed without any loss of generality. By removing these unnecessary decision variables and constraints from the mixed-integer linear optimization problem (1), we demonstrate through numerical experiments in Online Appendix C that the computation time of each iteration of the cutting plane method can be significantly decreased.

To motivate our subsequent developments in Section 5.1, we begin by analyzing the size of the mixed-integer linear optimization problem (1). Indeed, we observe that the number of binary decision variables, the number of continuous decision variables, and the number of constraints in the mixed-integer linear optimization problem (1) are as follows:

In real-world elections such as those from Michigan, the number of contests typically satisfies $15\le C\le 40$ (Figure 4), the number of candidates typically satisfies $60\le N\le 120$ (Figure 4), the number of ballots in an optimal test deck for (RO-$\mathrm{\Sigma }$) typically satisfies $20\le B\le 50$ (see Section 6.1), and the number of iterations of our cutting plane method typically satisfies $50\le |\widehat{\mathrm{\Sigma }}|\le 300$ (see Section 6.2). Combining the equations derived above with the real-world data observed from Michigan, we conclude that the size of the mixed-integer linear optimization problem (1) is driven primarily by the binary decision variables p, the continuous decision variables y, and the constraints (1e) and (1f).

In view of the above motivation, we first show that a number of the binary decision variables $p_{b,c}^{\sigma }\in \{0,1\}$ and Constraints (1f) can be removed from the mixed-integer linear optimization problem (1) without loss of generality. Indeed, we recall from the discussion in Section 4.2.1 that there always exists an optimal solution of the mixed-integer linear optimization problem (1) in which each binary decision variable $p_{b,c}^{\sigma }$ satisfies the equality $p_{b,c}^{\sigma }=0$ if and only if contest c in ballot b is interpreted as containing an overvote by the voting machine whose mapping is $\sigma$. To decrease the number of these binary decision variables, we utilize the following intermediary result.

Lemma 1.

Let $\sigma \in \widehat{\mathrm{\Sigma }}$ and $c\in \mathcal{C}$. If the inequality ${\sum }_{c^{\prime }\in \mathcal{C}}\min \{|\{\sigma (i)\in {\mathcal{N}}_{c^{\prime }}:i\in {\mathcal{N}}_c\}|,v_{c^{\prime }}\}\le v_c$ holds, then every feasible solution of the mixed-integer linear optimization problem (1) satisfies the equality $p_{b,c}^{\sigma }=1$ for all $b\in \mathcal{B}$.

To make sense of the above lemma, we remark that ${\sum }_{c^{\prime }\in \mathcal{C}}\min \{|\{\sigma (i)\in {\mathcal{N}}_{c^{\prime }}:i\in {\mathcal{N}}_c\}|,v_{c^{\prime }}\}$ is equal to the maximum number of votes that may be mapped to contest c under mapping $\sigma$ for any filled-out ballot in $ℬ$. If this summation is less than or equal to $v_c$, then contest c will never be overvoted by a filled-out ballot from $ℬ$ under mapping $\sigma$.

In view of Lemma 1, we now demonstrate that a subset of the binary decision variables of the form $p_{b,c}^{\sigma }$ and a subset of the constraints (1f) can be removed from the mixed-integer linear optimization problem (1) without loss of generality. Indeed, for each nonidentity bijection $\sigma \in \widehat{\mathrm{\Sigma }}$, let the subset of contests that have the possibility of being overvoted under a voting machine with mapping $\sigma$ be denoted by

We observe that the subset of contests ${\widehat{\mathcal{C}}}^{\sigma }$ for each $\sigma \in \widehat{\mathrm{\Sigma }}$ can be efficiently precomputed.⁷ Using these subsets of contests, it follows immediately from Lemma 1 that Constraints (1f) and (1g) can without loss of generality be replaced by the following constraints:

In particular, we observe that the binary decision variable $p_{b,c}^{\sigma }\in \{0,1\}$ for each $\sigma \in \widehat{\mathrm{\Sigma }}$, $b\in \mathcal{B}$, and $c\in \mathcal{C}$ that satisfies $c\notin {\widehat{\mathcal{C}}}^{\sigma }$ no longer appears in the mixed-integer linear optimization problem (1) and can thus be eliminated.

Next, we show that a number of the continuous decision variables $y_{i,j}$ and Constraints (1e) can be removed from the mixed-integer linear optimization problem (1) without loss of generality. Indeed, we recall from the discussion in Section 4.2.1 that each decision variable $y_{i,j}\in {\mathbb{R}}_{\ge 0}$ will at optimality be equal to zero only if candidates $i,j\in \mathcal{N}$ do not appear in the same number of ballots. Moreover, we observe that variable $y_{i,j}$ is only referenced in the constraint (1g) by the terms $y_{i,\sigma (i)}$ for each $i\in \mathcal{N}$ and $\sigma \in \widehat{\mathrm{\Sigma }}$. Therefore, we observe that the decision variable $y_{i,j}$ only needs to be defined for the pairs of candidates $(i,j)$ in the set

and we can replace the constraint (1e) with

We conclude that the mixed-integer linear optimization problem (1) can be reduced to an optimization problem with the following number of binary decision variables, number of continuous decision variables, and number of constraints:

As we show in Online Appendix C, the above reductions in the number of decision variables and constraints lead to a significant decrease in the computation time for solving the mixed-integer linear optimization problem (1) in each iteration of the cutting plane method.

5.2. Improvement 2: Distinct Votes for Candidates in the Same Contest

As our second step in increasing the practical efficiency of the cutting plane method, we add a set of extra constraints into the mixed-integer linear optimization problem (1). These extra constraints force the mixed-integer linear optimization problem (1) to output a test deck that proactively satisfies many of the constraints $\sigma \in \mathrm{\Sigma }$ from the optimization problem (RO-$\mathrm{\Sigma }$) that were not explicitly included in subset $\widehat{\mathrm{\Sigma }}$. As we demonstrate through numerical experiments in Online Appendix C, the addition of this set of extra constraints leads to a significant decrease in the number of iterations of the cutting plane method without any meaningful increase in the computation time for solving the mixed-integer linear optimization problem (1) in each iteration.

The motivation for the set of extra constraints is given by the following Lemma 2 and Proposition 1. In Lemma 2, we establish a structural property that is satisfied by every test deck that satisfies the constraints of the optimization problem (RO-$\mathrm{\Sigma }$). Specifically, the following lemma shows that a test deck satisfies the constraints of the optimization problem (RO-$\mathrm{\Sigma }$) only if all of the candidates that appear in the same contest receive a different number of votes, where we say that two candidates $i,j\in \mathcal{N}$ appear in the same contest if there exists a contest $c\in \mathcal{C}$ that satisfies $i,j\in {\mathcal{N}}_c$.

Lemma 2.

If $(B,{\beta }_1,\dots ,{\beta }_B)$ is a feasible solution for the optimization problem (RO-$\mathrm{\Sigma }$), then $|\{b\in \{1,\dots ,B\}:i\in {\beta }_b\}|\ne |\{b\in \{1,\dots ,B\}:j\in {\beta }_b\}|$ for all candidates $i<j$ that appear in the same contest.

Equipped with the above intermediary lemma, we show in the following Proposition 1 that there always exists an optimal solution for the optimization problem (RO-$\mathrm{\Sigma }$) in which all the candidates that appear in the same contest have a strictly increasing number of votes.

Proposition 1.

There exists an optimal solution for the optimization problem (RO-$\mathrm{\Sigma }$) that satisfies $|\{b\in \{1,\dots ,B\}:i\in {\beta }_b\}|<|\{b\in \{1,\dots ,B\}:j\in {\beta }_b\}|$ for all candidates $i<j$ that appear in the same contest.

Hence, the above proposition implies that we can, without loss of generality, restrict the solution spaces of the optimization problems (RO-$\mathrm{\Sigma }$) and (RO-$\widehat{\mathrm{\Sigma }}$) by adding extra constraints that enforce that $|\{b\in \{1,\dots ,B\}:i\in {\beta }_b\}|<|\{b\in \{1,\dots ,B\}:j\in {\beta }_b\}|$ for all candidates $i<j$ that appear in the same contest.

Motivated by the structure of optimal solutions for the optimization problem (RO-$\mathrm{\Sigma }$) that is established by Proposition 1, we now describe the set of extra constraints that we add into the mixed-integer linear optimization problem (1). The purpose of this set of extra constraints is to ensure that every feasible solution $(\beta ,\gamma ,y,p)$ of the mixed-integer linear optimization problem (1) satisfies the inequality $|\{b\in \{1,\dots ,B\}:{\beta }_{b,i}=1\}|<|\{b\in \{1,\dots ,B\}:{\beta }_{b,j}=1\}|$ for all candidates $i<j$ that appear in the same contest. We accomplish this by adding the following set of extra constraints (4) into the mixed-integer linear optimization problem (1). In the following extra constraints, we use the shorthand notation ${\mathcal{N}}_c^k$ to denote the candidate with the kth smallest index among all candidates in the cth contest (with the indexing of candidates that appear in the same contest starting at index 1).

Indeed, we observe that the set of extra constraints (4) ensure that the number of votes for each candidate i is strictly less than the number of votes for candidate $j>i$ whenever candidates i and j appear in the same contest.

5.3. Improvement 3: Distinct Votes for Candidates in Similar Contests

As our third step in increasing the practical efficiency of the cutting plane method, we add a second set of extra constraints into the mixed-integer linear optimization problem (1). Similarly as Section 5.2, the set of extra constraints from the present Section 5.3 force the mixed-integer linear optimization problem (1) to output a test deck that proactively satisfies many of the constraints $\sigma \in \mathrm{\Sigma }$ from the optimization problem (RO-$\mathrm{\Sigma }$) that were not explicitly included in subset $\widehat{\mathrm{\Sigma }}$. As we demonstrate through numerical experiments in Online Appendix C, the addition of this second set of extra constraints leads to a significant decrease in the number of iterations of the cutting plane method without any meaningful increase in the computation time for solving the mixed-integer linear optimization problem (1) in each iteration.

To describe our second set of extra constraints, we require some additional terminology. We begin with the following Definition 1, which provides a way of referring to contests that are similar to one another.

Definition 1

(Equivalence of Contests). We say that two contests $c,c^{\prime }\in \mathcal{C}$ are equivalent, denoted by $c\equiv c^{\prime }$, if and only if they satisfy $|{\mathcal{N}}_c|=|{\mathcal{N}}_{c^{\prime }}|$ and $v_c=v_{c^{\prime }}$.

In other words, we say that two contests are equivalent if and only if the contests have the same number of candidates and the same maximum number of votes. Next, recall from Section 5.2 that ${\mathcal{N}}_c^k$ refers to the candidate with the kth smallest index among all candidates in contest c. Equipped with this notation, the second additional terminology, which is denoted by Definition 2, provides a way to compare the votes received by candidates in two equivalent contests.

Definition 2

(Lexicographic Ordering of Contests). We say that two contests $c,c^{\prime }\in \mathcal{C}$ are lexicographically ordered with respect to a test deck ${\beta }_1,\dots ,{\beta }_B\in ℬ$, denoted by $c{\prec }_{{\beta }_1\cdots {\beta }_B}{c}^{\prime }$, if and only if $c\equiv c^{\prime }$ and there exists $k\in \{1,\dots ,|{\mathcal{N}}_c|\}$ that satisfies

$$\begin{array}{l}|\left\{b\in \{1,\dots ,B\}:{\mathcal{N}}_c^{|{\mathcal{N}}_c|}\in {\beta }_b\right\}|\\ =|\left\{b\in \{1,\dots ,B\}:{\mathcal{N}}_{c^{\prime }}^{|{\mathcal{N}}_c|}\in {\beta }_b\right\}|\\ ⋮\\ |\left\{b\in \{1,\dots ,B\}:{\mathcal{N}}_c^{k+1}\in {\beta }_b\right\}|\\ =|\left\{b\in \{1,\dots ,B\}:{\mathcal{N}}_{c^{\prime }}^{k+1}\in {\beta }_b\right\}|\\ |\left\{b\in \{1,\dots ,B\}:{\mathcal{N}}_c^k\in {\beta }_b\right\}|\\ <|\left\{b\in \{1,\dots ,B\}:{\mathcal{N}}_{c^{\prime }}^k\in {\beta }_b\right\}|.\end{array}$$

In other words, we say that two contests are lexicographically ordered with respect to a test deck if and only if the contests are equivalent and the number of votes received by candidates in the first contest is lexicographically less than the number of votes received by candidates in the second contest, beginning with the highest-indexed candidates in the contests.

In view of the additional terminology given by Definitions 1 and 2, we now describe the second set of extra constraints that we add into the mixed-integer linear optimization problem (1). The motivation for this second set of extra constraints is given by the following Lemma 3 and Proposition 2. In Lemma 3, we establish a structural property that is satisfied by every test deck that satisfies the constraints of the optimization problem (RO-$\mathrm{\Sigma }$). Specifically, the following lemma shows that a test deck satisfies the constraints of the optimization problem (RO-$\mathrm{\Sigma }$) only if all equivalent contests are lexicographically distinct.

Lemma 3.

If $(B,{\beta }_1,\dots ,{\beta }_B)$ is a feasible solution for the optimization problem (RO-$\mathrm{\Sigma }$), then $c{\prec }_{{\beta }_1\cdots {\beta }_B}{c}^{\prime }$ or $c^{\prime }{\prec }_{{\beta }_1\cdots {\beta }_B}c$ for all contests $c<c^{\prime }$ that satisfy $c\equiv c^{\prime }$.

Equipped with the above intermediary lemma, we show in the following Proposition 2 that there always exists an optimal solution for the optimization problem (RO-$\mathrm{\Sigma }$) in which all the equivalent contests are lexicographically ordered according to the indices of the contests.

Proposition 2.

There exists an optimal solution for the optimization problem (RO-$\mathrm{\Sigma }$) that satisfies $c{\prec }_{{\beta }_1\cdots {\beta }_B}{c}^{\prime }$ for all contests $c<c^{\prime }$ that satisfy $c\equiv c^{\prime }$.

Hence, the above proposition implies that we can, without loss of generality, restrict the solution spaces of the optimization problems (RO-$\mathrm{\Sigma }$) and (RO-$\widehat{\mathrm{\Sigma }}$) by adding extra constraints that enforce that $c{\prec }_{{\beta }_1\cdots {\beta }_B}{c}^{\prime }$ for all contests $c<c^{\prime }$ that satisfy $c\equiv c^{\prime }$.

Motivated by the structure of optimal solutions for the optimization problem (RO-$\mathrm{\Sigma }$) that is established by Proposition 2, we now describe the second set of extra constraints that we add into the mixed-integer linear optimization problem (1). The purpose of this second set of extra constraints is to ensure that any feasible solution $(\beta ,\gamma ,y,p)$ of the mixed-integer linear optimization problem (1) satisfies the property that for each pair of candidates $c<c^{\prime }$ that satisfy $c\equiv c^{\prime }$, there exists a $k\in \{1,\dots ,|{\mathcal{N}}_c|\}$ that satisfies

We accomplish this by adding the following set of extra constraints (5a)–(5c) into the mixed-integer linear optimization problem (1). In the following extra constraints, we use the shorthand notation $\mathcal{I}$ to denote to the set of sequential equivalent contests,

and we use extra binary decision variables ${\lambda }_{c,c^{\prime }}^k\in \{0,1\}$ that are added to the mixed-integer linear optimization problem (1) for each $(c,c^{\prime })\in \mathcal{I}$ and $k\in \{1,\dots ,|{\mathcal{N}}_c|\}$.

Indeed, Constraints (5a) and (5b) ensure for each $(c,c^{\prime })\in \mathcal{I}$ that the equality ${\lambda }_{c,c^{\prime }}^k=1$ can be satisfied if and only if there exists $k^{\prime }\in \{k,\dots ,|{\mathcal{N}}_c|\}$ that satisfies the equality ${\sum }_{b\in \mathcal{B}}{\beta }_{b,{\mathcal{N}}_c^{k^{″}}}={\sum }_{b\in \mathcal{B}}{\beta }_{b,{\mathcal{N}}_{c^{\prime }}^{k^{″}}}$ for all $k^{″}\in \{k^{\prime }+1,\dots ,|{\mathcal{N}}_c|\}$, as well as satisfies the strict inequality ${\sum }_{b\in \mathcal{B}}{\beta }_{b,{\mathcal{N}}_c^{k^{\prime }}}<{\sum }_{b\in \mathcal{B}}{\beta }_{b,{\mathcal{N}}_{c^{\prime }}^{k^{\prime }}}$. Hence, Constraint (5c) ensures that there exists $k^{\prime }\in \{1,\dots ,|{\mathcal{N}}_c|\}$ that satisfies the equality ${\sum }_{b\in \mathcal{B}}{\beta }_{b,{\mathcal{N}}_c^{k^{″}}}={\sum }_{b\in \mathcal{B}}{\beta }_{b,{\mathcal{N}}_{c^{\prime }}^{k^{″}}}$ for all $k^{″}\in \{k^{\prime }+1,\dots ,|{\mathcal{N}}_c|\}$, as well as satisfies the strict inequality ${\sum }_{b\in \mathcal{B}}{\beta }_{b,{\mathcal{N}}_c^{k^{\prime }}}<{\sum }_{b\in \mathcal{B}}{\beta }_{b,{\mathcal{N}}_{c^{\prime }}^{k^{\prime }}}$.

5.4. Improvement 4: Heuristic for Finding Good Cuts

As our fourth step in increasing the practical efficiency of the cutting plane method, we propose a modification to the objective function of the mixed-integer linear optimization problem (2) from Section 4.2.2. The purpose of this modification is to guide the mixed-integer optimization problem (2) to choosing nonidentity bijections in each iteration that eliminate large numbers of feasible test decks from the mixed-integer linear optimization problem (1). We demonstrate through numerical experiments in Online Appendix C that the proposed modification to the objective function of the mixed-integer linear optimization problem (2) can significantly decrease the number of iterations of the cutting plane method.

To motivate our subsequent developments in Section 5.4, we begin by presenting a framework for analyzing the quality of the nonidentity bijections $\sigma \in \mathrm{\Sigma }$ that are added to the set $\widehat{\mathrm{\Sigma }}$ at the end of each iteration of the cutting plane method. Indeed, we recall that the practical efficiency of the cutting plane method from Section 4.1 depends on the number of iterations until an optimal test deck for the optimization problem (RO-$\mathrm{\Sigma }$) is obtained. The number of iterations of the cutting plane method, in turn, depends on whether the optimization problem (CUT) in each iteration of the cutting plane method yields a nonidentity bijection $\sigma \in \mathrm{\Sigma }$ that eliminates a large number of feasible test decks from the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$). Letting $ℱ(\widehat{\mathrm{\Sigma }})$ denote the set of test decks that are feasible for the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$), we will henceforth say (informally) that the optimization problem (CUT) yields a high-quality nonidentity bijection $\sigma \in \mathrm{\Sigma }$ if the set of feasible test decks in the next iteration $ℱ(\widehat{\mathrm{\Sigma }}\cup \{\sigma \})$ is much smaller than the set of feasible test decks in the current iteration $ℱ(\widehat{\mathrm{\Sigma }})$.

A priori, it might appear difficult to determine whether a nonidentity bijection $\sigma \in \mathrm{\Sigma }$ will eliminate a large number of feasible test decks from the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$). Nonetheless, we demonstrate below that high-quality nonidentity bijections $\sigma \in \mathrm{\Sigma }$ always have a structural property that we refer to as minimal. To define this structural property, consider any given nonidentity bijection $\sigma \in \mathrm{\Sigma }$, and let ${\mathcal{G}}^{\sigma }\equiv ({\mathcal{V}}^{\sigma },{ℰ}^{\sigma })$ denote the undirected graph that is generated by that nonidentity bijection. The set of vertices of this undirected graph is defined as the subset of contests that include a candidate that is swapped by the nonidentity bijection $\sigma$,

and the set of edges of this undirected graph is defined as the pairs of contests containing candidates that are swapped by the nonidentity bijection $\sigma$,

We recall from graph theory that the vertices of an undirected graph can always be partitioned into a unique collection of connected components, and we henceforth let $K^{\sigma }$ denote the number of connected components and let ${\mathcal{K}}_1^{\sigma },\dots ,{\mathcal{K}}_{K^{\sigma }}^{\sigma }\subseteq {\mathcal{V}}^{\sigma }$ denote the connected components of the undirected graph ${\mathcal{G}}^{\sigma }\equiv ({\mathcal{V}}^{\sigma },{ℰ}^{\sigma })$.⁸ Equipped with this terminology, we are ready to define the structural property of nonidentity bijections that will form the basis of our subsequent discussions.

Definition 3

(Minimal). We say that a nonidentity bijection $\sigma \in \mathrm{\Sigma }$ is minimal if and only if the number of connected components of ${\mathcal{G}}^{\sigma }\equiv ({\mathcal{V}}^{\sigma },{ℰ}^{\sigma })$ satisfies $K^{\sigma }=1$.

Figure 6 provides an illustration of Definition 3 by showing an example of a nonidentity bijection that is not minimal. Specifically, Figure 6(a) presents a nonidentity bijection $\sigma$ in a ballot style with five contests. Figure 6(b) shows the undirected graph ${\mathcal{G}}^{\sigma }\equiv ({\mathcal{V}}^{\sigma },E^{\sigma })$ corresponding to the nonidentity bijection $\sigma$. The undirected graph in Figure 6(b) has two connected components, which implies that the nonidentity bijection from Figure 6(a) is not minimal.

Our main result of Section 5.4, which is presented below as Theorem 2, establishes the significance of nonidentity bijections that are minimal. In particular, the following theorem shows that there always exists a feasible solution for the optimization problem (CUT) that is minimal. More importantly, the following Theorem 2 shows that minimal nonidentity bijections are always preferred to nonminimal nonidentity bijections from the perspective of eliminating the greatest number of feasible test decks from the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$).

Theorem 2.

Let $\sigma \in \mathrm{\Sigma }$ denote a feasible solution for the optimization problem (CUT). For each $k\in \{1,\dots ,K^{\sigma }\}$, let ${\sigma }_k:\mathcal{N}\to \mathcal{N}$ be defined for each $c\in \mathcal{C}$ and $i\in {\mathcal{N}}_c$ by

$$\begin{array}{l}{\sigma }_k(i)\triangleq \{\begin{array}{ll}\sigma (i),\hfill & \text{if}\hspace{0.17em}c\in {\mathcal{K}}_k^{\sigma },\hfill \\ i,\hfill & \text{if}\hspace{0.17em}c\notin {\mathcal{K}}_k^{\sigma }.\hfill \end{array}\hfill \end{array}$$

Then ${\sigma }_1,\dots ,{\sigma }_{K^{\sigma }}$ are feasible solutions for the optimization problem (CUT) and

$${\displaystyle \underset{k=1}{\overset{K^{\sigma }}{\cup }}\mathcal{F}}\left(\widehat{\mathrm{\Sigma }}\cup \left\{{\sigma }_k\right\}\right)=ℱ\left(\widehat{\mathrm{\Sigma }}\cup \left\{\sigma \right\}\right).$$(6)

To appreciate the significance of Theorem 2, let us make several observations. First, we observe that each nonidentity bijection ${\sigma }_k\in \mathrm{\Sigma }$ can be interpreted as a restriction of the nonidentity bijection $\sigma \in \mathrm{\Sigma }$ that only affects the candidates from contests in the connected component ${\mathcal{K}}_k^{\sigma }$. Therefore, it follows that the number of connected components in the undirected graph ${\mathcal{G}}^{{\sigma }_k}\equiv ({\mathcal{V}}^{{\sigma }_k},E^{{\sigma }_k})$ corresponding to ${\sigma }_k$ is equal to one, which implies that each of the nonidentity bijections ${\sigma }_1,\dots ,{\sigma }_{K^{\sigma }}\in \mathrm{\Sigma }$ is minimal. Second, we observe from Line (6) that the inclusion $ℱ(\widehat{\mathrm{\Sigma }}\cup \{{\sigma }_k\})\subseteq ℱ(\widehat{\mathrm{\Sigma }}\cup \{\sigma \})$ holds for each of the connected components $k\in \{1,\dots ,K^{\sigma }\}$. Hence, Theorem 2 implies that each of the nonidentity bijections ${\sigma }_1,\dots ,{\sigma }_{K^{\sigma }}$ is preferred to $\sigma$ from the perspective of eliminating feasible test decks from the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$).

Thus motivated, we now turn to the algorithmic question of how to find a minimal nonidentity bijection that is feasible for the optimization problem (CUT). In Theorem 3, we show that such a minimal nonidentity bijection can be found though making a simple modification to the objective function of the mixed-integer linear optimization problem (2).

Theorem 3.

Consider the following mixed-integer linear optimization problem:

$$\begin{array}{l}\underset{x\in {\{0,1\}}^{\mathcal{N}\times \mathcal{N}}}{\text{minimize}}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{\displaystyle \sum _{i,j\in \mathcal{N}:i\ne j}{x}_{i,j}}\\ \begin{array}{l}\text{subject} \text{to} \left(2\text{a}\right), \left(2\text{b}\right), \left(2\text{c}\right), \left(2\text{d}\right), \left(2\text{e}\right).\hfill \end{array}\end{array}$$(7)

Let $x\in {\{0,1\}}^{\mathcal{N}\times \mathcal{N}}$ be an optimal solution of the mixed-integer linear optimization problem (7), and let $\sigma :\mathcal{N}\to \mathcal{N}$ be the function that satisfies the equality $\sigma (i)=j$ if and only if $x_{i,j}=1$ for all $i,j\in \mathcal{N}$. Then $\sigma$ is a minimal nonidentity bijection that is feasible for the optimization problem (CUT).

We observe that the mixed-integer linear optimization problems (2) and (7) have the same decision variables and constraints. Hence, Theorem 3 shows that obtaining a minimal nonidentity bijection that is feasible for the optimization problem (CUT) can be achieved by simply modifying the objective function of the mixed-integer linear optimization problem (2).

5.5. Improvement 5: Combining Noncompetitive Contests

As our fifth step in increasing the practical efficiency of the cutting plane method, we show that noncompetitive contests can be combined into one without loss of generality. By combining these contests, we demonstrate through numerical experiments in Online Appendix C that the number of iterations of the cutting plane method can be significantly decreased.

We begin by introducing the terminology and notation that will be used throughout Section 5.5. Indeed, let the original ballot style be denoted by the tuple $(\mathcal{N},\mathcal{C},{\{{\mathcal{N}}_c\}}_{c\in \mathcal{C}},{\{v_c\}}_{c\in \mathcal{C}}).$ For the original ballot style, we recall from Section 3.1 that a contest $c\in \mathcal{C}$ is noncompetitive if and only if the number of candidates in the contest $|{\mathcal{N}}_c|$ is equal to the maximum number of votes $v_c$. We represent the ballot style in which all of the noncompetitive contests from the original ballot style are combined into a single contest by the tuple $(\mathcal{N},\tilde{\mathcal{C}},{\{{\tilde{\mathcal{N}}}_c\}}_{c\in \tilde{\mathcal{C}}},{\{{\tilde{v}}_c\}}_{c\in \tilde{\mathcal{C}}})$, where

We observe in the new ballot style that contest 0 denotes the contest that is constructed by combining all of the noncompetitive contests from the original ballot style. Finally, for each nonidentity bijection $\sigma \in \mathrm{\Sigma }$, let the output of a voting machine in the new ballot style whose mapping from candidates to targets is the bijection $\sigma$ be given for each candidate $i\in {\tilde{\mathcal{N}}}_c$ in each contest $c\in \tilde{\mathcal{C}}$ by

Equipped with the above notation, we now present the main result of Section 5.5. This main result, presented as Proposition 3, establishes that the set of optimal solutions for the optimization problem (RO-$\mathrm{\Sigma }$) for any given original ballot style will not change if all of the noncompetitive contests in the original ballot style are combined into a single contest.

Proposition 3.

Consider any original ballot style $(\mathcal{N},\mathcal{C},{\{{\mathcal{N}}_c\}}_{c\in \mathcal{C}},{\{v_c\}}_{c\in \mathcal{C}})$, and let the ballot style in which all the noncompetitive contests from the original ballot style are combined into a single contest be denoted by $(\mathcal{N},\tilde{\mathcal{C}},{\{{\tilde{\mathcal{N}}}_c\}}_{c\in \tilde{\mathcal{C}}},{\{{\tilde{v}}_c\}}_{c\in \tilde{\mathcal{C}}})$. Then the following equality holds for all $B\in \mathbb{N}$, ${\beta }_1,\dots ,{\beta }_B\subseteq \mathcal{N}$, $\sigma \in \mathrm{\Sigma }\cup \{*\}$, and $i\in \mathcal{N}$:

$$T_i^{\sigma }({\beta }_1,\dots ,{\beta }_B)={\tilde{T}}_i^{\sigma }({\beta }_1,\dots ,{\beta }_B).$$

We conclude Section 5.5 by discussing why combining the noncompetitive contests into a single contest can decrease the number of iterations of the cutting plane method. In essence, the value of combining the noncompetitive contests stems from the second improvement to the cutting plane method that is proposed in Section 5.2. Indeed, we recall from Section 5.2 that our second improvement to the cutting plane method consisted of adding the following set of extra constraints into the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$):

Constraints (8) ensure that the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$) in each iteration of the cutting plane method outputs a test deck in which candidates in the same contest receive a strictly increasing number of votes. In view of our recollection of the second improvement from Section 5.2, we conclude the present Section 5.5 with an example that shows that combining the noncompetitive contests into a single contest can decrease the number of iterations of the cutting plane method.

Example 1.

Consider an original ballot style consisting of two contests, where the first contest is defined by the equalities ${\mathcal{N}}_1=\{1\}$ and $v_1=1$, and the second contest is defined by the equalities ${\mathcal{N}}_2=\{2,3\}$ and $v_2=2$. We observe that each of the two contests is a noncompetitive contest.

We first analyze the number of iterations of the cutting plane method in the case where the noncompetitive contests are combined into a single contest. Indeed, if the noncompetitive contests are combined into a single contest, then we observe that the new ballot style $(\mathcal{N},\tilde{\mathcal{C}},{\{{\tilde{\mathcal{N}}}_c\}}_{c\in \tilde{\mathcal{C}}},{\{{\tilde{v}}_c\}}_{c\in \tilde{\mathcal{C}}})$ consists of a single contest, $\tilde{\mathcal{C}}=\{0\}$, wherein the candidates in that contest are given by ${\tilde{\mathcal{N}}}_0=\{1,2,3\}$ and the maximum number of votes in that contest is given by ${\tilde{v}}_0=3$. In the first iteration of the cutting plane method, we start with $\widehat{\mathrm{\Sigma }}=\varnothing$, in which the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$) with Constraints (8) can be written as

$$\begin{array}{ll}\underset{B\in \mathbb{N},{\beta }_1,\dots ,{\beta }_B\in ℬ}{\text{minimize}}\hfill & B\hfill \\ \text{subject} \text{to}\hfill & T_1^{*}({\beta }_1,\dots ,{\beta }_B)\hfill \\ \hfill & <T_2^{*}({\beta }_1,\dots ,{\beta }_B)\hfill \\ \hfill & <T_3^{*}({\beta }_1,\dots ,{\beta }_B).\hfill \end{array}$$(9)

We observe from inspection that the optimization problem (9) has two optimal solutions, which are stated as follows:

$$\begin{array}{l}(B^1,{\beta }_1^1,{\beta }_2^1)=(2,\{2,3\},\{3\}),\hfill \\ (B^2,{\beta }_1^2,{\beta }_2^2)=(2,\{3\},\{2,3\}).\hfill \end{array}$$

In particular, we observe that both of those optimal solutions are feasible solutions of the optimization problem (RO-$\mathrm{\Sigma }$). Hence, if the noncompetitive contests are combined into a single contest, then we observe for this example that the cutting plane method will terminate after a single iteration.

We conclude Example 1 by showing that the number of iterations of the cutting plane method will always be strictly greater than one if the noncompetitive contests are not combined into a single contest. Indeed, suppose that we apply the cutting plane method to the original ballot style $(\mathcal{N},\mathcal{C},{\{{\mathcal{N}}_c\}}_{c\in \mathcal{C}},{\{v_c\}}_{c\in \mathcal{C}})$. In the first iteration of the cutting plane method, we start with $\widehat{\mathrm{\Sigma }}=\varnothing$, in which the optimization problem (RO-$\widehat{\mathrm{\Sigma }}$) with Constraints (8) can be written as

$$\begin{array}{ll}\underset{B\in \mathbb{N},{\beta }_1,\dots ,{\beta }_B\in ℬ}{\text{minimize}}\hfill & B\hfill \\ \text{subject} \text{to}\hfill & T_2^{*}({\beta }_1,\dots ,{\beta }_B)<T_3^{*}({\beta }_1,\dots ,{\beta }_B).\hfill \end{array}$$(10)

We observe from inspection that the optimization problem (10) has two optimal solutions, which are stated as follows:

$$\begin{array}{l}(B^1,{\beta }_1^1)=(1,\{3\}),\hfill \\ (B^2,{\beta }_1^2)=(1,\{1,3\}).\hfill \end{array}$$

However, neither of those optimal solutions are feasible solutions for the optimization problem (RO-$\mathrm{\Sigma }$).⁹ Hence, if the noncompetitive contests are not combined into a single contest, then we observe for this example that the cutting plane method will always require at least two iterations. □

6. Numerical Experiments in Real-World Election

In partnership with the Michigan Bureau of Elections, we applied our approach to each of the state’s 6,928 ballot styles from the November 2022 general election. Through conversations with state leadership, local election officials, and vendors, we found that the ease of deploying our approach depended on two main factors: the length of the test decks with rigorous security guarantees obtained by solving our optimization problem (RO-$\mathrm{\Sigma }$) and the computation time required by our algorithm to find optimal test decks for all 6,928 ballot styles. We report below on the performance of our approach with respect to those two factors.

6.1. Length of Optimal Test Decks

The length of test decks is a crucial factor in conducting LAT in real-world elections. Long decks pose challenges, both in terms of cost and difficulty for election officials. Consequently, the practicality of our approach to achieving rigorous security guarantees in LAT depends on whether the test decks obtained by solving the optimization problem (RO-$\mathrm{\Sigma }$) are significantly longer than the heuristic-based test decks that would otherwise be used.

To evaluate the practicality of our approach in application to Michigan’s November 2022 general election, we performed the following steps. First, we calculated the lengths of optimal test decks for each of the 6,928 ballot styles by solving the optimization problem (RO-$\mathrm{\Sigma }$) once per ballot style. To comply with minimum requirements and guidance in the state of Michigan, the following rules were added as constraints into the optimization problem (RO-$\mathrm{\Sigma }$) (see Online Appendix D):

• “A different number of valid votes shall be assigned to each candidate for an office, and for and against each question” (Michigan Department of State 2019, MCL 168.798(1)).

• “None of the candidates, write-in positions, or proposals shall have an accumulated vote total of zero” (Michigan Department of State 2019, R168.773-Rule 3(10)(a)).

Second, we calculated the lengths of heuristic-based test decks for each of the 6,928 ballot styles. Our implemented heuristic involves selecting a test deck with the minimum possible length that fulfills Michigan Department of State (2019, MCL 168.798(1)) and Michigan Department of State (2019, R168.773-Rule 3(10)(a)) for each specific ballot style.¹⁰ In comparison with the optimal test decks that were obtained by solving the optimization problem (RO-$\mathrm{\Sigma }$), the heuristic-based test decks are not feasible solutions for (RO-$\mathrm{\Sigma }$) and do not offer rigorous security guarantees for any practically important class of cyberattacks. We note that the lengths of these heuristic-based test decks serve as lower bounds on the lengths of test decks that could be obtained by any heuristic that complies with Michigan Department of State (2019, MCL 168.798(1)) and Michigan Department of State (2019, R168.773-Rule 3(10)(a)).

Figure 7(a) compares the distributions of the lengths of optimal test decks and the lengths of heuristic-based test decks across the 6,928 ballot styles from Michigan’s November 2022 general election. A priori, one might have anticipated that test decks that provide rigorous security guarantees would contain significantly more ballots than the shortest test decks that satisfy a state’s minimum legal requirements. However, the numerical results of our experiments in Figure 7(a) show this is not the case. The results from Figure 7(a) for Michigan’s November 2022 general election show that the optimal test decks obtained by solving the optimization problem (RO-$\mathrm{\Sigma }$) require only 1.2% more ballots on average than the heuristic-based test decks across the 6,928 ballot styles. Moreover, the optimal test decks require the same number of ballots as the heuristic-based test decks for all but 493 of the 6,928 ballot styles. These results suggest that the rigorous security guarantees of our robust optimization approach to designing test decks can be enjoyed with essentially no additional cost or difficulty to election officials for performing LAT.

Furthermore, we find that the increases in test deck lengths in 493 of the 6,928 ballot styles can be explained by a simple mathematical formula. To present this formula, let $H^1,\dots ,H^{7928}\ge 0$ denote the lengths of the heuristic-based test decks and $O^1,\dots ,O^{7928}\ge 0$ denote the lengths of the optimal test decks. Let a noncompetitive contest refer to any contest c in a ballot style in which the maximum number of candidates that a voter is allowed to select, denoted by $v_c$, is equal to the number of candidates in the contest, denoted by $|{\mathcal{N}}_c|$. In order for a test deck to satisfy the minimum legal requirement Michigan Department of State (2019, MCL 168.798(1)), we observe the test deck must assign a different number of votes to each candidate within each noncompetitive contest. Moreover, we prove in Section 5.5 that any feasible solution of the optimization problem (RO-$\mathrm{\Sigma }$) must assign a different number of votes to each candidate across all noncompetitive contests. Letting $N{C}^1,\dots ,N{C}^{7928}$ denote the number of candidates in noncompetitive contests, where $N{C}^k=\sum _{c:|{\mathcal{N}}_c|=v_c}|{\mathcal{N}}_c|$ for each ballot style k, we show in Figure 7(b) that the formula $O^k=\max \{H^k,N{C}^k\}$ is satisfied for all ballot styles k = 1,…, 6,928. In other words, Figure 7(b) shows that the optimization problem (RO-$\mathrm{\Sigma }$) yielded test decks of an equal length to current practice for every ballot style, except for the 493 ballot styles which require longer test decks to distinguish candidates in noncompetitive contests.

Remark 5.

When imposing Michigan Department of State (2019, MCL 168.798(1)) and Michigan Department of State (2019, R168.773-Rule 3(10)(a)), we note that it is possible to construct ballot styles for which the formula $O=\max \{H,NC\}$ does not hold. For example, consider a ballot style comprised of two contests, each with two candidates and a maximum vote of one ($|{\mathcal{N}}_1|=|{\mathcal{N}}_2|=2$ and $v_1=v_2=1$). For this ballot style, there are $NC=0$ candidates in noncompetitive contests, and we observe that the heuristic-based test deck requires $H=3$ ballots. However, it follows from Section 5.3 that the optimal test deck for this ballot style will require at least $O\ge 4$ ballots. This example demonstrates that, although the formula $O^k=\max \{H^k,N{C}^k\}$ explains the lengths of optimal test decks in all 6,928 ballot styles from Michigan’s November 2022 general election, the formula is not guaranteed to hold in general.

6.2. Practical Computational Time

Because of a strict schedule for finalizing ballot styles and conducting LAT, we have found that our approach must find optimal test decks for an entire state within 24–48 hours.

To apply our approach at scale, we developed strategies for reusing optimal solutions across instances of the optimization problem (RO-$\mathrm{\Sigma }$) that corresponded to similar ballot styles, which allowed us to decrease the number of invocations of our exact algorithm from 6,928 to 376 (see Online Appendix E). Applying those strategies, our exact algorithm from Section 4 computed optimal test decks for all 6,928 ballot styles in less than seven hours on a home computer. Figure 8(a) illustrates the distribution of computation times across the 376 invocations of our algorithm, showing that 90% of the invocations required less than 2.5 minutes. These findings demonstrate that our exact algorithm from Section 4 can find optimal test decks for all the ballot styles across a state in practical computation times. Figure 8(b) displays the number of iterations and the total computation time required for each of the 376 invocations of our algorithm. The results of Figure 8(b) show that the computation time of the algorithm is driven by the number of iterations of our cutting plane method, demonstrating the value of the algorithmic developments in Section 5 that decrease the number of iterations of the cutting plane method.

7. Conclusion

This paper describes the first formal procedure for detecting cyberattacks in computerized voting machines prior to their use in elections. We achieve this by applying rigorous scientific reasoning to a widely used pre-election procedure, LAT, which for more than a century has been performed using human intuition and simple heuristics. Unlike the longstanding practice of LAT, our approach provides a guarantee that LAT will detect any misconfiguration that swaps voting targets between candidates, whether those misconfigurations were induced deliberately or by human error. Such misconfigurations have occurred accidentally in recent elections in Michigan, Pennsylvania, and Georgia. Although these errors were later caught and corrected, they generated negative publicity, hurt public confidence, and served as the basis for a draft executive order that would have instructed the military to seize voting machines nationwide. We showed in Section 2 that similar misconfigurations could be strategically induced by technically unsophisticated adversaries to undermine public trust or change the outcome of an election. By applying tools from robust optimization to LAT, this paper offers a practical and scientifically rigorous way to defend against the aforementioned risks in future elections, and demonstrates that advanced computational tools can be used to realize novel benefits to public institutions.

Through our partnership with the Michigan Bureau of Elections, we found that our approach offered valuable security guarantees with only a 1.2% average increase in the number of test ballots compared with existing testing procedure in the state’s November 2022 general election. Coupled with the practical computation time of our algorithm, we conclude that our approach to obtaining rigorous security guarantees with LAT is well suited to deployment throughout the United States. We hope that other states and countries will adopt our approach as a low-cost tool to improving the security and increasing public confidence in election outcomes.

There are many interesting directions for future work.

• First, we foresee ways that randomization can be used to generate short test decks with probabilistic security guarantees. We provide evidence in Section 6 that for states with legal requirements like Michigan’s, the benefit of using randomization to design short test decks would be minuscule. This is because the test decks produced by our deterministic approach in Michigan’s November 2022 election were only 1.2% longer on average than the shortest test decks that satisfy Michigan’s minimal legal requirements. However, randomization may be useful for designing short test decks when considering more expansive classes of uncertainty sets (i.e., uncertainty sets that go beyond incorrect bijection mappings). Randomization could also help facilitate adoption of the robust optimization approach in states that currently have weak legal requirements that must be satisfied by test decks (e.g., states that do not require every candidate within a contest to have a distinct number of votes), as election officials in such states would be accustomed to shorter test decks.

• It is straightforward to see that the length of test decks could theoretically decrease if an election official could output the vote totals after each ballot is fed into the voting machine. However, it takes significant time for the voting machine to print the poll tape (i.e., the grocery store-like receipt that the machine prints out to show the vote totals) and significant time for the election official to then reset the machine after it prints a poll tape in order for the machine to scan more ballots. From conversations with election officials, we learned that a test deck that requires more than a few poll tapes to be printed is viewed by election officials as too time consuming to perform, too different from the current practice of logic and accuracy testing, and would thus be unlikely to be followed by election officials. In view of these practical considerations, an interesting future direction would be to characterize the savings that could be obtained in test deck length if election officials were required to print the poll tape a small (but greater than one) number of times during testing.

• On the theoretical side, many open questions remain about the computational complexity of the robust optimization problem, whether it would be possible to design approximation algorithms, and if special cases of the robust optimization problem can be solved in polynomial time.