Jörg Rothe

Modul: Präferenzaggregation durch Wählen: Algorithmik und Komplexität

Wintersemester 2021/2022

Vorlesung (4 SWS):
- Nutzen Sie die folgenden Präsenztermine am Dienstag im Hörsaal 3F (Geb. 23.21) bzw. am Donnerstag im Hörsaal 5H (Geb. 25.22), die für Fragen und Quizze zum Vorlesungsstoff benutzt werden und in unregelmäßigen Abständen (also nicht an jedem Dienstag bzw. Donnerstag) stattfinden:
  - Dienstag, 12.10.2021, die erste Vorlesung beginnt ausnahmsweise schon um 8:30 Uhr.
  - Donnerstag, 21.10.2021, ab 8:40 Uhr.
  - Donnerstag, 28.10.2021, ab 8:40 Uhr.
  - Dienstag, 9.11.2021, AUSNAHMSWEISE IN HÖRSAAL 3D (Geb. 23.21), ab 8:40 Uhr.
  - Donnerstag, 18.11.2021, ab 8:40 Uhr.
  - Donnerstag, 25.11.2021, ab 9:00 Uhr.
  - Donnerstag, 02.12.2021, ab 9:00 Uhr.
  - Donnerstag, 09.12.2021, ab 9:00 Uhr.
  - Donnerstag, 16.12.2021, ab 9:00 Uhr.
  - Donnerstag, 13.01.2022, ab 9:00 Uhr (entfällt leider - die verspätete Bekanntgabe tut mir wirklich sehr leid!).
  - Donnerstag, 20.01.2022, ab 9:00 Uhr.
  - Donnerstag, 27.01.2022, ab 9:00 Uhr.
  - Donnerstag, 03.02.2022, ab 9:00 Uhr.
- An sich werden aber alle Vorlesungen als besprochene Folien (siehe die Videoclips, die dann auf dieser Seite ganz unten stehen werden) zur Verfügung gestellt.
Übungen (2 SWS): Donnerstag von 14:30 Uhr bis 16:00 Uhr in HS 5H (Geb. 25.22). Zusätzlich bieten wir eine Online-Übung an (Informationen und BBB-Link im ILIAS).
(In diesem Modul findet in diesem Semester kein Seminar statt.)

Prüfung:

findet in Form einer schriftlichen Klausur am Freitag, dem 11.02.2022, im Hörsaal 2D (Geb. 22.01) statt, Einlass ab 14:30 Uhr.
Bitte bringen Sie Ihren Personal- und Studentenausweis mit zur Klausur. Falls der Platz auf den von uns ausgeteilten Klausurblättern nicht reicht, sollten Sie sich auch eigene Blätter mitbringen. Auch sind die derzeitigen Hygienemaßnahmen zu beachten: Verwenden Sie also auch einen Mund-Nasen-Schutz, achten Sie auf den Mindestabstand und beachten Sie die fakultätsspezifischen Hinweise zum Corona-Virus SARS-CoV-2!
Erlaubte Hilfsmittel: Vorlesungsmitschriften, Bücher, Übungsblätter, nicht programmierbare Taschenrechner, Gedächtnis.
Nicht erlaubte Hilfsmittel: Mobiltelefone und ähnliche Kommunikationsgeräte, Kommiliton/inn/en, programmierbare Taschenrechner.
Anmeldung: Melden Sie sich rechtzeitig (nach Ihrer PO) vor dem Klausurtermin beim Akademischen Prüfungsamt über das Studierendenportal zur Prüfung an. Haben Sie sich zur Klausur angemeldet, so können Sie bis eine Woche vor der Klausur noch zurücktreten. Die Abmeldung von der Klausur muss über das Akademische Prüfungsamt erfolgen.
Falls man zur Klausur nicht zugelassen ist, aber angemeldet war, muss man sich nicht extra beim Prüfungsamt abmelden, sondern wir teilen dem Prüfungsamt die Nichtzulassung mit, die selbstverständlich nicht als Fehlversuch gewertet wird.

können Sie hier als pdf herunterladen. In der Woche ab dem 10. Januar 2022 wird es kein neues Übungsblatt und keinen neuen Vorlesungsstoff geben, damit Sie Zeit für das Lösen der Probeklausur haben. Die Probeklausur wird nicht korrigiert und muss nicht abgegeben werden, d.h., die Teilnahme ist freiwillig. Wir besprechen die Probeklausur in der darauffolgenden Woche in den Übungsgruppen. Dabei sind Ihre Lösungen gefragt! Eine Musterlösung zur Probeklausur wird es nicht geben.

Übungen:

