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
(36)- Anyone but him: the complexity of precluding an alternative
- The complexity of probabilistic lobbying
- On the approximability of Dodgson and Young elections
- Complexity of stability
- Minimal envy and popular matchings
- Parameterized computational complexity of Dodgson and Young elections
- On stable rules for selecting committees
- A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison
- Rationalizations of Condorcet-consistent rules via distances of Hamming type
- On complexity of lobbying in multiple referenda
- Computational Aspects of Approval Voting
- Studies in Computational Aspects of Voting
- 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
- Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP
- Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
- Parameterized Computational Complexity of Dodgson and Young Elections
- Exact analysis of Dodgson elections
- Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP
- scientific article; zbMATH DE number 6928629 (Why is no real title available?)
- Preferences single-peaked on a tree: multiwinner elections and structural results
- Dogson's rule and Yong's rule
- The complexity landscape of outcome determination in judgment aggregation
- Voting procedures, complexity of
- Complexity of Stability.
- Stability, vertex stability, and unfrozenness for special graph classes
- Beyond the worst case: semi-random complexity analysis of winner determination
- Comparing multiagent systems research in combinatorial auctions and voting
- Collective decision making
- Declarative approaches to outcome determination in judgment aggregation
- The complexity of Kemeny elections
- Guarantees for the success frequency of an algorithm for finding Dodgson-election winners
- Dichotomy for voting systems
- A distance-based comparison of basic voting rules
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)
