@InProceedings{RSP17,
author = { Ronald L. Rivest and Philip B. Stark and Zara Perumal },
title = { {BatchVote}: Voting rules designed for auditability },
date = { 2017-04-07 },
venue = { Malta },
eventtitle = { Voting'17 workshop (associated with Financial Crypto 2017) },
eventdate = { 2017-04-07/2017-04-07 },
urla = { workshop },
urlb = { paper },
abstract = {
We propose a family of novel social choice functions. Our goal
is to explore social choice functions for which
\textbf{ease of auditing} is a primary design
goal, instead of being ignored or left as a puzzle to solve later.
\par
Our proposal, ``\textbf{BatchVote},'' creates a social choice function $f$ from
an arbitrary ``inner'' social choice function $g$, such as instant-runoff voting (IRV),
and an integer $B$, the number of batches.
\par
We aim to preserve flexibility by allowing $g$ to be arbitrary, while
providing the ease of auditing of a plurality election.
\par
To compute the winner of an election of $n$ votes,
the social choice function $f$ partitions the votes
into $B$ batches of roughly the same size, pseudorandomly.
The social choice function $g$ is applied to each batch.
The election winner, according to $f$, is the weighted
plurality winner for the $B$ outcomes, where the weight of each batch
is the number of votes it contains.
The social choice function $f$ may be viewed as an ``interpolation''
between plurality (which is easily auditable) and $g$ (which need
not be).
\par
Auditing is simple by design: we can view $f$ as being
a (weighted) plurality election by $B$
``\emph{supervoters},'' where $b$th supervoter's vote is
determined by applying $g$ to the votes in batch $b$, and the weight
of her vote is the number of votes in her batch.
Since plurality elections are easy to audit, the election
output can be audited by checking a random sample of ``supervotes''
against the corresponding paper records.
}
}