Parameterized computational complexity of Dodgson and Young elections
From MaRDI portal
Publication:2266990
DOI10.1016/j.ic.2009.10.001zbMath1191.68338OpenAlexW2004181309MaRDI QIDQ2266990
Jiong Guo, Nadja Betzler, Rolf Niedermeier
Publication date: 26 February 2010
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2009.10.001
winner determinationfixed-parameter tractabilitycomputational social choicevoting systemsW[2-completeness]
Related Items (15)
On stable rules for selecting committees ⋮ Studies in Computational Aspects of Voting ⋮ Dealing with several parameterized problems by random methods ⋮ Parameterized algorithms for edge biclique and related problems ⋮ Prices matter for the parameterized complexity of shift bribery ⋮ Gerrymandering on graphs: computational complexity and parameterized algorithms ⋮ Improved PTAS for the constrained \(k\)-means problem ⋮ Towards a dichotomy for the possible winner problem in elections based on scoring rules ⋮ An improved kernel for max-bisection above tight lower bound ⋮ Improved kernel results for some FPT problems based on simple observations ⋮ An improved FPT algorithm for almost forest deletion problem ⋮ On the approximability of Dodgson and Young elections ⋮ Improved approximation algorithms for two-stage flowshops scheduling problem ⋮ New kernels for several problems on planar graphs ⋮ Socially desirable approximations for dodgson’s voting rule
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Guarantees for the success frequency of an algorithm for finding Dodgson-election winners
- Algorithms for the coalitional manipulation problem
- Dichotomy for voting systems
- Approximability of Dodgson's rule
- Anyone but him: the complexity of precluding an alternative
- Fixed-parameter algorithms for Kemeny rankings
- Voting schemes for which it can be difficult to tell who won the election
- Extending Condorcet's rule
- Threshold dominating sets and an improved characterization of \(W[2\)]
- Exact complexity of the winner problem for Young elections
- On the approximability of Dodgson and Young elections
- On complexity of lobbying in multiple referenda
- Parametrized complexity theory.
- Integer Programming with a Fixed Number of Variables
- When are elections with few candidates hard to manipulate?
- Exact analysis of Dodgson elections
- A Richer Understanding of the Complexity of Election Systems
- A Short Introduction to Computational Social Choice
This page was built for publication: Parameterized computational complexity of Dodgson and Young elections
