I missed the earlier discussion on this.

So what if an elimination round /does /have a "pairwise-losing
candidate", what then?

And what exactly is a "pairwise-losing candidate"?

Just curious.

Chris Benham

On 13/01/2020 12:14 pm, VoteFair wrote:

On 1/13/2020 7:56 AM, C.Benham wrote:

My apologies. For brevity I omitted the first paragraph of the
description, which is here:

"Instant Pairwise Elimination (IPE) eliminates one candidate at a time.
During each elimination round the candidate who loses every pairwise
contest against every other not-yet-eliminated candidate is eliminated.
The last remaining candidate wins."

Hopefully now the second paragraph will make sense:

"If an elimination round has no pairwise-losing candidate, then the
method eliminates the candidate with the largest pairwise opposition
count, which is determined by counting on each ballot the number of
not-yet-eliminated candidates who are ranked above that candidate, and
adding those numbers across all the ballots. If there is a tie for the
largest pairwise opposition count, the method eliminates the candidate
with the smallest pairwise support count, which similarly counts support
rather than opposition. If there is also a tie for the smallest pairwise
support count, then those candidates are tied and all those tied
candidates are eliminated in the same elimination round."

Curiosity is what led me to election-method reform. Thanks for asking.

Richard Fobes

On 1/13/2020 7:56 AM, C.Benham wrote:

On 14/01/2020 01.03, VoteFair wrote:

The fallback sounds a lot like Raynaud(PO). If I'm right, then it should
always pick the same winner as Raynaud(PO) does.

Proof sketch: call the Smith set according to pairwise opposition the
"PO Smith set". Since Raynaud(wv or margins) passes Smith, Raynaud(PO)
passes PO Smith. Eliminating the Condorcet loser whenever it exists
can't make a method that passes PO Smith fail it.

Now suppose that every candidate not in the PO Smith set has been
eliminated. By definition of the PO Smith set, it has no Condorcet
losers, so IPE will then use the fallback to eliminate all but one
member of that set. Since the fallback uses the same elimination as
Raynaud, the winner must be the Raynaud winner.

Or to put it differently, both Raynaud(PO) and IPE will eliminate every
candidate outside of the PO Smith set. And once that's done, both
methods will use the IPE fallback, which clearly eliminates candidates
in the same order, ending up with the same winner.

As a consequence, if you were to change "pairwise opposition" to
"margins" or "winning votes" in the definition, the IPE variant -- call
it IPE(margins) or IPE(wv) -- would pass Condorcet, Smith, and ISDA.

If I'm right about that reduction, then it automatically follows for IPE
itself:

