[EM] Ranked Pairs

Colin Champion colin.champion at routemaster.app
Wed Sep 13 02:38:10 PDT 2023

That's neat. (But... )

On 13/09/2023 11:35, Kristofer Munsterhjelm wrote:
> 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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20230913/becce922/attachment-0001.htm>

More information about the Election-Methods mailing list