Stable Roommates Problem

In der Mathematik, den Wirtschaftswissenschaften und der Informatik, insbesondere in den Bereichen Kombinatorik, Spieltheorie und Algorithmen, ist das Stable Roommate Problem (SRP) das Problem, ein stabiles Matching für eine gerade Menge zu finden. Ein Matching ist eine Trennung der Menge in disjunkte Paare („Mitbewohner“). Das Matching ist „stabil“, wenn es keine zwei Elemente gibt, die keine Mitbewohner sind und sich unter dem Matching gegenseitig ihrem Mitbewohner vorziehen. Dies unterscheidet sich vom Stable Marriage Problem dadurch, dass das Stable Roommate Problem das Matching von zwei beliebigen Elementen erlaubt, nicht nur zwischen den Klassen „Männer“ und „Frauen“.

Es wird allgemein beschrieben als:

In einem bestimmten Fall des Stable Roommate Problems (SRP) ordnet jeder der 2n Teilnehmer die anderen in eine strikte Präferenzordnung. Ein Matching ist eine Menge von n disjunkten Teilnehmerpaaren. Ein Matching M in einer Instanz von SRP ist stabil, wenn es keine zwei Teilnehmer x und y gibt, von denen jeder den anderen seinem Partner in M vorzieht. Man sagt, ein solches Paar blockiert M oder ist ein blockierendes Paar in Bezug auf M.