On the robustness of preference aggregation in noisy environments

ABSTRACT

In an election held in a noisy environment, agents may unintentionally perturb the outcome by communicating faulty preferences. We investigate this setting by introducing a theoretical model of noisy preference aggregation and formally defining the (worst-case) robustness of a voting rule. We use our model to analytically bound the robustness of various prominent rules. The results show that the robustness of voting rules is diverse, with different rules positioned at either end of the spectrum. These results allow selection of voting rules that support preference aggregation in the face of noise.

REFERENCES

• 1: J. Bartholdi, C. A. Tovey, and M. A. Trick. The computational difficulty of manipulating an election. Social Choice and Welfare, 6:227--241, 1989.
• 2: S. J. Brams and P. C. Fishburn. Voting procedures. In K. J. Arrow, A. K. Sen, and K. Suzumura, editors, Handbook of Social Choice and Welfare, chapter 4. North-Holland, 2002.
• 3: 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
• 4: J. D. Dixon and B. Mortimer. Permutation Groups. Springer, 1996.
• 5: Eithan Ephrati , Jeffrey S. Rosenschein, A heuristic technique for multi-agent planning, Annals of Mathematics and Artificial Intelligence, v.20 n.1-4, p.13-67, 1997 [doi>10.1023/A:1018924209812]
• 6: Sumit Ghosh , Manisha Mundhe , Karina Hernandez , Sandip Sen, Voting for movies: the anatomy of a recommender system, Proceedings of the third annual conference on Autonomous Agents, p.434-435, April 1999, Seattle, Washington, United States [doi>10.1145/301136.301303]
• 7: A. Gibbard. Manipulation of voting schemes. Econometrica, 41:587--602, 1973.
• 8: Thomas Haynes , Sandip Sen , Neeraj Arora , Rajani Nadella, An automated meeting scheduling system that utilizes user preferences, Proceedings of the first international conference on Autonomous agents, p.308-315, February 05-08, 1997, Marina del Rey, California, United States [doi>10.1145/267658.267733]
• 9: G. Kalai. Noise sensitivity and chaos in social choice theory. Preprint, http://www.ma.huji.ac.il/~kalai/CHAOS.pdf, 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.

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