В 1962 году математики Дэвид Гейл и Ллойд Шепли предложили алгоритм, как составлять пары, чтобы никто не хотел расстаться со своим партнёром ради варианта получше. И именно алгоритм Гейла — Шепли до сих пор используется в сервисах онлайн-знакомств. Что внутри?

Задача максимально жизненная: есть N мужчин и N женщин, и у каждого — свой список предпочтений, где сначала те, к кому влечёт сильнее всего. Нужно создать такие пары, чтобы не осталось ситуаций, когда один партнёр или оба предпочли бы других.

Алгоритм Гейла-Шепли:

1. Каждый мужчина делает предложение первой женщине в своём списке. 2. Женщины выбирают лучшего из тех, кто сделал им предложение, отклоняя остальных. 3. Отклонённые мужчины делают предложение следующей женщине в списке. 4. Женщины снова выбирают лучшего кандидата, оставляя за собой право сменить партнёра, если им поступит более привлекательное предложение. 5. Повторяем процесс, пока все пары не будут сформированы.

В результате никто не хочет разорвать свою пару ради другого партнёра, а значит, распределение стабильно!

В 2012 году Ллойд Шепли получил Нобелевскую премию по экономике за свою теорию. А народ на сайтах знакомств — возможность, чтобы свайпы принесли самый подходящий вариант🤍

#sihaku #fkblague