Prof. Felix Brandt
Prof. Dr. Felix Brandt
Dipl.-Math. Markus Brill, Dr. Paul Harrenstein
Vorlesung + Übung im WS 2011/12
Computational Social Choice (IN2229)
News
- The exam will take place in room MW 0350 (November 29)
- The exam date has been moved to February 16, 2012 (November 8)
- From November 7 on, there will be a second tutorial: Mondays, 18.15 - 19.45, Room 01.12.035 (October 27)
- Exercise sheet 2 is online (October 25)
- The tutorial on Monday, October 31, is cancelled (October 24)
Organization
- Lecture: Tuesdays, 14.15 - 15.45, Room 01.10.011 (first lecture: October 18)
- Tutorials:
- Mondays, 16.15 - 17.45, Room 01.10.011
- Mondays, 18.15 - 19.45, Room 01.12.035
- SWS: 2+2
- Credits: 5
- Registration: Go to TUMonline and search for LV Nr. 0000000295
- Classification: "Formale Methoden und ihre Anwendungen" (FMA)
- Module decription: IN2229
- Language: English
- Exam: February 16, 2012, 15.00 - 17.00, room MW 0350
- Exam registration deadline: January 15, 2012
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 as well as computational complexity.
List of topics:
- Preferences
- Voting rules
- Rational choice theory (rationalizability, consistency)
- May's theorem
- Arrow's impossibility theorem
- Scoring rules
- Condorcet rules
- McGarvey's theorem
- Top cycle
- Uncovered set
- Banks set
- Minimal covering set
- Tournament equilibrium set
- Kemeny-Young rule
- Computational complexity of voting rules
Exercises
Exercises are voluntary, but highly recommended. Each exercise sheet will contain tutorial exercises (T) and homework exercises (H). Bonus points for correct homework exercises will be taken into account when grading the final exam, where up to 40 points can be reached using the standard grading scale. Bonus points will be awarded as follows:
- at least 40 per cent of (H) exercises solved: 1 point
- at least 60 per cent of (H) exercises solved: 2 points
- at least 80 per cent of (H) exercises solved: 3 points
Exercise sheets will be made available each Tuesday. They are due the following Monday at 4.15 pm (before the first tutorial begins).
Exam
There will be a written exam at the end of the semester, which will be graded according to the following 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 ((36,43] including bonus points)
The only resource you may use during the exam is a single hand-written DIN A4 paper that you prepared yourself (you may write on both sides). 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.
Literature
There is no textbook that covers all the topics listed above. Lecture slides will be published on a weekly basis.
Articles (available online):
- 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.
- V. Conitzer and J. Rothe (eds.). Proceedings of the 3rd International Workshop on Computational Social Choice, Düsseldorf University Press, 2010.
- 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.
- M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
- 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.
- A. Taylor. Social Choice and the Mathematics of Manipulation, Cambridge University Press, 2005.
Related courses:
- Computational Social Choice by Ulle Endriss, University of Amsterdam
- Algorithmische Eigenschaften von Wahlsystemen I by Jörg Rothe, Universität Düsseldorf