Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Encouraging voters to truthfully reveal their preferences in an election has long been an important issue. Previous studies have shown that some voting protocols are hard to manipulate, but predictably used NP-hardness as the complexity measure. Such a worst-case analysis may be an insufficient guarantee of resistance to manipulation.Indeed, we demonstrate that NP-hard manipulations may be tractable in the average-case. For this purpose, we augment the existing theory of average-case complexity with new concepts; we consider elections distributed with respect to junta distributions, which concentrate on hard instances, and introduce a notion of heuristic polynomial time. We use our techniques to prove that a family of important voting protocols is susceptible to manipulation by coalitions, when the number of candidates is constant.

REFERENCES

• 1: Y. Bachrach and J. S. Rosenschein. Achieving allocatively-efficient and strongly budget-balanced mechanisms in the network flow domain for bounded-rational agents. In The Nineteenth International Joint Conference on Artificial Intelligence, pages 1653--1654, Edinburgh, Scotland, August 2005.
• 2: Y. Bachrach and J. S. Rosenschein. Achieving allocatively-efficient and strongly budget-balanced mechanisms in the network flow domain for bounded-rational agents. The Seventh International Workshop on Agent-Mediated Electronic Commerce (AMEC 2005), Utrecht, The Netherlands, July 2005.
• 3: J. Bartholdi and J. Orlin. Single transferable vote resists strategic voting. Social Choice and Welfare, 8(4):341--354, 1991.
• 4: Vincent Conitzer , Jérôme Lang , Tuomas Sandholm, How many candidates are needed to make elections hard to manipulate?, Proceedings of the 9th conference on Theoretical aspects of rationality and knowledge, June 20-22, 2003, Univerity of Indiana, Indiana [doi>10.1145/846241.846268]
• 5: Vincent Conitzer , Tuomas Sandholm, Complexity of manipulating elections with few candidates, Eighteenth national conference on Artificial intelligence, p.314-319, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 6: V. Conitzer and T. Sandholm. Universal voting protocol tweaks to make manipulation hard. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 781--788, Acapulco, Mexico, August 2003.
• 7: E. Elkind and H. Lipmaa. Small coalitions cannot manipulate voting. In International Conference on Financial Cryptography, Lecture Notes in Computer Science. Springer-Verlag, Roseau, The Commonwealth of Dominica, 2005.
• 8: A. Gibbard. Manipulation of voting schemes. Econometrica, 41:587--602, 1973.
• 9: E. Hemaspaandra and L. A. Hemaspaandra. Dichotomy for voting systems. University of Rochester Department of Computer Science Technical Report 861, 2005.
• 10: M. Satterthwaite. Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory, 10:187--217, 1975.
• 11: L. Trevisan. Lecture notes on computational complexity. Available from http://www.cs.berkeley.edu/~luca/notes/complexitynotes02.pdf, 2002. Lecture 12.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Algorithms, Economics, Theory

Keywords:
computational complexity, voting