Document Open Access Logo

Determining a Slater Winner Is Complete for Parallel Access to NP

Author Michael Lampis

PDF
Thumbnail PDF

File

LIPIcs.STACS.2022.45.pdf
  • Filesize: 0.66 MB
  • 14 pages

Document Identifiers

Author Details

Michael Lampis
  • Université Paris-Dauphine, PSL University, CNRS, LAMSADE, 75016, Paris, France

Acknowledgements

I am grateful to Jérôme Lang for letting me know about this problem and for correctly conjecturing that it is complete for Θ₂^p.

Cite AsGet BibTex

Michael Lampis. Determining a Slater Winner Is Complete for Parallel Access to NP. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.STACS.2022.45

Abstract

We consider the complexity of deciding the winner of an election under the Slater rule. In this setting we are given a tournament T = (V,A), where the vertices of V represent candidates and the direction of each arc indicates which of the two endpoints is preferable for the majority of voters. The Slater score of a vertex v ∈ V is defined as the minimum number of arcs that need to be reversed so that T becomes acyclic and v becomes the winner. We say that v is a Slater winner in T if v has minimum Slater score in T. Deciding if a vertex is a Slater winner in a tournament has long been known to be NP-hard. However, the best known complexity upper bound for this problem is the class Θ₂^p, which corresponds to polynomial-time Turing machines with parallel access to an NP oracle. In this paper we close this gap by showing that the problem is Θ₂^p-complete, and that this hardness applies to instances constructible by aggregating the preferences of 7 voters.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Slater winner
  • Feedback Arc Set
  • Tournaments

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: Ranking and clustering. J. ACM, 55(5):23:1-23:27, 2008. Google Scholar
  2. Noga Alon. Ranking tournaments. SIAM J. Discret. Math., 20(1):137-142, 2006. Google Scholar
  3. Georg Bachmeier, Felix Brandt, Christian Geist, Paul Harrenstein, Keyvan Kardel, Dominik Peters, and Hans Georg Seedig. k-majority digraphs and the hardness of voting with a constant number of voters. J. Comput. Syst. Sci., 105:130-157, 2019. Google Scholar
  4. Felix Brandt, Markus Brill, and Paul Harrenstein. Tournament solutions. In Handbook of Computational Social Choice, pages 57-84. Cambridge University Press, 2016. Google Scholar
  5. Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia. Introduction to computational social choice. In Handbook of Computational Social Choice, pages 1-20. Cambridge University Press, 2016. Google Scholar
  6. Richard Chang and Jim Kadin. The Boolean hierarchy and the polynomial hierarchy: A closer connection. SIAM J. Comput., 25(2):340-354, 1996. URL: https://doi.org/10.1137/S0097539790178069.
  7. Pierre Charbit, Stéphan Thomassé, and Anders Yeo. The minimum feedback arc set problem is NP-hard for tournaments. Comb. Probab. Comput., 16(1):1-4, 2007. Google Scholar
  8. Irène Charon and Olivier Hudry. An updated survey on the linear ordering problem for weighted or unweighted tournaments. Ann. Oper. Res., 175(1):107-158, 2010. Google Scholar
  9. Vincent Conitzer. Computing Slater rankings using similarities among candidates. In Proceedings, The Twenty-First National Conference on Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference, July 16-20, 2006, Boston, Massachusetts, USA, pages 613-619. AAAI Press, 2006. URL: http://www.aaai.org/Library/AAAI/2006/aaai06-098.php.
  10. Ronald de Haan. Parameterized Complexity in the Polynomial Hierarchy - Extending Parameterized Complexity Theory to Higher Levels of the Hierarchy, volume 11880 of Lecture Notes in Computer Science. Springer, 2019. URL: https://doi.org/10.1007/978-3-662-60670-4.
  11. Ulle Endriss and Ronald de Haan. Complexity of the winner determination problem in judgment aggregation: Kemeny, Slater, Tideman, Young. In AAMAS, pages 117-125. ACM, 2015. Google Scholar
  12. Edith Hemaspaandra, Lane A. Hemaspaandra, and Jörg Rothe. 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. Google Scholar
  13. Edith Hemaspaandra, Lane A. Hemaspaandra, and Jörg Rothe. Raising NP lower bounds to parallel NP lower bounds. SIGACT News, 28(2):2-13, 1997. URL: https://doi.org/10.1145/261342.261344.
  14. Edith Hemaspaandra, Holger Spakowski, and Jörg Vogel. The complexity of Kemeny elections. Theor. Comput. Sci., 349(3):382-391, 2005. Google Scholar
  15. Olivier Hudry. On the complexity of Slater’s problems. Eur. J. Oper. Res., 203(1):216-221, 2010. Google Scholar
  16. Jörg Rothe, Holger Spakowski, and Jörg Vogel. Exact complexity of the winner problem for Young elections. Theory Comput. Syst., 36(4):375-386, 2003. Google Scholar
  17. Klaus W. Wagner. More complicated questions about maxima and minima, and some closures of NP. Theor. Comput. Sci., 51:53-80, 1987. URL: https://doi.org/10.1016/0304-3975(87)90049-1.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact