Group:Theory of Computing
Title:Voting with partial information: Minimal sets of questions to decide an outcome
Speaker: Fangzhen Lin Hong Kong University of Science and Technology
Time: 2012-12-21 14:00-2012-12-21 15:00
Venue:FIT-1-222

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 complete information about a voter's preference, and in this case, can only represent a voter's preference by a partial order. Sometimes, this partial information is enough to determine the outcomes of the election, but often it is not, and in this case, it makes sense to ask how much additional information is needed to determine the outcomes. In this talk, I will discuss some of our recent work on quantifying this "additional information". Specifically, we consider querying a voter with pair-wise comparison questions, and for each candidate, investigate minimal sets of such questions that once answered can determine the outcome for the candidate. I will present some interesting properties about these minimal sets of questions and discuss their applications in vote elicitation.

This is a joint work with Ning Ding.

 



Short Bio:


Fangzhen Lin is Professor of Computer Science at the Hong Kong University of Science and Technology. He received his Ph.D. in computer science from Stanford University, and before coming to Hong Kong, spent several years as a post-doctoral researcher at the University of Toronto. His main research area is Knowledge Representation and Reasoning. He received the Croucher Foundation Senior Research Fellowship award in 2006, a Distinguished Paper Award at IJCAI-1997, a Best Paper Award at KR-2000, an Outstanding Paper Honorable Mention at AAAI-2004, the Ray Reiter Best Paper award at KR-2006, and an Honorable Mention for his planner R at the AIPS-2000 planning competition. He is currently an Associate Editor and Chair of the Awards Committee of the journal Artificial Intelligence, and on the Advisory Board of Journal of Artificial Intelligence Research. He was program co-chairs of KR 2010 and LPNMR'09, and has served on the program committees of numerous international conferences in AI. More information about him can be found on his web page http://www.cs.ust.hk/~flin/ .