Post 2025-07-06

Алгоритм Гейла-Шепли и 100 стабильных пар (продолжение, начало)

Алгоритм простой: мужчины делают предложения в порядке своих предпочтений. Женщина может принять предложение "временно" или же отказать сразу. Если ей приходит предложение от более привлекательного кандидата, она может "разорвать помолвку" и принять новую.

Процесс продолжается, пока все не будут в парах. Гарантируется стабильность — никто не захочет сбежать друг с другом.

Звучит логично? Тогда почему Нобелевка? До Гейла-Шепли считалось, что стабильное решение может вообще не существовать. Типа хаос: Вася хочет Машу, Маша хочет Петю, Петя хочет Катю, Катя хочет Васю. Как тут составишь пары без драм?Гейл и Шепли доказали: стабильное решение всегда существует и их алгоритм его найдёт. Это типа такая была революция в теории игр и экономике

Алгоритм работает не только для свадеб — студенты в вузы, врачи в больницы, донорские органы. Каждый раз, когда нужно "поженить" два множества с предпочтениями, работает Гейл-Шепли 🤷

Аттакта