Document Open Access Logo

On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard

Authors Palash Dey, Neeldhara Misra

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.57.pdf
  • Filesize: 0.54 MB
  • 14 pages

Document Identifiers

Author Details

Palash Dey
Neeldhara Misra

Cite As Get BibTex

Palash Dey and Neeldhara Misra. On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 57:1-57:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.MFCS.2017.57

Abstract

We consider election scenarios with incomplete information, a situation that arises often in practice. There are several models of incomplete information and accordingly, different notions of outcomes of such elections. In one well-studied model of incompleteness, the votes are given by partial orders over the candidates. In this context we can frame the problem of finding a possible winner, which involves determining whether a given candidate wins in at least one completion of a given set of partial votes for a specific voting rule. 

The Possible Winner problem is well-known to be NP-Complete in general, and it is in fact known to be NP-Complete for several voting rules where the number of undetermined pairs in every vote is bounded only by some constant. In this paper, we address the question of determining precisely the smallest number of undetermined pairs for which the Possible Winner problem remains NP-Complete. In particular, we find the exact values of t for which the Possible Winner problem transitions to being NP-Complete from being in P, where t is the maximum number of undetermined pairs in every vote. We demonstrate tight results for a broad subclass of scoring rules which includes all the commonly used scoring rules (such as plurality, veto, Borda, and k-approval), Copeland^\alpha for every \alpha in [0,1], maximin, and Bucklin voting rules. A somewhat surprising aspect of our results is that for many of these rules, the Possible Winner problem turns out to be hard even if every vote has at most one undetermined pair of candidates.

Subject Classification

Keywords
  • Computational Social Choice
  • Dichotomy
  • NP-completeness
  • Maxflow
  • Voting
  • Possible winner

Metrics

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

