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
