Abstract
We consider election scenarios with incomplete information, a situation that arises often in practice. There are several models of incomplete information and accordingly, different notions of outcomes of such elections. In one wellstudied model of incompleteness, the votes are given by partial orders over the candidates. In this context we can frame the problem of finding a possible winner, which involves determining whether a given candidate wins in at least one completion of a given set of partial votes for a specific voting rule.
The Possible Winner problem is wellknown to be NPComplete in general, and it is in fact known to be NPComplete 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 Possible Winner problem remains NPComplete. In particular, we find the exact values of t for which the Possible Winner problem transitions to being NPComplete 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 kapproval), 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.
BibTeX  Entry
@InProceedings{dey_et_al:LIPIcs:2017:8135,
author = {Palash Dey and Neeldhara Misra},
title = {{On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard}},
booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
pages = {57:157:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770460},
ISSN = {18688969},
year = {2017},
volume = {83},
editor = {Kim G. Larsen and Hans L. Bodlaender and JeanFrancois Raskin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8135},
URN = {urn:nbn:de:0030drops81354},
doi = {10.4230/LIPIcs.MFCS.2017.57},
annote = {Keywords: Computational Social Choice, Dichotomy, NPcompleteness, Maxflow, Voting, Possible winner}
}
Keywords: 

Computational Social Choice, Dichotomy, NPcompleteness, Maxflow, Voting, Possible winner 
Collection: 

42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) 
Issue Date: 

2017 
Date of publication: 

01.12.2017 