The Computational Complexity of Choice Sets
From MaRDI portal
Publication:3392310
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
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
