IJCAI11ContentsIndexHelpTermsIJCAI WebsiteApproximately Strategy-Proof VotingEleanor Birrell∗and Rafael Pass†Cornell University{eleanor,rafael}@cs.cornell.eduAbstractThe classic Gibbard-Satterthwaite Theorem estab-lishes that only dictatorial voting rules are strategy-proof; under any other voting rule, players have anincentive to lie about their true preferences. Weconsider a new approach for circumventing thisresult: we consider randomized voting rules thatonly approximate a deterministic voting rule andonly are approximately strategy-proof. We showthat any deterministic voting rule can be approxi-mated by an approximately strategy-proof random-ized voting rule, and we provide asymptoticallytight lower bounds on the parameters required bysuch voting rules.1 IntroductionThe classic Gibbard-Satterthwaite Theorem[Gibbard, 1973;Satterthwaite, 1975]considers the question of when voterswill honestly report their preferences. It shows that if thevoting rule has at least three outcomes, then only dictatorialfunctions (i.e., one player determines the output) can be hon-estly computed by rational agents.The earliest approach to circumventing this limitation, firstsuggested by Gibbard[1977]and later advocated by Conitzerand Sandholm[2006], consists of using randomized approxi-mations as a means to bypass the limitations of deterministicrules. Unfortunately, the potential of this approach is lim-ited by two negative results. Gibbard showed that the onlystrategy-proof randomized voting rules are trivial in that theyconsist of simple probability distributions over rules that de-pend on only one voter (unilateral rules) and rules that haveat most two possible outputs (duple rules). In recent work,Procaccia[2010]quantified the quality of approximation thatcan be achieved by such trivial functions (for certain typesof voting rules): in particular, he constructed a simple ap-proximation of PLURALITY (the voting rule that returns theoutcome that receives the most first-choice votes). However,∗This material is based upon work supported under a NationalScience Foundation Graduate Research Fellowship†Supported in part by a Alfred P. Sloan Fellowship, MicrosoftNew Faculty Fellowship, NSF CAREER Award CCF-0746990,AFOSR Award FA9550-08-1-0197, BSF Grant 2006317.his approximation only guarantees that the expected numberof votes received by the returned output is 2/3 the number re-ceived by the true winner, and he proves that his mechanismis asymptotically optimal.An alternative approach that consists of restricting the classof preference functions. Notably, Moulin[1980]considersvoting rules defined over an output set with a natural totalordering with single-peaked preferences, that is utilities thathave an optimal outcome (the peak) and decrease monoton-ically with distance from the peak. He constructs rules thatare strategy-proof with respect to this (very restricted) classof utility functions.A final intriguing approach to circumventing this limita-tion, first suggested by Bartholdi et al.[1989], is to con-struct voting rules that are computationally difficult to ma-nipulate. However, there are strong impossibility results thatlimit the potential of this approach. In their original work,Bartholdi et al. showed that many standard voting rules canbe efficiently manipulated. Moreover, recent work demon-strates that for any voting rule, “bad inputs” (preference pro-files that admit a successful non-honest strategy) are notrare[Conitzer and Sandholm, 2006; Friedgut et al., 2009;Isaksson et al., 2010]; these papers develop lower bounds forthe number of preference profiles which admit some kind ofmanipulation and show that when the number of outputs issmall it is easy to find successful manipulations.In this work, we consider a new approach to circumventingthese previous negative results: approximately strategy-proofvoting rules. This approach is motivated by the observationthat previous work assumes that people will deviate from thehonest strategy even if the improvement in their utility is ex-tremely small. In practice, people often don’t deviate if thegain is very small; a small gain in utility may be offset by apsychological cost associated with lying or by the computa-tional cost of computing an effective deviation[Halpern andPass, 2010]. This phenomenon is compounded by the factthat when risk-averse individual voters are uncertain aboutthe preferences of the other voters, they may not pursue adeviation that is only expected to yield a small benefit. Inother contexts, these observations have led to the introduc-tion of relaxed solution concepts (e.g., ε-Nash equilibria andε-dominant strategies). In the context of voting, we thus con-sider ε-strategy-proof voting rules; that is voting rules forwhich no deviating strategy can improve a player’s expected67Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligenceutility by more than ε.Unfortunately, a corollary of the Gibbard-Satterthwaitetheorem shows that the only deterministic voting rules thatare ε-strategy-proof are dictatorial rules. We thus considerapproximate strategy-proofness in the context of randomizedvoting rules. As it turns out, the parameter ε quite sharplydetermines whether or not there exist non-trivial ε-strategy-proof voting rules.For the remainder of this section, let n be the number ofvoters and let the number of outcomes be a fixed constant k.ε = ω(1/n): In this regime, we show that there exist nat-ural, non-trivial, ε-strategy-proof voting rules. Moreover, weshow that every deterministic voting rule f can be approx-imated by a non-trivial, ε-strategy-proof voting rule g.To-wards formalizing this, we require a notion of what it meansfor a randomized mechanism to approximate a deterministicvoting rule. Intuitively, we want to capture the idea that withhigh probability, the output of g is “close” to that of f.Todefine closeness, we consider a specialized distance metricinspired by the idea of vote corruption, that is the observationthat in real-life elections, votes get miscounted, recounted,lost, etc. We say that the output y ∈ g(x) is δ-close to theright answer if there exists some vector xthat differs from xin only δ positions, such that f (x)=y; in other words, whenthe output is δ-correct, it means that we could have reachedthis output by flipping only δ votes. Our main theorem cannow be informally stated as follows:Theorem 1.1