[EM] Quick and Clean Burial Resistant Smith, compromise

[Daniel Carrera]

On Thu, Jan 13, 2022 at 8:05 AM Kristofer Munsterhjelm <km_elmet at t-online.de>
wrote:

>
> Maybe you could get a (very slight?) improvement by ranking the
> candidates in reverse social order, e.g. if A is the winner and the
> social order is A>B>C>D>E>F, then the B>A faction votes B>F>E>D>C>A.
>
> Could be worth a try, at least; but 92% of the time for a 6-candidate
> election is already pretty good!
>

Indeed it is. So last night I started running tests with several
strategies, in order of complexity. I wanted to see how often the strategy
can be trivial vs how often it has to be sophisticated. So I'm implemented
four strategies:

1) Trivial strategy:

Everyone who prefers c_k > w_A will put c_k on top, w_A at the bottom, and
leave the other candidates in the voter's preference order. This is a
strategy so simple that can be coordinated with memes and conversations by
the water cooler.

2) Simple strategy:

Everyone who prefers c_k > w_A will vote with the same ballot. The ballot
itself is a random version of c_k > ... > w_A. This one requires more
effort; you have to write the target ballot on a piece of paper and have it
in your pocket.

3) Moderate strategy: (aka JGA strategy)

Like (2), but the conspiracy of c_k > w_A voters has enough insight into
the other voters to run a simulation and pick the optimal ballot to improve
the chances of c_k winning.

4) Advanced strategy: (aka your strategy)

The conspiracy of c_k > w_A voters run an extensive random search through
the ballot phase space to pick a highly optimized ballot to alter the
election. You said in an earlier email that you were using 1,000 elections
and 512 strategies. I increased those to 10,000 elections and 10,000
strategies. This got expensive and I had to run the program in multiple
terminals to get some trivial parallelism that way.


At some point I could implement your "reverse social order" method. That is
more sophisticated than JGA, so it would sit between strategies 3 and 4. In
any event, my program first checks to see if there is a majority. If there
isn't, it tries strategy 1. If that fails, it tries strategy 2, and so on.
Here are the results for the spatial model with N = 1 dimensional issue
space:

Spatial model
N=1
method=Benham
strategy_iters=10,000

V , C, 95% c.i.     , trivial, simple , moderate, advanced, majority
19, 4, 0.2430-0.2830, 0.943  , 0.0241 , 0.0327  , 0       , 0.546
29, 4, 0.2697-0.3100, 0.946  , 0.0288 , 0.0257  , 0       , 0.520
29, 5, 0.3990-0.4415, 0.878  , 0.0602 , 0.0623  , 0       , 0.365
99, 5, 0.4645-0.5068, 0.877  , 0.0611 , 0.0620  , 0       , 0.310


Let me explain. The "95% c.i." is the same that we've been using all along
--- the fraction of elections that are susceptible to manipulation. Then
the "trivial" column shows, out of all the elections that could be
manipulated, what fraction of them could be manipulated with the trivial
strategy. The "simple" column is the fraction of susceptible elections
where "trivial" failed but "simple" succeeded, and so on and so forth. The
"majority" column is the fraction of non-susceptible elections where there
was a simple majority.

For example, for V=19, C=4, I found that 24 - 28% of elections can be
manipulated. Out of those, the overwhelming majority (94%) can be
manipulated with the trivial strategy, and an additional 2.4% and 3.3%
require one of the intermediate strategies. This pattern is typical across
my tests. When the number of candidates increases to 5 there is a greater
need for additional effort, the trivial strategy would work for 88% of
susceptible elections and the simple one would work for 88% + 6% = 94% of
susceptible elections.

I have not been able to find a single election where the first strategies
failed, but the 10,000 random searches through the ballot space produced a
successful strategy. I think that there is strong evidence that, at least
for Benham, successful strategies tend to be pretty dumb and simple.


Also, for IRV in particular, there's a shared ballot (JGA setting)
> manipulation algorithm with worst case complexity of O(phi^c) where phi
> is the golden ratio and c is the number of candidates.
>
> https://courses.cs.duke.edu/fall09/cps296.1/csecon_hardness_barrier_to_manipulation.ppt


Interesting. Thanks for the link!



> > Spatial model + Benham
> > V=29, C=3 --> 0.1233-0.1365 (95% c.i.), simple=1.00, majority=0.73
> > V=29, C=4 --> 0.2811-0.2989 (95% c.i.), simple=0.97, majority=0.52
> > V=29, C=5 --> 0.4186-0.4384 (95% c.i.), simple=0.94, majority=0.37
> > V=29, C=6 --> 0.5388-0.5575 (95% c.i.), simple=0.92, majority=0.26
>
> That's odd: the results are quite close to my impartial culture ones,
> and significantly removed from JGA's spatial model ones for IRV. Do you
> get results closer to JGA's for V=99?


I don't see a huge discrepancy. Note that this was done with N=1, so
considering the low V=29 I don't think it's *that* removed from JGA. Right
now I have only one test with V=99 and that's the one I posted a few
paragraphs above. So for V=99,N=1,C=5 I get 0.4645-0.5068 (95% c.i.) and
that interval contains the 0.487 value reported by JGA on Table 1. So it
looks like it's the number of voters that changed the result.

I've noticed that increasing the number of voters makes elections easier to
manipulate; at least in the spatial model.

Cheers,
-- 
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20220113/4ce97f4d/attachment-0001.html>