Introduction to Computational Social Choice
Санкт-Петербург, осень 2018
Computational social choice is an area on the intersection of computer science, mathematics, and economics, which deals with algorithmic issues that arise in group decision making. In this course, we will focus on algorithms regarding elections, and we will discuss some classic and cutting-edge results on this topic. We will start with problems regarding single-winner elections, complexity of winner determination and various problems regarding affecting their results. In the second part of the course, we will consider multiwinner elections, where our goal is to select a committee (of people, of items, of web pages) that jointly serve some purpose (form a good parliament, are attractive items to present on the homepage of an Internet store, are good answers to a given query). We will consider axiomatic properties of a number of voting rules and consider the complexity of computing their results.
On the technical side, this course will mostly discuss algorithmic and complexity-theoretic results (exact, approximate, fixed-parameter tractable algorithms, NP-hardness, etc.), as well as results from discrete math (e.g., axiomatic characterizations of voting rules).