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

DOI10.1007/978-3-031-22832-2_19MaRDI QIDQ6167260zbMATH OpenFDO

Authors 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

computational social choicesemi-random complexitywinner determination

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Social choice (91B14)

Abstract: The computational complexity of winner determination is a classical and important problem in computational social choice. Previous work based on worst-case analysis has established NP-hardness of winner determination for some classic voting rules, such as Kemeny, Dodgson, and Young. In this paper, we revisit the classical problem of winner determination through the lens of semi-random analysis, which is a worst average-case analysis where the preferences are generated from a distribution chosen by the adversary. Under a natural class of semi-random models that are inspired by recommender systems, we prove that winner determination remains hard for Dodgson, Young, and some multi-winner rules such as the Chamberlin-Courant rule and the Monroe rule. Under another natural class of semi-random models that are extensions of the Impartial Culture, we show that winner determination is hard for Kemeny, but is easy for Dodgson. This illustrates an interesting separation between Kemeny and Dodgson.

Recommendations

• A note on the query complexity of the Condorcet winner problem
• The approximation complexity of win-lose games
• On problem kernels for possible winner determination under the k-approval protocol
• Possible winner problems on partial tournaments: a parameterized study
• Possible winner problems on partial tournaments: a parameterized study
• The possible winner problem with uncertain weights revisited
• Exact complexity of the winner problem for Young elections
• scientific article; zbMATH DE number 2080339

Cites work

• A nearly instance optimal algorithm for top-k ranking under the multinomial logit model
• Aggregating inconsistent information: ranking and clustering
• Approximability of Dodgson's rule
• Average-Case and Smoothed Competitive Analysis of the Multilevel Feedback Algorithm
• Beyond the Worst-Case Analysis of Algorithms
• Coloring Random and Semi-Random k-Colorable Graphs
• Condorcet’s Paradox
• Exact analysis of Dodgson elections
• 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
• Guarantees for the success frequency of an algorithm for finding Dodgson-election winners
• Handbook of Computational Social Choice
• scientific article; zbMATH DE number 5081744 (Why is no real title available?)
• scientific article; zbMATH DE number 1414348 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2003
• On the approximability of Dodgson and Young elections
• On the complexity of achieving proportional representation
• Ranking Tournaments
• Smoothed analysis of algorithms
• Smoothed Efficient Algorithms and Reductions for Network Coordination Games.
• The complexity of Kemeny elections
• Typical Properties of Winners and Losers [0.2ex] in Discrete Optimization
• Voting schemes for which it can be difficult to tell who won the election

Cited in

(2)

• Reducing the time required to find the Kemeny ranking by exploiting a necessary condition for being a winner
• Analysis of 2-Opt Heuristic for the Winner Determination Problem Under the Chamberlin-Courant System

This page was built for publication: Beyond the worst case: semi-random complexity analysis of winner determination

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6167260)