Cette page appartient aux archives web de l'EPFL et n'est plus tenue à jour.
This page belongs to EPFL's web archive and is no longer updated.

Voting

Please submit your comments on the following paper

E. Birrell and R. Pass, 2011, Approximately strategy-proof voting, IJCAI 2011

Posted by Katherine Skirving Larson on Wednesday 25 April 2012 at 16:32
Comments
This paper examines randomized voting rules that approximate deterministic ones and are approximate strategy proof. The problem with deterministic voting rules is that for more than three outcomes only under unilateral (dictatorial) voting rules voters have an incentive to be honest. This can be circumvented by introducing some restrictions in the voting protocols, e.g. by restricting the class of preference functions or by constructing voting rules that are computationally difficult to manipulate. However, this parer relies on another idea, use of randomization and approximation. The main assumption is that people tend not to deviate from the honest strategy unless their gain is sufficiently large. Thus, the paper considers approximate strategy proofs in which voters don't deviate if they only expect to improve their utility functions by small amount. Unfortunately, the only deterministic voting rules that are approximate strategy proof are dictatorial rules. Therefor, the idea is to consider randomized voting rules and analyze approximate strategy proof for those randomized voting rules that approximate desired deterministic voting rule. The main contribution of the paper is that it first proofs the existence of randomized voting rules that approximate the desired deterministic voting rule, and then it shows that plurality voting has no trivial voting rule approximation.
Posted by Goran Radanovic on Tuesday 1 May 2012 at 12:59
This paper proposes approximately strategy-proof voting rules to circumvent the limitation of strategy-proofness by Gibbard-Satterthawite Theorem which states that only dictatorial functions make the voters to report their true preferences. It starts by describing the approaches proposed to overcome this limitation and mentions their weaknesses. The motivation for considering approximately strategy-proof voting rules is that in practice people don't deviate from the honest strategy if the gain in utility is very small. The paper has two main theorems that bound the approximation parameters that can be achieved for voting rules like plurality. First, it shows that there exist natural, non-trivial, w(1/n)-strategy-proof voting rules and every deterministic voting rule can be approximated by such a randomized voting rule. Second, it shows that for small values of epsilon, the randomized voting rule is trivial. In addition it shows that natural voting rules such as plurality cannot be well approximated by such mechanisms. The proposed randomized rules are also collusion-resistant and for neutral voting rules the mechanism is computationally efficient.
Posted by Mehdi Riahi on Wednesday 2 May 2012 at 1:32