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

[Kristofer Munsterhjelm]

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.