Computational Aspects of Approval Voting

DOI10.1007/978-3-642-02839-7_10MaRDI QIDQ2829683zbMATH OpenOpenAlexFDO

Authors Dorothea Baumeister, Gábor Erdélyi, Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe

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

Mathematics Subject Classification ID

Social choice (91B14) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Voting theory (91B12) Computational methods for problems pertaining to game theory, economics, and finance (91-08)

Cites work

• A heuristic technique for multi-agent planning
• Anyone but him: the complexity of precluding an alternative
• Approval voting: three examples
• Approximability of Dodgson's rule
• Condorcet Social Choice Functions
• Dichotomy for voting systems
• Exact analysis of Dodgson elections
• Exact complexity of the winner problem for Young elections
• Frequency of correctness versus average polynomial time
• Generalized juntas and NP-hard sets
• Going from theory to practice: the mixed success of approval voting
• Guarantees for the success frequency of an algorithm for finding Dodgson-election winners
• How hard is it to control an election?
• Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
• Manipulation of Voting Schemes: A General Result
• Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control
• Single transferable vote resists strategic voting
• Strategic manipulability without resoluteness or shared beliefs: Gibbard-Satterthwaite generalized
• Strategy-proofness and Arrow's conditions: existence and correspondence theorems for voting procedures and social welfare functions
• The computational difficulty of manipulating an election
• Voting schemes for which it can be difficult to tell who won the election

Cited in

(19)

• Studies in Computational Aspects of Voting
• A statistical approach to calibrating the scores of biased reviewers of scientific papers
• Complexity of control by partitioning veto elections and of control by adding candidates to plurality elections
• Multiwinner analogues of the plurality rule: axiomatic and algorithmic perspectives
• The complexity of probabilistic lobbying
• 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
• Resolute control: forbidding candidates from winning an election is hard
• Complexity of control in judgment aggregation for uniform premise-based quota rules
• On the hardness of bribery variants in voting with CP-nets
• Campaign management under approval-driven voting rules
• The shield that never was: societies with single-peaked preferences are more open to manipulation and control
• Complexity of manipulation and bribery in judgment aggregation for uniform premise-based quota rules
• 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
• Taking the final step to a full dichotomy of the possible winner problem in pure scoring rules
• Control complexity in Bucklin and fallback voting: a theoretical analysis
• Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey
• Normalized range voting broadly resists control

This page was built for publication: Computational Aspects of Approval Voting

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