[EM] Preliminary simulation of fpA-{sum, max} fpC and compromise vs burial incentive

[Kristofer Munsterhjelm]

So I finally wrote something quick (and hopefully less messy than my 
previous manipulability checker) to determine strategy susceptibility 
for a few voting methods. It's still very unoptimized and thus quite 
slow, but I've attached the Python source to my post. PDFs showing 
results can be found here: 
https://munsterhjelm.no/km/python_vote_strats/ and the Python source is 
available there as well.

This should both give some ideas as to where to take fpA-fpC, as well as 
the relative proportion of compromise vs burial for some Condorcet 
methods. (However, as my figures seem somewhat different from Daniel 
Carrera's, there may still be bugs. So take this with a pinch.)

I'll first note some observations, then explain how to use the Python 
code, and then how to read the bar charts.

For impartial culture, the observations seem to be:

- The two simple fpA-fpC generalizations are not robustly strategy 
resistant the way IRV is. While they do well with three candidates, as 
the number of candidates increases, the susceptibility increases; and at 
10 candidates, it's up at Minmax level.

- That said, even Contingent vote (which is a quick proxy for IRV) gets 
more susceptible to strategy as the number of candidates increases. I 
suspect that for any voting method in impartial culture, and any 
susceptibility level, there exists a sufficiently large number of voters 
and candidates where that method is vulnerable to strategy at least that 
often.

- The simple generalizations also lose strategy resistance when the 
number of voters is increased for more than four candidates, whereas 
Contingent vote and its Smith,Plurality version both seem to level off 
for a fixed number of candidates. See e.g. the contingent 99 voters 5 
candidates graph.

- fpA-max fpC is more resistant than fpA-sum fpC, both in terms of total 
susceptibility and in how much can be accomplished by just burial or 
compromise vs having to do both at once.

- There seems to be a baseline compromise level that all the depicted 
Condorcet methods follow -- see the sum of the blue plus purple bars for 
Copeland, Minmax, and the two fpA-fpC methods. If this really is 
universal, it might be possible to derive results about what that level 
is for *any* Condorcet method as number of voters approaches infinity. 
But I'd need to implement something known to be strategy resistant and 
Condorcet, e.g. Smith//IRV, to know whether the pattern is real or just 
a fluke.

- On some of the graphs, Contingent has a lower susceptibility than 
Smith-Contingent, even for three candidates. On the face of it, this 
shouldn't be possible since there's a proof that "Condorcet else X" is 
never less resistant than X alone, assuming certain majority-based 
criteria hold for X. I think the answer is that my simulation doesn't 
take more complex strategies into account, which means that Contingent 
has quite a few strategies that are neither full compromise nor full 
burial nor both at the same time.

- Smith-Contingent vote is both summable and robust to strategy with the 
number of candidates fixed in IC. This shows that summability and 
robustness is compatible. Furthermore, the method is vulnerable to my 
"nobodies ranked first" problem: if every voter ranked himself first, it 
would be unable to call a winner. So neither ISDA nor (the weaker) 
immunity to the nobodies ranked first problem is required for a method 
to be strategically robust in IC.

("Strategically robust" here would probably mean something close to: 1. 
the method starts at a low susceptibility level for modest number of 
candidates in IC. 2. With not too many candidates, the limit of 
strategic susceptibility as number of voters goes to infinity is not one.)

Note that this is all under impartial culture, which in a sense is the 
most tie-prone of them all. Spatial models might show much less 
potential for strategy.

---

Usage:

The Python code can be used by starting an interactive interpreter (e.g. 
python3 or ipython3), importing the strategy and generators modules, and 
then calling plot_MC_proportions, for instance like this:

strategy.plot_MC_proportions(election_space=generators.strict_ordinal_elections(99, 
5))

Note that burial doesn't yet work with the truncated ballot generators, 
as the burial function doesn't check if the candidate is unranked. And, 
as mentioned, it is very slow. Implementing a cache (for things like the 
current election's Condorcet matrix) would help a lot, as would reusing 
elections, e.g. drawing just 1000 and testing the same 1000 on each 
method instead of drawing 1000 * num methods elections in the 
Monte-Carlo simulator.

The code may understate nonmonotone methods' strategic susceptibility 
because it's possible that e.g. upranking a compromise all the way to 
first may not work but upranking it to second place does, as a 
consequence of pushover. But I don't have any nonmonotone methods 
implemented yet, so that shouldn't be a problem :-)

----

Reading the bar charts:

These are stacked charts, so the total height of a method's bar gives 
how often simple (compromise, burial, or minmaxing/two-sided 
maipulation) strategies work. It doesn't check for more complex 
strategies or coordinated arbitrary-ballot ones, so the total bar may 
still understate susceptibility slightly. But as Daniel Carrera noted 
back in January, most methods' strategy vulnerability can be exploited 
with simple strategies.

The "burial only" bar corresponds to elections where burial worked, but 
compromising didn't. The "compromise only" bar similarly corresponds to 
elections where compromising worked but burial didn't. The "burial and 
compromise" bar is for elections where either strategy worked, and 
"two-sided only" is for elections where two-sided strategy worked but 
neither burial nor compromising worked.

Two-sided strategy is simply putting the candidate you're trying to win 
first and the candidate who used to win last, i.e. doing both burial and 
compromising at once. Burial is putting the winner last, and 
compromising is putting a favored candidate first.

When an election is tested, it's tested for the possibility that the 
group that prefers A to the current winner W can get A elected by 
employing strategy, for any other candidate A. If there exists any such 
A, then the strategy is considered to be successful. In the case of 
ties, what is counted is whether the A>W voters are able to insert A 
into the set of winners.

-km
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ballots.py
Type: text/x-python
Size: 6220 bytes
Desc: not available
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20221123/d18f5a37/attachment-0004.py>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: generators.py
Type: text/x-python
Size: 6669 bytes
Desc: not available
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20221123/d18f5a37/attachment-0005.py>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: methods.py
Type: text/x-python
Size: 7185 bytes
Desc: not available
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20221123/d18f5a37/attachment-0006.py>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: strategy.py
Type: text/x-python
Size: 8126 bytes
Desc: not available
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20221123/d18f5a37/attachment-0007.py>