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

[Jobst Heitzig]

Dear Steve,

in my old post 
http://lists.electorama.com/htdig.cgi/election-methods-electorama.com/2004-April/012735.html, 
some simulations are reporterd. There the following sentence is found:

"Judging from who beats whom, max. length, mean length, or sum of
defeats, we get	MAM > River+ > Beatpath."

By this I meant that the MAM winner beat the River winner more often 
than vice versa. That simulation was apparently with 4 or 20 options and 
a heterogeneous electorate where there was "no linearity" in the sense 
that preferences of different voters were not correlated.

Yours, Jobst


Steve Eppley schrieb:
> Hi,
> 
> For a lot more information about the second place finisher, follow the 
> link to the "Immunity from Majority Complaints" criterion (and related 
> criteria) at the following website:
>     http://alumni.caltech.edu/~seppley
> (It's best viewed with the Internet Explorer browser, I think, since it 
> uses a Microsoft character set where Greek symbols are used.  For 
> instance, my Firefox browser renders the epsilon symbol, which means "is 
> an element of," as an I with a caret on top.  Sorry.)
> 
> That webpage includes a proof that the alternative that would be elected 
> by MAM (called Ranked Pairs by some people) if the winner were deleted 
> from all ballots is the alternative that finishes second in the ordering 
> that can be constructed from the acyclic set of majorities MAM 
> identified to select the winner. (Which also happens to be the same as 
> the ordering that minimizes the "largest thwarted majority" in the 
> minileximax sense, which is proved elsewhere in the website.)
> 
> I use the name Maximize Affirmed Majorities (MAM) rather than Ranked 
> Pairs, because Ranked Pairs is the name coined by Nicolaus Tideman for a 
> different voting method he proposed in 1987/1989.  The most important 
> difference is that Tideman's Ranked Pairs measures the size of a 
> pairwise majority for X over Y to be the number of voters who ranked X 
> over Y minus the number of voters who ranked Y over X.  Due to that 
> difference, Tideman's Ranked Pairs fails several criteria met by MAM.  I 
> think the potential for confusion if the name Ranked Pairs is used for a 
> methods other than Tideman's justifies using a different name, hence my 
> preference for the name MAM.
> 
> Jobst, is there any justification for the criterion you mentioned below 
> that's satisfied by Beatpath but not by MAM or River?  "For each 
> beatpath against the winner, there is a stronger (or equally strong) 
> beatpath back."  In scenarios where a losing alternative has a stronger 
> beatpath to the MAM winner and/or the River winner, what is the harm?  
> If there is no harm, why should anyone care about this criterion?
> 
> I never ran a simulation comparing MAM vs River to see which method's 
> winner is ranked over the other's winner more often over the long run.  
> Has anyone run that simulation?  The MAM vs Beatpath simulation showed 
> that MAM winners are ranked over Beatpath winners over the long run.  
> For more details, follow the link at the website above to "MAM vs 
> PathWinner."
> 
> Regards,
> Steve
> ----------------------------------------------------------------------
> Jobst Heitzig wrote:
>> 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
>> ----
>> Election-Methods mailing list - see http://electorama.com/em for list 
>> info
>>
> ----
> Election-Methods mailing list - see http://electorama.com/em for list info