[EM] Auditing IRV: RAIRE and SHANGRLA

[Neal McBurnett]

On Tue, Dec 17, 2019 at 10:41 AM robert bristow-johnson <
rbj at audioimagination.com> wrote:

> 1. Welcome to the EM list.
>

Thanks!


> 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.
>

Another relationship relates to the question of how to perform a
risk-limiting audit: how many paper ballots to audit against the published
results, what to do about discrepancies (which do indeed happen), and how
to decide when enough sampling and comparison has been done, that the risk
of an incorrect outcome has been sufficiently minimized. Different tally
methods require different statistical calculations.  This may not be the
list to discuss such things on, but knowing where to go for the answers and
who is doing the research do seem relevant, thus my message.


> 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'm computer scientist and security consultant. The communications issues
are indeed important, but so are other aspects.

I doubt it's appropriate to go in to a lot of depth here, but there are
indeed other reasons voting systems occasionally interpret and/or tabulate
ballots differently than a human would. Humans sometimes circle boxes
instead of filling them in, and some state laws require that those be
counted as votes. Distinguishing a "hesitation mark" or bit of toner from a
marked oval require human eyes. Devices are sometimes configured with the
wrong descriptions of the ballot, as happened just last month in
Northampton County, PA, causing a huge discrepancy. And even humans
sometimes differ on how to interpret a ballot. I've seen them.

Being able to deal with those discrepancies is one of the more challenging
aspects of the math behind RLAs. I'm working with Dr Vora at George
Washington University on an NSF grant to improve the efficiency of RLAs, a
field in which I've worked for nearly two decades, and been invited to
testify to a National Academies committee on. You can read their report
online at
https://www.nap.edu/catalog/25120/securing-the-vote-protecting-american-democracy


> 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.
>

That can help a lot. But there are a variety of ways that images can be
unreliable, as demonstrated e.g. at UnclearBallot: Automated Ballot Image
Manipulation - https://mbernhard.com/papers/unclearballot.pdf
So it is important under many circumstances to look at the paper ballot
rather than the image.


> 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.
>

I dearly wish that was true everywhere in the US, but sadly in a number of
states, including North Carolina and Indiana, paperless voting machines
allow election officials to connect voted ballots with the voter until
after the election day deadline to vote. They do so for the same reason
that they do so in the UK: e.g. an early ballot is invalid if the voter
dies before election day, and state law says it must not be counted in the
tally.


> 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.
>

Yes, I agree, from the standpoint of the security of the official results
of the election. And as I pointed out, there are new ways to audit the
results to within a specified statistical risk without a full hand count.

I was just also pointing out that some of us, like the message from Rob
that I responded to, do care about other ways tabulating the ballots, and
actually run the ballots thru our own tabulation software. That's what
caught the attention of folks in Burlington: a different tally method that
pointed out the Condorcet winner was different. And when I combine that
with the RLA techniques, I find it interesting (but not formally relevant
to the official outcome) to understand how close the tally was to other
outcomes via various methods.

And in general, as we design voting methods, we should consider how to
efficiently audit them.  Colorado law requires a risk-limiting audit of
many contests, and the research and software I pointed out make that much
easier to do now.


> 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


 I mean software bugs, hardware bugs, errors in specifying tally methods
(e.g. as I recall, an analysis of the IRV software in Ireland vs the Irish
tally law found that the software didn't perfectly implement the law),
security vulnerabilities that allow adversaries to change the results, etc.
And when you drill down far enough, cosmic rays can cause memory errors,
etc. but we don't need to go that far to know we have problems to solve.

Cheers,
Neal


> 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."
> ----
> Election-Methods mailing list - see https://electorama.com/em for list
> info
>


-- 
Neal McBurnett                 http://neal.mcburnett.org/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20191217/d400769a/attachment-0001.html>