A note on the query complexity of the Condorcet winner problem

DOI10.1016/J.IPL.2008.07.012MaRDI QIDQ975500zbMATH OpenOpenAlexFDO

Authors Ariel D. Procaccia

Publication date 9 June 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2008.07.012

zbMATH Keywords

analysis of algorithmsgraph algorithmstheory of computationsocial choiceconcrete complexity

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40)

Recommendations

• A survey on the complexity of tournament solutions
• Tournament games and Condorcet voting
• Computing with voting trees
• Condorcet winning sets
• How hard is it to tell which is a Condorcet committee?

Cites work

• scientific article; zbMATH DE number 3303831 (Why is no real title available?)
• A topological approach to evasiveness
• On recognizing graph properties from adjacency matrices
• Sorting, Minimal Feedback Sets, and Hamilton Paths in Tournaments

Cited in

(5)

• Condorcet winner configurations of linear networks
• Single-Elimination Brackets Fail to Approximate Copeland Winner.
• Beyond the worst case: semi-random complexity analysis of winner determination
• Reducing the time required to find the Kemeny ranking by exploiting a necessary condition for being a winner
• Query complexity of tournament solutions

This page was built for publication: A note on the query complexity of the Condorcet winner problem

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