[EM] Revised: Instant Pairwise Elimination (IPE)

[VoteFair]

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.)

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 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
>