[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