[EM] Who comes "second" in Ranked Pairs?

[Jobst Heitzig]

Hi folks,

you're right, the option ending up second in the ranking constructed in 
RP is also the one that wins when you exclude the first winner. Even 
more so, the whole new ranking is just the old one with the top removed.

There is, by the way, a related major difference between RP and the 
otherwise very similar methods Beatpath (aka Schulze) and River: In 
those two the 2nd place winner (= winner when 1st place winner is 
removed) cannot nearly as easily be determined from the original result.

And in those two methods it can even happen that the 2nd place winner is 
an option which defeats the 1st place winner pairwise. To see this, 
consider a situation with four options A,B,C,D and the following 
pairwise defeats in order of descending defeat strength: B>D, A>C, C>D, 
D>A, A>B, B>C. In this situation Beatpath will elect B 1st and will 
elect A when B is removed. Also River will elect B 1st, locking in the 
defeats B>D>A>C only, and will elect A when B is removed. So under both 
methods the 2nd place winner A defeats the 1st place B. But RP will lock 
in all defeats but D>A, making A the 1st place winner and B the 2nd place.

This property is one of the very few in which RP, Beatpath, and River 
differ. The other two such properties are (ii) that only River fulfills 
IPDA and ISDA, and (iii) only Beatpath fulfills (by definition) the 
requirement that for each beatpath against the winner there is a 
stronger (or equally strong) beatpath back. So each of the three similar 
methods has at least one desirable property the other two don't share.

Yours, Jobst


Kristofer Munsterhjelm schrieb:
> Scott Ritchie wrote:
>> I'm writing a ranked pairs counter as practice for learning python, and
>> I realized I don't know the answer to this question.
>>
>> Suppose I want to know who comes in second in a ranked pairs election.
>> Is it:
>>
>> 1) Run ranked pairs algorithm on the ballots, find that candidate A
>> wins, then purge A from all the ballots and rerun the algorithm to find
>> a new winner and call him the second place candidate OR
>>
>> 2) Run ranked pairs algorithm on the ballots, lock in all pairs in their
>> order that don't create cycles, then look at whom is second in the graph
>> (ie, whoever beats all but A)
>>
>>
>> Or will these two always be the same?  It'd be nice if I could see an
>> example where that's not the case.
> 
> I think they're the same. I don't have proof of this, but I think it was 
> given in an earlier post on this list.
> 
> In any event, your #2 answer is the right one. When you lock in 
> victories, you'll either go through all 0.5*n*(n-1) possible victories, 
> or enough that you have a complete ordering. In either case, you use 
> that ordering as the final result.
> 
> For instance, if you have a situation with candidates A, B, and C, and
> 
> 1. A > B
> 2. B > A
> 3. A > C
> 4. B > C
> 5. C > B
> 
> in that order, you lock A > B, A > C, B > C, which gives A > B > C. Thus 
> B comes in second.
> ----
> Election-Methods mailing list - see http://electorama.com/em for list info