[EM] Revised: Instant Pairwise Elimination (IPE)

[Kristofer Munsterhjelm]

On 14/01/2020 01.03, VoteFair wrote:
> On 1/13/2020 7:56 AM, C.Benham wrote:
>> I missed the earlier discussion on this.
>> ...
>> And what exactly is a "pairwise-losing candidate"?
> 
> 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."
> 
>> Just curious.
> 
> Curiosity is what led me to election-method reform. Thanks for asking.

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