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