[EM] Burlington VT reconsidering IRV 10 years after IRV failed to elect the Condorcet Winner

[Kristofer Munsterhjelm]

On 05/12/2019 12.57, Toby Pereira wrote:
> I think the biggest problem with Schulze, more than that it is
> complicated to explain, is that you're basically asking people to take
> it on trust that it is even a method at all. From the Wikipedia article:
> 
> "It can be proven that {\displaystyle p[X,Y]>p[Y,X]}p[X,Y] >
> p[Y,X] and {\displaystyle p[Y,Z]>p[Z,Y]}p[Y,Z] > p[Z,Y] together
> imply {\displaystyle p[X,Z]>p[Z,X]}p[X,Z] > p[Z,X].^[1]
> <https://en.wikipedia.org/wiki/Schulze_method#cite_note-schulze2011-1>
> ^:§4.1  Therefore, it is guaranteed (1) that the above definition of
> "/better/" really defines a transitive relation
> <https://en.wikipedia.org/wiki/Transitive_relation> and (2) that there
> is always at least one candidate {\displaystyle D}D with {\displaystyle
> p[D,E]\geq p[E,D]}{\displaystyle p[D,E]\geq p[E,D]} for every other
> candidate {\displaystyle E}E."
> 
> "It can be proven". Well thanks. And
> also https://rangevoting.org/SchulzeComplic.html

Wikipedia makes it unnecessarily complex. A beatpath from X to Y is
measured by the strength of its weakest link, and the path is
constructed so that the weakest link is as strong as possible.

If p[X,Y] is the strength of the beatpath from X to Y, and there's a
cycle from X to Y to W to X, then that means that
	- the strongest path from X to W is weaker than the strongest path from
W to X (since W beats X by beatpath),
but also
	- the strongest path from X to W through Y is stronger than the
strongest path from W to X (since X beats Y by beatpath, and Y beats W
by beatpath).

That's a contradiction, because "the strongest path from X to W" must be
at least as strong as the one through Y. So cycles can't happen, so
beatpaths are transitive.

Still complex, but not nearly as daunting as Wikipedia's "it can be
proven" makes it out to be.

> "If the strongest path from L to W, is stronger than, or at least as
> strong as, the strongest path from W to L, and if this
> is /simultaneously/ true for /every/ L, then W is a "Schulze winner."
> Schulze proved the theorem that such a W always exists (at least using
> "margins"; I am confused re the "winning-votes" enhancement)."
> 
> Even less convincing.

That kind of follows from the transitivity. If there are no cycles, you
can imagine running a sorting algorithm with "is p[X,Y] greater than or
equal to p[Y,X]" as the >= operator, and you'd get an unambiguous order
up to ties. Suppose it's a descending sort; then whoever is first in the
sorted list beats or ties everybody else in that list by beatpath.

> I know I'm going a bit off-topic, but what is the estimated probability
> that Schulze and Ranked Pairs would give a different result in a
> real-life election? I'd be surprised if it was more than about 1 in
> 10,000, and where there was a different winner between them, neither
> winner would be so much obviously the "right" winner that it would cause
> protests in the streets if the other one were to win.

It's low, although I couldn't quantify it because I don't know the
distribution of a real-life election after people have become used to
Condorcet. Even the question "would there be lots of Condorcet cycles"
is unknown, and just extrapolating from current elections leads into the
IRV trap (IRV works well on current elections, but then Burlington happens).

I'd probably say RP is better than Schulze, at least as a stepping stone
to proportional representation. It passes LIIA and can thus be used as a
base method for elimination in an STV method that reduces to RP itself
in the single-winner case, yet obeys Droop proportionality in the
multiwinner case.

The drawback is that ties are much messier, and any recount would need
to know just how pairwise ties were broken the first time. But perhaps
that doesn't matter with a very large election; the chance of a perfect
pairwise tie between any pair of candidates could well vanish to zero.

And Schulze is more well known, inasfar as any Condorcet method is well
known :-)