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

DOI10.4230/LIPICS.MFCS.2017.57MaRDI QIDQ5111273zbMATHOpenAlexFDO

Authors Palash Dey, Neeldhara Misra

Publication date 26 May 2020

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1288298 (Why is no real title available?)
• Determining possible and necessary winners given partial orders
• Frugal bribery in voting
• Handbook of Computational Social Choice
• Kernelization complexity of possible winner and coalitional manipulation problems in voting
• New candidates welcome! Possible winners with respect to the addition of new candidates
• On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard
• Parameterized algorithms
• Partial kernelization for rank aggregation: theory and experiments
• 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

Cited in

(10)

• Determining possible and necessary winners given partial orders
• Complexity of manipulation with partial information in voting
• Manipulative elicitation -- a new attack on elections with incomplete preferences
• On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard
• Possible and necessary winners of partial tournaments
• Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers
• A parameterized perspective on protecting elections
• Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules
• On the exact amount of missing information that makes finding possible winners hard
• Taking the final step to a full dichotomy of the possible winner problem in pure scoring rules

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)