[EM] Minimally manipulable methods: preliminary results

[Kristofer Munsterhjelm]

So I got around to actually creating that mixed integer program that can
be used to find the minimally manipulable election method for a small
number of voters and candidates (see
http://lists.electorama.com/pipermail/election-methods-electorama.com//2020-February/002501.html).


(If anyone has access to a powerful computer with lots of memory and/or
a sophisticated commercial solver like AMPL with CPLEX, that might also
help uncover some of the intractables below. I'd be interested :-)

Here's what I found so far:

The constraints for all of these methods are: only fully specified
rankings are allowed (no truncation or equal rank), and no ties are
allowed in the outcome unless explicitly specified.

Note that this inflates the manipulability of some of the methods due to
outcomes that must be tied (e.g. you can relabel A and B and get the
same election - then if A wins with positive probability, B must also
win with positive probability). I'm working on dealing with that issue,
but my code is very ugly, so I haven't fully got around to doing that. I
have tried to minimize the effect for three candidates by using a prime
number of voters, but I don't have the computational luxury to do that
for four candidates.

An election outcome is manipulable if, supposing A wins, it is possible
for the voters who prefer B to A to alter their ballots so that B wins
instead. A method is manipulable on a particular election if there
exists at least one such non-winning candidate B. The average
manipulability is the number of manipulable elections, divided by the
number of total possible elections.

Under "eligible candidates", "Anything goes" means there's no a-priori
restrictions on the winning sets. "Smith efficient" means that the
winner must come from the Smith set. Similarly with "Landau" and
"Copeland" (here, Copeland is considered to be a set, given how often
the Copeland method produces a tie).

For comparison purposes, I have also included the results of the fpA-fpC
method. It's very close to the (rough) optimum for three candidates.

Furthermore, I've included various set-constrained IRV methods. As I
have the results for these by Monte Carlo methods, the manipulability
numbers are uncertain. I've included in parentheses the figures that do
not fit in a 95% confidence interval. For instance, if the output is
0.22(664), that means that 0.220 - 0.229 is within the 95% C.I., but
0.2260-0.2269 is not. The Smith-IRV results are not affected by the
manipulability inflation I talked about earlier.
If every other method in the case in question are monotone, I've marked
the Smith-IRV hybrids (nm) for "not monotone".

Some errors: (intractable) means the MIP solver couldn't even load the
program, going out of memory on my 16 GB computer. (timeout) means I
could not find a solution in a reasonable amount of time. (memory) means
the MIP solver gradually used more and more memory until it failed. In
the latter two cases, I've given the best bounds the solver could
provide before failing.

For nonmonotone methods:

3 candidates:

Eligible       5 voters     7 voters     11 voters       13 voters
-------------  --------     --------     ---------       ---------
Anything goes  0.07142850   0.09090936   (intractable)   (intractable)
Smith-eff.     0.07142850   0.09090936   0.09340659      0.10363848
fpA-fpC        0.07142850   0.09848485   0.09340659      0.10854342

Monotone methods:

3 candidates:

Eligible cddts  5 voters    7 voters     11 voters
--------------- ----------  --------     ---------
Anything goes   0.07142850  0.09090936   (intractable)
Smith-efficient 0.07142850  0.09090936   0.09340659
fpA-fpC         0.07142850  0.09848485   0.09340659

4 candidates, monotone:

Eligible cddts    3 voters     4 voters       5 voters
--------------    ---------    --------       --------
Anything goes     0.21846416   (intractable)  (intractable)
Smith-efficient   0.23692592   * (timeout)    (intractable)
Landau            0.23692592   ** (memory)    (intractable)
Copeland          0.23692592   0.53623878!    0.25482576
Smith//IRV (nm)   0.21(24)     0.36(314)      0.21(831)
Landau//IRV(nm)   0.2(3026)    0.36(520)      0.23(797)
Copeland//IRV(nm) 0.2(664)     0.58(705)     ~0.32 (C.I.: 0.3196, 0.3206)

* 0.31703399 <= x <= 0.49948668
	Cbc0010I After 1172 nodes, 118 on tree, 0.49948668 best solution, best
possible 0.31703399 (179946.20 seconds)... gave up here

** 0.32401229 <= x <= 0.50905932

The election marked !: self-aliasing ties (relabeling candidates lead to
the same election) are handled here.

Handling self-aliasing ties, the best (sum of average manipulabilities)
3- and 4-candidate monotone ISDA clone-independent method, for 3 voters,
has manipulability 0.11904760 for three candidates and 0.26666987 for four.
Dropping the ISDA constraint (but still holding Smith) gives 0.1190476
and 0.24513115 for three and four candidates respectively.

--

Some observations:

- Monotonicity doesn't seem to cost anything for three candidates.
- fpA-fpC is very close to the optimum for three candidates.
- The least manipulable three-candidate method (under "anything goes")
satisfies Condorcet. Perhaps that is true in general? It's not true for
Smith.
- There's an effect where the Copeland set seems to do very badly as the
number of voters increases. This might be analogous to that Landau//IRV
tends to do worse than Smith//IRV with large numbers of voters (not
shown here). I've suspected that the least manipulable Landau method is
considerably more manipulable than Smith as the number of voters grows
large. If I'm right, and it's anything like the effect with Copeland,
then the problem seems to arise when there are lots of natural ties;
perhaps some kind of symmetry-breaking argument would show why.