[EM] Selective Ranked Pairs

[Kristofer Munsterhjelm]

On 8/14/23 13:12, Filip Ejlak wrote:
> Here's a Smith method that seems to be monotonic, cloneproof and DMTC 
> burial resistant (at least in non-tie scenarios):
> 
> 1. List all the pairwise victories.
> 2. For any XYZ cycle with X being the fpA-fpC winner, remove the Z>X 
> majority from the list.
> 3. Proceed with the Ranked Pairs method.
> 
> I'm not sure how to handle ties in order to get total criteria 
> compliance. Also, I will be thankful for some independent checks.

Ties are known to be a point of trouble even for ordinary Ranked Pairs. 
It's NP-complete to determine if some candidate X can win with a 
particular tiebreaking order: 
https://webspace.maths.qmul.ac.uk/felix.fischer/publications/bf_ranked.pdf

The standard fix is to use a random tiebreaker that is itself 
cloneproof, usually the random voter hierarchy: choose a random voter 
and use his preference ranking. Keep drawing new random ballots and fill 
out unspecified preferences with them until every preference is set. 
(E.g. if the first voter voted A=B>C, then you draw ballots until you 
find one that rankes A and B differently, then use that to break its tie.)

> (I've also looked into IRV with donations, but my implementation was 
> painfully clone-dependent - when the winner is cloned, then another 
> candidate may get the opportunity to donate their votes so that they 
> become the winner, as the previous winner's clones have too few votes on 
> their own to influence the elimination process.)

Right. I think there's a way to deal with this that uses IRV's own clone 
independence, but I'm not entirely sure how to do it. Something along 
the lines of: if it's a three candidate election (for the sake of 
simplicity) and A and B get into the final, and usually B would win but 
you can donate to C to make the final A and C instead, then if any 
candidate is cloned, you defer donations until the final round, where 
all the clones will have been eliminated anyway. In effect, using the 
O(phi^n) algorithm for devising strategy against IRV, but only for 
donations instead of arbitrary strategy.

But there could be snags that I'm not seeing right now, of course.

-km