@unpublished{Riv19i,
author = { Ronald L. Rivest },
title = { Voting and Auditing with Ternary Plurality Trees },
date = { 2019-08-23 },
OPTyear = { 2019 },
OPTmonth = { August 23, },
urla = { nbviewer },
urlb = { github },
abstract = { We suggest using "ternary plurality trees" to define
a voting method (called TPT). TPT voting is quite
close to, but different than, plurality voting; we
examine how close TPT and plurality are.
\par
Perhaps
the most interesting aspects of TPT voting have to
do with auditing. Auditing a TPT contest is
combinatorial in character rather than
statistical (as with a risk-limiting audit).
With TPT voting an election contest with $3^d$ cast
ballots can be audited in a zero-risk manner by
manually examining only $2^d$ cast paper ballots, in
the case of two candidates, with no missing or
invalid ballots. For example, a two-candidate
contest with one million cast paper ballots may be
audited by examining only 6104 ballots, assuming no
interpretation errors are found in the audit.
\par
The $n$ cast ballots are arranged as the leaves in a
ternary tree of height $\log_3(n)$. Each internal
node of the tree has a value equal to the plurality
vote of its three children (with ties broken
pseudorandomly). The value at the root is the
winner of the contest, by definition.
\par
Auditing the
contest outcome requires examining only two of every
three children of audited nodes (assuming two
candidates and no discrepancies discovered). The
TPT voting method is quite close to, but different
than, plurality voting; we examine how close TPT and
plurality are. The outcome of a TPT election may
depend on the way in which ballots are assigned to
leaves of the tree. TPT assigns ballots to leaves
in a randomized manner to ensure that all voters may
expect an equal voice in the outcome.
\par
We present
the result of a simple experiment illustrating how
auditing a TPT election expands gracefully when
interpretation errors are found. Finally, we show
how the TPT method extends to handle multiple
candidates and ballots with missing or invalid
choices. }
}