Copeland voting: ties matter

ABSTRACT

We study the complexity of manipulation for a family of election systems derived from Copeland voting via introducing a parameter α that describes how ties in head-to-head contests are valued. We show that the thus obtained problem of manipulation for unweighted Copeland^α elections is NP-complete even if the size of the manipulating coalition is limited to two. Our result holds for all rational values of α such that 0 < α < 1 except for α = 1/2. Since it is well known that manipulation via a single voter is easy for Copeland, our result is the first one where an election system originally known to be vulnerable to manipulation via a single voter is shown to be resistant to manipulation via a coalition of a constant number of voters.

REFERENCES

• 1: J. Bartholdi, III and J. Orlin. Single transferable vote resists strategic voting. Social Choice and Welfare, 8(4):341--354, 1991.
• 2: J. Bartholdi, III, C. Tovey, and M. Trick. The computational difficulty of manipulating an election. Social Choice and Welfare, 6(3):227--241, 1989.
• 3: J. Bartholdi, III, C. Tovey, and M. Trick. Voting schemes for which it can be difficult to tell who won the election. Social Choice and Welfare, 6(2):157--165, 1989.
• 4: C. Boutilier, R. Brafman, C. Domshlak, H. Hoos, and D. Poole. CP-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements. Journal of Artificial Intelligence Research, 21:135--191, 2004.
• 5: Vincent Conitzer , Tuomas Sandholm , Jérôme Lang, When are elections with few candidates hard to manipulate?, Journal of the ACM (JACM), v.54 n.3, p.14-es, June 2007 [doi>10.1145/1236457.1236461]
• 6: V. Conitzer and T. Sandholm. Universal voting protocol tweaks to make manipulation hard. In Proceedings of the 18th International Joint Conference on Artificial Intelligence, pages 781--788. Morgan Kaufmann, Aug. 2003.
• 7: V. Conitzer and T. Sandholm. Nonexistence of voting rules that are usually hard to manipulate. In Proceedings of the 21st National Conference on Artificial Intelligence. AAAI Press, July/August 2006.
• 8: A. Copeland. A 'reasonable' social welfare function. Seminar on Mathematics in Social Sciences, University of Michigan, 1951.
• 9: Cynthia Dwork , Ravi Kumar , Moni Naor , D. Sivakumar, Rank aggregation methods for the Web, Proceedings of the 10th international conference on World Wide Web, p.613-622, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372165]
• 10: E. Elkind and H. Lipmaa. Hybrid voting protocols and hardness of manipulation. In The 16th Annual International Symposium on Algorithms and Computation, ISAAC 2005, pages 206--215. Springer-Verlag Lecture Notes in Computer Science #3872, December 2005.
• 11: E. Ephrati and J. Rosenschein. Multi-agent planning as a dynamic search for social consensus. In Proceedings of the 13th International Joint Conference on Artificial Intelligence, pages 423--429. Morgan Kaufmann, 1993.
• 12: P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe. Llull and Copeland voting broadly resist bribery and control. In Proceedings of the 22nd AAAI Conference on Artificial Intelligence, pages 724--730. AAAI Press, July 2007.
• 13: Edith Hemaspaandra , Lane A. Hemaspaandra, Dichotomy for voting systems, Journal of Computer and System Sciences, v.73 n.1, p.73-83, February, 2007 [doi>10.1016/j.jcss.2006.09.002]
• 14: D. McGarvey. A theorem on the construction of voting paradoxes. Econometrica, 21(4):608--610, 1953.
• 15: I. McLean and A. Urken. Classics of Social Choice. University of Michigan Press, 1995.
• 16: A. Procaccia and J. Rosenschein. Junta distributions and the average-case complexity of manipulating elections. Journal of Artificial Intelligence Research, 28:157--181, Feb. 2007.
• 17: Ariel D. Procaccia , Jeffrey S. Rosenschein , Gal A. Kaminka, On the robustness of preference aggregation in noisy environments, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329205]
• 18: R. Stearns. The voting problem. The American Mathematical Monthly, 66(9):761--763, 1959.
• 19: L. Xia, J. Lang, and M. Ying. Stringly decomposable voting rules on multiattribute domains. In Proceedings of the 22nd AAAI Conference on Artificial Intelligence, pages 776--781. AAAI Press, July 2007.
• 20: Michael Zuckerman , Ariel D. Procaccia , Jeffrey S. Rosenschein, Algorithms for the coalitional manipulation problem, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.277-286, January 20-22, 2008, San Francisco, California

INDEX TERMS

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

General Terms:
Algorithms, Theory

Keywords:
computational complexity, multiagent systems, preferences