Towards a dichotomy for the possible winner problem in elections based on scoring rules
From MaRDI portal
Publication:1959429
DOI10.1016/j.jcss.2010.04.002zbMath1232.91168OpenAlexW2116531647MaRDI QIDQ1959429
Publication date: 7 October 2010
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2010.04.002
Abstract computational complexity for mathematical programming problems (90C60) Voting theory (91B12) Economics of information (91B44)
Related Items (26)
Ranking chain sum orders ⋮ The possible winner problem with uncertain weights revisited ⋮ Selections from ordered sets ⋮ On the hardness of bribery variants in voting with CP-nets ⋮ Studies in Computational Aspects of Voting ⋮ The complexity of online manipulation of sequential elections ⋮ Prices matter for the parameterized complexity of shift bribery ⋮ The nearest neighbor Spearman footrule distance for bucket, interval, and partial orders ⋮ Weighted partial order oriented three-way decisions under score-based common voting rules ⋮ Taking the final step to a full dichotomy of the possible winner problem in pure scoring 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 ⋮ How hard is it to tell which is a Condorcet committee? ⋮ Complexity of and algorithms for the manipulation of Borda, Nanson's and Baldwin's voting rules ⋮ The Nearest Neighbor Spearman Footrule Distance for Bucket, Interval, and Partial Orders ⋮ Control complexity in Borda elections: solving all open cases of offline control and some cases of online control ⋮ Multivariate complexity analysis of Swap 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 ⋮ Multivariate Complexity Analysis of Swap Bribery ⋮ Preference elicitation and robust winner determination for single- and multi-winner social choice ⋮ Balanced stable marriage: how close is close enough? ⋮ Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers ⋮ COMPARING AND AGGREGATING PARTIAL ORDERS WITH KENDALL TAU DISTANCES ⋮ Computing possible and certain answers over order-incomplete data
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Taking the final step to a full dichotomy of the possible winner problem in pure scoring rules
- New candidates welcome! Possible winners with respect to the addition of new candidates
- The shield that never was: societies with single-peaked preferences are more open to manipulation and control
- Incompleteness and incomparability in preference aggregation: complexity results
- Algorithms for the coalitional manipulation problem
- Dichotomy for voting systems
- On the parameterized complexity of multiple-interval graph problems
- Fixed-parameter algorithms for Kemeny rankings
- Parameterized computational complexity of Dodgson and Young elections
- Parametrized complexity theory.
- Reflections on Multivariate Algorithmics and Problem Parameterization
- When are elections with few candidates hard to manipulate?
- Average Parameterization and Partial Kernelization for Computing Medians
- On Problem Kernels for Possible Winner Determination under the k-Approval Protocol
- Swap Bribery
- Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
- Improved Parameterized Algorithms for the Kemeny Aggregation Problem
- A Richer Understanding of the Complexity of Election Systems
- A Short Introduction to Computational Social Choice
This page was built for publication: Towards a dichotomy for the possible winner problem in elections based on scoring rules
