Studies in Computational Aspects of Voting
From MaRDI portal
Publication:2908543
DOI10.1007/978-3-642-30891-8_16zbMath1358.68118OpenAlexW2185001042MaRDI QIDQ2908543
Nadja Betzler, Rolf Niedermeier, Jiehua Chen, Robert Bredereck
Publication date: 5 September 2012
Published in: The Multivariate Algorithmic Revolution and Beyond (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-30891-8_16
Analysis of algorithms and problem complexity (68Q25) Voting theory (91B12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Resolute control: forbidding candidates from winning an election is hard, Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control, A Basic Parameterized Complexity Primer, Prices matter for the parameterized complexity of shift bribery, Even more effort towards improved bounds and fixed-parameter tractability for multiwinner rules, Kernelization complexity of possible winner and coalitional manipulation problems in voting, Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey, On the Computational Complexity of Variants of Combinatorial Voter Control in Elections, Control complexity in Bucklin and fallback voting: a theoretical analysis, Exact algorithms for weighted and unweighted Borda manipulation problems, Balanced stable marriage: how close is close enough?, Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers, Parameterized Complexity of Control and Bribery for d-Approval Elections, Combinatorial voter control in elections, Parameterized complexity of control and bribery for \(d\)-approval elections
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- New candidates welcome! Possible winners with respect to the addition of new candidates
- Lower bounds on kernelization
- Complexity of and algorithms for the manipulation of Borda, Nanson's and Baldwin's voting rules
- Confronting intractability via parameters
- Campaign management under approval-driven voting rules
- Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring
- Infeasibility of instance compression and succinct PCPs for NP
- Kernel bounds for disjoint cycles and disjoint paths
- Incompleteness and incomparability in preference aggregation: complexity results
- Parameterized complexity of control problems in Maximin election
- Advice classes of parametrized tractability
- Finding odd cycle transversals.
- Average parameterization and partial kernelization for computing medians
- On bounded-degree vertex deletion parameterized by treewidth
- The complexity of Kemeny elections
- Parameterizing above or below guaranteed values
- On the complexity of crossings in permutations
- Anyone but him: the complexity of precluding an alternative
- Parameterized computational complexity of control problems in voting systems
- On problems without polynomial kernels
- Fixed-parameter algorithms for Kemeny rankings
- Parameterized complexity of candidate control in elections and related digraph problems
- Sophisticated voting outcomes and agenda control
- 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
- Extending Condorcet's rule
- A heuristic technique for multi-agent planning
- Exact complexity of the winner problem for Young elections
- Which problems have strongly exponential complexity?
- Multivariate complexity analysis of Swap Bribery
- A note on ``Bank winners in tournaments are difficult to recognize by G. J. Woeginger
- The computational difficulty of manipulating an election
- Towards a dichotomy for the possible winner problem in elections based on scoring rules
- Control complexity in Bucklin and fallback voting: an experimental analysis
- Handbook of social choice and welfare. Vol. 1.
- Parameterized computational complexity of Dodgson and Young elections
- Aggregation of partial rankings, \(p\)-ratings and top-\(m\) lists
- Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
- On the complexity of achieving proportional representation
- On complexity of lobbying in multiple referenda
- Banks winners in tournaments are difficult to recognize
- Computational Aspects of Approval Voting
- On the Computation of Fully Proportional Representation
- Determining the winner of a Dodgson election is hard
- Ranking and Drawing in Subexponential Time
- Determining Possible and Necessary Winners Given Partial Orders
- Integer Programming with a Fixed Number of Variables
- Partial Kernelization for Rank Aggregation: Theory and Experiments
- Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament
- On Making a Distinguished Vertex Minimum Degree by Vertex Deletion
- Multimode Control Attacks on Elections
- Reflections on Multivariate Algorithmics and Problem Parameterization
- Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
- Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control
- When are elections with few candidates hard to manipulate?
- On Problem Kernels for Possible Winner Determination under the k-Approval Protocol
- Iterative Compression for Exactly Solving NP-Hard Minimization Problems
- Fast FAST
- Incompressibility through Colors and IDs
- The Complexity of Probabilistic Lobbying
- Swap Bribery
- Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
- How Hard Is Bribery in Elections?
- Towards Fully Multivariate Algorithmics: Some New Results and Directions in Parameter Ecology
- Kernelization: New Upper and Lower Bound Techniques
- Improved Parameterized Algorithms for the Kemeny Aggregation Problem
- Manipulation of Voting Schemes: A General Result
- Condorcet Social Choice Functions
- A Consistent Extension of Condorcet’s Election Principle
- Exact analysis of Dodgson elections
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Color-coding
- A Richer Understanding of the Complexity of Election Systems
- Computational Complexity
- Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves
- A Short Introduction to Computational Social Choice
- Statistical Decision Functions
- On the complexity of \(k\)-SAT
