• Einführungstreffen: Dienstag, 4.10., 14:15-15:45, Raum noch nicht bekannt
• Block-Vorträge im neuen Jahr: Dienstags, 14:00-18:00, Raum noch nicht bekannt
• Interessierte können sich per E-Mail bei Antonia Kalb melden
• Anmeldung und Zuweisung der Seminarplätze ist bereits abgeschlossen

Ein Zuweisungsproblem sucht nach einer Zuweisung von bestimmten Menge zu einer anderen, die bestimmte Eigenschaften erfüllt. Bei den meisten Zuweisungsproblemen geben sogenannte Agenten Präferenzen darüber ab, wem sie zugeordnet werden möchten. Nach diesen Angaben findet die Zuweisung unter verschiedenen Optimalitätskriterien statt, z.B. Stabilität, Neidfreiheit oder Pareto-Optimalität (Fair Matchings). Ein Zuweisungsproblem ist ein- oder mehrseitig, je nachdem, wie viele Gruppen Präferenzen über die anderen abgeben. Das Hospital-Residents-Problem ist zweiseitig, da sowohl die Ärzte Präferenzen über die Krankenhäuser abgeben, als auch die Krankenhäuser über die Ärzte. Bei einem einseitigen Zuweisungsproblem gibt eine Agentenmenge Präferenzen über eine Mengen von teilbaren oder unteilbaren sowie homogenen oder heterogenen Gütern ab (Fair Division).

Beispiel: Cut & Choose

1. Spieler A teilt das Brötchen.
2. Spieler B sucht sich ein Stück aus.
3. Spieler A bekommt das andere Stück.

Dieser Algorithmus ist fair unter den Kriterien der Neidfreiheit und Proportionalität, da beide Spieler gleicher Maßen Einfluss auf das Ergebnis haben.

• Cake-Cutting
• House-Allocation-Problem
• Hosipital-Residence-Problem
• Das Projekt-Zuweisungs-Problem
• Das Arbeiter-Firmen-Problem
• Stable-Roommates-Problem
• Hedonische Spiele

• Datenstrukturen, Algorithmen und Programmierung 2

• schriftliche Ausarbeitung zu einem ausgewählten Thema
• Rückmeldung zu einer anderen Ausarbeitung in Form eines Peer-Reviews
• erfolgreich absolvierte Zwischengespräche jeweils zu Ausarbeitung und Vortrag
• 25-minütiger Vortrag des Themas (+10 min für Fragen und Diskussion)
• aktive Teilnahme an den Vorträgen

Studierende müssen für das erfolgreiche Abschließen des Moduls den Präsentationskurs der Fakultät besuchen. Es empfiehlt sich diesen vor dem Vortragstermin zu absolvieren. Anmeldung über LSF

• F. Brandt, V. Conitzer, U. Endriss, J. Lang und A. Procaccia, Editoren. Handbook of Computational Social Choice. Cambridge University Press, 2016.
• D. Gusfield und R. Irving The Stable Marriage Problem: Structure and Algorithms. MIT Press, 1989.
• D. Knuth. Stable Marriage and its Relation to Other Combinatorial Problems. volume 10 of CRM Proceedings and Lecture Notes, American Mathematical Society, 1997. Original: Mariages Stables, Les Presses de L' Université de Montreal, 1976.
• D. Manlove Algorithmics Of Matching Under Preferences. Volume 2 of Theoretical computer science. World Scientific Publishing, 2013.