Computational Aspects of Approval Voting
From MaRDI portal
Publication:2829683
DOI10.1007/978-3-642-02839-7_10zbMath1348.91101OpenAlexW1528175708MaRDI QIDQ2829683
Jörg Rothe, Edith Hemaspaandra, Dorothea Baumeister, Hemaspaandra, Lane A., Gábor Erdélyi
Publication date: 8 November 2016
Published in: Studies in Choice and Welfare (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/1802/6722
Voting theory (91B12) Computational methods for problems pertaining to game theory, economics, and finance (91-08) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Social choice (91B14)
Related Items
A statistical approach to calibrating the scores of biased reviewers of scientific papers, Resolute control: forbidding candidates from winning an election is hard, On the hardness of bribery variants in voting with CP-nets, Studies in Computational Aspects of Voting, The complexity of probabilistic lobbying, Normalized range voting broadly resists control, FPT approximation schemes for maximizing submodular functions, Multiwinner analogues of the plurality rule: axiomatic and algorithmic perspectives, Complexity of control in judgment aggregation for uniform premise-based quota rules, Taking the final step to a full dichotomy of the possible winner problem in pure scoring rules, Complexity of manipulation and bribery in judgment aggregation for uniform premise-based quota rules, The shield that never was: societies with single-peaked preferences are more open to manipulation and control, Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey, Control complexity in Borda elections: solving all open cases of offline control and some cases of online control, Campaign management under approval-driven voting rules, Control complexity in Bucklin and fallback voting: a theoretical analysis, Complexity of control by partitioning veto elections and of control by adding candidates to plurality elections, Binary linear programming solutions and non-approximability for control problems in voting systems, Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control, Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers
Cites Work
- Guarantees for the success frequency of an algorithm for finding Dodgson-election winners
- Generalized juntas and NP-hard sets
- Dichotomy for voting systems
- Approval voting: three examples
- Frequency of correctness versus average polynomial time
- Approximability of Dodgson's rule
- Anyone but him: the complexity of precluding an alternative
- Voting schemes for which it can be difficult to tell who won the election
- Single transferable vote resists strategic voting
- How hard is it to control an election?
- Strategy-proofness and Arrow's conditions: existence and correspondence theorems for voting procedures and social welfare functions
- A heuristic technique for multi-agent planning
- Exact complexity of the winner problem for Young elections
- The computational difficulty of manipulating an election
- Strategic manipulability without resoluteness or shared beliefs: Gibbard-Satterthwaite generalized
- Going from theory to practice: the mixed success of approval voting
- Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
- Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control
- Manipulation of Voting Schemes: A General Result
- Condorcet Social Choice Functions
- Exact analysis of Dodgson elections
