Publication:2316935

DOI10.1016/J.JCSS.2019.04.005zbMATH Open1427.91122arXiv1704.06304OpenAlexW2964190823WikidataQ127903053 ScholiaQ127903053MaRDI QIDQ2316935FDOQ2316935

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)

Abstract: Many hardness results in computational social choice make use of the fact that every directed graph may be induced as the pairwise majority relation of some preference profile. However, this fact requires a number of voters that is almost linear in the number of alternatives. It is therefore unclear whether these results remain intact when the number of voters is bounded, as is, for example, typically the case in search engine aggregation settings. In this paper, we provide a systematic study of majority digraphs for a constant number of voters resulting in analytical, experimental, and complexity-theoretic insights. First, we characterize the set of digraphs that can be induced by two and three voters, respectively, and give sufficient conditions for larger numbers of voters. Second, we present a surprisingly efficient implementation via SAT solving for computing the minimal number of voters that is required to induce a given digraph and experimentally evaluate how many voters are required to induce the majority digraphs of real-world and generated preference profiles. Finally, we leverage our sufficient conditions to show that the winner determination problem of various well-known voting rules remains hard even when there is only a small constant number of voters. In particular, we show that Kemeny's rule is hard to evaluate for 7 voters, while previous methods could only establish such a result for constant even numbers of voters.

Full work available at URL: https://arxiv.org/abs/1704.06304

zbMATH Keywords

votingNP-hardnesstournamentscomputational social choice

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Practical graph isomorphism. II.
• Probability models on rankings
• NON-NULL RANKING MODELS. I
• Reducibility among Combinatorial Problems
• On the complexity of Slater's problems
• A Consistent Extension of Condorcet’s Election Principle
• A Richer Understanding of the Complexity of Election Systems
• Ranking Tournaments
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• A simplified NP-complete satisfiability problem
• Tournament solutions and majority voting
• The Voting Problem
• The Complexity of the Partial Order Dimension Problem
• On the complexity of crossings in permutations
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
• When are elections with few candidates hard to manipulate?
• A Constructive Solution to a Tournament Problem
• Independence of clones as a criterion for voting rules
• Elections with Few Voters: Candidate Control Can Be Easy
• Handbook of Computational Social Choice
• Banks winners in tournaments are difficult to recognize
• Automated Search for Impossibility Theorems in Social Choice Theory: Ranking Sets of Objects
• A computational analysis of the tournament equilibrium set
• 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
• Dominating sets in \(k\)-majority tournaments.
• Linear-time modular decomposition of directed graphs
• A counterexample to a conjecture of Schwartz
• Minimal stable sets in tournaments
• In Silico Voting Experiments
• A recurrence for bounds on dominating sets in \(k\)-majority tournaments
• On the structure of stable tournament solutions
• Minimal extending sets in tournaments
• Smallest tournaments not realizable by \({\frac{2}{3}}\)-majority voting
• A note on the voting problem
• On the Discriminative Power of Tournament Solutions
• Tournament Solutions
• Weighted Tournament Solutions
• Realizing Small Tournaments Through Few Permutations

Cited In (7)

• 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
• Voting 'Against' in regular and nearly regular graphs

Uses Software

• nauty
• Plingeling
• PrefLib
• Traces
• Treengeling
• Lingeling

This page was built for publication: \(k\)-majority digraphs and the hardness of voting with a constant number of voters

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