Economics Faculty Database
Economics
Arts & Sciences
Duke University

 HOME > Arts & Sciences > Economics > Faculty    Search Help Login pdf version printable version 

Publications [#236246] of Vincent Conitzer

Journal articles or Book chapters PUBLISHED

  1. Xia, L; Conitzer, V, A sufficient condition for voting rules to be frequently manipulable, Proceedings of the ACM Conference on Electronic Commerce (December, 2008), pp. 99-108, ACM Press [doi]
    (last updated on 2024/03/28)

    Abstract:
    The Gibbard-Satterthwaite Theorem states that (in unrestricted settings) any reasonable voting rule is manipulable. Recently, a quantitative version of this theorem was proved by Ehud Friedgut, Gil Kalai, and Noam Nisan: when the number of alternatives is three, for any neutral voting rule that is far from any dictatorship, there exists a voter such that a random manipulation - -that is, the true preferences and the strategic vote are all drawn i.i.d., uniformly at random - -will succeed with a probability of Ω(1/n), where n is the number of voters. However, it seems that the techniques used to prove this theorem can not be fully extended to more than three alternatives. In this paper, we give a more limited result that does apply to four or more alternatives. We give a sufficient condition for a voting rule to be randomly manipulable with a probability of Ω(1/n) for at least one voter, when the number of alternatives is held fixed. Specifically, our theorem states that if a voting rule r satisfies 1. homogeneity, 2. anonymity, 3. non-imposition, 4. a canceling-out condition, and 5. there exists a stable profile that is still stable after one given alternative is uniformly moved to different positions; then there exists a voter such that a random manipulation for that voter will succeed with a probability of Ω(1/n). We show that many common voting rules satisfy these conditions, for example any positional scoring rule, Copeland, STV, maximin, and ranked pairs. Copyright 2008 ACM.


Duke University * Arts & Sciences * Economics * Faculty * Research * Staff * Master's * Ph.D. * Reload * Login