[EM] Auditing IRV: RAIRE and SHANGRLA

[robert bristow-johnson]

Hello Neal,

Several things to say here:

1. Welcome to the EM list.  I am not any of the founding members, I was told about it 10 years ago by Terry Bouricius who is a fellow resident of Burlington Vermont, a past city councilor, a political scientist who works for FairVote, and an advocate for IRV, and as I found out a week ago when RCV began to reappear in Burlington, not much of an advocate for fixing what went wrong in Burlington in 2009.  I joined soon after the infamous Burlington 2009 IRV election, I believe the only one in which the Pairwise Champion (a.k.a. Condorcet candidate) did not win.  Much controversy and IRV was repealed the following year.

2. Although there is a relationship, the issues of Voting Methods (ballot type, FPTP, IRV, Condorcet, Score, Approval...) and Voting Security are not the same.  The only immediate connection between the two issues is that of precinct summability.  FPTP and Condorcet methods are both precinct summable, IRV is not unless you want to count all of the possible ways a ranked ballot can be marked and that is a very large number.

3. I took a look at the papers you reference and the only real Electrical Engineering aspect of this (one of the papers is IEEE) in my opinion (as an electrical engineer) is that of secure communications.  All that is important, but the auditing thing is just that, recounting ballots.  We do this routinely when the election is close or there is some other funny business.  To that, the only engineering solution, in my opinion are optical scan paper ballots, where the candidate name is on the physical instrument storing the vote (not those punch card butterfly ballots) so that the voter and the auditor see exactly the same ballot and there is no way a voter can think he/she voted for A but the physical instrument appears that he/she voted for someone else.  (If those punch cards were misaligned, you might end up voting for whom you hate the most.)  Regarding secure communications, having total transparency regarding all procedures, including the code use to scan and tabulate ballots, is the key.  It should be public domain and accessible by anyone.

I was talking with Jim Condos, the Vermont Secretary of State, about this and he said that there is a technology that will digitally photograph each ballot so that if it looks poorly marked, the system can flag a team of election officials, who can immediately pull up the ballot image and look and judge for themselves what the voter intent was.

One thing is, that if the election is in the U.S., the ballot must not, in any manner, be traceable to the identity of the voter who marked it.  If the ballots have serial numbers, those must not be associated with the voter.  That is different from the U.K. and some other democracies.

4. That said, I don't see what the big deal is.  If you have paper ballots *and* a manual recount is done, there is a way to do IRV manually with piles of ballots.  But it's laborious.  The issue of election security really is unrelated to the issue of whether the Condorcet candidate is elected or not.  Whether a particular IRV election will or will not elect the Condorcet winner is independent of security, redundancy, and auditing issues.  It's only a voting method issue.

5. I am skeptical of the "computers make mistakes" notion. Do you mean a hardware crash?  Because a numerical error with integer arithmetic is not really possible.

bestest,

r b-j

