Speaker: |
Palash Dey |

Organiser: |
Anamay Tengse |

Date: |
Friday, 29 Dec 2017, 17:15 to 18:15 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

The possible winner problem is well-known to be NP-complete in general, and it is in fact known to be NP-complete for several voting rules where the number of undetermined pairs in every vote is bounded only by some constant. In this paper, we address the question of determining precisely the smallest number of undetermined pairs for which the \PW problem remains NP-complete. In particular, we find the exact values of t for which the possible winner problem transitions to being NP-complete from being in P, where t is the maximum number of undetermined pairs in every vote. We demonstrate tight results for a broad subclass of scoring rules which includes all the commonly used scoring rules (such as plurality, veto, Borda, and k-approval), Copeland^\alpha for every \alpha\in[0,1], maximin, and Bucklin voting rules. A somewhat surprising aspect of our results is that for many of these rules, the possible winner problem turns out to be hard even if every vote has at most one undetermined pair of candidates.