[EM] Method X

[Kristofer Munsterhjelm]

On 8/3/23 20:17, Filip Ejlak wrote:
> Method X is cloneproof as well! That makes it even more superior to 
> Kemeny (I think that cloneproofness is a must for a good electoral 
> method). I also think that IIB *is* met, because if a given ballot is 
> not exhausted, it is not irrelevant.
> I'm building something similar to the quadelect program so I can check 
> similar things; indeed the results show that Smith//Method_X is 
> monotonic (if ties are resolved properly), cloneproof and 
> DMTBR-compliant (and of course ISDA-compliant). Finding a method that 
> combines it all is an amazing achievement! A polytime version, if such 
> exists, would certainly be the Holy Grail Method. If it doesn't exist, 
> then the non-polytime version would probably still be the best option - 
> as it was already mentioned, real-life elections wouldn't be at all as 
> computation-costly as it is theoretically possible.

Nice! It's always a good thing to get more evidence that it works!

> Perhaps basing the elimination process on first. pref. Copeland score or 
> "friendly" score instead of simple plurality score should be considered 
> - I guess it might at least make Method X naturally ISDA-compliant, but 
> the criteria compliance and strategy resistance would need to be checked 
> again.

Another idea I've been bouncing around in my mind is to do it Tideman's 
Alternative style, i.e. if there are candidates in the current round who 
aren't in the Smith set (based on the remaining candidates), then 
eliminate all of them before continuing the procedure. It would be more 
strict than Smith//Method X, but it would also eliminate more candidates 
at once, easing the computational burden. Like your proposals, I don't 
know if it would be monotone or keep the strategy resistance.

> Below I present the closest thing to a non-monotonicity example that I 
> found; by the way, you can check if the X score results are correct (and 
> the implementation is OK):
> 
> 1: A>B>D>C
> 1: B>C>A>D
> 1: B>C>D>A
> 1: C>A>B>D
> 1: C>B>A>D
> 1: C>D>A>B
> 1: D>A>B>C
> 2: D>C>A>B
> 1: D>C>B>A
> 
> The scores are A:0, B:5, C:5, D:5, so there's a B-C-D tie.
> But then we raise B by changing CBAD to BCAD and DCBA to DBCA.
> The new scores are A:4, B:5, C:0, D:6, so D wins - B is no longer in the 
> winning tie.
> So if we want to 100% guarantee the monotonicity in all edge cases, we 
> should make sure that such a tie is not resolved by making B the winner.

I can verify that the scores are 0, 5, 5, 5 before, and that after 
raising B they're 4, 5, 0, 6.

I briefly experimented with using first preferences as a tiebreaker; it 
seemed to work -- I didn't get any pushover strategies, and indeed 
Plurality's order for the example above is D>C>B>A, keeping B from first 
place. However, it did slightly increase strategic susceptibility, and 
if you're doing things like Smith//, it could add a remote chance of 
nonmonotonicity through usual Smith//Plurality shenanigans.

I'm thinking that a more consistent or elegant tiebreaker is to use 
leximax: find the next highest score obtainable, then the third highest, 
etc. But it's a real pain to implement (particularly to pass through 
vectors of scores recursively), so I haven't tried yet.

I can't prove that either is monotone because I don't know why method X 
itself is monotone yet :-)

-km