On the approximability of Dodgson and Young elections

DOI10.1016/j.artint.2012.04.004zbMath1251.91026OpenAlexW2024298276MaRDI QIDQ1761290

Christopher M. Homan, Ioannis Caragiannis, Michal Feldman, Ariel D. Procaccia, Christos Kaklamanis, Jeffrey S. Rosenschein, Nikos Karanikolas, Jason A. Covey

Publication date: 15 November 2012

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.artint.2012.04.004

zbMATH Keywords

approximation algorithmscomputational social choice

Mathematics Subject Classification ID

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

Related Items (6)

On stable rules for selecting committees ⋮ Finding a collective set of items: from proportional multirepresentation to group recommendation ⋮ The complexity of probabilistic lobbying ⋮ Proportional Approval Voting, Harmonic k-median, and Negative Association ⋮ Parameterized computational complexity of Dodgson and Young elections ⋮ Socially desirable approximations for dodgson’s voting rule

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Guarantees for the success frequency of an algorithm for finding Dodgson-election winners
• The learnability of voting rules
• Approximability of Dodgson's rule
• Voting schemes for which it can be difficult to tell who won the election
• Monotonicity paradoxes in the theory of elections
• Strategy-proofness and Arrow's conditions: existence and correspondence theorems for voting procedures and social welfare functions
• Extending Condorcet's rule
• Exact complexity of the winner problem for Young elections
• The Dodgson ranking and its relation to Kemeny's method and Slater's rule
• A comparison of Dodgson's method and the Borda count
• The Dodgson ranking and the Borda count: a binary comparison
• Parameterized computational complexity of Dodgson and Young elections
• A comparison of Dodgson's method and Kemeny's rule
• Multimode Control Attacks on Elections
• A threshold of ln n for approximating set cover
• Some Remarks on Dodgson's Voting Rule
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Manipulation of Voting Schemes: A General Result
• Condorcet Social Choice Functions
• Exact analysis of Dodgson elections
• Socially desirable approximations for dodgson’s voting rule
• Aggregating inconsistent information
• Ordering by weighted number of wins gives a good ranking for weighted tournaments

This page was built for publication: On the approximability of Dodgson and Young elections