[EM] Strategy-proof vs Monotone
Kristofer Munsterhjelm
km_elmet at t-online.de
Wed Jan 19 06:57:55 PST 2022
On 19.01.2022 08:10, Daniel Carrera wrote:
> So recently I've been posting a lot about using simulations to estimate
> which voting systems are most vulnerable or resistant to strategy. That
> was certainly interesting. But as Colin pointed out, strategy resistance
> is not the only goal. One issue that keeps coming to mind is that, I
> think..., all the Condorcet-IRV systems are non-motone. Am I right about
> that? I think all (most?) runoff-based methods non-monotone.
>
> So I guess I have two questions:
>
> 1) How important do you think monotonicity is? I'm not comfortable with
> the idea that you can harm a candidate by ranking him higher, but I
> would say the same thing about failing the participation criterion yet
> all Condorcet methods fail (for reasons I still don't fully understand).
>
> 2) Does anyone know a different class of Condorcet systems that are also
> resilient to strategy?
My optimal strategy simulations seem to indicate that (in the model
we're using) monotonicity is essentially free: you don't lose any
strategic susceptibility by insisting that the method should be
monotone. At least not for c=3 or v<5, c=4. (See below for my results.
If you have Gurobi, perhaps I could send you some of my MIPs to see if
it can solve them quicker; I only have access to Cbc and CPLEX myself.)
However, monotone strategy resistant Condorcet methods are very hard to
understand. I'm still trying to devise a method that's Condorcet, DMTBR,
and monotone, but I haven't had much luck yet. I know through (more or
less) exhaustive search that for three candidates, fpA-fpC and
Smith,Carey are close to optimal. But as Craig himself pointed out,
generalizing to more than three candidates is very tough.
I'd share your position -- I probably would put it like this: common
sense criteria shouldn't be broken unless there's a very good reason for
them to be. In the case of participation, there's a good reason in that
Condorcet is more important; but for mono-raise, it doesn't seem to be
giving up too much.
Of course, the same can be said about Smith and mono-add-top. I suspect
that in the case of complete ballots, Smith is not incompatible with
mono-add-top, although the question remains open (and is seemingly very
hard to prove or disprove). However, Smith and the plurality criterion
combined are incompatible with mono-add-top. If asked, I would say that
the former is better than the latter, but I couldn't justify this
particular decision. There's ultimately some aspect of value judgement
to all of this.
So I guess I would say Mazur's quote about number theory applies to
voting methods too :-)
-km
Results:
If "method" is a set (e.g. "anything goes" or "Smith-efficient") then
the result is for the optimal method that's constrained to electing from
that set. Otherwise, it's a particular voting method. (MC) means
Monte-Carlo, i.e. not exact, and the significant figures encompass the
95% c.i. The model is impartial culture.
For the exact results, I have the susceptibility values in fraction
form, but I've written them in decimal here. There's a tradeoff between
decisiveness and strategic resistance: trivially, a method that returns
every candidate tying for first can never be manipulated. So I've marked
(NT) where I've constrained the method to a minimal number of ties
beforehand: this is necessary to stop "Anything" from having
manipulability zero (due to the aforementioned pathological solution).
When I've included both monotone and nonmonotone methods, the
nonmonotone ones are marked *.
Potentially nonmonotone, 3 candidates:
Method 5 voters 7 voters 9 voters 11 voters 13 voters
-------------- --------- --------- --------- --------- ---------
Anything(NT) 0.0925926 0.1140261 intractable intractable
Condorcet 0.0925926 0.1140261 0.1993789 0.1208137 0.1356658
fpA-fpC 0.0925926 0.1455333 0.2226342 0.1211194 0.1620844
*Benham 0.0925926 0.1455333 0.1993789 0.1211194 0.1606773
*IRV 0.0925926 0.1455333 0.1993789 0.1211935 0.1626362
IFPP 0.0925926 0.1500343 0.2203871 0.1212722 0.1626776
Ext-Minmax 0.3472222 0.4365998 0.5005727 0.5394900 0.5716314
The optimal monotone Smith-efficient method is below IRV in every case,
and fpA-fpC does worse than IRV only with 9 voters. I seem to have lost
the data for the nonmonotone optimal methods, but I also seem to recall
that they have the same manipulability as monotone ones.
Four candidates:
Method 3 voters 4 voters 5 voters
-------------- --------- --------- ---------
Anything(NT) intract. intract.
Smith-eff. 0.2673611
Schwartz 0.2673611 <=0.4635
Landau 0.2673611 <=0.229
Copeland 0.6004743 <=0.380
*Smith//IRV 0.375 0.4900174 0.1866319
*Landau//IRV 0.375 0.4900174 0.2622252
*Copeland//IRV 0.3506944 0.6684028 0.3174450
Smith//E-Minm. 0.3506944 0.6579861 0.5287905
Again the optimal monotone methods do better than IRV (where known).
"intractable" means I couldn't even load the MIP model without going out
of memory. (This was before my recent upgrade, so perhaps I should try
it again...) For the blank fields, I couldn't find my data for these or
there is none because it's intractable.
More information about the Election-Methods
mailing list