[EM] Ranked Pairs
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
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