[EM] minx(fpA-fpC) DMTBR counterexample?
Kristofer Munsterhjelm
km_elmet at t-online.de
Sat Apr 16 04:05:23 PDT 2022
Define the fpA-fpC scores for three candidates like this:
- If W is the CW, then W gets score equal to |V|, the number of voters;
and the other two get score 0
- If the Smith set is size 2, both get |V|/2 and the final candidate gets 0
- Otherwise the scores are as in fpA-fpC. If the cycle is A=B>C>A, then
B is counted as if A beat him pairwise.
Now define minx(fpA-fpC) as the following:
- fpA-fpC restricted to a three-set is the fpA-fpC election with every
candidate but those three eliminated.
- A's score is the vector of three-candidate fpA-fpC scores of every
three-set that includes A.
- The candidate with the greatest leximin score wins.
Clearly, this method is monotone because raising A can't decrease A's
score on any three-set containing A, due to three-candidate fpA-fpC
being monotone. And it's summable because we only need the Condorcet
matrix, as well as three Plurality count values for every three-set.
Can anyone find a DMTBR counterexample for minx(fpA-fpC)? I haven't been
able to for either four or five candidates. Since DMTBR plus Condorcet
and either monotonicity or summability is a high bar in itself, I want
to be *very* sure before proclaiming that I've accomplished something
spectacular.
Even proving plain DMT is hard! I think the logic is something like: a
candidate outside of the DMT set will have very low scores when matched
up against someone *in* the DMT set. No amount of extremely good scores
elsewhere can compensate for that when the metric is leximin. On the
other hand, someone *in* the DMT set will not get these very low scores
against other candidates.
A test election:
3: A>B>C>D
1: B>C>D>A
2: C>D>A>B
1: C>D>B>A
The sorted score arrays, according to my implementation, are:
A: (0, 0, 0)
B: (-2, -2, 7)
C: (0, 2, 7)
D: (0, 0, 2)
so the social order is C>D>A>B.
My manipulability check gives the following exact results for
Smith,minx(fpA-fpC):
4 candidates, 4 voters: manipulable 475/768 (0.62), 9% tied
4 candidates, 5 voters: manipulable 1165/4608 (0.25), <0.1% tied
To compare, here's Smith,IRV:
4 candidates, 4 voters: manipulable 1129/2304 (0.49), 22% tied
4 candidates, 5 voters: manipulable 215/1152 (0.19), <0.1% tied
Smith,IFPP:
4 candidates, 4 voters: manipulable 1189/2304 (0.52), 20% tied
4 candidates, 5 voters: manipulable 1585/6912 (0.23), <0.1% tied
and Smith,Ext-Minmax:
4 candidates, 4 voters: manipulable 379/576 (0.66), 7% tied
4 candidates, 5 voters: manipulable 3655/6912 (0.53), 3% tied
With 4 voters, tie-breaking matters a lot (the nitty-gritty as it were).
But with five, there's a threshold of sorts with strategy resistant
methods having 20%-30% susceptibility and not so strategy resistant ones
having 50% or more, and minx(fpA-fpC) is on the right side of this divide.
More information about the Election-Methods
mailing list