Beyond the worst case: semi-random complexity analysis of winner determination

DOI10.1007/978-3-031-22832-2_19arXiv2210.08173MaRDI QIDQ6167260

Lirong Xia, Weiqiang Zheng

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

zbMATH Keywords

winner determinationcomputational social choicesemi-random complexity

Mathematics Subject Classification ID

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