[EM] Auditing IRV: RAIRE and SHANGRLA

[Neal McBurnett]

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/