Towards less Manipulable Voting Systems

Speaker : François Durand
INRIA / Alcatel Lucent Bell Labs
Date: 19/09/2012
Time: 2:00 pm - 3:00 pm
Location: LINCS Meeting Room 40

Abstract

Voting systems can be used in any situation where several entities are to make a decision together. However, the sincere vote may lead to a situation that is not a generalized Nash equilibrium: a group of electors can hide their sincere preferences in order to change the outcome to a candidate they prefer. In that case, we say that the situation is manipulable (i.e. susceptible to tactical voting). Gibbard-Satterthwaite theorem (1973) states that for 3 candidates and more, all voting systems but dictatorship are vulnerable to manipulation. So we would like to know, amongst “reasonable” voting systems, which ones are manipulable with a probability as little as possible. We show that, under quite weak assumptions on the meaning of “reasonable”, such optimal voting systems can be found in the class of systems that depend only on the electors’ preorders of preferences over the candidates and meet Condorcet criterion.