Für die Übungen sind die Aufgaben auf den Übungsblättern zu lösen. Die Lösungen werden in den Übungen besprochen und es wird eine aktive Beteiligung aller Studierenden erwartet (also die Vorstellung eigener Lösungen in der Übung).

Die Übungsblätter können jeweils am Dienstag ab 12 Uhr mittags hier von dieser Website heruntergeladen werden. Eine Woche später sind die Lösungen (in LaTeX; siehe die Vorlagen unten) über ILIAS abzugeben und werden dann korrigiert. Für die Zulassung zur Prüfung sind mindestens 50% der Punkte für Übungsaufgaben erforderlich.

Woche Nr. Übungsblätter Vorlagen für die Übungen Musterlösungen

0 Übungsblatt 0 Vorlage 0 Musterlösung 0

1 Übungsblatt 1 Vorlage 1 Musterlösung 1

2 Übungsblatt 2 Vorlage 2 Musterlösung 2

3 Übungsblatt 3 Vorlage 3 Musterlösung 3

4 Übungsblatt 4 Vorlage 4 Musterlösung 4

5 Übungsblatt 5 Vorlage 5 Musterlösung 5

6 Übungsblatt 6 Vorlage 6 Musterlösung 6

7 Übungsblatt 7 Vorlage 7 Musterlösung 7

8 Übungsblatt 8 Vorlage 8 Musterlösung 8

9 Übungsblatt 9 Vorlage 9 Musterlösung 9

10 Übungsblatt 10 Vorlage 10 Musterlösung 10

11 Übungsblatt 11 Vorlage 11 Musterlösung 11

12 Übungsblatt 12 Vorlage 12 Musterlösung 12

Pingo:

Die Vorlesungsinhalte werden von Zeit zu Zeit in Form eines Pingo-Quiz wiederholt. Die Fragen stehen dann hier online:

Die Antworten werden in der Vorlesung bekannt gegeben und besprochen.

Empfohlene Literatur:

Jörg Rothe (ed.): "Economics and Computation: An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division", Springer-Verlag, 2015

Für die Vorlesung relevant sind:

Chapter 4: "Preference Aggregation by Voting", Dorothea Baumeister · Jörg Rothe, pp. 197 - 325
Chapter 5: "The Complexity of Manipulative Actions in Single-Peaked Societies", Edith Hemaspaandra · Lane A. Hemaspaandra · Jörg Rothe, pp. 327 - 360

Jörg Rothe, Dorothea Baumeister, Claudia Lindner, and Irene Rothe: "Einführung in Computational Social Choice: Individuelle Strategien und kollektive Entscheidungen beim Spielen, Wählen und Teilen", Spektrum Akademischer Verlag, 2011

Für die Vorlesung relevant ist:

Kapitel 4: "Präferenzaggregation: Gemeinsame Entscheidungsfindung durch Wählen", Dorothea Baumeister · Jörg Rothe, pp. 121 - 214

Ergänzende Literatur:

Piotr Faliszewski, Lane A. Hemaspaandra, Edith Hemaspaandra, and Jörg Rothe: "A Richer Understanding of the Complexity of Election Systems", Chapter 14 in: "Fundamental Problems in Computing: Essays in Honor of Professor Daniel J. Rosenkrantz", pp. 375-406, S. Ravi and S. Shukla (eds.), Springer, 2009.
Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel Procaccia (eds.): "Handbook of Computational Social Choice", Cambridge University Press, 2016.
Steven J. Brams and Peter C. Fishburn: "Voting Procedures", Chapter 4 in: "Handbook of Social Choice and Welfare", Kenneth J. Arrow, Amartya Sen, and Kotaro Suzumura (eds.), North-Holland, 2002.

Skript:

Es gibt keins. Es gibt aber gute Literatur, siehe oben. Meine Folien zur Vorlesung und die Videoclips können Sie hier jeweils am Dienstag ab 12 Uhr mittags:

herunterladen. Diese werden im Laufe des Semesters ergänzt und sind auf Englisch. Foliensatz 3 von Folie 161 bis zu Folie 200 und die Videoclips 43-47 sowie Übungsblatt 11 gelten für die halbe Woche vor Weihnachten und die erste halbe Woche im Januar nach den Feiertagen; Abgabe des Blattes am 11.1.22. Die Woche ab dem 10.1.22 ist nur für die Probeklausur reserviert. Die nächsten Vorlesungsfolien und Videoclips kommen also erst am 18.1.22.

Modul: Präferenzaggregation durch Wählen: Algorithmik und Komplexität

Wintersemester 2021/2022

Dozent: Prof. Dr. Jörg Rothe

Übungsleiter/innen: Dr. Marc Neveling, Joanna Kaczmarek, Christian Laußmann, Tessa Seeger,