Taking the final step to a full dichotomy of the possible winner problem in pure scoring rules

DOI10.1016/J.IPL.2011.11.016zbMATH Open1242.68110arXiv1108.4436OpenAlexW1590328194MaRDI QIDQ413279FDOQ413279

Authors: Dorothea Baumeister, Jörg Rothe 

Publication date: 4 May 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Abstract: The Possible Winner problem asks, given an election where the voters' preferences over the candidates are specified only partially, whether a designated candidate can become a winner by suitably extending all the votes. Betzler and Dorn [1] proved a result that is only one step away from a full dichotomy of this problem for the important class of pure scoring rules in the case of unweighted voters and an unbounded number of candidates: Possible Winner is NP-complete for all pure scoring rules except plurality, veto, and the scoring rule with vector (2,1,...,1,0), but is solvable in polynomial time for plurality and veto. We take the final step to a full dichotomy by showing that Possible Winner is NP-complete also for the scoring rule with vector (2,1,...,1,0).

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

Recommendations

• Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules
• Towards a dichotomy for the possible winner problem in elections based on scoring rules
• Determining possible and necessary winners given partial orders
• The possible winner problem with uncertain weights
• On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard

zbMATH Keywords

computational complexityNP-completenessdichotomycomputational social choicepossible winner problem

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Computational Aspects of Approval Voting
• A Richer Understanding of the Complexity of Election Systems
• The complexity of satisfiability problems
• Towards a dichotomy for the possible winner problem in elections based on scoring rules
• When are elections with few candidates hard to manipulate?
• Swap bribery
• Algorithms for the coalitional manipulation problem
• Dichotomy for voting systems

Cited In (21)

• On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard
• Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules
• Weighted partial order oriented three-way decisions under score-based common voting rules
• Complexity of control by partitioning veto elections and of control by adding candidates to plurality elections
• Computing possible and certain answers over order-incomplete data
• Control complexity in Borda elections: solving all open cases of offline control and some cases of online control
• Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers
• The possible winner problem with uncertain weights revisited
• Prices matter for the parameterized complexity of shift bribery
• When winning sets have full dimension
• Approximation and hardness of shift-Bribery
• The complexity of online manipulation of sequential elections
• New candidates welcome! Possible winners with respect to the addition of new candidates
• How hard is it to tell which is a Condorcet committee?
• Complexity of manipulation and bribery in judgment aggregation for uniform premise-based quota rules
• Towards a dichotomy for the possible winner problem in elections based on scoring rules
• Preference elicitation and robust winner determination for single- and multi-winner social choice
• On the evaluation of election outcomes under uncertainty
• On problem kernels for possible winner determination under the \(k\)-approval protocol
• On the exact amount of missing information that makes finding possible winners hard
• The possible winner with uncertain weights problem

This page was built for publication: Taking the final step to a full dichotomy of the possible winner problem in pure scoring rules

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