[EM] Ranked Pairs

Colin Champion colin.champion at routemaster.app
Wed Sep 13 00:18:18 PDT 2023

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.


More information about the Election-Methods mailing list