×

Exact analysis of Dodgson elections: Lewis Carroll’s 1876 voting system is complete for parallel access to NP. (English) Zbl 1401.68097

Degano, Pierpaolo (ed.) et al., Automata, languages and programming. 24th international colloquium, ICALP ’97, Bologna, Italy, July 7–11, 1997. Proceedings. Berlin: Springer-Verlag (ISBN 978-3-540-63165-1/pbk; 978-3-540-69194-5/ebook). Lecture Notes in Computer Science 1256, 214-224 (1997).
Summary: In 1876, Lewis Carroll proposed a voting system in which the winner is the candidate who with the fewest changes in voters’ preferences becomes a Condorcet winner – a candidate who beats all other candidates in pairwise majority-rule elections. J. Bartholdi III et al. [Soc. Choice Welfare 6, No. 2, 157–165 (1989; Zbl 0672.90004)] provided a lower bound – NP-hardness – on the computational complexity of determining the election winner in Carroll’s system. We provide a stronger lower bound and an upper bound that matches our lower bound. In particular, determining the winner in Carroll’s system is complete for parallel access to NP, i.e., it is complete for \(\boldsymbol{\Theta}_2^p\), for which it becomes the most natural complete problem known. It follows that determining the winner in Carroll’s elections is not NP-complete unless the polynomial hierarchy collapses.
For the entire collection see [Zbl 1369.68020].

MSC:

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
91B12 Voting theory

Biographic References:

Carroll, Lewis

Citations:

Zbl 0672.90004
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] [BC93]D. Bovet and P. Crescenzi. \(Introduction to the Theory of Complexity\). Prentice Hall, 1993. · Zbl 0809.68067
[2] [Bla58]D. Black. \(Theory of Committees and Elections\). Cambridge University Press, 1958. · Zbl 0091.15706
[3] [BTT89]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:157-165, 1989. · Zbl 0672.90004
[4] [Con85]M. J. A. N. de Caritat, Marquis de Condorcet. \(Essai sur l'Application de L'Analyse à la Probabilité des Décisions Rendues à la Pluraliste des Voix\). 1785. Facsimile reprint of original published in Paris, 1972, by the Imprimerie Royale.
[5] [Dod76]C. Dodgson. A method of taking votes on more than two issues, 1876. Pamphlet printed by the Clarendon Press, Oxford, and headed “not yet published” (see the discussions in [MU95,Bla58], both of which reprint this paper).
[6] [Hem89]L. Hemachandra. The strong exponential hierarchy collapses. \(Journal of Computer and System Sciences\), 39(3):299-322, 1989. · Zbl 0693.03022 · doi:10.1016/0022-0000(89)90025-1
[7] [HHR96]E. Hemaspaandra, L. Hemaspaandra, and J. Rothe. Exact analysis of Dodgson elections: Lewis Carroll’s 1876 voting system is complete for parallel access to NP. Technical Report TR-640, University of Rochester, Department of Computer Science, Rochester, NY, October 1996. · Zbl 0904.68111
[8] [JT95]B. Jenner and J. Torán. Computing functions with parallel queries to NP. \(Theoretical Computer Science\), 141(1-2):175-193, 1995. · Zbl 0873.68058 · doi:10.1016/0304-3975(94)00080-3
[9] [Kad89]J. Kadin. p\^{}{NP[log n]} and sparse Turing-complete sets for NP. \(Journal of Computer and System Sciences\), 39(3):282-298, 1989. · Zbl 0693.68027
[10] [KSW87]J. Köhler, U. Schöning, and K. Wagner. The difference and truth-table hierarchies for NP. \(RAIRO Theoretical Informatics and Applications\), 21:419-435, 1987. · Zbl 0642.03024
[11] [LLS75]R. Ladner, N. Lynch, and A. Selman. A comparison of polynomial time reducibilities. \(Theoretical Computer Science\), 1(2): 103-124, 1975. · Zbl 0321.68039 · doi:10.1016/0304-3975(75)90016-X
[12] [MU95]I. McLean and A. Urken. \(Classics of Social Choice\). University of Michigan Press, 1995.
[13] [Mue89]D. Mueller. \(Public Choice II\). Cambridge University Press, 1989.
[14] [NR76]R. Niemi and W. Riker. The choice of voting systems. \(Scientific American\), 234:21-27, 1976.
[15] [Pap84]C. Papadimitriou. On the complexity of unique solutions. \(Journal of the ACM\), 31(2):392-400, 1984. · Zbl 0631.68038 · doi:10.1145/62.322435
[16] [Pap94]C. Papadimitriou. \(Computational Complexity\). Addison-Wesley, 1994. · Zbl 0833.68049
[17] [SK83]D. Sankoff and J. Kruskal, editors. \(Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison\). Addison-Wesley, 1983.
[18] [Wag87]K. Wagner. More complicated questions about maxima and minima, and some closures of NP. \(Theoretical Computer Science\), 51 (l-2):53-80, 1987. · Zbl 0653.03027 · doi:10.1016/0304-3975(87)90049-1
[19] [Wag90]K. Wagner. Bounded query classes. \(SIAM Journal on Computing\), 19(5):833-846, 1990. · Zbl 0711.68047 · doi:10.1137/0219058
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.