Beyond the worst case: semi-random complexity analysis of winner determination
From MaRDI portal
Publication:6167260
DOI10.1007/978-3-031-22832-2_19arXiv2210.08173MaRDI QIDQ6167260
Publication date: 4 August 2023
Published in: Web and Internet Economics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2210.08173
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Social choice (91B14)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of Kemeny elections
- Guarantees for the success frequency of an algorithm for finding Dodgson-election winners
- Approximability of Dodgson's rule
- Voting schemes for which it can be difficult to tell who won the election
- Exact complexity of the winner problem for Young elections
- Feedback arc set problem and NP-hardness of minimum recurrent configuration problem of chip-firing game on directed graphs
- On the complexity of achieving proportional representation
- Smoothed analysis of algorithms
- Exact analysis of Dodgson elections
- Coloring Random and Semi-Random k-Colorable Graphs
- Beyond the Worst-Case Analysis of Algorithms
- Handbook of Computational Social Choice
- Average-Case and Smoothed Competitive Analysis of the Multilevel Feedback Algorithm
- Mathematical Foundations of Computer Science 2003
- Typical Properties of Winners and Losers [0.2ex in Discrete Optimization]
- Ranking Tournaments
- Condorcet’s Paradox
- Smoothed Efficient Algorithms and Reductions for Network Coordination Games.
- Aggregating inconsistent information
This page was built for publication: Beyond the worst case: semi-random complexity analysis of winner determination