BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/839
DTSTAMP:20230914T125940Z
SUMMARY:On the Exact Amount of Missing Information that makes Finding Possi
ble Winners Hard
DESCRIPTION:Speaker: Palash Dey\n\nAbstract: \nWe consider election scenari
os with incomplete information\, a situation that arises often in practice
. There are several models of incomplete information and accordingly\, dif
ferent notions of outcomes of such elections. In one well-studied model of
incompleteness\, the votes are given by partial orders over the candidate
s. 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.\n\
nThe 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 t
he number of undetermined pairs in every vote is bounded only by some cons
tant. 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 p
ossible winner problem transitions to being NP-complete from being in P\,
where t is the maximum number of undetermined pairs in every vote. We demo
nstrate tight results for a broad subclass of scoring rules which includes
all the commonly used scoring rules (such as plurality\, veto\, Borda\, a
nd k-approval)\, Copeland^\\alpha for every \\alpha\\in[0\,1]\, maximin\,
and Bucklin voting rules. A somewhat surprising aspect of our results is t
hat 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.\n
URL:https://www.tcs.tifr.res.in/web/events/839
DTSTART;TZID=Asia/Kolkata:20171229T171500
DTEND;TZID=Asia/Kolkata:20171229T181500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR