Seminar Logic, Complexity, Games: Computational Social Choice

WS 2018/19

Registration

Students with a subject in mathematics can apply by writing an email to seminar [AT] logic.rwth-aachen.de until september 20th including their name, immatriculation no., subject of studies, no. of semesters of studies, and information about relevant modules they have passed (especially lectures from our group).

Organisation

Die Vorbesprechung findet am 27.09. um 11:00 Uhr im Seminarraum des I7 statt (Informatikzentrum, E1, erste Etage).

Die Veranstaltung wird als Blockseminar angeboten, die Vorträge werden am Ende des Semesters wahlweise auf deutsch oder englisch gehalten.

Die Vorträge finden in unserem Seminarraum (Raum 4116, E1, Ahornstr. 55) am 06. Februar, sowie am 07. Februar statt.

Die Ausarbeitungen werden allen TeilnehmerInnen zur Verfügung gestellt und sind bis zu den Vorträgen zu lesen.

Deadlines

23. Januar Ausarbeitungen
30. Januar Folien
6./7. Februar Vorträge

Content

Social choice theory is concerned with designing and analysing methods for deriving a collective decision from individual preferences.

We investigate, using formal logical methods, how preferences of individuals in a group can be aggregated to a social preference representing the "will of the people". For example Arrow's theorem states that there is no non-dictatorial election system satisfying certain axioms, e.g. "if every individual ranks alternative A above B, then so should society".

In this seminar we also look into the computational complexity of such systems. We will see that every sensible election system can be manipulated, however it might require an enormous amount of computational power to do so, hence one can consider such a system as safe.

Topics

Thema Vortragende(r) Betreuer(in) Literatur
Der Satz von Arrow Caroline Jabs Matthias Hoelzel []
Social Choice Functions Hannah Mertens Svenja Schalthöfer []
Strategic Manipulation Tom Neuhäuser Svenja Schalthöfer []
Computational Complexity of Manipulation Rene Pasing Svenja Schalthöfer []
Single Peak Preferences Maksim Rotmann Richard Wilke [ELO08, M80, I64]
Nicely Structured Preferences André Kusidlo Richard Wilke [S66]
Graph Aggregation Tony Wang Katrin Dannert []
Judgement Aggregation (1) Peter Birk Matthias Hoelzel []
Judgement Aggregation (2) Lukas Westhofen Matthias Hoelzel []
Cake Cutting (1) Daniela Schmid Katrin Dannert []
Cake Cutting (2) Oliver Gaul Katrin Dannert []

Literature

[BCE12] F. Brandt, V. Conitzer, and U. Endriss. Computational Social Choice. In Multiagent Systems (G. Weiss, Ed.). MIT Press, 2012.
[BCW13] R. Bredereck, J. Chen, and G. J. Woeginger. Are There Any Nicely Structured Preference Profiles Nearby? In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI '13, pp. 62–68. AAAI Press, 2013.
[CELM07] Y. Chevaleyre, U. Endriss, J. Lang, and N. Maudet. A Short Introduction to Computational Social Choice. In SOFSEM 2007: Theory and Practice of Computer Science (J. van Leeuwen, G. F. Italiano, W. van der Hoek, C. Meinel, H. Sack, and F. Plášil, Eds.), vol. 4362 of Lecture Notes in Computer Science, pp. 51–69. Springer Berlin Heidelberg, 2007.
[E11] U. Endriss. Logic and Social Choice Theory. In Logic and Philosophy Today (A. Gupta and J. van Benthem, Eds.). College Publications, 2011.
[ELO08] B. Escoffier, J. Lang, and M. Öztürk. Single-peaked Consistency and Its Complexity. In Proceedings of the 2008 Conference on ECAI 2008: 18th European Conference on Artificial Intelligence, pp. 366–370, Amsterdam, The Netherlands, The Netherlands. IOS Press, 2008.
[I64] K. Inada. A Note on the Simple Majority Decision Rule. Econometrica, vol. 32(4), pp. 525–531, 1964.
[M80] H. Moulin. On Strategy-Proofness and Single Peakedness. Public Choice, vol. 35(4), pp. 437–455, 1980.
[S66] A. K. Sen. A Possibility Theorem on Majority Decisions. Econometrica, vol. 34(2), pp. 491–499, 1966.

Classification

  • Informatik (B.Sc.)/Seminar Informatik
  • Mathematik (B.Sc.)/Seminar: Logik, Komplexität, Spiele
  • Informatik (M.Sc.)/Seminar Theoretische Informatik
  • Mathematik (M.Sc.)/Seminar: Logik, Komplexität, Spiele (Reine Mathematik)
  • Informatik (S II)
  • Mathematik (S II)/Hauptstudium/Modul Algebra
  • Mathematik (S II)/Hauptstudium/Modul Angewandte Mathematik

Prerequisites

  • Module Mathematical Logic
  • for B.Sc. Computer Science: Module "Einführung in das wissenschaftliche Arbeiten (Proseminar)"

Contact

Erich Grädel, Richard Wilke, Matthias Hoelzel, Katrin Dannert, Svenja Schalthöfer