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

Aktuelles

Inhalte

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 will deal with various aspects of matching as well as related problems. 

Ablauf

Alle Studierenden erhalten ein konkretes Thema. Sie erhalten nach Zuteilung eines Platzes im Seminar eine Themenliste und können hier Wünsche äußern, die im Abgleich mit den anderen Studenten berücksichtigt werden. 

Sie werden in Ihrem Thema und Ihrer Ausarbeitung individuell betreut.

Themen

Nach Zuteilung der Seminarplätze erhalten Sie weitere Informationen zu den Themen per E-Mail, sodass Sie ihre Auswahl besser treffen können.

Ausarbeitungen

 

Anmeldung

Die Vergabe der Plätze erfolgt zentral über UniWorX. Melden Sie sich also bitte bei Uniworx für das Seminar an. Die Bewerbungsphase läuft vom 22.08.2016 bis 29.09.2016 Es werden keine Plätze direkt vergeben.

Termine

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 40 Minuten mit anschließender, 10 minütiger, Diskussion und eine Ausarbeitung mit 7-12 Seiten.

Benötigte Vorkenntnisse

Keine.