> On December 17, 2019 11:07 AM Neal McBurnett <neal at bcn.boulder.co.us> wrote:
> 
>  
> I just joined the list (after a few decades of activity with election methods and auditing). Thanks for the fascinating discussion.  This stuff is even more complicated than I knew.
> 
> Let me note one more complication though.  The interpretations by the voting system of the votes ("cast vote records" or CVRs) might
> be wrong, and IRV is famously vulnerable to interpretation errors at each round of tallying.
> Even figuring out how sensitive the outcome of a particular contest is to discrepancies between
> the paper ballots and the CVRs is a challenging computation.
> 
> Thankfully, I can also pass on some news of progress in the field: the new RAIRE / SHANGRLA method of auditing IRV elections, which was piloted in the November 2019 election in San Francisco.  Armed with these techniques (and associated open-source code) we should be able to figure out how much error we could tolerate before an IRV tally might end up with a non-Condorcet winner, even though the tally of the official CVRs did pick a Condorcet winner.
> 
> And thus there's also more work to be done for any given election method to figure out how to audit it and limit the risk that the outcome is actually incorrect.
> 
> Background:
> 
> When we declare that a particular election resulted in a particular outcome according
> to a particular algorithm, we are of course trusting that the election system interpreted the human input
> with perfect accuracy and fidelity.  But of course we all know that computers make mistakes and are
> vulnerable to hacking.
> 
> Ron Rivest and John Wack invented the concept of Software Independence to deal with that concern.
> 
>  Software Independence (Wack and Rivest)
>   http://people.csail.mit.edu/rivest/RivestWack-OnTheNotionOfSoftwareIndependenceInVotingSystems.pdf
> 
> The field of Evidence-Based Elections presents a general framework for how to gather evidence to check
> the outcome (set of winners) of a particular contest via software-independent evidence.
> 
>  Evidence-Based Elections  -  P.B. Stark and D.A. Wagner
>   IEEE Security and Privacy, Special Issue on Electronic Voting, 2012.
>   http://statistics.berkeley.edu/~stark/Preprints/evidenceVote12.pdf
> 
> Evidence-Based Elections employ Risk-Limiting Audits (RLAs) to sample some ballots, compare the paper with the electronic records, and limit the risk of declaring the wrong outcome.  In Colorado, we've pioneered and pushed forward the state of the art in RLAs as I describe here:
> 
>  https://bcn.boulder.co.us/~neal/elections/corla/
> 
> But defining RLAs for IRV has been a challenge for many years. Now a better method is available:
> 
>  RAIRE: Risk-Limiting Audits for IRV Elections - Michelle Blom · Peter J. Stuckey · Vanessa J. Teague
>   https://arxiv.org/pdf/1903.08804.pdf
> 
> It can be used with the new more general RLA approach described in SHANGRLA:
> 
>  SHANGRLA: Sets of Half-Average Nulls Generate Risk-Limiting Audits: tools for assertion-based risk-limiting election audits
>   https://github.com/pbstark/SHANGRLA
> 
> Which brings me to the post that prompted this post:
> 
> On Mon, Dec 16, 2019 at 11:12:24PM -0800, Rob Lanphier wrote:
> > On Sat, Dec 14, 2019 at 7:21 AM robert bristow-johnson
> > <rbj at audioimagination.com> wrote:
> > > >  So BTR-STV seems like a
> > > > fine compromise, since IRV has failed to pick the Condorcet winner in
> > > > at least one recent public election.
> > >
> > > yes, and i am trying to remind the Progs of that.  but they are not listening.
> > 
> > *sigh*.  Yeah, sounds tough.  We had a close mayoral election here in
> > San Francisco in 2018.  Given how close it was, I was really terrified
> > that we'd end up with an election like Burlington 2009.  Thankfully,
> > the IRV elimination order didn't threaten to eliminate the Condorcet
> > winner.  The closeness of the race was between two candidates who
> > probably would have been the final two candidates in a BTR-IRV tally
> > (though the third place candidate wasn't far behind either of the
> > frontrunners).  Given the closeness bitterness of the race, it would
> > have been an electoral reform disaster if any of the top three
> > candidates had lost the way that Andy Montroll did in Burlington (as
> > the Condorcet winner and IRV loser).
> > 
> > Rob
> 
> Re the 2018 San Francisco mayoral election that Rob alludes to, we can of course use RAIRE / SHANGRLA to audit the winner.
> But he's also interested in whether the winner was a Condorcet winner. Related auditing techniques should be
> able to calculate the minimum number of vote discrepancies that would have resulted in a different Condorcet winner.
> But I don't know of anyone looking at that problem right now.
> 
> In general, if we want similar confidence in outcomes for other tally methods, we'll need to come up with RLA methods for them.
> For many of the ranked-choice methods, RAIRE is probably a good model, and it might even provide insights in to other
> aspects of voting methods.
> 
> Cheers,
> 
> Neal McBurnett                 http://neal.mcburnett.org/

--
 
r b-j                  rbj at audioimagination.com
 
"Imagination is more important than knowledge."