@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. } }