bccyan bspurple bccyan bspurple

# Improving the Security of United States Elections with Robust Optimization

Braden L. Crimmins,1 J. Alex Halderman,1 Bradley Sturt2

1Computer Science and Engineering, University of Michigan, Ann Arbor
2Information and Decision Sciences, University of Illinois Chicago

###### Abstract

For more than a century, election officials across the United States have
inspected voting machines before elections using a procedure called Logic and
Accuracy Testing (LAT). This procedure consists of election officials casting
a test deck of ballots into each voting machine and confirming the machine
produces the expected vote total for each candidate. We bring a scientific
perspective to LAT by introducing the first formal approach to designing test
decks with rigorous security guarantees. Specifically, our approach employs
robust optimization to find test decks that are guaranteed to detect any
voting machine misconfiguration that would cause votes to be swapped across
candidates. Out of all the test decks with this security guarantee, our robust
optimization problem yields the test deck with the minimum number of ballots,
thereby minimizing implementation costs for election officials. To facilitate
deployment at scale, we develop a practically efficient exact algorithm for
solving our robust optimization problems based on the cutting plane method. In
partnership with the Michigan Bureau of Elections, we retrospectively applied
our approach to all 6928 ballot styles from Michigan’s November 2022 general
election; this retrospective study reveals that the test decks with rigorous
security guarantees obtained by our approach require, on average, only 1.2%
more ballots than current practice. Our approach has since been piloted in
real-world elections by the Michigan Bureau of Elections as a low-cost way to
improve election security and increase public trust in democratic
institutions.

##  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—i.e., 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 [14]. The
erroneous vote totals announced as a result of this flaw received widespread
media coverage [8, 1], 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 [26].

  * •

Similar accidental misconfigurations affected announced election results in
Pennsylvania [10] and Georgia [12] 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.

  * •

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 [11]. 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
[22]—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 post-election interventions such as risk-limiting audits and
cryptographic systems that make announced results publicly verifiable [19, 6].
These post-election procedures are increasingly being implemented in the
United States and have received attention in popular media [23]. 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).

Figure 1:  Visualization of Logic and Accuracy Testing (LAT). Procedure is
conducted chronologically from left to right on voting machines before each
election. The modification to LAT proposed in this paper is denoted by the
white box with the text “Test deck is chosen as the solution to an
optimization problem”.

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 (see 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
[15, 27].

Figure 2:  A test deck composed of six ballots for a simple election with two
contests. The first contest is a presidential contest with three candidates;
the second contest is a senatorial contest with two candidates. In each
contest, a voter is allowed to vote for at most one candidate.

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.111Such
manipulations are sometimes called “Volkswagen attacks”, in reference to the
2015 Volkswagen emissions scandal wherein vehicle motors were programmed to
reduce their emission levels only when the vehicles were undergoing testing
for compliance with environmental efficiency regulations [9]. 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, i.e., 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
[27]. 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 LABEL:fig:latesting_simpleexample 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 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.2 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 [5, 7]. 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.222Because the contests available on a ballot
depend on granular political subdivisions like county, municipality,
legislative district, and school district, there are often many thousands of
ballot styles used across the different jurisdictions of a state in any given
election. Voting machines across the state are configured separately for each
of the different ballot styles, and a different test deck must be used to
evaluate each such configuration. 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 §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 United States
elections, the number of candidates across the contests of a ballot style is
often greater than one hundred. 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 [28]. An optimization problem that explicitly encodes
all possible swaps thus cannot be represented nor solved on any extant
computer for many real-world elections.

We contend with this computational challenge by developing an exact algorithm
inspired by the cutting plane method (see §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 of 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 §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 §4.3) 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 (§4.3.1), adding
constraints that impose the structure of optimal test decks into the mixed-
integer linear optimization problems (§4.3.2 and §4.3.3), developing a
combinatorial framework for identifying which swap to add to the relaxed
optimization problem in each iteration (§4.3.4), and combining all contests
that are not competitive (§4.3.5). In 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 6928 ballot
styles from the November 2022 general election. Our results for this election
(see §5) reveal that our approach only required a 1.2% average increase in the
number of test ballots compared to current practice across the state’s 6928
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 6928 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.

##  2 Vulnerabilities of Existing Heuristics for Designing Test Decks

Our proposed approach to designing test decks with rigorous security
guarantees is presented in §3. To motivate our approach, we begin in this
section by describing three examples of misconfiguration attacks against
United States 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.

##### 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
[17], 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
LABEL:fig:latesting_simpleexample:swap_jefferson_clay is an example of such a
swap that goes undetected, since it swaps the second candidate in the
presidential contest with the second candidate in the senatorial contest.

##### 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 [25] and environmental policy [4, 18] to recalling sitting
politicians from their office [20]. 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
[27]—then this misconfiguration would not be detected by LAT (see §4.3.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.

##### 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, then deliberately construct a test deck which would fail
to detect the modification. Indeed, we show in 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. §3.1
develops the terminology and mathematical notation that will be used
throughout the paper. §3.2 presents a general formulation of RLAT and
discusses its value from the perspective of various stakeholders in United
States elections. §3.3 uses the RLAT framework to derive our robust
optimization problem (RO-$\Sigma$) for finding a minimum-length test deck that
will detect whether a voting machine is misconfigured to swap votes between
candidates. §3.4 establishes the fundamental structural properties of test
decks that are feasible for the robust optimization problem (RO-$\Sigma$).

###  3.1 Preliminaries

A ballot style is composed of a set of contests
$\mathcal{C}\triangleq\\{1,\ldots,C\\}$ and a set of candidates
$\mathcal{N}\triangleq\\{1,\ldots,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.333Noncompetitive contests often arise when
an incumbent to some local office runs unopposed for re-election. This is
especially common in states which elect judges, since there is a strong
normative prohibition against challenging a sitting judge’s re-election bid
[24].  In real-world elections such as those from Michigan (see Figure 3), the
number of contests in each ballot style typically satisfies $15\leq C\leq 40$,
and the number of candidates in each ballot style typically satisfies $60\leq
N\leq 120$.

Figure 3: Histogram of the total number of contests (red) and total number of
candidates (blue) that appeared across the 6928 ballot styles in Michigan’s
November 2022 general election.

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,\ldots,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$. A deck refers to any finite-length sequence of filled-out ballots
$(\beta_{1},\ldots,\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},\ldots,\beta_{B})$, we denote the output of a voting machine that
operates correctly by the vector-valued function

$T^{*}(\beta_{1},\ldots,\beta_{B})\equiv(T^{*}_{1}(\beta_{1},\ldots,\beta_{B}),\ldots,T^{*}_{N}(\beta_{1},\ldots,\beta_{B})),$

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

$\displaystyle T_{i}^{*}(\beta_{1},\ldots,\beta_{B})$
$\displaystyle\triangleq\sum_{b=1}^{B}\mathbb{I}\left\\{i\in\beta_{b}\textnormal{
and }\left|\mathcal{N}_{c}\cap\beta_{b}\right|\leq v_{c}\right\\}.$

In the above definition, and throughout the rest of this paper, we let
$\mathbb{I}\left\\{\cdot\right\\}$ represent the indicator function that is
equal to one if $\cdot$ is true and is equal to zero if $\cdot$ 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
$\left|\left\\{j\in\beta_{b}:j\in\mathcal{N}_{c}\right\\}\right|\leq 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$. For
notational convenience, we denote the set of ballots that do not overvote any
contest by
$\mathscr{B}\triangleq\left\\{\beta\subseteq\mathcal{N}:\left|\mathcal{N}_{c}\cap\beta\right|\leq
v_{c}\;\forall c\in\mathcal{C}\right\\}.$

######  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},\ldots,\beta_{B}\in\mathscr{B}$, then the equality
$T^{*}_{i}(\beta_{1},\ldots,\beta_{B})=|\left\\{b\in\\{1,\ldots,B\\}:i\in\beta_{b}\right\\}|$
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

$\widehat{T}(\beta_{1},\ldots,\beta_{B})\equiv(\widehat{T}_{1}(\beta_{1},\ldots,\beta_{B}),\ldots,\widehat{T}_{N}(\beta_{1},\ldots,\beta_{B})).$

This function represents the output of the voting machine for any input deck
of filled-out ballots $(\beta_{1},\ldots,\beta_{B})$. We say that the voting
machine represented by the vector-valued function $\widehat{T}(\cdot)$ is not
operating correctly if there exists a deck $(\beta_{1},\ldots,\beta_{B})$ and
a candidate $i\in\mathcal{N}$ such that
$\widehat{T}_{i}(\beta_{1},\ldots,\beta_{B})\neq
T^{*}_{i}(\beta_{1},\ldots,\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 Robust Logic and Accuracy
Testing (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:

$\displaystyle\begin{aligned}
\underset{B\in\mathbb{N},\;\beta_{1},\ldots,\beta_{B}\in\mathscr{B}}{\textnormal{minimize}}\quad&B\\\
\textnormal{subject to}\quad&\widehat{T}(\beta_{1},\ldots,\beta_{B})\neq
T^{*}(\beta_{1},\ldots,\beta_{B})\quad\forall\widehat{T}(\cdot)\in\mathcal{U}.\end{aligned}$
(RO)

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},\ldots,\beta_{B}\in\mathscr{B}$. 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},\ldots,\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},\ldots,\beta_{B})$ will be different
from the output of a voting machine that operates correctly
$T^{*}(\beta_{1},\ldots,\beta_{B})$ whenever the voting machine
$\widehat{T}(\cdot)$ 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 §3.3. The objective of the optimization problem (RO) is
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:

##### 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.

