Exact Complexity of the Winner Problem for Young Elections

Details Exact Complexity of the Winner Problem for Young Elections Exact Complexity of the Winner Problem for Young Elections

2001-12-20

arxiv.org/abs/cs/0112021v1

Computer Science

Computational Complexity

10 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Exact Complexity of the Winner Problem for Young Elections does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Exact Complexity of the Winner Problem for Young Elections, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exact Complexity of the Winner Problem for Young Elections will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-314510