Exact complexity of the winner problem for Young elections
From MaRDI portal
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.
Recommendations
Cited in
(34)- Dogson's rule and Yong's rule
- Complexity of Stability.
- 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
- Guarantees for the success frequency of an algorithm for finding Dodgson-election winners
- The complexity landscape of outcome determination in judgment aggregation
- Parameterized Computational Complexity of Dodgson and Young Elections
- The complexity of Kemeny elections
- Stability, vertex stability, and unfrozenness for special graph classes
- Voting procedures, complexity of
- The complexity of probabilistic lobbying
- Complexity of stability
- Collective decision making
- A distance-based comparison of basic voting rules
- scientific article; zbMATH DE number 6928629 (Why is no real title available?)
- 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
- On the approximability of Dodgson and Young elections
- Rationalizations of Condorcet-consistent rules via distances of Hamming type
- On complexity of lobbying in multiple referenda
- Preferences single-peaked on a tree: multiwinner elections and structural results
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)
