<div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-family:trebuchet ms,sans-serif;font-size:small"><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Jan 13, 2022 at 8:05 AM Kristofer Munsterhjelm <<a href="mailto:km_elmet@t-online.de">km_elmet@t-online.de</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><br>
Maybe you could get a (very slight?) improvement by ranking the<br>
candidates in reverse social order, e.g. if A is the winner and the<br>
social order is A>B>C>D>E>F, then the B>A faction votes B>F>E>D>C>A.<br>
<br>
Could be worth a try, at least; but 92% of the time for a 6-candidate<br>
election is already pretty good!<br></blockquote><div><br></div><div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">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:</div></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">1) Trivial strategy:</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">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.<br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">2) Simple strategy:</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">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.</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">3) Moderate strategy: (aka JGA strategy)</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">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.</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">4) Advanced strategy: (aka your strategy)</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">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.</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">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:</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">Spatial model<br>N=1</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">method=Benham<br>strategy_iters=10,000<br><br>V , C, 95% c.i.     , trivial, simple , moderate, advanced, majority<br>19, 4, 0.2430-0.2830, 0.943  , 0.0241 , 0.0327  , 0       , 0.546<br>29, 4, 0.2697-0.3100, 0.946  , 0.0288 , 0.0257  , 0       , 0.520<br>29, 5, 0.3990-0.4415, 0.878  , 0.0602 , 0.0623  , 0       , 0.365<br>99, 5, 0.4645-0.5068, 0.877  , 0.0611 , 0.0620  , 0       , 0.310<br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">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.</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">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.</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">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.</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Also, for IRV in particular, there's a shared ballot (JGA setting)<br>
manipulation algorithm with worst case complexity of O(phi^c) where phi<br>
is the golden ratio and c is the number of candidates.<br>
<a href="https://courses.cs.duke.edu/fall09/cps296.1/csecon_hardness_barrier_to_manipulation.ppt" rel="noreferrer" target="_blank">https://courses.cs.duke.edu/fall09/cps296.1/csecon_hardness_barrier_to_manipulation.ppt</a></blockquote><div><br></div><div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">Interesting. Thanks for the link!</div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">> Spatial model + Benham<br>
> V=29, C=3 --> 0.1233-0.1365 (95% c.i.), simple=1.00, majority=0.73<br>
> V=29, C=4 --> 0.2811-0.2989 (95% c.i.), simple=0.97, majority=0.52<br>
> V=29, C=5 --> 0.4186-0.4384 (95% c.i.), simple=0.94, majority=0.37<br>
> V=29, C=6 --> 0.5388-0.5575 (95% c.i.), simple=0.92, majority=0.26<br>
<br>
That's odd: the results are quite close to my impartial culture ones,<br>
and significantly removed from JGA's spatial model ones for IRV. Do you<br>
get results closer to JGA's for V=99?</blockquote><div><br></div><div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">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.</div></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">I've noticed that increasing the number of voters makes elections easier to manipulate; at least in the spatial model.</div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small"><br></div><div class="gmail_default" style="font-family:"trebuchet ms",sans-serif;font-size:small">Cheers,</div></div>-- <br><div dir="ltr" class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><font face="trebuchet ms, sans-serif">Dr. Daniel Carrera</font></div><div dir="ltr"><font face="trebuchet ms, sans-serif">Postdoctoral Research Associate</font></div><div><font face="trebuchet ms, sans-serif">Iowa State University</font></div></div></div></div></div></div></div></div></div></div></div>