i misunderstood you.  we're on the same page.  yes, Burlington 2009 had a single, clear Condorcet winner.

it was the only IRV election that i know of where the Condorcet winner was not elected.

--

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

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:

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/

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

--

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

On Tue, Dec 17, 2019 at 9:19 AM [EST] robert bristow-johnson
rbj@audioimagination.com wrote:

Cool.  I kinda figured it was a thinko, but I wanted to be
doubly-triply sure I check because I talk about Burlington 2009 so
much.

It's the only municipal IRV election that I've independently confirmed
the discrepancy as well.  But I haven't independently audited that
many municipal IRV elections.

I haven't analyzed /u/curiouslefty's claim that there was an
IRV/Condorcet discrepancy in Queensland Australia in 1998:
https://www.reddit.com/r/EndFPTP/comments/e4ogcg/condorcet_failure_and_condorcet_cycle_analysis_of/

In general, though, my hunch is that others can be found.  If
IRV/Condorcet discrepancies are truly one-in-a-million events under
real-world conditions, then we should stop obsessing about Burlington
2009, and get on board with
IRV/RCV/whatever-the-cool-kids-call-it-these-days.  But if the number
is more like one-in-a-hundred or maybe three-in-a-hundred with a naive
electorate (i.e an electorate that probably hasn't learned how to vote
strategically), then that's an enormous problem.  My hunch is that
it's closer to the latter, and that others can be found without too
much work because it's not that rare.

I'm aware of another ranked ballot election where there was an
IRV/Condorcet discrepancy: the 2003 Debian leader election.  Debian
uses Condorcet-Schulze, so the pairwise winner won the election.  But
intuitively, the result seemed to fall in the jagged borderline area
of Ka-Ping Yee's IRV simulations (that is, if we were talking about
that particular election as a datapoint in a simulation).  Having
carefully analyzed both Debian 2003 and Burlington 2009, and then read
some of Ka-Ping Yee's research (and played with Nicky Case's wonderful
interactive version), I'm pretty sure that IRV is "stinky cheese" (as
Nicky Case puts it).

r b-j, thanks for advocating for BTR-IRV in Burlington!  These
conversations inspired me to do a little clean up the BTR-IRV/BTR-STV
pages over on Electowiki:
https://electowiki.org/wiki/BTR-IRV

Rob

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

Thanks!

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.

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

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.

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.

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.

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

--
Neal McBurnett                http://neal.mcburnett.org/

On 17/12/2019 08.12, Rob Lanphier wrote:

Doesn't BTR-IRV pass Smith? Suppose that X is in the Smith set and Y is
not. Once X and Y meet in the bottom-two runoff, then by definition of
the Smith set, X beats Y pairwise, so Y is eliminated.

This holds no matter who X and Y are, so a Smith set member can never be
eliminated in a bottom-two runoff when facing a candidate outside the
Smith set. And since every candidate has been subjected to at least one
such runoff, every member outside the Smith set must necessarily have
been eliminated. Thus the method passes Smith.

Or am I missing something? :-)

That also seems wrong. See theorem 1 of
http://dss.in.tum.de/files/brandt-research/choicesets.pdf.

Kristofer, I stand corrected on both of the points I was trying to
make (thank you!).  More inline:

On Tue, Dec 17, 2019 at 4:02 PM Kristofer Munsterhjelm
km_elmet@t-online.de wrote:

Oh, that's delightfully simple!  Your informal proof of BTR-IRV
passing Smith seems correct to me.

I'm now struggling to figure out what the practical benefits of the
other Condorcet methods over BTR-IRV.  Given that BTR-IRV is
reasonably simple to explain, it has an intuitive connection to IRV,
it's hard to understand what the practical benefit is to advocating
for other Condorcet-winner compliant systems.

Based on what I learned about Copeland back in 1996 when I was first
learning this stuff, I somehow dismissed the usefulness of the
Copeland set, and exhalted the use of the Smith set (since
Smith//Minmax(wv) seemed to be the preferred method discussed on EM
back in 1996, as I recall).  That paper looks like something I should
spend more time reading.

Rob

How does BTR-STV not "guarantee Smith set membership" ?      It is a
silly Mickey Mouse method that (at least) pointlessly fails Clone
Independence.

Why do you (Rob)  suspect that all "Condorcet-compliant methods perform
better at strategy resistance than standard IRV does"?

IRV is somewhat more vulnerable to Compromise than Condorcet methods at
the expense of being much more vulnerable to Burial strategy.

43: A
03: A>B
44: B>C (sincere is B or B>A)
10: C

Here A is the sincere and voted  FPP and IRV winner and the sincere
CW.   C is a should-be-irrelevant (say) extreme wing candidate.

Schulze, Ranked Pairs, MinMax, Smith//MinMax using Winning Votes (as
Schulze himself advocates) or Margins (as Robert advocates) as the measure
of defeat-strength all reward the insincere voters (who simply Buried
against the other front-runner, nothing implausibly ingenious) by
electing B.

I rate plain IRV  (where the voters are free to strictly rank from the
top as many candidates as they like and eliminations are one-at-a-time)
as better
than the worst Condorcet methods such as Margins and  "BTR-STV".

Chris  Benham

On 17/12/2019 5:42 pm, Rob Lanphier wrote:

On 18/12/2019 06.15, Rob Lanphier wrote:

As Chris Benham pointed out, it fails clone independence. It also
inherits a lot of the compliance failures of IRV (e.g. nonmonotonicity,
no reversal symmetry), and it's not summable. Contrasted with Schulze,
it doesn't tend to elect Minmax winners, and with Ranked Pairs, it fails
LIIA.

I vaguely seem to recall that Warren found out it does worse than
Schulze/RP/etc on Bayesian regret. But I'm not entirely sure of this.

I'm going through the messages of the Condorcet Yahoo group, and it
seems like Alex Small proved something along the lines of BTR-IRV giving
the same winner as Benham with three candidates. Let's see if I can redo
it and make it clearer.

Either we have a Condorcet cycle or there's a CW. If there's a CW, the
equivalence obviously holds. So suppose without loss of generality that
there's an A>B>C>A cycle and that A is the IRV winner. (It's always
possible to relabel the candidates so that this holds.)

When there are two candidates left in IRV, the ultimate IRV winner must
beat the loser pairwise. So given the assumptions above, the full order
must be A>B>C (otherwise, A and C would be in the final round, which
contradicts that A is the IRV winner).

BTR-IRV will first hold a runoff between B and C, and since B beats C
pairwise, B wins. In the next runoff, A wins against B.

Benham will directly eliminate C. In the next round, we have A vs B and
A wins. So the winners are the same.

That seems to show that if you think Smith cycles above three are rare,
then it doesn't matter whether you use Benham or BTR-IRV, because
they'll give the same winner: the CW if there is one, and the IRV winner
if there's a cycle. (Or it almost does: I have to show that the Smith vs
non-Smith runoff rounds don't alter anything.)

But since I'm always adding caveats, BTR-IRV's failure of clone
independence could lead parties to puff up the size of the Smith set in
an attempt to benefit. So if you want a good Smith-IRV hybrid in
general, Benham is better.

The Copeland set is interesting: for instance, it's a subset of the
uncovered set[1]. However, there don't seem to be any good ways to turn
the set into a proper method that satisfies good properties (clone
independence etc).

[1] E.g. proposition 3.2. of
https://researchportal.port.ac.uk/portal/files/1894394/SELCUK_2010_cright_EL_A_characterization_of_the_Copeland_solution.pdf