10.9 Heiratsproblem

Gegeben: n Männer, n Frauen
Jeder Mann hat Präferenzliste mit Frauen.
Jede Frau hat Präferenzliste mit Männern.

Definition:

Eine Heirat (= Paarung aller) heißt instabil, falls es zwei Leute gibt, die nicht miteinander verheiratet sind, sich aber jeweils ihrem Partner vorziehen.

z.B.:

Eine Heirat heißt stabil, falls sie nicht instabil ist.

Gesucht: Stabile Heirat.

Algorithmus

Ein unverheirateter Mann x arbeitet seine Präferenzliste der Reihe nach ab, bis er zu einer unverheirateten Frau kommt (und sie heiratet) oder zu einer verheirateten Frau y kommt, die x ihrem jetzigen Partner z vorzieht (Ehe (y,z) wird geschieden, x heiratet y und z arbeitet seine Liste weiter ab).

1.

Alle werden verheiratet, denn für jeden Freier ex. mindestens eine unverheiratete Frau im Rest seiner Liste.

2.

Instabile Heirat nicht möglich.

Annahme: Doch! z.B.:

Als A um y buhlte, wurde er entweder sofort oder später abgewiesen, da y eine aus ihrer Sicht bessere Wahl hatte. Widerspruch!

3.

Laufzeit:

Offenbar gilt: Jeder Mann arbeitet seine Liste ab.
Vorhanden: Matrix prior[x,j] = p (Person p ist j -te Wahl von x )
Überführen in: rang[x,p] = j
O(m) bei Eingabelänge m
(Aber quadratisch gegenüber n = Anzahl der Männer bzw. Frauen)

Der Algorithmus ist ``Mann-optimal'', d.h., es ex. keine andere stabile Heirat, bei der die Männer besser abschneiden.