Proseminar: Aufteilungs- und Zuweisungsalgorithmen (WiSe 22/23)

[Allocation and matching algorithms]

Veranstalter Dr. Carolin Rehs, Antonia Kalb
Modul Proseminar INF-BA-110 (Bachelor Informatik / Angewandte Informatik)
Veranstaltungsnummer 040221
Moodle https://moodle.tu-dortmund.de/course/view.php?id=36375
SWS 2 (dieses Proseminar umfasst keinen Präsentationskurs)

Aktuelles

Beschreibung

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.

Ablauf und Themen

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

Voraussetzungen

  • Datenstrukturen, Algorithmen und Programmierung 2

Modulprüfung

Prüfungsleistung - Proseminar (3CP)
  • 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
Prüfungsleistung - Präsentationstechniken (1CP)

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

Literatur

  • 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.
 
Last modified: 2022-10-03 18:59 by Antonia Kalb
DokuWikiRSS-Feed