Exact complexity of the winner problem for Young elections
From MaRDI portal
Publication:1405784
DOI10.1007/S00224-002-1093-ZzbMATH Open1061.90084arXivcs/0112021OpenAlexW1646465584MaRDI QIDQ1405784FDOQ1405784
Authors: Jörg Rothe, Holger Spakowski, Jörg Vogel 
Publication date: 26 August 2003
Published in: Theory of Computing Systems (Search for Journal in Brave)
Abstract: In 1977, Young proposed a voting scheme that extends the Condorcet Principle based on the fewest possible number of voters whose removal yields a Condorcet winner. We prove that both the winner and the ranking problem for Young elections is complete for the class of problems solvable in polynomial time by parallel access to NP. Analogous results for Lewis Carroll's 1876 voting scheme were recently established by Hemaspaandra et al. In contrast, we prove that the winner and ranking problems in Fishburn's homogeneous variant of Carroll's voting scheme can be solved efficiently by linear programming.
Full work available at URL: https://arxiv.org/abs/cs/0112021
Recommendations
Cited In (34)
- Minimal envy and popular matchings
- Studies in Computational Aspects of Voting
- On stable rules for selecting committees
- Parameterized computational complexity of Dodgson and Young elections
- Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP
- The complexity landscape of outcome determination in judgment aggregation
- Guarantees for the success frequency of an algorithm for finding Dodgson-election winners
- Parameterized Computational Complexity of Dodgson and Young Elections
- Stability, vertex stability, and unfrozenness for special graph classes
- Voting procedures, complexity of
- The complexity of Kemeny elections
- The complexity of probabilistic lobbying
- Complexity of stability
- Collective decision making
- Title not available (Why is that?)
- A distance-based comparison of basic voting rules
- Manipulation complexity of same-system runoff elections
- The complexity of priced control in elections
- Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games
- Control of Condorcet voting: complexity and a relation-algebraic approach
- Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
- Comparing multiagent systems research in combinatorial auctions and voting
- Dichotomy for voting systems
- Anyone but him: the complexity of precluding an alternative
- Computational Aspects of Approval Voting
- A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison
- Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP
- Beyond the worst case: semi-random complexity analysis of winner determination
- Rationalizations of Condorcet-consistent rules via distances of Hamming type
- On the approximability of Dodgson and Young elections
- Preferences single-peaked on a tree: multiwinner elections and structural results
- On complexity of lobbying in multiple referenda
- Complexity of Stability.
- Dogson's rule and Yong's rule
This page was built for publication: Exact complexity of the winner problem for Young elections
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1405784)
