On auditing elections when precincts have different sizes, 2007. Available at: http://theory.csail.mit.edu/ ~rivest/Rivest-OnAuditingElections WhenPrecinctsHaveDifferentSizes.pdf

We address the problem of auditing an elec-tion when precincts may have different sizes, and suggest methods for picking a sample of precincts to audit that precinct size into ac-count. One method yields optimal auditing strategies together with an exact measure of its effectiveness (probability of detecting corrup-tion of a given size). We restrict attention to basic auditing strate-gies, in which each precinct Pi is audited inde-pendently with some probability pi determined by the auditor. The auditing probability for a precinct will depend on the size of the precinct, with larger precincts audited more frequently; when all precincts have the same size they will have the same probability of being audited. We first show how, given the auditor’s sim-pel auditing strategy, how to efficiently compute an optimal strategy for the adversary, using dy-namic programming. This also yields the exact probability that the auditor will detect the ad-versary’s corruption in one or more precincts. We then show how to embed the above proce-dure in an efficient iterative optimization com-putation that appears to always converge upon the optimal auditing strategy. Finally, we present the “logistic auditing ∗The latest version of this paper can al-ways be found a