[EM] Durand: Minimally strategic methods

[Kristofer Munsterhjelm]

While checking Google Scholar's citation list for JGA's paper on
Condorcet-IRV, I found this dissertation in French:

https://hal.inria.fr/tel-01242440v2/document

Now my French is extremely basic to be generous, but from what I can
understand, it seems Durand got the same idea I got for determining
optimal strategic methods by using integer programming (10.1.6,
"optimisation linéaire en nombres entires"). He also refers to JGA's
proof that applying Condorcet to most methods can't increase its
strategic susceptibility, and uses Condorcet,IRV (I think?) as a
reference for strategy-resistant methods.

So far, so good; nothing we don't already know.

(There are also some concrete results for very small voter/candidate
elections: e.g. in 3 voters, 3 candidates, every Condorcet method is
equally susceptible, and is manipulable in 1/9 of the elections; and
with 3 voters, 5 candidates, Condorcet-IRV meets the lower bound of
9.26% These values are higher than my results, so comparing our ways of
calculating them might be useful.)

But there seems to be more. 10.1.5 mentions a greedy algorithm
("gluttonous algorithm") based around two theorems: JGA's Condorcet
resistance theorem, and something called a slicing theorem which
apparently shows(?) that minimally manipulable methods rely only on
binary relations between candidates, though not necessarily preference
orders: e.g. "A has a score > 0 in [-10..10] Range and B has a score <
0" would be a binary relation. I don't understand the details about the
algorithm itself, but it seems to be a way of generating
hard-to-manipulate Condorcet voting rules.

So both the existence of an algorithm to create voting methods that are
hard to manipulate, and additional restriction theorems in the vein of
JGA's (i.e. that minimally manipulable methods can be assumed to be of
form X) are interesting. I did a bit more searching and found some
English presentation notes for the dissertation:

https://www.irif.fr/~displexity/Larochelle/votes.pdf and
https://www.irif.fr/~displexity/docpub/6mois/votes.pdf.

Being presentation notes without the actual presentation, they're pretty
hard to decipher, but they contain some simulation results for the
particular voting distribution he uses. It appears that every method's
manipulability approaches unity with enough candidates.

Durand has also written a paper on the Condorcet restriction theorem,
here: https://ebooks.iospress.nl/pdf/doi/10.3233/978-1-61499-672-9-707
and a voting simulator for determining manipulability here:
https://github.com/francois-durand/svvamp (paper:
https://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/download/12242/12288).
Other papers of his can be found here: https://dblp.org/pid/38/11269.html.

Finally, he's also written a paper
https://hal.inria.fr/hal-01009136/document that seems to show that being
cardinal does not really buy you any strategy resistance: for any method
using expressive ballots, as long as a majority can force a particular
outcome, there exists an ordinal system that is no more manipulable than
the cardinal method.

I haven't investigated these other papers and software, though, and it
might still be easier to make a *simple* (or monotone) method that
violates universal domain resist strategy than an ordinal one; or the
optimal cardinal method might enjoy greater VSE for a given level of
manipulability. I'm not sure what the independence assumption implies,
either.

Still, there seem to be interesting things in here. Perhaps someone more
well versed in French could help find the good parts :-)

-km