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.