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.