Optimizations for election tabulation auditing

Abstract

In this thesis, we explore different techniques to improve the field of election tabulation audits. In particular, we start by discussing the open problems in statistical election tabulation audits and categorizing these problems into three main sections - audit correctness, flexibility, and efficiency. In our first project, we argue that Bayesian audits provide a more flexible framework for a variety of elections than RLAs. Thus, we initially focus on analyzing their statistical soundness. Furthermore, we design and implement optimization techniques for Bayesian audits which show an increase in efficiency on synthetic election data. Then, motivated by empirical feedback from audit teams, we focus on workload estimation for RLAs. That is, we note that audit teams often want to finish the audit in a single round even if it requires sampling a few additional ballots. Hence, for the second project, we design software tools which can make initial sample size recommendations with this in mind. For our largest project, we focus on approximate sampling. That is, we argue that approximate sampling would provide an increase in efficiency for RLAs and suggest a particular sampling scheme, k-cut. We explore the usability of k-cut by providing and analyzing empirical data on single cuts. We argue that for large k, the model will converge to the uniform distribution exponentially quickly. We discuss simple mitigation procedures to make any statistical procedure work with approximate sampling and provide guidance on how to choose k. We also discuss usage of k-cut in practice, from pilot audit experiences in Indiana and Michigan, which showed that k-cut led to a significant real-life increase in efficiency.