Algorithmic Analysis of Elections
Lecturer:
Piotr Faliszewski
(AGH University of Science and Technology).
Location and schedule  About the lecturer  Course Summary  Slides  Assignment
Location and schedule: Room 3180 in MIMUW building,



Piotr Faliszewski obtained his PhD in 2009 from the Department of Computer Science at the University of Rochester, USA, under the supervision of Prof. Lane A. Hemaspaandra. After his PhD studies, he has taken a faculty position at the AGH University in Krakow, Poland, but also held visiting professor positions at University of Auckland, New Zealand, at the Universite ParisDauphine, France, and was Mercator fellow in the group of Prof. Rolf Niedermeier at TU Berlin, Germany. His research regards various areas of computational social choice, ranging from the complexity of strategic behavior, through cooperative game theory, to axiomatic analysis of voting rules. He is an associate editor of the Journal of Artificial Intelligence Research.
Computational social choice (COMSOC) is an interdisciplinary research that focuses on using methods from computer science, economics, and operations research in the context of group decision making. In this course we will focus on one of its core topics, algorithmic analysis of elections.
The course is divided into two parts. In the first one, we will focus on singlewinner elections and more classic results. We will see the mathematical model of elections, go over a number of voting rules, and analyze their computational properties. In particular, we will see that there are very natural voting rules (such as the Dodgson rule) for which deciding who won an election is computationally hard. We will also analyze various issues regarding strategic behavior in voting, such as manipulation and bribery. For example, we will prove the classic GibbardSatterthwaite theorem (which says that every voting rule creates incentives for the voters to act dishonestly) and we will see how bribery can be used for good.
In the second part of the course, we will consider the topic of committee elections, which is currently receiving increased attention from the research community. We will discuss applications of committee voting, axiomatic properties of multiwinner rules, and the computational problem of computing winners. We will focus on the example of the ChamberlinCourant rule, which is NPhard to compute, but for which we will first show a 11/e approximation algorithm and then a PTAS. Then we will discuss how to evaluate such approximation algorithms in practice.
Methodologically, the course is focused on: classic algorithmics, discrete mathematics, (parametrized) complexity theory, and approximation algorithms.
Slides
Part 1: Basics
Part 2: Multiwinner complexity
Part 3: Axiomatic properties
Assignment:
problem set. Please submit the solutions at the address faliszew@agh.edu.pl by November 17th.