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)

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

Related Items (17)

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

This page was built for publication: The Computational Complexity of Choice Sets