The Computational Complexity of Choice Sets

DOI10.1002/malq.200810027zbMath1173.91358OpenAlexW2167710837MaRDI QIDQ3392310

Paul Harrenstein, Felix Brandt, Felix Fischer

Publication date: 14 August 2009

Published in: Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/malq.200810027

zbMATH Keywords

computational complexitysocial choice theory

Mathematics Subject Classification ID

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

Related Items

Possible winner problems on partial tournaments: a parameterized study ⋮ Extending tournament solutions ⋮ The complexity of computing minimal unidirectional covering sets ⋮ Comparing multiagent systems research in combinatorial auctions and voting ⋮ The supercovering relation, the pairwise winner, and more missing links between Borda and Condorcet ⋮ A new old solution for weak tournaments ⋮ A note on contestation-based tournament solutions ⋮ Minimal retentive sets in tournaments ⋮ Voting Procedures, Complexity of ⋮ A distributed social choice protocol for combinatorial domains ⋮ A computational analysis of the tournament equilibrium set ⋮ Making choices with a binary relation: relative choice axioms and transitive closures ⋮ A new perspective on implementation by voting trees ⋮ Representations of votes based on pairwise information: monotonicity versus consistency ⋮ A survey on the complexity of tournament solutions ⋮ Finding kings in tournaments ⋮ Socially desirable approximations for dodgson’s voting rule

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of Kemeny elections
• Computing the minimal covering set
• A computational analysis of the tournament equilibrium set
• Choosing from a tournament
• Covering sets and a new Condorcet choice correspondence
• Voting games, indifference, and consistent sequential choice rules
• Voting schemes for which it can be difficult to tell who won the election
• On uniform circuit complexity
• A note on generalized stable sets
• On Schwartz's rule
• Tournament solutions and majority voting
• A note on ``Bank winners in tournaments are difficult to recognize by G. J. Woeginger
• Banks winners in tournaments are difficult to recognize
• Constant Depth Reducibility
• Condorcet Social Choice Functions
• Aggregation of Preferences with Variable Electorate
• Stable sets of weak tournaments
• A Richer Understanding of the Complexity of Election Systems
• Ranking Tournaments