[EM] Strategy-resistant monotone methods

[Kristofer Munsterhjelm]

On 02/09/2016 03:57 AM, Kevin Venzke wrote:
> Hi Kristofer,
> 
> Thanks for the additional details.
> 
> 
> ----- Mail original -----
> De : Kristofer Munsterhjelm <km_elmet at t-online.de>
> À : Kevin Venzke <stepjak at yahoo.fr>; EM list <election-methods at electorama.com>
> Envoyé le : Dimanche 7 février 2016 16h52
> Objet : Re: [EM] Strategy-resistant monotone methods
>>>>
>>>> The best simple linear method I could find was this:
>>>>
>>>> f = fpA - fpC
>>>>
>>>> i.e. a candidate's score is the number of first preferences he has,
>>>
>>>> minus the number of first preferences for whoever is beating him pairwise.
>>>
>>> I think it's clear why this works: the candidate C who beats A doesn't get
>>> "credit" for all C>A votes but only those dedicated to C as first preference.
>>> So, the effect of strategic B>C>A votes (where sincere is B>A>C) is limited
>>> to causing a cycle.
>>
>> Right, it feels a bit like a restricted tactical position in chess,
>> where you know what you need to accomplish, but you can't get your
>> pieces around in time. In other words, there's not enough freedom for
>> the strategic voters to do everything they want to do at once.
>>
>> So intuitively I can see how it works. But I was hoping it'd be possible
>> to derive some kind of theory of methods resistant to strategy, and that
>> intuition doesn't seem to help us much; unless the best way of making a
>> method resist strategy is reducing the freedom in a way analogous to the
>> above.
> 
> That's an interesting way of looking at it. I'm not sure if we could easily
> generalize this reduction of freedom concept though.
> 
> I see the issue much more simply, that the effect (or perhaps "independence")
> of lower preferences needs to be kept low, on the assumption that they might
> be mischief votes. (The possibility that they might NOT be mischief votes 
> usually limits my enthusiasm for these efforts!)

That'd seem intuitive, but neither C/Plurality nor C/Antiplurality do
very well, resistance wise. The simulation provides the following results:

[Condorcet],[ER-Plurality]:
 Impartial Culture: susceptible 78269/100000 = 78.3% of the time, 1547 ties
 Gaussian: susceptible 21595/100000 = 21.6% of the time, 80 ties

[Condorcet],[ER-Antiplurality]:
 Impartial Culture: susceptible 47579/100000 = 47.6% of the time, 1957 ties
 Gaussian: susceptible 20841/100000 = 20.8% of the time, 91 ties.

Plurality passes both LNHelp and LNHarm because it doesn't care about
later preferences at all. Yet it does badly even when its vulnerability
to compromising is reduced by prefixing it by Condorcet. Its IC
susceptibility is greater than the 75% of the advanced reversal
symmetric Condorcet methods even though the latter meet neither LNHelp
nor LNHarm.

> In this scenario, when you have decided in advance that it's going to be a
> Condorcet method, you necessitate that some mischief is going to be possible.
> That's inherent to Condorcet, and the nature of the vulnerability is
> basically the same no matter what you do. So all you can do is try to reduce
> the damage done within the method of cycle resolution.

I agree with this. Condorcet implies some vulnerabilities (and some
incompatibilities in general, e.g. it's impossible to get both
Participation and Condorcet). So the method can be resistant in two
ways: either resistant on its own inside the cycle regime, or resistant
in a way that meshes with the Condorcet completion (i.e. strategy X
would ordinarily be possible, but trying to execute it makes someone you
don't want into the CW).

I also think that you're right about C,IRV working because IRV works.
The main thing Condorcet gives to IRV is compromising resistance (and
some degree of clone resistance, IIRC; see JGA's paper). You lose some
burial resistance and gain some compromising resistance, and in IRV's
case, the trade seems to be worth it. But the question then becomes why
IRV works yet Plurality fails.

> I guess that doesn't cover all the bases, only burial. I doubt push-over is
> really a big deal; in my own simulations I don't recall any sensible methods
> with lots of push-over incentive.

I see push-over more as a problem that hurts honesty than a strategy as
such. If voters find out that they could have had X if only they ranked
him lower, they're understandably going to be upset. Since IRV is
chaotic, it'd be very hard to actually use push-over to cheat or do harm.

One of the reasons that I started with the whole search was that I
suspected that nonmonotonicity was something you'd just have to endure
to get strategy resistance - kind of like Random Ballot in that if you
want resistance, you're going to have to scramble the field so it's
either hard or impossible for strategists to find a consistent strategy.
But the search proved me (somewhat) wrong, since the fpA-fpC method is
monotone yet resists quite well. If I had done more thorough research
before starting, I'd also have remembered that Carey is monotone when
limited to three candidates and that C,Carey is also quite resistant.