Towards a Dichotomy for the Possible Winner Problem in Elections Based on Scoring Rules

Details Towards a Dichotomy for the Possible Winner Problem in Elections Based on Scoring Rules Towards a Dichotomy for the Possible Winner Problem in Elections Based on Scoring Rules

2009-11-18

arxiv.org/abs/0911.3492v2

Computer Science

Computational Complexity

minor changes and updates; accepted for publication in JCSS, online version available.

Scientific paper

10.1016/j.jcss.2010.04.002

To make a joint decision, agents (or voters) are often required to provide their preferences as linear orders. To determine a winner, the given linear orders can be aggregated according to a voting protocol. However, in realistic settings, the voters may often only provide partial orders. This directly leads to the Possible Winner problem that asks, given a set of partial votes, whether a distinguished candidate can still become a winner. In this work, we consider the computational complexity of Possible Winner for the broad class of voting protocols defined by scoring rules. A scoring rule provides a score value for every position which a candidate can have in a linear order. Prominent examples include plurality, k-approval, and Borda. Generalizing previous NP-hardness results for some special cases, we settle the computational complexity for all but one scoring rule. More precisely, for an unbounded number of candidates and unweighted voters, we show that Possible Winner is NP-complete for all pure scoring rules except plurality, veto, and the scoring rule defined by the scoring vector (2,1,...,1,0), while it is solvable in polynomial time for plurality and veto.

Affiliated with

Also associated with

No associations

Rating

Towards a Dichotomy for the Possible Winner Problem in Elections Based on Scoring Rules 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 Towards a Dichotomy for the Possible Winner Problem in Elections Based on Scoring Rules, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Towards a Dichotomy for the Possible Winner Problem in Elections Based on Scoring Rules will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-240836