[EM] Immunity From Majority Complaints now free of Symbol font (was: Re: Who comes "second" in Ranked Pairs?)

[Steve Eppley]

Hi,

I replaced the Symbol fonts with Unicode in the "Immunity from Majority 
Complaints" html mentioned below. (I also made a few minor grammar 
improvements.)

I also updated the link in my home page to the MAMcalc vote server 
engine.  Its host website had upgraded to PHP 5 which no longer supports 
by default the inclusion of remote files.

It'll be awhile before I replace the Symbol fonts with Unicode in my 
other web pages.  I'm considering writing a Ruby script to automate the 
process.

Regards,
Steve

-------- Original Message --------
Subject: 	Re: [EM] Who comes "second" in Ranked Pairs?
Date: 	Sat, 18 Oct 2008 09:07:38 -0700
From: 	Steve Eppley <SEppley at alumni.caltech.edu>
To: 	election-methods at electorama.com
References: 	<48F45574.6070309 at open-vote.org> 
<48F46CBB.20305 at broadpark.no> <48F51180.7050007 at web.de>


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.