Computational Social Choice (IN2229)
Prof. Dr. Felix Brandt
Patrick Lederer, René Romen
Lecture and Tutorials in WS 23/24
Organization
We will have a new modus operandi for this course. All the details will be explained at the kick-off meeting.
Kick-off meeting: FMI HS2, Wednesday, October 18th, 14:15.
- A lecture video and an exercise sheet will be published each Wednesday evening.
- The main slot of the course will take place in FMI HS2 on Wednesdays, 14:15 - 17:00: Questions & Central Exercise Session. At the beginning of this slot, Prof. Brandt will be present to answer questions regarding the lecture material. Afterwards, the solutions to the exercises released in the previous week will be presented in a central exercise session. These sessions will be live-streamed and recorded via live.rbg.tum.de.
- We additionally offer two tutorial sessions on Monday, 12:00 - 14:00, Room 01.010.011 and Tuesday, 10:00 - 12:00, Room 01.010.011. These tutorial sessions will deal with the exercises published in the previous week and are intended to give students the chance to discuss and get individual feedback on solution attempts, or simply have a fixed time slot to work on the exercises in teams. A tutor will be present to supervise and guide the session. Note, however, that we will not present sample solutions in the tutorial sessions. This will be done in the central exercise session on Wednesdays. Tutorials are optional activities for students who like to have personal interactions with other students and the course staff.
IMPORTANT NOTICE: This is a theory course. It is expected that participants are familiar with formal mathematics and standard proof techniques. Addtionally, basic knowledge about NP-completeness is useful (e.g., Module IN0011).
Content
Social choice theory deals with the aggregation of individual preferences into a collective choice such as in voting. This course focusses on the analysis and comparison of aggregation functions that are based on simple majority rule. After introducing the mathematical and microeconomic foundations of social choice theory, particular attention will be paid to algorithmic aspects.
Tentative list of topics:
- Preferences
- Voting rules
- Rational choice theory (rationalizability, consistency)
- May's theorem
- Arrow's impossibility theorem
- Scoring rules
- Condorcet rules (Top cycle, Uncovered set, Banks set, Minimal covering set, Bipartisan set, Kemeny-Young rule)
- McGarvey's theorem
- Computational complexity of voting rules
- Strategic manipulation (Gibbard-Satterthwaite Theorem)
Exercises
We will publish an exercise sheet each Wednesday evening containing one tutorial exercise (T) and three homework exercises (H). We highly recommend students try to solve the homework exercises by themselves before the central exercise session. Homework solutions cannot be handed in, but students can ask for feedback in the tutorial sessions.
Moreover, there will be an exam grade bonus that will be assigned based on the student's performance in three Moodle quizzes. Solving at least 66% of the Moodle quiz questions will improve your grade by 0.3 (only if passed).
Exam
There will be a written, on-site only exam at the end of the semester, which will be graded according to the following (tentative) grading scale:
- [0,5) points: 5,0
- [5,11) points: 4,7
- [11,17) points: 4,3
- [17,19] points: 4,0
- (19,22] points: 3,7
- (22,24] points: 3,3
- (24,26] points: 3,0
- (26,28] points: 2,7
- (28,30] points: 2,3
- (30,32] points: 2,0
- (32,34] points: 1,7
- (34,36] points: 1,3
- (36,40] points: 1,0
The only resource you may use during the exam are two hand-written sheets of DIN A4 paper that you prepared yourself (you may write on both sides of each sheet). In particular, electronic devices, books, photocopies, and printouts are disallowed. Please remember to bring your student id (or an equivalent photo id). We will notify you by email when the grades are available in TUMonline.
The exam will be in English. If need be, answers in German are acceptable, too.
Literature
There is no textbook that covers all the topics listed above. Lecture slides will be published on a weekly basis. You can learn more about the computational social choice community here.
Available online:
- F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia. Handbook of Computational Social Choice, Cambridge University Press, 2016.
- F. Brandt, V. Conitzer, and U. Endriss. Computational Social Choice. In "Multiagent Systems" (G. Weiss, ed.), MIT Press, 2012.
- Y. Chevaleyre, U. Endriss, J. Lang, and N. Maudet. A Short Introduction to Computational Social Choice. In Proceedings of the 33rd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM-2007), LNCS 4362, Springer-Verlag, 2007.
- P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe. A Richer Understanding of the Complexity of Election Systems. In "Fundamental Problems in Computing: Essays in Honor of Professor Daniel J. Rosenkrantz" (S. Ravi and S. Shukla, eds.), Springer-Verlag, 2007.
Recommended advanced books:
- D. Austen-Smith and J. Banks: Positive Political Theory I, University of Michigan Press, 1999.
- W. Gärtner: A Primer in Social Choice Theory, Oxford University Press, 2009.
- J. Laslier. Tournament Solutions and Majority Voting, Springer-Verlag, 1997.
- H. Moulin. Axioms of Cooperative Decision Making, Cambridge University Press, 1988.
- S. Nitzan. Collective Preference and Choice, Cambridge University Press, 2010
- A. Taylor. Social Choice and the Mathematics of Manipulation, Cambridge University Press, 2005.
Refresher on basic mathematical concepts and proof techniques
You may consult this document by Itzhak Gilboa or this document by Walter Bossert (the latter covers much more than we need in this course). Michael Sipser's book "An Introduction to the Theory of Computation" also contains a good introduction to basic mathematical concepts and proof techniques.
Related courses:
- Computational Social Choice by Ulle Endriss, University of Amsterdam, Netherlands
- Computational Social Choice by Lirong Xia, Rensselaer Polytechnic Institute, USA
- Algorithmische Eigenschaften von Wahlsystemen I by Jörg Rothe, Universität Düsseldorf, Germany