Seminar Logik, Komplexität, Spiele: Computational Social Choice

WS 2018/19

Anmeldung

  • Studierende in Mathematik-Studiengängen können sich bis zum 20.09. per Email an seminar [AT] logic.rwth-aachen.de bewerben. Bitte geben Sie dazu Ihren vollständigen Namen, Matrikelnummer, Studiengang, Fachsemester und Ihre Vorkenntnisse (insbesondere an unserem Lehrgebiet besuchte Vorlesungen) an.
  • Studierende in Informatik-Studiengängen können sich über die zentrale Vergabe von Seminarplätzen bewerben.

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.

Zeitplan

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

Programm

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

Inhalt

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.

Einführungsliteratur

Folgende Übersichtsartikel sind für alle Themen als Einführungsliteratur empfohlen: [BCE12, CELM07, E11]

Themen

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 []

Literatur

[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.

Zuordnung

  • 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

Voraussetzungen

  • Modul Mathematische Logik
  • für B.Sc. Informatik: bestandenes Modul "Einführung in das wissenschaftliche Arbeiten (Proseminar)"

Rückfragen

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