×

The complexity of Kemeny elections. (English) Zbl 1086.68046

Summary: Kemeny proposed a voting scheme which is distinguished by the fact that it is the unique voting scheme that is neutral, consistent, and Condorcet. Bartholdi, Tovey, and Trick showed that determining the winner in Kemeny’s system is NP-hard. We provide a stronger lower bound and an upper bound matching the lower bound, namely, we show that determining the winner in Kemeny’s system is complete for P\(_{\|}^{\mathrm{NP}}\), the class of sets solvable via parallel access to NP.

MSC:

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
91B12 Voting theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arrow, K., Social Choice and Individual Values (1951), Wiley: Wiley New York, (revised edition, 1963) · Zbl 0984.91513
[2] Bartholdi III, J.; Tovey, C.; Trick, M., Voting schemes for which it can be difficult to tell who won the election, Social Choice Welfare, 6, 157-165 (1989) · Zbl 0672.90004
[3] M.J.A.N. de Caritat, Marquis de Condorcet, Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix. 1785, Facsimile reprint of original published in Paris, 1972, by the Imprimerie Royale, English translation appears in I. McLean and A. Urken, Classics of Social Choice, University of Michigan Press, 1995, pp. 91-112.; M.J.A.N. de Caritat, Marquis de Condorcet, Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix. 1785, Facsimile reprint of original published in Paris, 1972, by the Imprimerie Royale, English translation appears in I. McLean and A. Urken, Classics of Social Choice, University of Michigan Press, 1995, pp. 91-112.
[4] T. Eiter, G. Gottlob, The complexity class \(\operatorname{\Theta;}_2^p\); T. Eiter, G. Gottlob, The complexity class \(\operatorname{\Theta;}_2^p\)
[5] Hemachandra, L., The strong exponential hierarchy collapses, J. Comput. System Sci., 39, 3, 299-322 (1989) · Zbl 0693.03022
[6] Hemaspaandra, E.; Hemaspaandra, L.; Rothe, J., Exact analysis of Dodgson elections: Lewis Carroll’s 1876 voting system is complete for parallel access to NP, J. ACM, 44, 6, 806-825 (1997) · Zbl 0904.68111
[7] E. Hemaspaandra, J. Rothe, Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP, Technical Report Math/Inf/97/14, Institut für Informatik, Friedrich-Schiller-Universität, Jena, Germany, May 1997.; E. Hemaspaandra, J. Rothe, Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP, Technical Report Math/Inf/97/14, Institut für Informatik, Friedrich-Schiller-Universität, Jena, Germany, May 1997. · Zbl 1338.68087
[8] Karp, R., Reducibilities among combinatorial problems, (Miller, R.; Thatcher, J., Complexity of Computer Computations (1972)), 85-103 · Zbl 1467.68065
[9] Kemeny, J., Mathematics without numbers, Daedalus, 88, 571-591 (1959)
[10] Ladner, R.; Lynch, N.; Selman, A., A comparison of polynomial time reducibilities, Theoret. Comput. Sci., 1, 2, 103-124 (1975) · Zbl 0321.68039
[11] Levenglick, A., Fair and reasonable election systems, Behavioral Sci., 20, 34-46 (1975)
[12] McGarvey, D., A theorem on the construction of voting paradoxes, Econometrica, 21, 608-610 (1953)
[13] C. Papadimitriou, S. Zachos, Two remarks on the power of counting, in: Proc. of the Sixth GI Conf. Theoretical Computer Science, Lecture Notes in Computer Science, vol. 145, Springer, Berlin, 1983, pp. 269-276.; C. Papadimitriou, S. Zachos, Two remarks on the power of counting, in: Proc. of the Sixth GI Conf. Theoretical Computer Science, Lecture Notes in Computer Science, vol. 145, Springer, Berlin, 1983, pp. 269-276.
[14] Rothe, J.; Spakowski, H.; Vogel, J., Exact complexity of the winner problem for Young elections, Theory Comput. Systems, 36, 4, 375-386 (2003) · Zbl 1061.90084
[15] H. Spakowski, J. Vogel, \( \operatorname{\Theta;}_2^p\); H. Spakowski, J. Vogel, \( \operatorname{\Theta;}_2^p\) · Zbl 1044.68062
[16] Wagner, K., More complicated questions about maxima and minima, and some closures of NP, Theoret. Comput. Sci., 51, 1-2, 53-80 (1987) · Zbl 0653.03027
[17] Wagner, K., Bounded query classes, SIAM J. Comput., 19, 5, 833-846 (1990) · Zbl 0711.68047
[18] Young, H.; Levenglick, A., A consistent extension of Condorcet’s election principle, SIAM J. Appl. Math., 35, 285-300 (1978) · Zbl 0385.90010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.