Real Democracy: Post-Election Audits for Range Voting

1 1 real democracy : Post-Election Auditsfor Range VotingBerj Chilingirian, Eric Huppert, Zara PerumalMIT CSAIL,{berjc, ehuppert, 11, 2016 Abstract The election system of the United States of Americais flawed in two ways. First, it relies on a Voting scheme thatdoes not enforce true democracy . Second, it relies on electronicvoting systems to properly tabulate ballots despite such systemsbeing susceptible to bugs and malicious behavior. To address thefirst issue, we advocate for the use of Range Voting , a scheme thatallows a voter to express their true and complete preferences. Toaddress the second concern, we propose four new Post-Election ,ballot-polling Audits for Range Voting contests.}

2 We compare ourauditing procedures to existing strategies via a simulated errorrate analysis. As a consequence of this research, we propose amodel for generating Range Voting contests and implement theElectionEngine, an open source election simulation , we discuss the tradeoffs present in choosing INTRODUCTIONThe 2016 presidential election has arguably been one of themost entertaining elections in recent years [1]. At one point thecontest consisted of six democratic and 17 republican candi-dates, including controversial businessman Donald Trump andformer Secretary of State Hilary Clinton [2]. Nevertheless, thefield has narrowed to three candidates and come November,the general public will make a pivotal decision on the futuredirection of the United States of America.

3 A large portion ofvoters across the country will travel to their local polling sitesand cast their choice as a traditional paper ballot [3]. Thesepaper ballots will then be tabulated by an electronic votingsystem and the result of the election will be nature of this election brings to light two issues thatthreaten the integrity of our Voting process. First, the field ofcandidates is thinned by a sequence of primary contests andcaucuses whose order may determine the fate of a candidatebefore that candidate has the chance to compete in everystate. This effect may be attributed to the United State ssimple plurality system in which voters may choose only onecandidate to support, with no way to distinguish a secondoption from a last choice.

4 By prioritizing logistics over thevoter s voice, this phenomenon weakens the democracy of theelection process [4].Second, the general public relies entirely on the honesty andcorrectness of Voting system software to report the true elec-tion outcome. It could be, however, thatTrump Technologiesand/orClinton Cryptosystemshas software/firmware/hardwareincorporated into Voting systems that influences the , considering the prevalence of bugs inindustry software (15-50 errors per 1000 lines of code) [5],it could be that the Voting system has a bug that causes it toreport the wrong outcome. In either case, the democracy ofthe election process is address the first concern, the United States governmentmay consider replacing the traditional simple plurality schemewith a Range Voting scheme.

5 In Range Voting , each voterscoresevery candidate from[0,m]wheremis the maximum score( 100). In this manner, a voter may specify their preferencefor each candidate independent of their preferences for othercandidates. To determine a winner, the mean/median of eachcandidate s score across all ballots can be computed andthe candidate with the highest score is declared the electionwinner. Range Voting gives the voter the power to express theircomplete preferences and has numerous favorable propertiescompared to simple plurality Voting [6].Of course, the democracy delivered by Range Voting maystill be violated by un/intentional malicious Voting systemsoftware.

6 This problem, however, may be mitigated by a Post-Election audit in which paper ballots are polled at random andused to either verify the election outcome or signal a manualrecount. Numerous auditing procedures have been proposedin the literature [7], including both scheme-specific [8] ( plurality-specific auditing procedures) and black-boxprocedures that work for any social choice function [9]. As thevoting system is not trusted, an audit may provideevidencethat the reported outcome is correct [10].Despite the plethora of research in election Audits , therehas been no work in ballot-polling Audits specifically forrange Voting .

7 This paper proposes several ballot-pollingaudits for Range Voting and demonstrates their performancevia simulation. Our problem statement is as Statement:Can we develop Post-Election Audits forrange Voting that outperform existing black-box methods?In solving this problem, our paper makes the followingcontributions. Comparison of Black-Box Audits :We replicate andextend the results in [9] by comparing several black-box1To our knowledge, neitherTrump TechnologiesnorClinton Cryptosystemsare real SystemOutcomeTrump TechnologiesMake Software Great Again!ClintonCryptoSystemsYour Emails are Safe with Us!Fig. audit Threat cannot trust that the software in our electronic Voting system produces the actual outcome for every instance, it could be that the software vendor of the system is biased towards a specific political party and/or that the software contains schemes.

8 Four New Ballot-Polling Audits for Range Voting :Wepropose four new ballot-polling Audits for Range votingcontests. Two of the four proposed Audits are consideredblack-box Audits . Model for Range Voting Contests:We propose a wayto model Range Voting contests using Yee-Pictures [11]. Error Rate Analysis and Comparison to ExistingAudits:We compare our proposed Audits to existingtechniques by measuring their error rates on simulatedcontests. Open Source election Simulation Platform:We havedevelopedElectionEngine, an open source electionsimulation platform for anyone to write and test theirown auditing schemes on both simple plurality and rangevoting rest of this paper is outlined as follows.

9 Section 2presents background information on our notation and previouswork on Post-Election Audits . Section 3 presents the threatmodel faced by Post-Election Audits . Section 4 describes rangevoting and our proposed method for generating a Range votingcontest. Section 5 describes the four Post-Election auditingprocedures we developed for Range Voting . Section 6 presentsa simulation-based comparison of the performance of ourmethods against the performance of other black-box 7 discusses these results and section 8 , section 9 mentions possible future directions for thework BACKGROUNDTo develop an auditing procedure for a Range Voting contest,we must first understand what is meant by an election contestand review previous work in contest PreliminariesAn election consists of a set of contests.

10 Each contestconsists of a set of candidates and a set of ballots making upthe voterprofilefor that contest [9]. At the end of an election ,each contest publishes areportedoutcome,R. The reportedoutcome is not necessarily equal to theactualoutcome,A,of the contest, or the outcome computed manually fromthe contest s profile [12]. For example, it could be that thereported outcome is incorrect due to a software bug in thevote tabulation Post-Election AuditsPost- election Audits provide evidence that the reported out-come of an election contest corresponds to the actual outcomeof that contest. Such Audits sample the contest s profile re-peatedly to build evidence for the reported outcome.