Odwrócenie ról mężczyzn i kobiet doprowadziłoby do powstania stabilnego dopasowania, które byłoby preferowane przez kobiety.
Algorytm zapewnia, że:
Każdy weźmie ślub
Ostatecznie nie może zaistnieć taka sytuacja, że zarówno mężczyzna, jak i kobieta nie są zaręczeni, ponieważ w pewnym momencie ten mężczyzna musiał się oświadczyć tej kobiecie (ostatecznie mężczyzna musiał się oświadczyć każdej kobiecie, jeśli było to konieczne), więc ostatecznie musiała ona przyjąć jego oświadczyny.
Małżeństwo będzie trwałe
Niech kobieta A i mężczyzna B będą zaręczeni, ale nie ze sobą nawzajem. Od zakończenia algorytmu nie jest możliwe, żeby A i B preferowali siebie nawzajem względem swoich obecnych partnerów. Jeśli B wolałby A względem swojej aktualnej partnerki, to musiałby oświadczyć się A przed poproszeniem o rękę swojej obecnej partnerki. Jeśli A przyjęła jego oświadczyny, a ostatecznie nie jest z nim zaręczona, to musiała z nim zerwać na rzecz kogoś, kogo woli, a tym samym preferuje swojego obecnego partnera od mężczyzny B. Jeśli A odrzuciła oświadczyny B, to znaczy, że już była zaręczona z kimś, kogo woli od B.
Algorytm ma zastosowanie w rekrutacji do szkół w Nowym Jorku oraz Bostonie, przy przydziale stażystów do szpitali w USA, a nawet do kojarzenia dawców organów z biorcami przeszczepów.
Przypisy
Bibliografia Hal R. Varian, Mikroekonomia. Kurs średni. Ujęcie nowoczesne.
Kategoria:Algorytmy grafowe