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

DOI10.1016/j.ipl.2011.11.016zbMath1242.68110arXiv1108.4436OpenAlexW1590328194MaRDI QIDQ413279

Dorothea Baumeister, Jörg Rothe

Publication date: 4 May 2012

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

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

zbMATH Keywords

computational complexityNP-completenessdichotomycomputational social choicepossible winner problem

Mathematics Subject Classification ID

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

Related Items (18)

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

Cites Work

• Unnamed Item
• Algorithms for the coalitional manipulation problem
• Dichotomy for voting systems
• Towards a dichotomy for the possible winner problem in elections based on scoring rules
• Computational Aspects of Approval Voting
• When are elections with few candidates hard to manipulate?
• Swap Bribery
• A Richer Understanding of the Complexity of Election Systems
• The complexity of satisfiability problems

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