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

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.