\(k\)-majority digraphs and the hardness of voting with a constant number of voters
From MaRDI portal
Publication:2316935
DOI10.1016/j.jcss.2019.04.005zbMath1427.91122arXiv1704.06304OpenAlexW2964190823WikidataQ127903053 ScholiaQ127903053MaRDI QIDQ2316935
Keyvan Kardel, Dominik Peters, Paul Harrenstein, Felix Brandt, Christian Geist, Hans Georg Seedig, Georg Bachmeier
Publication date: 7 August 2019
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1704.06304
Voting theory (91B12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Social choice (91B14)
Related Items (6)
Space reduction constraints for the median of permutations problem ⋮ A unifying rank aggregation framework to suitably and efficiently aggregate any kind of rankings ⋮ On weakly and strongly popular rankings ⋮ Construction of aggregation paradoxes through load-sharing models ⋮ The nonmanipulative vote-deficits of voting rules ⋮ Exploring the median of permutations problem
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Independence of clones as a criterion for voting rules
- Minimal stable sets in tournaments
- A recurrence for bounds on dominating sets in \(k\)-majority tournaments
- A simplified NP-complete satisfiability problem
- Smallest tournaments not realizable by \({\frac{2}{3}}\)-majority voting
- A computational analysis of the tournament equilibrium set
- On the complexity of crossings in permutations
- On the complexity of Slater's problems
- Probability models on rankings
- Tournament solutions and majority voting
- On the structure of stable tournament solutions
- Linear-time modular decomposition of directed graphs
- A note on ``Bank winners in tournaments are difficult to recognize by G. J. Woeginger
- NP-hardness results for the aggregation of linear orders into median orders
- Minimal extending sets in tournaments
- Practical graph isomorphism. II.
- A counterexample to a conjecture of Schwartz
- Dominating sets in \(k\)-majority tournaments.
- Banks winners in tournaments are difficult to recognize
- On the Discriminative Power of Tournament Solutions
- In Silico Voting Experiments
- Automated Search for Impossibility Theorems in Social Choice Theory: Ranking Sets of Objects
- NON-NULL RANKING MODELS. I
- The Voting Problem
- The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
- When are elections with few candidates hard to manipulate?
- The Complexity of the Partial Order Dimension Problem
- A Consistent Extension of Condorcet’s Election Principle
- Elections with Few Voters: Candidate Control Can Be Easy
- Reducibility among Combinatorial Problems
- Tournament Solutions
- Weighted Tournament Solutions
- A Richer Understanding of the Complexity of Election Systems
- Handbook of Computational Social Choice
- A note on the voting problem
- Realizing Small Tournaments Through Few Permutations
- Ranking Tournaments
- Transitive Orientation of Graphs and Identification of Permutation Graphs
- A Constructive Solution to a Tournament Problem
This page was built for publication: \(k\)-majority digraphs and the hardness of voting with a constant number of voters