References

  1. Dorothea Baumeister, Magnus Roos, and Jörg Rothe. Computational complexity of two variants of the possible winner problem. In Proc. International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 853-860, 2011. Google Scholar
  2. Dorothea Baumeister and Jörg Rothe. Taking the final step to a full dichotomy of the possible winner problem in pure scoring rules. Inf. Process. Lett., 112(5):186-190, 2012. URL: http://dx.doi.org/10.1016/j.ipl.2011.11.016.
  3. Piotr Berman, Marek Karpinski, and Alex D. Scott. Approximation hardness and satisfiability of bounded occurrence instances of SAT. Electronic Colloquium on Computational Complexity (ECCC), 10(022), 2003. URL: http://eccc.hpi-web.de/eccc-reports/2003/TR03-022/index.html.
  4. Nadja Betzler, Robert Bredereck, and Rolf Niedermeier. Partial kernelization for rank aggregation: theory and experiments. In Proc. 5th International Symposium on Parameterized and Exact Computation (IPEC), pages 26-37. Springer, 2010. Google Scholar
  5. Nadja Betzler, Robert Bredereck, and Rolf Niedermeier. Theoretical and empirical evaluation of data reduction for exact kemeny rank aggregation. Autonomous Agents and Multi-Agent Systems, 28(5):721-748, 2014. URL: http://dx.doi.org/10.1007/s10458-013-9236-y.
  6. Nadja Betzler and Britta Dorn. Towards a dichotomy of finding possible winners in elections based on scoring rules. In Proc. 34th Mathematical Foundations of Computer Science (MFCS), pages 124-136. Springer, 2009. Google Scholar
  7. Nadja Betzler, Susanne Hemmann, and Rolf Niedermeier. A Multivariate Complexity Analysis of Determining Possible Winners given Incomplete Votes. In Proc. 21st International Joint Conference on Artificial Intelligence (IJCAI), volume 9, pages 53-58, 2009. Google Scholar
  8. Yann Chevaleyre, Jérôme Lang, Nicolas Maudet, and Jérôme Monnot. Possible winners when new candidates are added: The case of scoring rules. In Proc. 24th International Conference on Artificial Intelligence (AAAI), 2010. Google Scholar
  9. William W. Cohen, Robert E. Schapire, and Yoram Singer. Learning to order things. J. Artif. Int. Res., 10(1):243-270, May 1999. URL: http://dl.acm.org/citation.cfm?id=1622859.1622867.
  10. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3.
  11. Palash Dey. Resolving the complexity of some fundamental problems in computational social choice. CoRR, abs/1703.08041, 2017. URL: http://arxiv.org/abs/1703.08041.
  12. Palash Dey and Neeldhara Misra. On the exact amount of missing information that makes finding possible winners hard. CoRR, abs/1610.08407, 2016. URL: http://arxiv.org/abs/1610.08407.
  13. Palash Dey, Neeldhara Misra, and Y. Narahari. Kernelization complexity of possible winner and coalitional manipulation problems in voting. In Proc. 14th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2015, Istanbul, Turkey, May 4-8, 2015, pages 87-96, 2015. URL: http://dl.acm.org/citation.cfm?id=2772894.
  14. Palash Dey, Neeldhara Misra, and Y. Narahari. Complexity of manipulation with partial information in voting. In Proc. 25th International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, USA, pages 229-235, 2016. URL: http://www.ijcai.org/Abstract/16/040.
  15. Palash Dey, Neeldhara Misra, and Y. Narahari. Frugal bribery in voting. In Proc. 30th AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA., pages 2466-2472, 2016. URL: http://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12133.
  16. Palash Dey, Neeldhara Misra, and Y. Narahari. Kernelization complexity of possible winner and coalitional manipulation problems in voting. Theor. Comput. Sci., 616:111-125, 2016. URL: http://dx.doi.org/10.1016/j.tcs.2015.12.023.
  17. Palash Dey, Neeldhara Misra, and Y. Narahari. Frugal bribery in voting. Theor. Comput. Sci., 676:15-32, 2017. URL: http://dx.doi.org/10.1016/j.tcs.2017.02.031.
  18. Piotr Faliszewski, Yannick Reisch, Jörg Rothe, and Lena Schend. Complexity of manipulation, bribery, and campaign management in bucklin and fallback voting. In Proc. 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 1357-1358. International Foundation for Autonomous Agents and Multiagent Systems, 2014. Google Scholar
  19. Michael R Garey and David S Johnson. Computers and Intractability, volume 174. freeman New York, 1979. Google Scholar
  20. Benjamin G. Jackson, Patrick S. Schnable, and Srinivas Aluru. Consensus genetic maps as median orders from inconsistent sources. IEEE/ACM Trans. Comput. Biology Bioinform., 5(2):161-171, 2008. URL: http://dx.doi.org/10.1145/1371585.1371586.
  21. Kathrin Konczak and Jérôme Lang. Voting procedures with incomplete preferences. In Proc. 19th International Joint Conference on Artificial Intelligence-05 Multidisciplinary Workshop on Advances in Preference Handling, volume 20, 2005. Google Scholar
  22. Jérôme Lang, Maria Silvia Pini, Francesca Rossi, Domenico Salvagnin, Kristen Brent Venable, and Toby Walsh. Winner determination in voting trees with incomplete preferences and weighted votes. Auton. Agent Multi Agent Syst., 25(1):130-157, 2012. Google Scholar
  23. Jérôme Lang, Maria Silvia Pini, Francesca Rossi, Kristen Brent Venable, and Toby Walsh. Winner determination in sequential majority voting. In Proc. 20th International Joint Conference on Artificial Intelligence (IJCAI), volume 7, pages 1372-1377, 2007. Google Scholar
  24. David C McGarvey. A theorem on the construction of voting paradoxes. Econometrica, pages 608-610, 1953. Google Scholar
  25. Hervé Moulin, Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D Procaccia. Handbook of Computational Social Choice. Cambridge University Press, 2016. Google Scholar
  26. David M. Pennock, Eric Horvitz, and C. Lee Giles. Social choice theory and recommender systems: Analysis of the axiomatic foundations of collaborative filtering. In Proc. 17th National Conference on Artificial Intelligence and 12th Conference on on Innovative Applications of Artificial Intelligence, July 30 - August 3, 2000, Austin, Texas, USA., pages 729-734, 2000. URL: http://www.aaai.org/Library/AAAI/2000/aaai00-112.php.
  27. Maria Silvia Pini, Francesca Rossi, Kristen Brent Venable, and Toby Walsh. Incompleteness and incomparability in preference aggregation. In Proc. 20th International Joint Conference on Artificial Intelligence (IJCAI), volume 7, pages 1464-1469, 2007. Google Scholar
  28. Toby Walsh. Uncertainty in preference elicitation and aggregation. In Proc. 22nd International Conference on Artificial Intelligence (AAAI), volume 22, page 3, 2007. Google Scholar
  29. Lirong Xia and Vincent Conitzer. Determining possible and necessary winners under common voting rules given partial orders. J. Artif. Intell. Res., 41(2):25-67, 2011. Google Scholar
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 About DROPS Imprint Privacy Contact