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

Schedule

Mittwoch, 6. Februar (Seminarraum i7 4116, E1, Ahornstr. 55)
10:00 10:30 Caroline Jabs Der Satz von Arrow
10:30 11:00 Hannah Mertens Social Choice Functions
11:00 11:30 Tom Neuhäuser Strategic Manipulation
11:30 12:00 Rene Pasing Computational Complexity of Manipulation
12:00 13:00 Pause
13:00 13:30 Maksim Rotmann Single Peak Preferences
13:30 14:00 André Kusidlo Nicely Structured Preferences
Donnerstag, 07. Februar
10:00 10:30 Tony Wang Graph Aggregation
10:30 11:00 Peter Birk Judgement Aggregation (1)
11:00 11:30 Lukas Westhofen Judgement Aggregation (2)
11:30 12:00 Oliver Gaul Fair Cake Cutting and its Complexity
12:00 12:30 Daniela Schmid Envy-free Cake Cutting

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 []
Fair Cake Cutting and its Complexity Oliver Gaul Katrin Dannert []
Envy-free Cake Cutting Daniela Schmid Katrin Dannert []

Literature

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