[EM] Method X, bummer

[Kristofer Munsterhjelm]

On 8/5/23 05:49, Kevin Venzke wrote:
> Hi Kristofer,
> 
> It wasn't so easy, but regrettably I think I have a monotonicity counter-example:
> 
> 408: B>C>A
> 329: A>C>B
> 126: C>A>B
> 91: C>B>A
> 43: A>B>C  -->  B>A>C
> (total 997)
> 
> For the first round, A and B votes both exceed 1/3rd (332.33) and so only C can be
> eliminated.
> The match-up A:B gives B a very slight win of 499 vs 498 for A. C can't score anything.
> Scores: B 499, A 498, C 0.

I can verify that the scores are B: 499 > A: 498 > C: 0.

> Now change the 43 to B>A>C, theoretically helping B further.
> First round totals become 329 A, 451 B, 217 C. So it is now allowed to eliminate A.
> Both A and B fare worse against C than against each other and so prefer to score off of
> eliminating C.
> B improves its score to 542 while A's score is reduced to 455.
> However, when A is eliminated, C can score 546 from their matchup with B.
> New scores: C 546, B 542, A 455.

And I can verify that the scores are C: 546 > B: 542 > A: 455.

Well done. Well, I would rather have wanted it to be monotone, but it's 
better to know the truth! I guess that makes this "very low 
nonmonotonicity" rather than monotone - now I know how the IRVists feel 
when people complain about nonmonotonicity!

Here's a minimal example produced by linear programming:

1: A>B>C
7: A>C>B
8: B>A>C
3: C>A>B
4: C>B>A

the scores are B: 12 > A: 11 > C: 0, then after changing ABC to BAC the
scores become C: 14 > B: 13 > A: 10.

Interestingly, for your example, fpA-fpC says that the correct ordering 
for the "before" election is C>B>A, whle Carey says B>A>C. My example, 
on the other hand, doesn't have this distinction... but it has a 
Condorcet cycle both before and after, thus showing that Smith//X won't 
solve the problem.

Despite the example showing that X itself isn't monotone, I'm more 
confident now that (properly phrased) DMTBR is compatible with both 
monotonicity and Condorcet. Prior to method X, we only had the fpA-fpC 
generalizations, IFPP, and IRV; the first were only DMTCBR, while the 
latter two were clearly nonmonotone. I was worried that there might be 
an impossibility theorem of some kind proving that monotonicity would be 
forever out of our grasp for burial-resistant Condorcet methods.

I can also use method X to find out just what kind of DMTBR should hold, 
and then build off that. I think I have another idea that could work, 
but it would be so incredibly ugly - basically "IRV with donations".

Or we could try to find out why X comes so close to monotonicity, since 
it's the closest we've got so far. Doing so would require figuring out 
why max A>B ("max votes-for") is monotone, and why Smith//method X also 
seems to be (nearly) monotone, I think.

> One thing I noticed is that modifying the quota rule allows you at one extreme to
> implement IRV (i.e. by saying that only the candidate with the fewest votes can be
> eliminated each round) and at the other extreme to implement "max votes-for wins" (by
> imposing no quota requirement at all). While the latter is monotone, it doesn't satisfy
> majority favorite.

That's right; making the quota more loose (i.e. giving the method more 
candidates to choose eliminations from in a given round) doesn't seem to 
hurt monotonicity until you go past 1/3, but it does hurt strategy 
resistance. Going in the other direction is not strictly possible 
because if you're in an n-way tie, every candidate has exactly 1/n of 
the first preferences. So you would then need to also allow eliminating 
the lowest scorer no matter what. This would make it more like IRV and 
thus compromise its monotonicity (further).

> It's interesting to consider whether any quota rule could at least
> preserve monotonicity and add majority favorite. I'm thinking no, though.
The weakest quota I can think of that will preserve majority is 1/2. 
Suppose A is voted first by a majority. Then A can never be eliminated, 
so for any other candidate B, it eventually ends up being A vs B, and 
since A is a majority favorite, A then wins. However, this is not 
strategy resistant; even a constant quota of 1/3 for everything but the 
final round (which is what I tried first) destroys strategy resistance.

Furthermore, as mentioned above, there seems to be a strange 
relationship between the quota and the degree of nonmonotonicity - at 
least if "Other" is a good indicator. For a three-candidate election, 
1/3 is equivalent to "normal" method X, which we now know is (barely) 
nonmonotone. However, loosening the quota to 1/2 introduces more 
nonmonotonicity; then getting rid of the quota altogether gets us back 
into the monotone domain.

E.g. with fixed quota 1/2, impartial culture, 5 candidates, 97 voters, 
7500 elections:

Burial, no compromise:  218     0.0305793
Compromise, no burial:  1138    0.15963
Burial and compromise:  435     0.0610184
Two-sided:              5297    0.743021
Other coalition strats: 41      0.00575116
==========================================
Manipulable elections:  7129    1

and with fixed quota 1/3:

Burial, no compromise:  403     0.0558017
Compromise, no burial:  1544    0.213791
Burial and compromise:  86      0.0119081
Two-sided:              5149    0.71296
Other coalition strats: 0       0
==========================================
Manipulable elections:  7182    0.994461

-km