Title: Voting with Partial Information: What Questions to Ask?

Speaker: Ning Ding, HKUST

Time/Date:  Friday, Apr 20, 11-12
Location: Room 3301

Abstract:

Voting is a way to aggregate individual voters' preferences.
Traditionally a voter's preference is represented by a total order
on the set of candidates. However, sometimes one may not have a complete
information about a voter's preference, and in this case, can only
represent a voter's preference by a partial order. Given this framework,
there has been work on computing the possible and necessary winners
of a (partial) vote. In this paper, we take a step further, look at
sets of questions to ask in order to determine the outcome of such a vote.
Specifically, we call a set of questions a deciding set for
a candidate if the outcome of the vote
for the candidate is determined no matter how the questions are
answered by the voters,
and a possible winning (losing) set if there is a way to answer
these questions to make the candidate a winner (loser) of the vote.
We discuss some interesting properties about these sets of queries and
prove some complexity results about them under some
well-known voting rules such as plurality and Borda.

Joint work with Fangzhen Lin