💘 Математика и любовь. Теория стабильного брака

14 февраля хочется подумать о задаче, как сделать так, чтобы «с любимыми не расставались». И в математике есть на это ответ!

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

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

⬇️ Порядок алгоритма Гейла-Шепли:

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

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

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

Happy Valentines! ❤️