Bachelorseminar "Das Stable Marriage Problem und andere (verwandte) Zuordnungs- und Verteilungsprobleme "

Aktuelles

Inhalt

A famous problem is the so called-stable marriage problem. Here n men and n women should be arranged in couples. Every men expresses a ranking of all the women and so does every women with respect to the men. A coupling is called stable if there do not exist two couples (m,w), (m',w')in this coupling such that m prefers w' to his partner w and w' prefers m to her partner m'. The question is if there is always a stable coupling(marriage) and how it can be found. Similar problems are for example the stable roommates problem and the hospital/residents problem. A one sided version is e.g. the following allocation problem: here we have n people 1,..,n and, say, n items of candy c_i, i= 1,...,n. Initially person i owns c _i. Every person expresses a ranking with respect to the candies. The goal is to make trades to find a better allocation. A group of individuals is called a trading coalition if they can swap items among themselves such every person gets an item that they like better. An allocation is called stable if there does not exist a trading coalition. Another matching problems is e.g. the bipartite matching problem. Here we have two sets A and B of possibly different size. In addition we have the information which elements of A can be coupled with which elements in B. The aim is to find a maximal set of possible pairs such that no element of A and B shows up in more than one pair. Matching theory, a name referring to several loosely related research areas concerning matching, allocation, and exchange of indivisible resources, such as jobs, school seats, houses, etc., lies at the intersection of computer science, game theory, social choice theory, and mechanism design. Matching can involve the allocation or exchange of indivisible objects, such as dormitory rooms, transplant organs, courses, summer houses, etc. Or matching can involve two-sided matching, in markets with two sides, such as firms and workers, students and schools, or men and women, that need to be matched with each other. In this seminar we wil deal with various aspects of matching as well as related problems.

Termine

Immer Dienstags, 16-20 Uhr in der Oettingenstr. 67, Raum 131:
  • 25.04.: Vorbesprechung und Themenvergabe
  • 09.05.: Individuelle Vorbesprechungen
  • 13.06.: Vorträge 1 bis 3
  • 20.06.: Vorträge 4 bis 6
  • 27.06.: Vorträge 7 bis 9
  • 04.07.: Vorträge 10 bis 12
  • 11.07.: Ersatztermin

Personen

Materialien

Die folgenden Materialien unterliegen dem Copyright. Teilnehmern der Vorlesung ist die Verwendung für persönliche Studien gestattet. Alle anderen Rechte sind vorbehalten.

Bewertungskriterien

Vortrag

  • Inhalt: Motivation und Einführung, Gliederung, Argumentationskette, Abstraktionsniveau, Vollständigkeit
  • Form: Form der Folien (Schriftgröße, Diagramme, Folien nicht überladen), freie Rede, sprachliche Verständlichkeit (deutliche Sprechweise, Wortwahl), Einhalten der Zeit
  • Beantwortung von Fragen

Ausarbeitung

  • Darstellung: Klarheit des Textes, sprachliche Gewandtheit, äußere Form, Rechtschreibung, Quellenangaben, sinnvolle Darstellung von Abbildungen
  • Hinführung: Abstract, Einleitung und Motivation
  • Hauptteil: Argumentationskette, Darstellung der Hauptresultate
  • Abschluss: Schlussbewertung und Zusammenfassung, Ausblick

Hörerkreis

Bachelor Informatik oder Medieninformatik. Gefordert ist ein Vortrag von 30-40 Minuten mit anschließender, 10 minütiger, Diskussion und eine Ausarbeitung mit 7-12 Seiten.

Benötigte Vorkenntnisse

Grundlegende Kenntnisse der Informatik genügen, allerdings wird erwartet, dass die Teilnehmer Interesse an Ihrem Thema zeigen und dem korrekten Referenzieren von verwendeten Quellen nicht abgeneigt sind.

Literatur

Wird bei der Vorbesprechung bekanntgegeben.