Algorithmic Analysis of Elections

(see http://phdopen.mimuw.edu.pl/index.php?page=z17w1 for full description)

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.