City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Introduction to Computational Social Choice
Saint Petersburg / autumn 2018, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

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).

Date and time Class|Name Venue|short Materials
24 November
Лекция 1, Lecture ПОМИ РАН slides,  video
24 November
Лекция 2, Lecture ПОМИ РАН video
25 November
Лекция 3, Lecture ПОМИ РАН slides,  video
25 November
Лекция 4, Lecture ПОМИ РАН video
25 November
Лекция 5, Lecture ПОМИ РАН video