How similarity helps to efficiently compute Kemeny rankings

ABSTRACT

The computation of Kemeny rankings is central to many applications in the context of rank aggregation. Unfortunately, the problem is NP-hard. We show that the Kemeny score (and a corresponding Kemeny ranking) of an election can be computed efficiently whenever the average pairwise distance between two input votes is not too large. In other words, Kemeny Score is fixed-parameter tractable with respect to the parameter "average pairwise Kendall-Tau distance d_a". We describe a fixed-parameter algorithm with running time 16^[d_a] · poly. Moreover, we extend our studies to the parameters "maximum range" and "average range" of positions a candidate takes in the input votes. Whereas Kemeny Score remains fixed-parameter tractable with respect to the parameter "maximum range", it becomes NP-complete in case of an average range value of two. This excludes fixed-parameter tractability with respect to the parameter "average range" unless P=NP.

REFERENCES

• 1: Nir Ailon , Moses Charikar , Alantha Newman, Aggregating inconsistent information: Ranking and clustering, Journal of the ACM (JACM), v.55 n.5, p.1-27, October 2008 [doi>10.1145/1411509.1411513]
• 2: J. Bartholdi III, C. A. Tovey, and M. A. Trick. Voting schemes for which it can be difficult to tell who won the election. Social Choice and Welfare, 6:157--165, 1989.
• 3: Nadja Betzler , Michael R. Fellows , Jiong Guo , Rolf Niedermeier , Frances A. Rosamond, Fixed-Parameter Algorithms for Kemeny Scores, Proceedings of the 4th international conference on Algorithmic Aspects in Information and Management, p.60-71, June 23-25, 2008, Shanghai, China [doi>10.1007/978-3-540-68880-8_8]
• 4: Nadja Betzler , Jiong Guo , Rolf Niedermeier, Parameterized Computational Complexity of Dodgson and Young Elections, Proceedings of the 11th Scandinavian workshop on Algorithm Theory, July 02-04, 2008, Gothenburg, Sweden [doi>10.1007/978-3-540-69903-3_36]
• 5: Nadja Betzler , Johannes Uhlmann, Parameterized Complexity of Candidate Control in Elections and Related Digraph Problems, Proceedings of the 2nd international conference on Combinatorial Optimization and Applications, p.43-53, August 21-24, 2008, St. John's, Canada [doi>10.1007/978-3-540-85097-7_5]
• 6: R. Christian, M. R. Fellows, F. A. Rosamond, and A. Slinko. On complexity of lobbying in multiple referenda. Review of Economic Design, 11(3):217--224, 2007.
• 7: Vincent Conitzer, Computing slater rankings using similarities among candidates, Proceedings of the 21st national conference on Artificial intelligence, p.613-619, July 16-20, 2006, Boston, Massachusetts
• 8: Vincent Conitzer , Andrew Davenport , Jayant Kalagnanam, Improved bounds for computing Kemeny rankings, Proceedings of the 21st national conference on Artificial intelligence, p.620-626, July 16-20, 2006, Boston, Massachusetts
• 9: V. Conitzer, M. Rognlie, and L. Xia. Preference functions that score rankings and maximun likelihood estimation. In Proc. of 2nd COMSOC, pages 181--192, 2008.
• 10: V. Conitzer and T. Sandholm. Common voting rules as maximum likelihood estimators. In Proc. of 21st UAI, pages 145--152. AUAI Press, 2005.
• 11: Andrew Davenport , Jayant Kalagnanam, A computational study of the Kemeny rule for preference aggregation, Proceedings of the 19th national conference on Artifical intelligence, p.697-702, July 25-29, 2004, San Jose, California
• 12: M. J. A. N. de Caritat (Marquis de Condorcet). Essai sur l'application de l'analyse à la probabilité des décisions redues à la pluralité des voix. Paris: L'Imprimerie Royal, 1785.
• 13: R. G. Downey and M. R. Fellows. Parameterized Complexity. Springer, 1999.
• 14: 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]
• 15: C. Dwork, R. Kumar, M. Naor, and D. Sivakumar. Rank aggregation revisited, 2001. Manuscript.
• 16: P. Faliszewski, E. Hemaspaandra, L. A. Hemaspaandra, and J. Rothe. Llull and Copeland voting broadly resist bribery and control. In Proc. of 22nd AAAI, pages 724--730. AAAI Press, 2007.
• 17: J. Flum , M. Grohe, Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 18: Edith Hemaspaandra , Holger Spakowski , Jörg Vogel, The complexity of Kemeny elections, Theoretical Computer Science, v.349 n.3, p.382-391, 16 December 2005 [doi>10.1016/j.tcs.2005.08.031]
• 19: Claire Kenyon-Mathieu , Warren Schudy, How to rank with few errors, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250806]
• 20: Jon Kleinberg , Eva Tardos, Algorithm Design, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2005
• 21: R. Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006.
• 22: M. Truchon. An extension of the Condorcet criterion and Kemeny orders. Technical report, cahier 98-15 du Centre de Recherche en Économie et Finance Appliquées, Université Laval, Québec, Candada, 1998.
• 23: A. van Zuylen and D. P. Williamson. Deterministic algorithms for rank aggregation and other ranking and clustering problems. In Proc. 5th WAOA, volume 4927 of LNCS, pages 260--273. Springer, 2007.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES

General Terms:
Algorithms

Keywords:
NP-hard problem, exact algorithm, fixed-parameter tractability, rank aggregation, structural parameterization