[EM] Method X, bummer

[Forest Simmons]

On Sat, Aug 5, 2023, 4:52 AM Kristofer Munsterhjelm <km_elmet at t-online.de>
wrote:

> 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.
>

Do you consider Implicit Approval Chain Climbing to be burial resistant?

It certainly punishes the burying faction on all of the examples Chris gave
highlighting his MinLosingVotes Pairwise Margins method.

As a reminder it is the only Banks efficient monotone, clone independent,
Universal Domain method that we know of so far.

In general, Agenda Based Chain Climbing is monotone when the agenda
formation is monotone ... so Borda and Kemeny Chain Climbing are also Banks
efficient monotone methods that are probably burial resistant, but neither
one is clone proof.

In general, elimination with "take down" is Banks efficient ... but not
monotone unless based on a fixed (no renormalization between eliminations)
monotone agenda.

Implicit Approval is monotone and clone proof and UD, but just barely UD.
It is maddenly frustrating trying to find another UD monotone, clone proof
agenda forming method.

>
> 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
> ----
> Election-Methods mailing list - see https://electorama.com/em for list
> info
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20230805/91b85e1f/attachment.htm>