Voting schemes for which it can be difficult to tell who won the election

DOI10.1007/BF00303169zbMath0672.90004MaRDI QIDQ1120433

Craig A. Tovey, Michael A. Trick, John J. III Bartholdi

Publication date: 1989

Published in: Social Choice and Welfare (Search for Journal in Brave)

zbMATH Keywords

votingNP-hardimpracticality theorems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Social choice (91B14) Mathematical sociology (including anthropology) (91D99)

Related Items (only showing first 100 items - show all)

On stable rules for selecting committees ⋮ Consensus functions and patterns in molecular sequences ⋮ Ranking chain sum orders ⋮ Approximate and dynamic rank aggregation ⋮ Guarantees for the success frequency of an algorithm for finding Dodgson-election winners ⋮ On the difficulty of making social choices ⋮ Are there any nicely structured preference profiles nearby? ⋮ Manipulation complexity of same-system runoff elections ⋮ The complexity of priced control in elections ⋮ Studies in Computational Aspects of Voting ⋮ Weighted majority tournaments and Kemeny ranking with 2-dimensional Euclidean preferences ⋮ An algorithm for rank aggregation problem ⋮ It is difficult to tell if there is a Condorcet spanning tree ⋮ Recursive inversion models for permutations ⋮ Vote trading in public elections ⋮ Computational complexity of manipulation: a survey ⋮ Label ranking by learning pairwise preferences ⋮ A survey on the linear ordering problem for weighted or unweighted tournaments ⋮ Dichotomy for voting systems ⋮ Prices matter for the parameterized complexity of shift bribery ⋮ The nearest neighbor Spearman footrule distance for bucket, interval, and partial orders ⋮ The complexity of probabilistic lobbying ⋮ Optimizing the cost of preference manipulation in the graph model for conflict resolution ⋮ Three practical criteria of comparison among ordinal preference aggregating rules ⋮ A distance-based comparison of basic voting rules ⋮ Monotonicity-based consensus states for the monometric rationalisation of ranking rules and how they are affected by ties ⋮ Voting: a machine learning approach ⋮ Correlation Clustering with Constrained Cluster Sizes and Extended Weights Bounds ⋮ A new correlation coefficient for comparing and aggregating non-strict and incomplete rankings ⋮ Comparing multiagent systems research in combinatorial auctions and voting ⋮ Distance rationalization of voting rules ⋮ Byzantine preferential voting ⋮ Approaching the rank aggregation problem by local search-based metaheuristics ⋮ Optimal social choice functions: a utilitarian view ⋮ Voting rules as error-correcting codes ⋮ On the complexity of achieving proportional representation ⋮ Fixed-Parameter Algorithms for Kemeny Scores ⋮ Copeland Voting Fully Resists Constructive Control ⋮ Parameterized Computational Complexity of Dodgson and Young Elections ⋮ Finding socially best spanning treesî ⋮ Preference aggregation in the generalised unavailable candidate model ⋮ Computing kemeny rankings from \(d\)-Euclidean preferences ⋮ Lazy Gale-Shapley for many-to-one matching with partial information ⋮ Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey ⋮ On the computation of median linear orders, of median complete preorders and of median weak orders ⋮ Voting with rubber bands, weights, and strings ⋮ Experiments with Kemeny ranking: What works when? ⋮ On the complexity of bribery with distance restrictions ⋮ The geometry of manipulation -- a quantitative proof of the Gibbard-Satterthwaite theorem ⋮ How hard is it to tell which is a Condorcet committee? ⋮ Comparing and aggregating partially resolved trees ⋮ Manipulation can be hard in tractable voting systems even for constant-sized coalitions ⋮ Kernels for feedback arc set in tournaments ⋮ Using extension sets to aggregate partial rankings in a flexible setting ⋮ Ranking and Drawing in Subexponential Time ⋮ The Nearest Neighbor Spearman Footrule Distance for Bucket, Interval, and Partial Orders ⋮ On complexity of lobbying in multiple referenda ⋮ Computing the minimal covering set ⋮ Predicting winner and estimating margin of victory in elections using sampling ⋮ How hard is it to control an election? ⋮ Computability of simple games: A characterization and application to the core ⋮ On the approximability of Dodgson and Young elections ⋮ On the evaluation of election outcomes under uncertainty ⋮ An updated survey on the linear ordering problem for weighted or unweighted tournaments ⋮ Computability of simple games: a complete investigation of the sixty-four possibilities ⋮ Parameterized computational complexity of Dodgson and Young elections ⋮ On the hardness of maximum rank aggregation problems ⋮ NP-hardness results for the aggregation of linear orders into median orders ⋮ Computer science and decision theory ⋮ Average parameterization and partial kernelization for computing medians ⋮ Sincere-Strategy Preference-Based Approval Voting Broadly Resists Control ⋮ Efficient algorithms using subiterative convergence for Kemeny ranking problem ⋮ Median linear orders: Heuristics and a branch and bound algorithm ⋮ A note on generalized rank aggregation ⋮ Frequency of correctness versus average polynomial time ⋮ Partial Kernelization for Rank Aggregation: Theory and Experiments ⋮ Approaching rank aggregation problems by using evolution strategies: the case of the optimal bucket order problem ⋮ On the complexity of crossings in permutations ⋮ Hybrid Elections Broaden Complexity-Theoretic Resistance to Control ⋮ Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control ⋮ The Computational Complexity of Choice Sets ⋮ Some Remarks on Dodgson's Voting Rule ⋮ Approximability of Dodgson's rule ⋮ An Algorithmic View of Voting ⋮ Mining maximum consensus sequences from group ranking data ⋮ Computational Aspects of Approval Voting ⋮ The computational difficulty of manipulating an election ⋮ A probabilistic evaluation framework for preference aggregation reflecting group homogeneity ⋮ Beyond pairwise comparisons in social choice: a setwise Kemeny aggregation problem ⋮ Fixed-parameter algorithms for Kemeny rankings ⋮ The Nakamura numbers for computable simple games ⋮ Improved Parameterized Algorithms for the Kemeny Aggregation Problem ⋮ COMPARING AND AGGREGATING PARTIAL ORDERS WITH KENDALL TAU DISTANCES ⋮ A new approach for identifying the Kemeny median ranking ⋮ Reducing the time required to find the Kemeny ranking by exploiting a necessary condition for being a winner ⋮ Parameterized Complexity of Control and Bribery for d-Approval Elections ⋮ Multidimensional welfare rankings under weight imprecision: a social choice perspective ⋮ Complexity results for extensions of median orders to different types of remoteness ⋮ Parameterized complexity of control and bribery for \(d\)-approval elections ⋮ The complexity of Kemeny elections

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The median procedure in cluster analysis and social choice theory
• The computational difficulty of manipulating an election
• Integer Programming with a Fixed Number of Variables
• A Cutting Plane Algorithm for the Linear Ordering Problem
• The Voting Problem
• Voting Anomalies, the Number of Voters, and the Number of Alternatives
• Condorcet Social Choice Functions
• A Consistent Extension of Condorcet’s Election Principle

This page was built for publication: Voting schemes for which it can be difficult to tell who won the election