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 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 Veranstaltung wird als Blockseminar angeboten, die Vorträge werden am Ende des Semesters wahlweise auf deutsch oder englisch gehalten.

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.

Literature

[BCE12]F. Brandt, V. Conitzer, and U. Endriss. Computational Social Choice. In Multiagent Systems (G. Weiss, Ed.). MIT Press, 2012.
[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.

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