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 <[EMAIL PROTECTED]>
To:     [EMAIL PROTECTED]
References: <[EMAIL PROTECTED]> <[EMAIL PROTECTED]> <[EMAIL PROTECTED]>


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

Reply via email to