[EM] Revised: Instant Pairwise Elimination (IPE)

[Kristofer Munsterhjelm]

On 16/01/2020 01.36, VoteFair wrote:
> On 1/14/2020 2:34 PM, Kristofer Munsterhjelm 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.
> 
> 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.)

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.