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