[EM] Strategy-resistant monotone methods

[Kristofer Munsterhjelm]

On 02/07/2016 09:02 PM, Kevin Venzke wrote:
> Hi Kristofer,
> 
> Interesting project. A few thoughts/questions on details:
> 1. I assume your ballots are cast with full, strict rankings.

Yes. Otherwise, I would have more variables, which would make it harder
to cover the whole space. For three candidates and truncation, you'd get

A, B, C, AB, AC, BA, BC, CA, CB + the 6 full rank ones = 21

and equal ranks add more still.

> 2. Does the definition of susceptibility include changes caused by compromise strategy?

It includes any kind of strategy. Basically,

if the winner is W,
and there's some other candidate X different from W,
and there's some ballot that, if a subset of the voters who prefer X to
W all switch to, makes X win,
then the method is susceptible to strategy for that ballot set.

In practice, the check works by repeatedly finding an X, some voters who
prefer X to W, and trying lots of different ballots for them. If any of
those ballots make X win, then success - the method is susceptible.
Otherwise, try another X and repeat. After a while (512 tries, I think),
it'll give up on its own and mark the ballot set as not susceptible.

So it measures susceptibility to constructive strategy ("make Gore win")
rather than destructive strategy ("anybody but Bush"). It's probably
harder to resist destructive than constructive strategy since the former
can let more voters in on the strategy attempt. But within the domain of
constructive strategy, it measures every kind; it doesn't distinguish
between burial, compromising, pushover or any other form.

I have been thinking about making strategy modules that only do burial
(or compromising or pushover) so that I could get better stats on what
kind of strategy the methods are vulnerable to. James did something
similar in his paper. I haven't had the time, though.

> 3. Did you try any issue space models simpler than 4D?

No, but it should be relatively easy to run it on simpler Gaussian
models. I don't have uniform issue space models coded yet. I also tried
writing a ballot generator for what Warren calls the Dirichlet model,
but I got very similar results to IC, so I assumed it was buggy and thus
didn't include the results for it.

If I had infinite time, I would also create a ballot generator that
takes random users and movie subsets from the Netflix data set and ranks
in that order. That would give a somewhat realistic model, although
ratings on a movie site and honest political votes might be somewhat
different anyway.

> More below...
> 
>> De : Kristofer Munsterhjelm <km_elmet at t-online.de>
>> À : EM <election-methods at lists.electorama.com> 
>> Envoyé le : Dimanche 7 février 2016 8h03
>> Objet : [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.

Similarly, I get the impression that C,IRV works in part for the reason
above (e.g. mutual dominant third and burial resistance) and in part
because it's so chaotic. Because it's chaotic and has an exponential
amplification in the worst case, an attempt at strategy can backfire
quite easily.

> You could say the opposite approach to effecting this is in Condorcet//Approval,
> where a strategic lower preference for C gets evaluated (when breaking the
> cycle) with equal weight to the first preference for B.
> 
> I half think the answer to your reversal symmetry question is in there:
> Perhaps reversal symmetry requires too much consideration of the middle rank.

That's possible, but if I give up on monotonicity, nonlinear
reversal-symmetric methods can do relatively well (around 10% on IC if
my simulation is right) .  Those resistant reversal-symmetric methods
seem to look at particular ballot types (e.g. ABC, ACB, BAC, BCA) rather
than the usual aggregates (first preferences, pairwise strengths). I'm
not sure what that means, but either reversal symmetry or monotonicity
on its own is fine enough; it's when you combine them that it becomes a
lot more manipulable.

I'll have to check this more closely to see that my program's working
correctly. Linear reversal symmetric methods don't do very well; with no
constraints but reversal symmetry, they're around 40-50% on IC and 1% on
Gaussian.

>> The linear method is not quite at Condorcet,IRV's level, but the
>> nonlinear methods can do much better. The best one I found there was:
>>
>> f = A>B * min(C>A, A>B)/fpC
>>
>> so in an ABCA cycle:
>>
>> A's score: A>B * min(C>A, A>B)/fpC
>> B's score: B>C * min(A>B, B>C)/fpA
> 
>> C's score: C>A * min(B>C, C>A)/fpB
> 
> So you get the strength of your win, times the strength of the weakest contest
> you were part of, divided by the FPs of the candidate who beat you. That seems
> to work in a similar way, emphasizing first preferences.
> 
> From a mono-raise standpoint it does seem a little weird that if C>A drops,
> it appears that that could hurt A. It's true that fpC would very likely drop
> at the same rate, but I think this should still produce a slightly decreasing
> ratio (i.e. the value of C>A / fpC), which A does not want.

An example of that would be BCA -> BAC. That doesn't alter fpC but it
does alter C>A. Perhaps it decreases the person who would have
benefitted from it more than it decreases A's score. It's hard to tell
with nonlinearity.