2017/2018 Edition

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,

Thursday, October 12th,
15:00 - 16:30 lecture
16:30 - 16:45 coffee and cake
16:45 - 17:45 class
Friday, October 13th,
14:15 - 15:45 lecture
15:45 - 16:15 coffee and cake
16:15 - 17:15 class
Saturday, October 14th,
10:15 - 11:45 lecture
11:45 - 12:00 coffee and cake
12:00 - 13:30 class

About the lecturer:

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 Paris-Dauphine, 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.

Course summary:

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 single-winner 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 Gibbard--Satterthwaite 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 Chamberlin--Courant rule, which is NP-hard to compute, but for which we will first show a 1-1/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.

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.