election-methods@mailman.electorama.com

Technical discussion of election methods

View all threads

Durand: Minimally strategic methods

KM
Kristofer Munsterhjelm
Tue, Jan 11, 2022 5:52 PM

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

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