Summable: O(n^2)
(You can find the Condorcet loser using the Condorcet matrix, and
eliminating someone doesn't change the pairwise counts for other pairs)

Majority: pass
(Suppose X is ranked first by a majority. X has a stronger pairwise
victory over everybody else than anyone else has over him, and X is not
a Condorcet loser. So X will never be eliminated.)

Majority loser: pass
(The majority loser is not in the PO Smith set)

And since pairwise opposition, margins, and wv all agree when nobody
truncates or equal-ranks, and it's possible to make Raynaud fail certain
criteria without using either truncation or equal-rank:

IIA: fail
Monotonicity: fail
Consistency: fail
Burying: fail
Participation: fail

On 1/14/2020 2:34 PM, Kristofer Munsterhjelm wrote:

Highlight from below: The fact that the Raynaud method passes the
Condorcet criterion suggested to me that the two methods could not be
the same.

Apparently my description of the "fallback" method was not clear. So, I
added an example to the Electowiki article:

https://electowiki.org/wiki/Instant_Pairwise_Elimination#Example

Notice that it looks at columns in the pairwise matrix and sums the
pairwise counts in each column -- and looks for the highest sum.

If there is a tie, then it looks at rows in the pairwise matrix (and
sums each row and looks for the smallest sum).

I believe -- but I could be wrong -- that Instant Pairwise Elimination
(IPE) fails the Condorcet criterion. (This would only happen when there
is a Condorcet cycle.)

By design IPE does pass the Condorcet loser criterion.

The fact that the Raynaud method passes the Condorcet criterion
suggested to me that the two methods could not be the same.

I have not seen any other (non-IPE) methods that use pairwise counts and
yet fail the Condorcet criterion.  Is that right?

As a reminder I created IPE to appeal to non-math voters. They don't
care about the Condorcet criterion. Apparently they do care that the
method eliminates just one candidate at a time, the way IRV does. And
based on some feedback they like the idea of eliminating a candidate who
is strongly disliked by a group of voters.

For us math geeks, what I like about IPE is that when pass/fail
frequencies/rates are finally calculated, IPE should perform better than
some methods that are carefully designed to pass specific criteria --
without concern that they might often (rather than rarely) fail other
criteria (which they are known to fail).

Once again I greatly appreciate your sharp mind analyzing the IPE
method. Thank you Kristofer!

Richard Fobes

On 1/14/2020 2:34 PM, Kristofer Munsterhjelm wrote:

On 16/01/2020 01.36, VoteFair wrote:

I see; I thought your fallback was to eliminate the candidate who's on
the losing end of the strongest pairwise victory (by anyone over anyone
else). The fallback as I thought it would have reduced IPE to
Raynaud(PO), but the fallback you've given here does not.

So you should probably disregard what I've said about criterion
compliances. Or you could change the fallback to eliminate the candidate
on the losing end of the strongest pairwise victory :-) It wouldn't take
much to get you all the way to Condorcet.

Though I would make one qualification to my previous sentence. IPE as
you've defined it here is still O(n^2) summable. Consider what happens
when you eliminate a candidate X:

• Every pairwise contest between candidates not involving X stay the same.
• Every pairwise contest including X is removed from the pairwise matrix.

So you can modify a pairwise matrix to the effect of eliminating a
candidate without needing more information than the pairwise matrix
itself -- as long as your criterion of who to eliminate only needs to
use the pairwise matrix.

For instance, Schulze can be stated like this:

1. Find the smallest group of candidates who collectively beat or tie
   everybody else.
2. Eliminate every candidate not in that group. If only one candidate
   remains, he's the winner.
3. Replace the weakest pairwise defeat (between uneliminated candidates)
   with a tie.
4. Go to 1.

And this can be done with only the pairwise matrix.

On 1/22/2020 4:13 PM, Kristofer Munsterhjelm wrote:

OK. I removed
(at https://electowiki.org/wiki/Instant_Pairwise_Elimination)
these two criteria (which I have not found definitions for) because I
don't know if IPE passes or fails them:

• Ranks equal

• Ranks greater than 2

Now the only criteria that Instant Pairwise Elimination (IPE) is
indicated as passing are:

• Condorcet loser

• Resolvable

• Polytime

All other criteria are listed as "fail".

And I specified order N squared for summability (if that's a word).

The recent modification I made enables it to be calculated with just the
pairwise matrix.

Interestingly IPE can be calculated "by hand" on paper just using the
printed pairwise matrix and a calculator.  Each time a candidate is
eliminated, the sums for each row and each column are updated by
subtracting just one pairwise count in each row and each column.

Kristofer, thank you for your feedback!

As a reminder for anyone who is following this discussion, IPE is
intended to have very low failure rates for the "fairness" criteria,
even though there are some cases that cause it to fail almost all the
criteria.  Its advantages will become clearer when failure rates are
used instead of checklists.

Also keep in mind that the method is designed to be easy to understand
for non-math folks.

And admittedly I named it in a way to help clarify that IRV is not the
only "instant" runoff/elimination method.  :)

Richard Fobes

On 1/22/2020 4:13 PM, Kristofer Munsterhjelm wrote: