Advanced Topics in Computational Social Choice (CIT423011)
Organization
- Lecture: Thu 12:00-14:00
- Central Exercise Session: Tue 14:00-16:00 biweekly
- SWS: 2+1
- Credits: 5
- Classification: "Algorithmen" (ALG)
- Module description: CIT423011
- Language: English
- Exam: tba
- Exam format: written, in-person
- Exam registration: TUMonline
This is a theory course. Participants are expected to be familiar with formal mathematics as well as standard proof techniques. Additionally, basic knowledge about NP-completeness and linear programming is helpful.
Content
Social Choice Theory deals with methods for collective decision-making. Beyond classical applications such as voting procedures, these methods have found applications in various areas of computer science and multi-agent systems. This course builds on the foundations introduced in Computational Social Choice (IN2229). It covers three major research areas that have attracted significant interest in recent years:
- Fair Division: cake cutting, allocating indivisible goods, and the house allocation problem
- Public Goods Allocation: multi-winner approval voting, participatory budgeting, budget aggregation, and the Lindahl equilibrium
- Probabilistic Social Choice: SSB utilities, maximal lotteries, random dictatorship theorem, and random assignment
Across all topics, the course focuses on mathematically rigorous, provable results. Students will read and understand formal arguments, develop their own proofs, and gain a solid introduction to how research is conducted in theoretical computer science.
Slides and exercise sheets
Lecture slides, exercise sheets, and solution hints will only be available in Moodle.
Exam
There will be a written exam at the end of the semester. The only resource you may use during the exam is one hand-written sheet of DIN A4 paper that you prepared yourself (you may write on both sides). In particular, electronic devices, books, photocopies, and printouts are disallowed. All content from lecture and tutorials is relevant for the exam. You will be notified by email when the grades are available in TUMonline.
Literature
This course is not based on a textbook. The literature listed below can be helpful to get a better understanding of some concepts, but the notation and terminology might deviate from the lecture. The following books are available online for free and provide a good overview of the topic:
- Handbook of Computational Social Choice (by F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia)
- Trends in Computational Social Choice (by U. Endriss)