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

DOI10.4230/LIPICS.MFCS.2017.57zbMATH Open1447.91053arXiv1610.08407OpenAlexW2964079196MaRDI QIDQ5111273FDOQ5111273

Palash Dey, Neeldhara Misra

Publication date: 26 May 2020

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, $k$-approval, and so on), Copeland${}^{a}lpha$ for every $alphain[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.

Full work available at URL: https://arxiv.org/abs/1610.08407

Recommendations

• Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules
• Determining possible and necessary winners given partial orders
• Towards a dichotomy for the possible winner problem in elections based on scoring rules
• Taking the final step to a full dichotomy of the possible winner problem in pure scoring rules
• Possible and necessary winners of partial tournaments

zbMATH Keywords

NP-completenessvotingdichotomycomputational social choicepossible winnermaxflow

Mathematics Subject Classification ID

Social choice (91B14) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Title not available (Why is that?)
• Partial Kernelization for Rank Aggregation: Theory and Experiments
• Title not available (Why is that?)
• Parameterized Algorithms
• Determining Possible and Necessary Winners Given Partial Orders
• New candidates welcome! Possible winners with respect to the addition of new candidates
• Handbook of Computational Social Choice
• Taking the final step to a full dichotomy of the possible winner problem in pure scoring rules
• Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules
• Frugal bribery in voting
• Kernelization complexity of possible winner and coalitional manipulation problems in voting
• On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard

Cited In (6)

• On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard
• Manipulative elicitation -- a new attack on elections with incomplete preferences
• Complexity of manipulation with partial information in voting
• Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers
• A parameterized perspective on protecting elections
• On the exact amount of missing information that makes finding possible winners hard

This page was built for publication: On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111273)