The rapidly growing field of computational social choice, at the intersection of computer science and economics, deals with the algorithmic and complexity-theoretic aspects of collective decision making. Some of the classical themes pursued include (but are not limited to) voting procedures, problems of fair division, and matching.
The ingredients of a typical voting problem are agents (or voters) and alternatives (or candidates). Agents express their opinions over the alternatives (either in the form of approval ballots, or partial orders, or complete rankings), and our task is typically to produce an outcome (either a single winner, a committee, or a ranking) that reflects the overall societal opinion. The voting setup is ubiquitous and finds applications in various scenarios, ranging from political elections and hiring committees, to recommender systems and crowdsourcing.
This course addresses several algorithmic and complexity-theoretic themes in computational social choice, such as the design of efficient mechanisms for a given task, the use of computational complexity as a barrier against strategic behaviour, and the exploitation of input structure to work around axiomatic impossibility issues. For the most part, we will use the voting scenario as the running backdrop, although we will allude to other types of problems briefly as well.
Course participants will learn these topics through lectures and assignments. The classes will be transcribed by the students.
For a detailed schedule of lectures, please click here. The materials will be made available to all registered students via the Canvas interface. More details will be available soon.