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

[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