The Computational Complexity of Choice Sets

DOI10.1002/MALQ.200810027MaRDI QIDQ3392310zbMATH OpenOpenAlexFDO

Authors Felix Brandt, Felix Fischer, Paul Harrenstein

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)

Recommendations

• scientific article; zbMATH DE number 3934404
• Complexity of extremal set decision problem
• On the computational complexity of defining sets
• scientific article; zbMATH DE number 4130139
• The computational complexity of the game of Set and its theoretical applications
• The complexity types of computable sets
• scientific article; zbMATH DE number 3873343
• scientific article; zbMATH DE number 6077
• scientific article; zbMATH DE number 1555173
• Sources of complexity in subset choice

Cites work

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

Cited in

(21)

• A survey on the complexity of tournament solutions
• Social choice and computational complexity
• Extending tournament solutions
• The supercovering relation, the pairwise winner, and more missing links between Borda and Condorcet
• Finding kings in tournaments
• Possible winner problems on partial tournaments: a parameterized study
• A new old solution for weak tournaments
• A note on contestation-based tournament solutions
• scientific article; zbMATH DE number 4130139 (Why is no real title available?)
• How hard is it to tell which is a Condorcet committee?
• Minimal retentive sets in tournaments
• Voting procedures, complexity of
• A new perspective on implementation by voting trees
• A distributed social choice protocol for combinatorial domains
• A short proof of Deb's theorem on Schwartz's rule
• Socially desirable approximations for dodgson’s voting rule
• Choosability conjectures and multicircuits
• Comparing multiagent systems research in combinatorial auctions and voting
• Representations of votes based on pairwise information: monotonicity versus consistency
• A computational analysis of the tournament equilibrium set
• Making choices with a binary relation: relative choice axioms and transitive closures

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

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