@InProceedings{APR08,
author = { Javed Aslam and Raluca A. Popa and Ronald L. Rivest },
title = { On Auditing Elections When Precincts Have Different Sizes },
url = { http://www.usenix.org/events/evt08/tech/full_papers/aslam/aslam.pdf },
urla = { EVT'08 },
booktitle = { Proceedings 2008 USENIX/ACCURATE Electronic Voting Technology Workshop },
OPTyear = { 2008 },
OPTmonth = { July 28--August 1, },
date = { 2008 },
editor = { David Dill and Tadayoshi Kohno },
eventtitle = { EVT'08 },
eventdate = { 2008-07-28/2008-08-01 },
venue = { San Jose, California },
organization = { USENIX/ACCURATE },
OPTpublisher = {},
abstract = {
We address the problem of auditing an election when
precincts may have different sizes. Prior work in this
field has emphasized the simpler case when all precincts
have the same size. Using auditing methods developed
for use with equal-sized precincts can, however, be inefficient
or result in loss of statistical confidence when
applied to elections with variable-sized precincts.
\par
We survey, evaluate, and compare a variety of approaches
to the variable-sized precinct auditing problem,
including the SAFE method [11] which is based on theory
developed for equal-sized precincts. We introduce
new methods such as the negative-exponential method
``NEGEXP'' that select precincts independently for auditing
with predetermined probabilities, and the ``PPEBWR''
method that uses a sequence of rounds to select precincts
with replacement according to some predetermined probability
distribution that may depend on error bounds for
each precinct (hence the name PPEBWR: probability proportional
to error bounds, with replacement), where the
error bounds may depend on the sizes of the precincts, or
on how the votes were cast in each precinct.
\par
We give experimental results showing that NEGEXP
and PPEBWR can dramatically reduce (by a factor or two
or three) the cost of auditing compared to methods such
as SAFE that depend on the use of uniform sampling.
Sampling so that larger precincts are audited with appropriately
larger probability can yield large reductions in
expected number of votes counted in an audit.
\par
We also present the optimal auditing strategy, which
is nicely representable as a linear programming problem
but only efficiently computable for small elections (fewer
than a dozen precincts). We conclude with some recommendations
for practice.
},
}