##### 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
trade-offs for their own state or jurisdiction, and based on factors like the
known traits of the voting machines that are used in their elections. The
optimization problem (RO) can also easily integrate minimum legal requirements
on test decks that are specified by policy makers, as we elaborate in Appendix
D. Moreover, given a defined uncertainty set $\mathcal{U}$ and a test deck
$(\beta_{1},\ldots,\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 §2.

##### 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 which specifies the scope of their capabilities. This allows
for the development of security interventions which 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) [5, 7].

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 the
present §3.3 as the optimization problem (RO-$\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 [12], 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 $\Sigma$ denote the set of all non-identity
bijections of the form $\sigma:\mathcal{N}\to\mathcal{N}$, where we say that
the function $\sigma(\cdot)$ is a non-identity bijection if and only if the
function satisfies the following two criteria:

  1. 1.

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

  2. 2.

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

Each non-identity bijection can be understood as an incorrect mapping from
candidates to targets.444We note that the voting machine that operates
correctly can be represented by the identity function
$*:\mathcal{N}\to\mathcal{N}$, defined as the function that satisfies the
equality $*(i)=i$ for all $i\in\mathcal{N}$. 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

$\displaystyle
T^{\sigma}_{i}(\beta_{1},\ldots,\beta_{B})\triangleq\sum_{b=1}^{B}\mathbb{I}\left\\{\sigma(i)\in\beta_{b}\textnormal{
and
}\left|\left\\{\sigma(j)\in\beta_{b}:j\in\mathcal{N}_{c}\right\\}\right|\leq
v_{c}\right\\}.$

To make sense of the above definition, we remark that the inclusion
$\sigma(i)\in\beta_{b}$ holds if and only if the $b$-th 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
$\left|\left\\{\sigma(j)\in\beta_{b}:j\in\mathcal{N}_{c}\right\\}\right|\leq
v_{c}$ holds if and only if the $b$-th 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 non-identity bijections:

$\displaystyle\mathcal{U}\triangleq\left\\{T^{\sigma}(\cdot)\equiv(T^{\sigma}_{1}(\cdot),\ldots,T^{\sigma}_{N}(\cdot)):\sigma\in\Sigma\right\\}.$

Hence, we conclude that a test deck comprised of filled-out ballots
$\beta_{1},\ldots,\beta_{B}\in\mathscr{B}$ 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 is stated below as (RO-$\Sigma$):

$\displaystyle\begin{aligned}
\underset{B\in\mathbb{N},\;\beta_{1},\ldots,\beta_{B}\in\mathscr{B}}{\textnormal{minimize}}\quad&B\\\
\textnormal{subject to}\quad&T^{\sigma}(\beta_{1},\ldots,\beta_{B})\neq
T^{*}(\beta_{1},\ldots,\beta_{B})\quad\forall\sigma\in\Sigma.\end{aligned}$
(RO-$\Sigma$)

The subsequent §3.4 and §4 focus on developing algorithms for solving the
optimization problem (RO-$\Sigma$).

###  3.4 Discussion

We conclude §3 by characterizing the key structural properties of test decks
that satisfy the constraints of the optimization problem (RO-$\Sigma$).
Specifically, the main contribution of §3.4 is a technical result, denoted
below 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 non-identity
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},\ldots,\beta_{B}\in\mathscr{B}$ and $\sigma\in\Sigma$. Then
$T^{\sigma}(\beta_{1},\ldots,\beta_{B})\neq T^{*}(\beta_{1},\ldots,\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,\ldots,B\\}:i\in\beta_{b}\\}|\neq|\\{b\in\\{1,\ldots,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,\ldots,B\\}$ that satisfy

$\left|\left\\{\sigma(j)\in\beta_{b}:j\in\mathcal{N}_{c}\right\\}\right|>v_{c}.$

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 non-identity bijection
$\sigma\in\Sigma$ if and only if the test deck comprised of filled-out ballots
$\beta_{1},\ldots,\beta_{B}\in\mathscr{B}$ 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,\ldots,B\\}:i\in\beta_{b}\\}|$, is different from
the number of filled-out ballots that selected target $\sigma(i)$,
$|\\{b\in\\{1,\ldots,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,\ldots,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-$\Sigma$).

######  Corollary 1.

A tuple $(B,\beta_{1},\ldots,\beta_{B})$ is feasible for the optimization
problem (RO-$\Sigma$) if and only if $B\in\mathbb{N}$,
$\beta_{1},\ldots,\beta_{B}\in\mathscr{B}$, and for every $\sigma\in\Sigma$,
at least one of the following two conditions hold:

  * •

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

$|\\{b\in\\{1,\ldots,B\\}:i\in\beta_{b}\\}|\neq|\\{b\in\\{1,\ldots,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,\ldots,B\\}$ that satisfy

$\left|\left\\{\sigma(j)\in\beta_{b}:j\in\mathcal{N}_{c}\right\\}\right|>v_{c}.$

##  4 Exact Algorithm

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

###  4.1 Overview of Exact Algorithm

To begin our discussion of our exact algorithm, we recall from §1.1 that one
of the key challenges in solving the optimization problem (RO-$\Sigma$) is
that the problem contains an enormous number of constraints. Indeed, we
observe that the number of constraints in the optimization problem
(RO-$\Sigma$) is driven by the cardinality of the set of non-identity
bijections $\Sigma$, and it follows readily from §3.3 that the number of non-
identity bijections satisfies $|\Sigma|=N!-1$ for a ballot style with $N$
candidates. Because the number of candidates in real-world ballot styles often
satisfies $N\geq 100$, an optimization problem that explicitly encodes all
possible non-identity bijections thus cannot be represented nor solved on any
extant computer for many real-world elections.

To contend with the computational challenge of solving the optimization
problem (RO-$\Sigma$), we draw inspiration from an algorithmic strategy known
as the cutting plane method [16, 13]. 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-$\Sigma$) takes the form of an iterative algorithm
that is described below and visualized in Figure 4.

Figure 4: Visualization of our exact algorithm from §4.1 for solving the
optimization problem (RO-$\Sigma$).

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

$\displaystyle\begin{aligned}
\underset{B\in\mathbb{N},\;\beta_{1},\ldots,\beta_{B}\in\mathscr{B}}{\textnormal{minimize}}\quad&B\\\
\textnormal{subject to}\quad&T^{\sigma}(\beta_{1},\ldots,\beta_{B})\neq
T^{*}(\beta_{1},\ldots,\beta_{B})\quad\forall\sigma\in\widehat{\Sigma}.\end{aligned}$
(RO-$\widehat{\Sigma}$)

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

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

$\displaystyle\underset{\sigma\in\Sigma}{\textnormal{minimize}}$
$\displaystyle 0$ (CUT) subject to $\displaystyle
T^{\sigma}(\beta_{1},\ldots,\beta_{B})=T^{*}(\beta_{1},\ldots,\beta_{B}),$

where $(B,\beta_{1},\ldots,\beta_{B})$ denotes the optimal solution of the
optimization problem (RO-$\widehat{\Sigma}$). The optimization problem (CUT)
has two possible outputs. First, if the optimization problem (CUT) outputs an
optimal solution $\sigma\in\Sigma$, then we conclude that
$(B,\beta_{1},\ldots,\beta_{B})$ is not a feasible solution of the
optimization problem (RO-$\Sigma$), since the constraint
$T^{\sigma}(\beta_{1},\ldots,\beta_{B})\neq T^{*}(\beta_{1},\ldots,\beta_{B})$
in the optimization problem (RO-$\Sigma$) is violated by the test deck
$(\beta_{1},\ldots,\beta_{B})$. Second, if the optimization problem (CUT) does
not have any optimal solution, then we conclude that
$(B,\beta_{1},\ldots,\beta_{B})$ is a feasible solution for the optimization
problem (RO-$\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},\ldots,\beta_{B})$ must
be a feasible solution for the optimization problem (RO-$\Sigma$). Moreover,
since $(B,\beta_{1},\ldots,\beta_{B})$ was an optimal solution for the
optimization problem (RO-$\widehat{\Sigma}$), and since the optimization
problem (RO-$\widehat{\Sigma}$) is a relaxation of the optimization problem
(RO-$\Sigma$), it must be the case that $(B,\beta_{1},\ldots,\beta_{B})$ is
also an optimal solution for the optimization problem (RO-$\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-$\Sigma$), and the
algorithm terminates. Otherwise, if the optimization problem (CUT) outputs
$\sigma\in\Sigma$, then we conclude the current iteration by updating
$\widehat{\Sigma}\leftarrow\widehat{\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-$\Sigma$) after finitely many iterations, regardless of the choice of the
subset $\widehat{\Sigma}\subseteq\Sigma$ in the first iteration. Indeed, the
finite convergence of the algorithm follows from the fact that $\Sigma$ is a
finite set and from the fact that the optimization problem (CUT) will never
output a non-identity bijection $\sigma\in\Sigma$ that is an element of
$\widehat{\Sigma}$ when the test deck $(\beta_{1},\ldots,\beta_{B})$ satisfies
the constraints of the optimization problem (RO-$\widehat{\Sigma}$).
Therefore, the number of iterations of the algorithm is always upper bounded
by $|\Sigma|=N!-1$. In our numerical experiments throughout this paper, we
initialize $\widehat{\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{\Sigma}$)
when $|\widehat{\Sigma}|\ll|\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{\Sigma}$ remains much smaller
than the cardinality of $\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{\Sigma}$). In the subsequent §4.2 and §4.3, 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 §4.1, we are tasked with
solving the optimization problems (RO-$\widehat{\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 subsection enables the cutting plane method from §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 subsection are proposed and
analyzed in the subsequent §4.3.

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

At a high level, our procedure for solving the optimization problem
(RO-$\widehat{\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{\Sigma}$). We then solve the following
optimization problem:

$\displaystyle\begin{aligned}
\underset{\beta_{1},\ldots,\beta_{B}\in\mathscr{B}}{\textnormal{minimize}}\quad&0\\\
\textnormal{subject to}\quad&T^{\sigma}(\beta_{1},\ldots,\beta_{B})\neq
T^{*}(\beta_{1},\ldots,\beta_{B})\quad\forall\sigma\in\widehat{\Sigma}.\end{aligned}$
(RO-$\widehat{\Sigma}$-$B$)

If the optimization problem (RO-$\widehat{\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{\Sigma}$).
In that case, we update $B\leftarrow B+1$ and re-solve the optimization
problem (RO-$\widehat{\Sigma}$-$B$) with the new value for the parameter $B$.
We repeat this loop until the optimization problem (RO-$\widehat{\Sigma}$-$B$)
is feasible, at which point (RO-$\widehat{\Sigma}$-$B$) will yield an optimal
solution for the optimization problem (RO-$\widehat{\Sigma}$).

######  Remark 2.

We use the above procedure to solve the optimization problem
(RO-$\widehat{\Sigma}$) because the number of decision variables in the
optimization problem (RO-$\widehat{\Sigma}$) depends on the integer $B$, where
the integer $B$ is itself a decision variable in the optimization problem
(RO-$\widehat{\Sigma}$). In contrast, the number of decision variables in the
optimization problem (RO-$\widehat{\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{\Sigma}$-$B$) can be
reformulated as a mixed-integer linear optimization problem.

######  Remark 3.

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{\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{\Sigma}$) from the previous iteration of the cutting plane
method.555We recall that $\widehat{\Sigma}$ in the current iteration of the
cutting plane method is a superset of $\widehat{\Sigma}$ from the previous
iteration of the cutting plane method. As a result, the constraints of the
optimization problem (RO-$\widehat{\Sigma}$) in the current iteration of the
cutting plane method is always a strict superset of the constraints of the
optimization problem (RO-$\widehat{\Sigma}$) in the previous iteration of the
cutting plane method. This implies that the optimal objective value of the
optimization problem (RO-$\widehat{\Sigma}$) from the previous iteration of
the cutting plane method is always less than or equal to the optimal objective
value of the optimization problem (RO-$\widehat{\Sigma}$) in the current
iteration of the cutting plane method.

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

$\displaystyle\underset{\beta\in\\{0,1\\}^{\mathcal{B}\times\mathcal{N}}}{\textnormal{minimize}}\quad$
$\displaystyle 0$ (1a) subject to
$\displaystyle\sum_{i\in\mathcal{N}_{c}}\beta_{b,i}\leq v_{c}$
$\displaystyle\forall b\in\mathcal{B},c\in\mathcal{C}$ (1b) $\displaystyle
T^{\sigma}(\\{i:\beta_{1,i}=1\\},\ldots,\\{i:\beta_{B,i}=1\\})$
$\displaystyle\;\;\neq
T^{*}(\\{i:\beta_{1,i}=1\\},\ldots,\\{i:\beta_{B,i}=1\\})$
$\displaystyle\forall\sigma\in\widehat{\Sigma}.$ (–) 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 $b$-th filled-out ballot in the test deck. Hence, each vector
$\beta_{b}\equiv(\beta_{b,1},\ldots,\beta_{b,N})\in\\{0,1\\}^{\mathcal{N}}$
serves as a binary encoding of the targets that are selected in the $b$-th
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
(– ‣ 1) says that the output of a voting machine whose mapping from candidates
to targets is $\sigma\in\widehat{\Sigma}$ must be different from the output of
a correctly operating voting machine when using the test deck
$(\\{i:\beta_{1,i}=1\\},\ldots,\\{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{\Sigma}$-$B$) as a mixed-integer linear optimization problem is
to reformulate the constraint (– ‣ 1). This can be done through the
introduction of new decision variables $\gamma$, $y$, and $p$, resulting in
the following mixed-integer linear optimization problem:

$\displaystyle\underset{\begin{subarray}{c}\beta\in\\{0,1\\}^{\mathcal{B}\times\mathcal{N}}\\\
\gamma\in\\{0,1\\}^{\mathcal{N}\times\mathcal{B}_{0}},\;y\in\mathbb{R}_{\geq
0}^{\mathcal{N}\times\mathcal{N}}\\\
p^{\sigma}\in\\{0,1\\}^{\mathcal{B}\times\mathcal{C}}\forall\sigma\in\widehat{\Sigma}\end{subarray}}{\textnormal{minimize}}\quad$
$\displaystyle\eqref{prob:complete_transposition:obj}$ subject to
$\displaystyle\eqref{prob:complete_transposition:beta_feas}$
$\displaystyle\sum_{g\in\mathcal{B}_{0}}\gamma_{i,g}=1$ $\displaystyle\forall
i\in\mathcal{N}$ (1c)
$\displaystyle\sum_{b\in\mathcal{B}}\beta_{b,i}=\sum_{g\in\mathcal{B}_{0}}g\gamma_{i,g}$
$\displaystyle\forall i\in\mathcal{N}$ (1d) $\displaystyle
y_{i,j}\geq-1+\gamma_{i,g}+\gamma_{j,g}$ $\displaystyle\forall
i,j\in\mathcal{N},g\in\mathcal{B}_{0}$ (1e) $\displaystyle
p^{\sigma}_{b,c}\geq
1-\frac{1}{v_{c}+1}\sum_{i\in\mathcal{N}_{c}}\beta_{b,\sigma(i)}$
$\displaystyle\forall\sigma\in\widehat{\Sigma},b\in\mathcal{B},c\in\mathcal{C}$
(1f)
$\displaystyle\sum_{i\in\mathcal{N}}\left(1-y_{i,\sigma(i)}\right)+\sum_{b\in\mathcal{B}}\sum_{c\in\mathcal{C}}\left(1-p^{\sigma}_{b,c}\right)\geq
1$ $\displaystyle\forall\sigma\in\widehat{\Sigma}.$ (1g)

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, constraints
(1e) and (1g) together imply that we can assume without loss of generality
that each decision variable $y_{i,j}\in\mathbb{R}_{\geq 0}$ will be equal to
one if candidates $i$ and $j$ appear in the same number of ballots and will be
equal to zero if candidates $i$ and $j$ appear in a different number of
ballots. Finally, constraints (1f) and (1g) together imply that we can assume
without loss of generality that each decision variable
$p^{\sigma}_{b,c}\in\\{0,1\\}$ will be equal to one if a voting machine whose
mapping is $\sigma\in\widehat{\Sigma}$ interprets the filled-out ballot
$\\{i:\beta_{b,i}=1\\}$ as containing $v_{c}$ or fewer votes in contest $c$
and will be equal to zero if that same machine interprets the ballot as
containing an overvote in contest $c$. In other words, we can assume without
loss of generality that each binary decision variable $p^{\sigma}_{b,c}$ will
be equal to zero if and only if
$\sum_{i\in\mathcal{N}_{c}}\beta_{b,\sigma(i)}>v_{c}.$

To make sense of constraint (1g), let us make several observations under the
aforementioned assumptions on the decision variables $y$ and $p$. First, we
observe that the inequality
$\sum_{i\in\mathcal{N}}\left(1-y_{i,\sigma(i)}\right)$ $\geq 1$ will hold if
and only if the voting machine with mapping $\sigma\in\widehat{\Sigma}$ is
swapping the targets of candidates that received different numbers of votes in
the test deck. Second, we observe that the inequality
$\sum_{b\in\mathcal{B}}\sum_{c\in\mathcal{C}}(1-p^{\sigma}_{b,c})\geq 1$ holds
if and only if there exists at least one contest in at least one ballot that
is interpreted as containing an overvote by the voting machine whose mapping
is $\sigma\in\widehat{\Sigma}$. Combining those two observations, we conclude
that constraint (1g) enforces for each mapping $\sigma\in\widehat{\Sigma}$
that a voting machine with the mapping $\sigma$ gives an incorrect output
using the test deck $(\\{i:\beta_{1,i}=1\\},\ldots,\\{i:\beta_{B,i}=1\\})$.

In summary, we have shown in the present §4.2.1 that the optimization problem
(RO-$\widehat{\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{\Sigma}$) and then incrementing $B$ until
the optimization problem (RO-$\widehat{\Sigma}$-$B$) has a feasible solution.
Moreover, for each fixed choice of the integer $B$, we showed that the
optimization problem (RO-$\widehat{\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{\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 §4.2 by reformulating the optimization problem (CUT) as a mixed-
integer linear optimization problem.666More precisely, our reformulation (2)
of the optimization problem (CUT) is a _binary_ linear optimization problem.
Given any test deck $(\beta_{1},\ldots,\beta_{B})$, our mixed-integer linear
optimization reformulation of the optimization problem (CUT) is the following:

$\displaystyle\underset{x\in\\{0,1\\}^{\mathcal{N}\times\mathcal{N}}}{\textnormal{minimize}}\quad\quad$
$\displaystyle 0$ subject to $\displaystyle\sum_{j\in\mathcal{N}}x_{i,j}=1$
$\displaystyle\forall i\in\mathcal{N}$ (2a)
$\displaystyle\sum_{i\in\mathcal{N}}x_{i,j}=1$ $\displaystyle\forall
j\in\mathcal{N}$ (2b)
$\displaystyle\sum_{i\in\mathcal{N}}x_{i,i}\leq|\mathcal{N}|-2$ (2c)
$\displaystyle\sum_{i\in\mathcal{N}_{c}}\sum_{j\in\beta_{b}}x_{i,j}\leq v_{c}$
$\displaystyle\forall b\in\mathcal{B},c\in\mathcal{C}$ (2d) $\displaystyle
x_{i,j}=0$ $\displaystyle\forall
i,j\in\mathcal{N}:\;\left|\left\\{b\in\mathcal{B}:i\in\beta_{b}\right\\}\right|\neq\left|\left\\{b\in\mathcal{B}:j\in\beta_{b}\right\\}\right|.$
(2e)

The constraints (2a)-(2c) enforce that the decision variables
$x\in\\{0,1\\}^{\mathcal{N}\times\mathcal{N}}$ are a binary encoding of a non-
identity bijection $\sigma\in\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)\neq i$.

The last two constraints (2d) and (2e) enforce that the non-identity bijection
$\sigma\in\Sigma$ corresponding to the decision variables
$x\in\\{0,1\\}^{\mathcal{N}\times\mathcal{N}}$ satisfies the equality
$T^{\sigma}(\beta_{1},\ldots,\beta_{B})=T^{*}(\beta_{1},\ldots,\beta_{B})$. To
see why this is the case, we first observe that constraint (2d) enforces that
the inequality
$\left|\left\\{\sigma(j)\in\beta_{b}:j\in\mathcal{N}_{c}\right\\}\right|\leq
v_{c}$ holds for all contests $c\in\mathcal{C}$ and $b\in\mathcal{B}$.
Moreover, constraint (2d) enforces that the equality
$|\\{b\in\\{1,\ldots,B\\}:i\in\beta_{b}\\}|=|\\{b\in\\{1,\ldots,B\\}:\sigma(i)\in\beta_{b}\\}|$
holds for all candidates $i\in\mathcal{N}$. Therefore, it follows from Theorem
1 in §3.4 that constraints (2d) and (2e) are satisfied if and only if the non-
identity bijection $\sigma\in\Sigma$ corresponding to the decision variables
$x\in\\{0,1\\}^{\mathcal{N}\times\mathcal{N}}$ satisfies the equality
$T^{\sigma}(\beta_{1},\ldots,\beta_{B})=T^{*}(\beta_{1},\ldots,\beta_{B})$.

###  4.3 Improvements to Exact Algorithm

In this subsection, we present five improvements to the mixed-integer linear
optimization reformulations from §4.2 that significantly increase the
practical efficiency of the cutting plane method from §4.1. Our five
improvements to the mixed-integer linear optimization reformulations are
presented and analyzed in the subsequent §4.3.1-§4.3.5. In Appendix C, we
demonstrate the practical value of each of the five improvements through
numerical experiments on synthetic elections.

####  4.3.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 §4.1, we show that a number of the decision variables and
constraints in the mixed-integer linear optimization problem (1) from §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 Appendix C that
the computation time of each iteration of the cutting plane method can be
significantly decreased.

To motivate our subsequent developments in §4.3.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:

$\displaystyle\begin{aligned} \text{\\# binary decision
variables}=&\underbrace{\left(|\mathcal{B}|\times|\mathcal{N}|\right)}_{\beta}+\underbrace{\left(|\mathcal{B}_{0}|\times|\mathcal{N}|\right)}_{\gamma}+\underbrace{\left(|\mathcal{B}|\times|\mathcal{C}|\times|\widehat{\Sigma}|\right)}_{p}\\\
=&BN+(B+1)N+BC|\widehat{\Sigma}|\\\
=&\mathcal{O}\left(BN+BC|\widehat{\Sigma}|\right);\end{aligned}$
$\displaystyle\begin{aligned} \text{\\# continuous decision
variables}&=\underbrace{|\mathcal{N}|\times|\mathcal{N}|}_{y}\\\
&=N^{2};\end{aligned}$ $\displaystyle\begin{aligned} \text{\\#
constraints}=&\underbrace{\left(|\mathcal{B}|\times|\mathcal{C}|\right)}_{\eqref{prob:complete_transposition:beta_feas}}+\underbrace{|\mathcal{N}|}_{\eqref{prob:complete_transposition:gamma_1}}+\underbrace{|\mathcal{N}|}_{\eqref{prob:complete_transposition:gamma_2}}+\underbrace{\left(|\mathcal{N}|\times|\mathcal{N}|\times|\mathcal{B}_{0}|\right)}_{\eqref{prob:complete_transposition:y}}+\underbrace{\left(|\mathcal{B}|\times|\mathcal{C}|\times\left|\widehat{\Sigma}\right|\right)}_{\eqref{prob:complete_transposition:p}}+\underbrace{|\widehat{\Sigma}|}_{\eqref{prob:complete_transposition:defeated}}\\\
=&BC+2N+N^{2}(B+1)+BC|\widehat{\Sigma}|+|\widehat{\Sigma}|\\\
=&\mathcal{O}\left(BN^{2}+BC|\widehat{\Sigma}|\right).\end{aligned}$

In real-world elections such as those from Michigan, the number of contests
typically satisfies $15\leq C\leq 40$ (see Figure 3 in §3.1), the number of
candidates typically satisfies $60\leq N\leq 120$ (see Figure 3 in §3.1), the
number of ballots in an optimal test deck for (RO-$\Sigma$) typically
satisfies $20\leq B\leq 50$ (see Figure LABEL:fig:michigan in §5.1), and the
number of iterations of our cutting plane method typically satisfies
$50\leq|\widehat{\Sigma}|\leq 300$ (see Figure LABEL:fig:time_vs_iteration in
§5.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^{\sigma}_{b,c}\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 §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^{\sigma}_{b,c}$ satisfies the
equality $p^{\sigma}_{b,c}=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{\Sigma}$ and $c\in\mathcal{C}$. If the inequality
$\sum_{c^{\prime}\in\mathcal{C}}\min\left\\{\left|\left\\{\sigma(i)\in\mathcal{N}_{c^{\prime}}:i\in\mathcal{N}_{c}\right\\}\right|,v_{c^{\prime}}\right\\}\leq
v_{c}$ holds, then every feasible solution of the mixed-integer linear
optimization problem (1) satisfies the equality $p^{\sigma}_{b,c}=1$ for all
$b\in\mathcal{B}$.

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

In view of Lemma 1, we now demonstrate that a subset of the binary decision
variables of the form $p^{\sigma}_{b,c}$ 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 non-identity bijection
$\sigma\in\widehat{\Sigma}$, let the subset of contests that have the
possibility of being overvoted under a voting machine with mapping $\sigma$ be
denoted by

$\displaystyle\widehat{\mathcal{C}}^{\sigma}\triangleq\left\\{c\in\mathcal{C}:\;\sum_{c^{\prime}\in\mathcal{C}}\min\left\\{\left|\left\\{\sigma(i)\in\mathcal{N}_{c^{\prime}}:i\in\mathcal{N}_{c}\right\\}\right|,v_{c^{\prime}}\right\\}\geq
v_{c}+1\right\\}.$

We observe that the subset of contests $\widehat{\mathcal{C}}^{\sigma}$ for
each $\sigma\in\widehat{\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:

$\displaystyle p^{\sigma}_{b,c}\geq
1-\frac{1}{v_{c}+1}\sum_{i\in\mathcal{N}_{c}}\beta_{b,\sigma(i)}$
$\displaystyle\forall\sigma\in\widehat{\Sigma},b\in\mathcal{B},c\in\widehat{\mathcal{C}}^{\sigma}$
(3a)
$\displaystyle\sum_{i\in\mathcal{N}}\left(1-y_{i,\sigma(i)}\right)+\sum_{b\in\mathcal{B}}\sum_{c\in\widehat{\mathcal{C}}^{\sigma}}\left(1-p^{\sigma}_{b,c}\right)\geq
1$ $\displaystyle\forall\sigma\in\widehat{\Sigma}.$ (3b) In particular, we
observe that the binary decision variable $p^{\sigma}_{b,c}\in\\{0,1\\}$ for
each $\sigma\in\widehat{\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 §4.2.1 that each decision variable $y_{i,j}\in\mathbb{R}_{\geq 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{\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

$\displaystyle\mathcal{P}(\widehat{\Sigma})\triangleq\left\\{(i,j)\in\mathcal{N}^{2}:i\neq
j\textnormal{ and there exists }\sigma\in\widehat{\Sigma}\textnormal{ that
satisfies }\sigma(i)=j\right\\},$

and we can replace the constraint (1e) with

$\displaystyle y_{i,j}\geq-1+\gamma_{i,g}+\gamma_{j,g}$
$\displaystyle\forall(i,j)\in\mathcal{P}(\widehat{\Sigma}),g\in\mathcal{B}_{0}.$
(3c)

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:

$\displaystyle\begin{aligned} \text{\\# binary decision
variables}=&\underbrace{\left(|\mathcal{B}|\times|\mathcal{N}|\right)}_{\beta}+\underbrace{\left(|\mathcal{B}_{0}|\times|\mathcal{N}|\right)}_{\gamma}+\underbrace{\left(|\mathcal{B}|\times\sum_{\sigma\in\widehat{\Sigma}}\left|\widehat{\mathcal{C}}^{\sigma}\right|\right)}_{p}\\\
=&BN+(B+1)N+B\sum_{\sigma\in\widehat{\Sigma}}\left|\widehat{\mathcal{C}}^{\sigma}\right|\\\
=&\mathcal{O}\left(BN+B\sum_{\sigma\in\widehat{\Sigma}}\left|\widehat{\mathcal{C}}^{\sigma}\right|\right);\end{aligned}$
$\displaystyle\begin{aligned} \text{\\# continuous decision
variables}=&\underbrace{|\mathcal{P}(\widehat{\Sigma})|}_{y};\end{aligned}$
$\displaystyle\begin{aligned} \text{\\#
constraints}=&\underbrace{\left(|\mathcal{B}|\times|\mathcal{C}|\right)}_{\eqref{prob:complete_transposition:beta_feas}}+\underbrace{|\mathcal{N}|}_{\eqref{prob:complete_transposition:gamma_1}}+\underbrace{|\mathcal{N}|}_{\eqref{prob:complete_transposition:gamma_2}}+\underbrace{\left(|\mathcal{B}|\times\sum_{\sigma\in\widehat{\Sigma}}\left|\widehat{\mathcal{C}}^{\sigma}\right|\right)}_{\eqref{prob:reduced_variables:p}}+\underbrace{|\widehat{\Sigma}|}_{\eqref{prob:reduced_variables:defeated}}+\underbrace{\left(|\mathcal{P}(\widehat{\Sigma})|\times|\mathcal{B}_{0}|\right)}_{\eqref{prob:reduced_variables:y}}\\\
=&BN+BC+2N+B\sum_{\sigma\in\widehat{\Sigma}}\left|\widehat{\mathcal{C}}^{\sigma}\right|+|\widehat{\Sigma}|+|\mathcal{P}(\widehat{\Sigma})|(B+1)\\\
=&\mathcal{O}\left(B|\mathcal{P}(\widehat{\Sigma})|+B\sum_{\sigma\in\widehat{\Sigma}}\left|\widehat{\mathcal{C}}^{\sigma}\right|\right).\end{aligned}$

As we show in 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.

####  4.3.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\Sigma$ from the optimization
problem (RO-$\Sigma$) that were not explicitly included in subset
$\widehat{\Sigma}$. As we demonstrate through numerical experiments in
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-$\Sigma$). Specifically, the following lemma shows
that a test deck satisfies the constraints of the optimization problem
(RO-$\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},\ldots,\beta_{B})$ is a feasible solution for the
optimization problem (RO-$\Sigma$), then
$|\\{b\in\\{1,\ldots,B\\}:i\in\beta_{b}\\}|\neq|\\{b\in\\{1,\ldots,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-$\Sigma$) in which all of 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-$\Sigma$)
that satisfies
$|\\{b\in\\{1,\ldots,B\\}:i\in\beta_{b}\\}|<|\\{b\in\\{1,\ldots,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-$\Sigma$) and
(RO-$\widehat{\Sigma}$) by adding extra constraints which enforce that
$|\\{b\in\\{1,\ldots,B\\}:i\in\beta_{b}\\}|<|\\{b\in\\{1,\ldots,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-$\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

$\displaystyle|\\{b\in\\{1,\ldots,B\\}:\beta_{b,i}=1\\}|<|\\{b\in\\{1,\ldots,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
$k$th smallest index among all candidates in the $c$th contest (with the
indexing of candidates that appear in the same contest starting at index 1).

$\displaystyle\sum_{b\in\mathcal{B}}\left(\beta_{b,\mathcal{N}^{k+1}_{c}}-\beta_{b,\mathcal{N}^{k}_{c}}\right)\geq
1\quad\forall c\in\mathcal{C}\text{ and
}k\in\\{1,\ldots,|\mathcal{N}_{c}|-1\\}.$ (4)

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.

####  4.3.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 §4.3.2, the set of extra constraints
from the present §4.3.3 force the mixed-integer linear optimization problem
(1) to output a test deck that proactively satisfies many of the constraints
$\sigma\in\Sigma$ from the optimization problem (RO-$\Sigma$) that were not
explicitly included in subset $\widehat{\Sigma}$. As we demonstrate through
numerical experiments in 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 §4.3.2 that $\mathcal{N}^{k}_{c}$ refers to the
candidate with the $k$th smallest index among all candidates in contest $c$.
Equipped with this notation, the second additional terminology, which is
denoted below 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},\ldots,\beta_{B}\in\mathscr{B}$, 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,\ldots,|\mathcal{N}_{c}|\\}$ that
satisfies

$\displaystyle\left|\left\\{b\in\\{1,\ldots,B\\}:\mathcal{N}^{|\mathcal{N}_{c}|}_{c}\in\beta_{b}\right\\}\right|=\left|\left\\{b\in\\{1,\ldots,B\\}:\mathcal{N}^{|\mathcal{N}_{c}|}_{c^{\prime}}\in\beta_{b}\right\\}\right|$
$\displaystyle\vdots$
$\displaystyle\left|\left\\{b\in\\{1,\ldots,B\\}:\mathcal{N}^{k+1}_{c}\in\beta_{b}\right\\}\right|=\left|\left\\{b\in\\{1,\ldots,B\\}:\mathcal{N}^{k+1}_{c^{\prime}}\in\beta_{b}\right\\}\right|$
$\displaystyle\left|\left\\{b\in\\{1,\ldots,B\\}:\mathcal{N}^{k}_{c}\in\beta_{b}\right\\}\right|<\left|\left\\{b\in\\{1,\ldots,B\\}:\mathcal{N}^{k}_{c^{\prime}}\in\beta_{b}\right\\}\right|.$

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-$\Sigma$).
Specifically, the following lemma shows that a test deck satisfies the
constraints of the optimization problem (RO-$\Sigma$) only if all equivalent
contests are lexicographically distinct.

######  Lemma 3.

If $(B,\beta_{1},\ldots,\beta_{B})$ is a feasible solution for the
optimization problem (RO-$\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-$\Sigma$) in which all of 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-$\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-$\Sigma$) and
(RO-$\widehat{\Sigma}$) by adding extra constraints which 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-$\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,\ldots,|\mathcal{N}_{c}|\\}$ that satisfies

$\displaystyle\left|\left\\{b\in\\{1,\ldots,B\\}:\beta_{b,\mathcal{N}^{|\mathcal{N}_{c}|}_{c}}=1\right\\}\right|=\left|\left\\{b\in\\{1,\ldots,B\\}:\beta_{b,\mathcal{N}^{|\mathcal{N}_{c}|}_{c^{\prime}}}=1\right\\}\right|$
$\displaystyle\vdots$
$\displaystyle\left|\left\\{b\in\\{1,\ldots,B\\}:\beta_{b,\mathcal{N}^{k+1}_{c}}=1\right\\}\right|=\left|\left\\{b\in\\{1,\ldots,B\\}:\beta_{b,\mathcal{N}^{k+1}_{c^{\prime}}}=1\right\\}\right|$
$\displaystyle\left|\left\\{b\in\\{1,\ldots,B\\}:\beta_{b,\mathcal{N}^{k}_{c}}=1\right\\}\right|<\left|\left\\{b\in\\{1,\ldots,B\\}:\beta_{b,\mathcal{N}^{k}_{c^{\prime}}}=1\right\\}\right|.$

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,

$\mathcal{I}\triangleq\left\\{(c,c^{\prime})\in\mathcal{C}\times\mathcal{C}:\quad\begin{aligned}
&c<c^{\prime},\;c\equiv c^{\prime},\textnormal{ and there does not exist a}\\\
&\textnormal{contest
}\bar{c}\in\left\\{c+1,\ldots,c^{\prime}-1\right\\}\textnormal{ that satisfies
}c\equiv\bar{c}\end{aligned}\right\\},$

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

$\displaystyle\lambda_{c,c^{\prime}}^{|\mathcal{N}_{c}|}$
$\displaystyle\leq\sum_{b\in\mathcal{B}}\beta_{b,\mathcal{N}^{k}_{c^{\prime}}}-\sum_{b\in\mathcal{B}}\beta_{b,\mathcal{N}^{k}_{c}}$
$\displaystyle\forall(c,c^{\prime})\in\mathcal{I}$ (5a)
$\displaystyle\lambda_{c,c^{\prime}}^{k}$ $\displaystyle\leq
B\lambda_{c,c^{\prime}}^{k+1}+\sum_{b\in\mathcal{B}}\beta_{b,\mathcal{N}^{k}_{c^{\prime}}}-\sum_{b\in\mathcal{B}}\beta_{b,\mathcal{N}^{k}_{c}}$
$\displaystyle\forall(c,c^{\prime})\in\mathcal{I},\;k\in\left\\{1,\ldots,|\mathcal{N}_{c}|-1\right\\}$
(5b) $\displaystyle\lambda_{c,c^{\prime}}^{1}$ $\displaystyle=1$
$\displaystyle\forall(c,c^{\prime})\in\mathcal{I}.$ (5c)

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

####  4.3.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 §4.2.2. The purpose of this
modification is to guide the mixed-integer optimization problem (2) to
choosing non-identity 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 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 §4.3.4, we begin by presenting a
framework for analyzing the quality of the non-identity bijections
$\sigma\in\Sigma$ that are added to the set $\widehat{\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 §4.1 depends on the
number of iterations until an optimal test deck for the optimization problem
(RO-$\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 non-identity bijection
$\sigma\in\Sigma$ that eliminates a large number of feasible test decks from
the optimization problem (RO-$\widehat{\Sigma}$). Letting
$\mathscr{F}(\widehat{\Sigma})$ denote the set of test decks that are feasible
for the optimization problem (RO-$\widehat{\Sigma}$), we will henceforth say
(informally) that the optimization problem (CUT) yields a high-quality non-
identity bijection $\sigma\in\Sigma$ if the set of feasible test decks in the
next iteration $\mathscr{F}(\widehat{\Sigma}\cup\\{\sigma\\})$ is much smaller
than the set of feasible test decks in the current iteration
$\mathscr{F}(\widehat{\Sigma})$.

A priori, it might appear difficult to determine whether a non-identity
bijection $\sigma\in\Sigma$ will eliminate a large number of feasible test
decks from the optimization problem (RO-$\widehat{\Sigma}$). Nonetheless, we
demonstrate below that high-quality non-identity bijections $\sigma\in\Sigma$
always have a structural property that we refer to as _minimal_. To define
this structural property, consider any given non-identity bijection
$\sigma\in\Sigma$, and let
$\mathscr{G}^{\sigma}\equiv(\mathscr{V}^{\sigma},\mathscr{E}^{\sigma})$ denote
the undirected graph that is generated by that non-identity 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 non-identity bijection $\sigma$,

$\displaystyle\mathscr{V}^{\sigma}\triangleq\left\\{c\in\mathcal{C}:\textnormal{
there exists }i\in\mathcal{N}_{c}\textnormal{ that satisfies }\sigma(i)\neq
i\right\\},$

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

$\displaystyle\mathscr{E}^{\sigma}\triangleq\left\\{(c,c^{\prime})\in\mathcal{C}\times\mathcal{C}:\begin{gathered}\textnormal{
there exist }i\in\mathcal{N}_{c}\textnormal{ and
}i^{\prime}\in\mathcal{N}_{c^{\prime}}\textnormal{ that satisfy the}\\\
\textnormal{equality }\sigma(i)=i^{\prime}\textnormal{ or satisfy the equality
}\sigma(i^{\prime})=i\end{gathered}\right\\}.$

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
$\mathscr{K}^{\sigma}_{1},\ldots,\mathscr{K}^{\sigma}_{K^{\sigma}}\subseteq\mathscr{V}^{\sigma}$
denote the connected components of the undirected graph
$\mathscr{G}^{\sigma}\equiv(\mathscr{V}^{\sigma},\mathscr{E}^{\sigma})$.777It
is a straightforward exercise to show that
$\mathscr{K}^{\sigma}_{1},\ldots,\mathscr{K}^{\sigma}_{K^{\sigma}}\subseteq\mathscr{V}^{\sigma}$
are the connected components of the undirected graph
$\mathscr{G}^{\sigma}\equiv(\mathscr{V}^{\sigma},\mathscr{E}^{\sigma})$ if and
only if (1)
$\mathscr{K}^{\sigma}_{1},\ldots,\mathscr{K}^{\sigma}_{K^{\sigma}}$ are
disjoint, (2) the union of
$\mathscr{K}^{\sigma}_{1},\ldots,\mathscr{K}^{\sigma}_{K^{\sigma}}$ is equal
to $\mathscr{V}^{\sigma}$, and (3) $(c,c^{\prime})\in\mathscr{E}^{\sigma}$
implies that there exists $k\in\\{1,\ldots,|K^{\sigma}|\\}$ that satisfies
$c,c^{\prime}\in\mathscr{K}^{\sigma}_{k}$.  Equipped with this terminology, we
are ready to define the structural property of non-identity bijections that
will form the basis of our subsequent discussions:

######  Definition 3 (Minimal).

We say that a non-identity bijection $\sigma\in\Sigma$ is minimal if and only
if the number of connected components of
$\mathscr{G}^{\sigma}\equiv(\mathscr{V}^{\sigma},\mathscr{E}^{\sigma})$
satisfies $K^{\sigma}=1$.

Our main result of §4.3.4, which is presented below as Theorem 2, establishes
the significance of non-identity 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 non-identity bijections are always
preferred to non-minimal non-identity bijections from the perspective of
eliminating the greatest number of feasible test decks from the optimization
problem (RO-$\widehat{\Sigma}$).

######  Theorem 2.

Let $\sigma\in\Sigma$ denote a feasible solution for the optimization problem
(CUT). For each $k\in\\{1,\ldots,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

$\displaystyle\sigma_{k}(i)$
$\displaystyle\triangleq\begin{cases}\sigma(i),&\textnormal{if
}c\in\mathscr{K}^{\sigma}_{k},\\\ i,&\textnormal{if
}c\notin\mathscr{K}^{\sigma}_{k}.\end{cases}$

Then $\sigma_{1},\ldots,\sigma_{K^{\sigma}}$ are feasible solutions for the
optimization problem (CUT) and

$\displaystyle\bigcup_{k=1}^{K^{\sigma}}\mathscr{F}\left(\widehat{\Sigma}\cup\\{\sigma_{k}\\}\right)=\mathscr{F}\left(\widehat{\Sigma}\cup\\{\sigma\\}\right).$
(6)

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

Thus motivated, we now turn to the algorithmic question of how to find a
minimal non-identity bijection that is feasible for the optimization problem
(CUT). In the following Theorem 3, we show that such a minimal non-identity
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:

$\displaystyle\underset{x\in\\{0,1\\}^{\mathcal{N}\times\mathcal{N}}}{\textnormal{minimize}}$
$\displaystyle\sum_{i,j\in\mathcal{N}:i\neq j}x_{i,j}$ (7) subject to
$\displaystyle\eqref{prob:oracle_mip:bijective_1},\eqref{prob:oracle_mip:bijective_2},\eqref{prob:oracle_mip:dishonest},\eqref{prob:oracle_mip:overvote},\eqref{prob:oracle_mip:vote_total}.$

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 non-identity 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 non-identity 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).

####  4.3.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 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 §4.3.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 §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}},\widetilde{\mathcal{C}},\\{\widetilde{\mathcal{N}}_{c}\\}_{c\in\widetilde{\mathcal{C}}},\\{\widetilde{v}_{c}\\}_{c\in\widetilde{\mathcal{C}}})$,
where

$\displaystyle\widetilde{\mathcal{C}}$
$\displaystyle\triangleq\\{0\\}\cup\left\\{c\in\mathcal{C}:|\mathcal{N}_{c}|>v_{c}\right\\};$
$\displaystyle\widetilde{\mathcal{N}}_{c}$
$\displaystyle\triangleq\begin{cases}\mathcal{N}_{c},&\text{if }c\neq 0,\\\
\bigcup\limits_{c^{\prime}\in\mathcal{C}:|\mathcal{N}_{c^{\prime}}|=v_{c^{\prime}}}\mathcal{N}_{c^{\prime}},&\text{if
}c=0;\end{cases}$ $\displaystyle\widetilde{v}_{c}$
$\displaystyle\triangleq\begin{cases}v_{c},&\text{if }c\neq 0,\\\
\left|\bigcup\limits_{c^{\prime}\in\mathcal{C}:|\mathcal{N}_{c^{\prime}}|=v_{c^{\prime}}}\mathcal{N}_{c^{\prime}}\right|,&\text{if
}c=0.\end{cases}$

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 non-identity bijection
$\sigma\in\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\widetilde{\mathcal{N}}_{c}$ in each contest
$c\in\widetilde{\mathcal{C}}$ by

$\displaystyle\widetilde{T}^{\sigma}_{i}(\beta_{1},\ldots,\beta_{B})\triangleq\sum_{b=1}^{B}\mathbb{I}\left\\{\sigma(i)\in\beta_{b}\textnormal{
and
}\left|\left\\{\sigma(j)\in\beta_{b}:j\in\widetilde{\mathcal{N}}_{c}\right\\}\right|\leq\widetilde{v}_{c}\right\\}.$

Equipped with the above notation, we now present the main result of §4.3.5.
This main result, presented below as Proposition 3, establishes that the set
of optimal solutions for the optimization problem (RO-$\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 of the noncompetitive contests from the
original ballot style are combined into a single contest be denoted by
$({\mathcal{N}},\widetilde{\mathcal{C}},\\{\widetilde{\mathcal{N}}_{c}\\}_{c\in\widetilde{\mathcal{C}}},\\{\widetilde{v}_{c}\\}_{c\in\widetilde{\mathcal{C}}})$.
Then the following equality holds for all $B\in\mathbb{N}$,
$\beta_{1},\ldots,\beta_{B}\subseteq\mathcal{N}$,
$\sigma\in\Sigma\cup\\{*\\}$, and $i\in\mathcal{N}$:

$\displaystyle
T^{\sigma}_{i}(\beta_{1},\ldots,\beta_{B})=\widetilde{T}_{i}^{\sigma}(\beta_{1},\ldots,\beta_{B}).$

We conclude §4.3.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 §4.3.2. Indeed, we recall from §4.3.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{\Sigma}$):

$\displaystyle\begin{aligned}
|\\{b\in\\{1,\ldots,B\\}:i\in\beta_{b}\\}|<|\\{b\in\\{1,\ldots,B\\}:j\in\beta_{b}\\}|\quad\forall
c\in\mathcal{C},i,j\in\mathcal{N}_{c}:i<j.&\end{aligned}$ (8)

The constraints (8) ensure that the optimization problem
(RO-$\widehat{\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 §4.3.2, we conclude the present §4.3.5 with an example which
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}},\widetilde{\mathcal{C}},\\{\widetilde{\mathcal{N}}_{c}\\}_{c\in\widetilde{\mathcal{C}}},\\{\widetilde{v}_{c}\\}_{c\in\widetilde{\mathcal{C}}})$
consists of a single contest, $\widetilde{\mathcal{C}}=\\{0\\}$, wherein the
candidates in that contest are given by
$\widetilde{\mathcal{N}}_{0}=\\{1,2,3\\}$ and the maximum number of votes in
that contest is given by $\widetilde{v}_{0}=3$. In the first iteration of the
cutting plane method, we start with $\widehat{\Sigma}=\emptyset$, in which the
optimization problem (RO-$\widehat{\Sigma}$) with the constraints (8) can be
written as

$\displaystyle\begin{aligned}
\underset{B\in\mathbb{N},\;\beta_{1},\ldots,\beta_{B}\in\mathscr{B}}{\textnormal{minimize}}\quad&B\\\
\textnormal{subject
to}\quad&T^{*}_{1}(\beta_{1},\ldots,\beta_{B})<T^{*}_{2}(\beta_{1},\ldots,\beta_{B})<T^{*}_{3}(\beta_{1},\ldots,\beta_{B}).\end{aligned}$
(9)

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

$\displaystyle(B^{1},\beta_{1}^{1},\beta_{2}^{1})=(2,\\{2,3\\},\\{3\\}),$
$\displaystyle(B^{2},\beta_{1}^{2},\beta_{2}^{2})=(2,\\{3\\},\\{2,3\\}).$

In particular, we observe that both of those optimal solutions are feasible
solutions of the optimization problem (RO-$\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{\Sigma}=\emptyset$, in which the optimization problem
(RO-$\widehat{\Sigma}$) with the constraints (8) can be written as

$\displaystyle\begin{aligned}
\underset{B\in\mathbb{N},\;\beta_{1},\ldots,\beta_{B}\in\mathscr{B}}{\textnormal{minimize}}\quad&B\\\
\textnormal{subject
to}\quad&T^{*}_{2}(\beta_{1},\ldots,\beta_{B})<T^{*}_{3}(\beta_{1},\ldots,\beta_{B}).\end{aligned}$
(10)

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

$\displaystyle(B^{1},\beta_{1}^{1})$ $\displaystyle=(1,\\{3\\}),$
$\displaystyle(B^{2},\beta_{1}^{2})$ $\displaystyle=(1,\\{1,3\\}).$

However, neither of those optimal solutions are feasible solutions for the
optimization problem (RO-$\Sigma$).888The fact that neither
$(B^{1},\beta_{1}^{1})=(1,\\{3\\})$ nor $(B^{2},\beta_{1}^{2})=(1,\\{1,3\\})$
is a feasible solution of the optimization problem (RO-$\Sigma$) follows
immediately from the fact that the optimal objective value of the optimization
problem (RO-$\Sigma$) is equal to two. 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. ∎

##  5 Numerical Experiments in Real-World Election

In partnership with the Michigan Bureau of Elections, we applied our approach
to each of the state’s 6928 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-$\Sigma$), and the computation time required by our algorithm to find
optimal test decks for all 6928 ballot styles. We report below on the
performance of our approach with respect to those two factors.

###  5.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-$\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 6928 ballot
styles by solving the optimization problem (RO-$\Sigma$) once per ballot
style. To comply with minimum requirements required by law in the state of
Michigan, the following rules were added as constraints into the optimization
problem (RO-$\Sigma$) (see Appendix D):

  * •

“A different number of valid votes shall be assigned to each candidate for an
office, and for and against each question” [21, MCL 168.798(1)].

  * •

“None of the candidates, write-in positions, or proposals shall have an
accumulated vote total of zero” [21, R168.773 - Rule 3(10)(a)].

Second, we calculated the lengths of heuristic-based test decks for each of
the 6928 ballot styles. Our implemented heuristic involves selecting a test
deck with the minimum possible length that fulfills the aforementioned minimum
legal requirements [21, MCL 168.798(1)] and [21, R168.773 - Rule 3(10)(a)] for
each specific ballot style.999We compute the minimal possible length of a
legally-compliant test deck for each ballot style as the maximum of
$\lceil|\mathcal{N}_{c}|(|\mathcal{N}_{c}|+1)/2v_{c}\rceil$ over all contests
$c$ in the ballot style, where $|\mathcal{N}_{c}|$ is the number of candidates
in the contest and $v_{c}$ is the maximum number of candidates that can be
selected in the contest per ballot. In comparison to the optimal test decks
that were obtained by solving the optimization problem (RO-$\Sigma$), the
heuristic-based test decks are not feasible solutions for (RO-$\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_ legally-compliant heuristic.

Figure LABEL:fig:michigan compares the distributions of the lengths of optimal
test decks and the lengths of heuristic-based test decks across the 6928
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 LABEL:fig:michigan show this is
not the case. The results from Figure LABEL:fig:michigan for Michigan’s
November 2022 general election show that the optimal test decks obtained by
solving the optimization problem (RO-$\Sigma$) require only 1.2% more ballots
on average than the heuristic-based test decks across the 6928 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 6928 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
6928 ballot styles can be explained by a simple mathematical formula. To
present this formula, let $H^{1},\ldots,H^{6928}\geq 0$ denote the lengths of
the heuristic-based test decks and $O^{1},\ldots,O^{6928}\geq 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 [21, 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 §4.3.5 that any feasible
solution of the optimization problem (RO-$\Sigma$) must assign a different
number of votes to each candidate across _all_ noncompetitive contests.
Letting $NC^{1},\ldots,NC^{6928}$ denote the number of candidates in
noncompetitive contests, where
$NC^{k}=\sum_{c:|\mathcal{N}_{c}|=v_{c}}|\mathcal{N}_{c}|$ for each ballot
style $k$, we show in Figure LABEL:fig:max that the formula
$O^{k}=\max\left\\{H^{k},NC^{k}\right\\}$ is satisfied for all ballot styles
$k=1,\ldots,6928$. In other words, Figure LABEL:fig:max shows that the
optimization problem (RO-$\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.101010When the minimum legal requirements are [21, MCL 168.798(1)]
and [21, 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 §4.3.3 that the optimal test
deck for this ballot style will require at least $O\geq 4$ ballots. This
example demonstrates that while the formula
$O^{k}=\max\left\\{H^{k},NC^{k}\right\\}$ explains the lengths of optimal test
decks in all 6928 ballot styles from Michigan’s November 2022 general
election, the formula is not guaranteed to hold in general.

###  5.2 Practical Computational Time

Due to 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-$\Sigma$) that
corresponded to similar ballot styles, which allowed us to decrease the number
of invocations of our exact algorithm from 6928 to 376 (see Appendix E).
Applying those strategies, our exact algorithm from §4 computed optimal test
decks for all 6928 ballot styles in less than seven hours on a home computer.
Figure LABEL:fig:time_cdf 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 §4 can find optimal test decks for all of the ballot
styles across a state in practical computation times. Figure
LABEL:fig:time_vs_iteration displays the number of iterations and the total
computation time required for each of the 376 invocations of our algorithm.
The results of Figure LABEL:fig:time_vs_iteration 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 §4.3
which decrease the number of iterations of the cutting plane method.

##  6 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, Logic and Accuracy Testing, 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 which would have instructed
the military to seize voting machines nationwide. We showed in §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 to 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.

## Acknowledgements

The authors are grateful to the Michigan Department of State Bureau of
Elections for their partnership in this research. This material is based upon
work supported by the U.S. National Science Foundation under Grant No.
CNS-1518888. Any opinions, findings, and conclusions or recommendations
expressed in this material are those of the authors and do not necessarily
reflect the views of the National Science Foundation.

## References

  * AP [2020] AP.  Officials: Clerk error behind county results favoring Biden.  _Associated Press News_ , November 2020.
  * Arizona Secretary of State [2019] Arizona Secretary of State.  Arizona elections procedures manual, 2019.  URL https://azsos.gov/sites/default/files/2019_ELECTIONS_PROCEDURES_MANUAL_APPROVED.pdf.
  * Arkansas State Board of Election Commissioners [2022] Arkansas State Board of Election Commissioners.  County board of election commissioners procedures manual, 2022.  URL https://static.ark.org/eeuploads/elections/2022_CBEC_Manual_FINAL.pdf.
  * Barron [2022] James Barron.  On the ballot: Clean air, clean water, green jobs.  _New York Times_ , November 2022.
  * Ben-Tal et al. [2009] Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski.  _Robust Optimization_ , volume 28.  Princeton University Press, 2009.
  * Bernhard et al. [2017] Matthew Bernhard, Josh Benaloh, J Alex Halderman, Ronald L Rivest, Peter YA Ryan, Philip B Stark, Vanessa Teague, Poorvi L Vora, and Dan S Wallach.  Public evidence from secret ballots.  In _Electronic Voting: Second International Joint Conference_ , pages 84–109. Springer, 2017.
  * Bertsimas et al. [2011] Dimitris Bertsimas, David B Brown, and Constantine Caramanis.  Theory and applications of robust optimization.  _SIAM Review_ , 53(3):464–501, 2011.
  * Bowden and Teague [2021] Mark Bowden and Matthew Teague.  How a Michigan clerk got embroiled in Trump’s attempt to overturn the election.  _Time_ , December 2021.
  * Burki [2015] Talha Khan Burki.  Diesel cars and health: the Volkswagen emissions scandal.  _The Lancet Respiratory Medicine_ , 3(11):838–839, 2015.
  * Corasaniti [2019] Nick Corasaniti.  A Pennsylvania county’s election day nightmare underscores voting machine concerns.  _New York Times_ , November 2019.
  * [11] PLLC DePerno Law Office.  Dominion.  URL https://www.depernolaw.com/dominion.html.  (Accessed on July 22, 2023).
  * Georgia Voter Registration & Elections - DeKalb County [2022] Georgia Voter Registration & Elections - DeKalb County.  Board of registration and elections meeting notes, July 2022.  URL https://www.dekalbcountyga.gov/sites/default/files/users/user3597/Board%20Materials%202022-07-14.pdf.
  * Gilmore and Gomory [1961] Paul C Gilmore and Ralph E Gomory.  A linear programming approach to the cutting-stock problem.  _Operations Research_ , 9(6):849–859, 1961.
  * Halderman [2022] J. Alex Halderman.  Analysis of the Antrim county, Michigan November 2020 election incident.  In _Proceedings of the 31st USENIX Security Symposium_ , pages 589–605. USENIX Association, 2022.
  * Jones and Simons [2012] Douglas Jones and Barbara Simons.  _Broken ballots: Will your vote count?_ CSLI Publications, 2012.
  * Kelley [1960] James E Kelley, Jr.  The cutting-plane method for solving convex programs.  _Journal of the Society for Industrial and Applied Mathematics_ , 8(4):703–712, 1960.
  * Kimball and Kropf [2008] David C Kimball and Martha Kropf.  Voting technology, ballot measures, and residual votes.  _American Politics Research_ , 36(4):479–509, 2008.
  * Kollipara [2016] Puneet Kollipara.  On election day, science also on the ballot in some states.  _Science_ , November 2016.
  * Lindeman and Stark [2012] Mark Lindeman and Philip B Stark.  A gentle introduction to risk-limiting audits.  _IEEE Security & Privacy_, 10(5):42–49, 2012\.
  * Mai-Duc [2021] Christine Mai-Duc.  California recall puts governor’s pandemic leadership to the test.  _Wall Street Journal_ , July 2021.
  * Mic [2019] _Test Procedure Manual for Tabulators and Voter Assist Terminals (VAT)_.  Michigan Department of State, Bureau of Elections, 2019.  URL https://www.michigan.gov/-/media/Project/Websites/sos/01vanderroest/TEST_DECK_MANUAL05.pdf.
  * National Conference of State Legislators [2022] National Conference of State Legislators.  Initiative and referendum processes, January 2022.  URL https://www.ncsl.org/elections-and-campaigns/initiative-and-referendum-processes.
  * [23] John Oliver.  Voting machines: Last Week Tonight with John Oliver (HBO).  URL https://www.youtube.com/watch?v=svEuG_ekNT0.
  * Olson and Stone [2022] Michael P Olson and Andrew R Stone.  The incumbency advantage in judicial elections: Evidence from partisan trial court elections in six US states.  _Political Behavior_ , pages 1–22, 2022.
  * Slevin [2023] Peter Slevin.  The abortion fight has voters turning to ballot initiatives.  _The New Yorker_ , June 2023.
  * Swan [2022] Betsy Woodruff Swan.  Read the never-issued trump order that would have seized voting machines.  _Politico_ , January 2022.
  * Walker et al. [2022] Josiah Walker, Nakul Bajaj, Braden L Crimmins, and J Alex Halderman.  Logic and accuracy testing: A fifty-state review.  In _Electronic Voting: Seventh International Joint Conference_ , volume 13553 of _Lecture Notes in Computer Science_. International Joint Conference on Electronic Voting, Springer, September 2022.
  * Whittaker [1945] Edmund Whittaker.  Eddington’s theory of the constants of nature.  _The Mathematical Gazette_ , 29(286):137–144, 1945.

Appendices

The appendices have the following organization:

  * •

Appendix A proposes two simple heuristics for obtaining feasible solutions for
the optimization problem (RO-$\Sigma$). Using real-world data, we show that
these simple heuristics will result in test decks that contain too many
ballots to be used in practice.

  * •

Appendix B describes the capabilities of an adversary who chooses both the
voting machine’s configuration and the test deck used in LAT.

  * •

Appendix C contains additional numerical experiments that showcase the value
of the five improvements from §4.3 on the practical efficiency of the cutting
plane method from §4.1.

  * •

Appendix D shows that various state-level legal requirements on the design of
test decks can be enforced either by adding constraints into the optimization
problem (RO-$\Sigma$) or by augmenting the output of the optimization problem
(RO-$\Sigma$).

  * •

Appendix E identifies circumstances in which an optimal test deck for the
optimization problem (RO-$\Sigma$) for one ballot style can be efficiently
translated into an optimal test deck for another similar ballot style.

  * •

Appendix F contains the proofs of the paper’s technical results.

##  Appendix A Upper Bounds

Our exact algorithm for solving the optimization problem (RO-$\Sigma$) is
found in §4. In this appendix, we motivate the exact algorithm by presenting
and analyzing two simple heuristics for the optimization problem
(RO-$\Sigma$). These two heuristics, which can be found below in Propositions
4 and 5, obtain a feasible solution for the optimization problem (RO-$\Sigma$)
by constructing a test deck that contains a distinct positive number of votes
for each candidate. Our purpose for presenting these heuristics is (a) to show
that the optimization problem (RO-$\Sigma$) always has a feasible solution and
(b) to show using real-world data that heuristics based on assigning a
distinct number of votes for each candidate will result in test decks that
contain too many ballots to be implementable in practice.

Our first simple heuristic for the optimization problem (RO-$\Sigma$) is
stated formally in the proof of the following Proposition 4. The heuristic
consists of constructing a test deck in which each filled-out ballot in the
test deck contains a vote for exactly one candidate (i.e.,
$|\beta_{1}|=\cdots=|\beta_{B}|=1$) and in which each candidate
$i\in\mathcal{N}$ is selected in exactly $i$ of the filled-out ballots. The
fact that this heuristic yields a test deck that is feasible for the
optimization problem (RO-$\Sigma$) is shown in the proof of Proposition 4 to
follow from Corollary 1 coupled with the fact that the heuristic gives a
distinct total number of votes to each of the candidates. More generally, this
heuristic is useful because it yields a simple, closed-form upper bound on the
length of optimal test decks for the optimization problem (RO-$\Sigma$).

######  Proposition 4.

There exists a feasible solution for the optimization problem (RO-$\Sigma$)
that satisfies $B\leq N(N+1)/2$.

Our second heuristic for the optimization problem (RO-$\Sigma$) can be viewed
as a refinement of the first heuristic from Proposition 4. Like the first
heuristic, our second heuristic yields a test deck that is feasible for the
optimization problem (RO-$\Sigma$) by giving a distinct positive number of
votes to each candidate. However, our second heuristic assigns a different
positive number of votes to each candidate in such a way that allows the votes
to be packed into the fewest number of ballots. More specifically, our second
heuristic consists of solving the following optimization problem (11) to find
a minimum-length test deck that assigns a distinct positive number of votes to
each of the candidates across each of the contests:

$\displaystyle\underset{B\in\mathbb{N},\;\beta_{1},\ldots,\beta_{B}\in\mathscr{B}}{\textnormal{minimize}}\quad$
$\displaystyle B$ (11a) subject to
$\displaystyle\left|\left\\{b\in\\{1,\ldots,B\\}:i\in\beta_{b}\right\\}\right|\neq\left|\left\\{b\in\\{1,\ldots,B\\}:j\in\beta_{b}\right\\}\right|$
$\displaystyle\forall i,j\in\mathcal{N}:i\neq j$ (11b)
$\displaystyle\left|\left\\{b\in\\{1,\ldots,B\\}:i\in\beta_{b}\right\\}\right|\geq
1$ $\displaystyle\forall i\in\mathcal{N}.$ (11c)

Indeed, constraint (11b) ensures that the test deck gives a distinct number of
votes to each candidate, and constraint (11c) ensures that each candidate
receives at least one vote. It follows immediately from Corollary 1 that any
test deck that is feasible for the optimization problem (11) is feasible for
the optimization problem (RO-$\Sigma$). Hence, the optimization problem (11)
provides the tightest upper bound on the optimal objective value of the
optimization problem (RO-$\Sigma$) that can be obtained by a test deck that
assigns a distinct positive number of votes to each of the candidates across
all of the contests.

In the following Proposition 5, we show that the optimization problem (11) can
be reformulated as a mixed-integer linear optimization problem. In contrast to
the optimization problem (11), the mixed-integer linear optimization problem
(12) from the following Proposition 5 can be easily implemented and solved
using widely available open-source and commercial optimization software such
as Gurobi and Mosek.

######  Proposition 5.

The optimal objective value of the optimization problem (11) is equal to the
optimal objective value of the following mixed-integer linear optimization
problem (12), and every optimal solution for (12) can be transformed into an
optimal solution for (11).

$\displaystyle\underset{B\in\mathbb{N},\gamma\in\\{0,1\\}^{\mathcal{C}\times\mathcal{N}}}{\textnormal{minimize}}$
$\displaystyle B$ (12a) subject to
$\displaystyle\sum_{g\in\mathcal{N}}\gamma_{c,g}=|\mathcal{N}_{c}|$
$\displaystyle\forall c\in\mathcal{C}$ (12b)
$\displaystyle\sum_{c\in\mathcal{C}}\gamma_{c,g}=1$ $\displaystyle\forall
g\in\mathcal{N}$ (12c) $\displaystyle
B\geq\frac{1}{v_{c}}\sum_{g\in\mathcal{N}}g\gamma_{c,g}$ $\displaystyle\forall
c\in\mathcal{C}$ (12d) $\displaystyle B\geq N.$ (12e)

Let us provide an interpretation of the decision variables and constraints of
the mixed-integer linear optimization problem (12). Each binary decision
variable $\gamma_{c,g}$ will be equal to one if and only if there exists a
candidate $i\in\mathcal{N}_{c}$ in contest $c$ that satisfies the equality
$\left|\left\\{b\in\\{1,\ldots,B\\}:i\in\beta_{b}\right\\}\right|=g$.
Constraints (12b) and (12c) ensure that a distinct number of votes are given
to each of candidates across each of the contests. Constraint (12d) enforces,
for each contest $c\in\mathcal{C}$, the fact that a test deck
$\beta_{1},\ldots,\beta_{B}\in\mathscr{B}$ needs to be comprised of at least
$B\geq\lceil\frac{1}{v_{c}}\sum_{g\in\mathcal{N}}g\gamma_{c,g}\rceil$ ballots
in order for it to be possible for the test deck to give
$\sum_{g\in\mathcal{N}}g\gamma_{c,g}$ votes to the candidates in contest $c$
without causing an overvote for that contest in any of the ballots. Constraint
(12e) enforces that we include at least the $N$ ballots which are necessary
for the candidate who receives $N$ votes.

We conclude Appendix A by showing using real-world data that any heuristic
that assigns a distinct positive number of votes to each candidate across all
of the contests will result in test decks that contain too many ballots to be
useful in practice. Specifically, we applied our second heuristic to the 6928
ballot styles that appeared in the state of Michigan in the November 2022
general election. In Figure 5, we compare the number of ballots for test decks
that are optimal for the optimization problem (RO-$\Sigma$) (red bars) and the