[EM] Ranked Pairs

[Kristofer Munsterhjelm]

On 9/13/23 09:18, Colin Champion wrote:
> I notice that RP is the only election method mentioned by name in the 
> Virginia agenda.
> 
> A while ago I ran some simulations on elections with truncated ballots. 
> Something I noticed was that the presence of RP in the list of methods 
> made the software unacceptably slow. I didn't look into the cause, but 
> there's a natural explanation, which is the fact that RP is known to be 
> NP-complete when it deals correctly with tied margins, i.e. by 
> exhausting over all their permutations. Presumably if some candidates 
> are unpopular and ballots are extensively truncated, then tied margins 
> are much likelier than with complete ballots.
> 
> I gather that practical implementations of RP choose a random 
> permutation rather than exhausting. This seems to me to bring a danger. 
> The presence of a few vanity candidates (truncated off almost all 
> ballots) may lead to ties, and this may lead to a comfortable winner 
> looking as though he owes his victory to a coin-toss. Obviously this 
> undermines the legitimacy of his win.

Since RP passes LIIA and Smith, it should be possible to answer such 
suspicion by first doing RP, then eliminating every candidate ranked 
below the lowest ranked Smith set candidate, and then showing that the 
ranking between the remaining candidates does not change.

-km