- Vivi Padova
- Il Bo
Title: Algorithms and complexity results for predicting election winners
Speaker: Piotr Faliszewski, Univ. of Science and Technology, Krakow, Poland
Date: October 5, 2012
Room: 1BC45, Torre Archimede
Who will be the next president? Which song will win "the best song of the summer" contest? How high will the taxes be? Such questions are usually resolved using elections, and it is natural to wonder how election winners can be predicted. In this talk I will consider two problems related to predicting election winners. In the first one, we assume we have perfect knowledge as to which candidates and which voters participate in the election, but we are unsure as to how they will vote. In the second one, we assume we have perfect knowledge regarding voters' preferences (e.g., due to opinion polls), but we are not sure which voters (or, which candidates) will eventually turn out for the vote.
We show algortihms and complexity results for each of these settings and for several different voting rules.
Rif. int. F. Rossi