Экономика и романтика
Сегодня, 14 февраля, отмечается День Святого Валентина – праздник, посвященный романтическим отношениям. Казалось бы, что может быть дальше от экономики, науки, считающей, что все люди ведут себя рационально? На самом деле, экономика занимается и этим вопросом!
Рассмотрим задачу:
- Есть N женщин и N мужчин;
- У каждого мужчины и каждой женщины есть строгие предпочтения относительно всех представителей противоположного пола;
- Отношения внутри одного пола невозможны;
- Остаться одиноким нельзя.
Всегда ли существует способ найти устойчивое разбиение на пары (такое, чтобы никаким четырем людям не хотелось поменяться парами между собой)? И если да, то как это сделать? Предлагаем вам подумать над решением (например подумать, как это решается в реальной жизни), а потом прочитать решение.
Решение
В 1962 году Дэвид Гэйл и Ллойд Шепли решили эту задачу, за что Шепли был удостоен Нобелевской Премии в 2012 году. Вот предложенный ими алгоритм:
- Мужчины делают предложение наиболее предпочитаемой женщине.
- Каждая женщина из всех поступивших предложений выбирает наилучшее и отвечает на него «может быть» (помолвка), на все остальные отвечает «нет» (отказ).
- Мужчины, получившие отказ, обращаются к следующей женщине из своего списка предпочтений, мужчины, получившие ответ «может быть», ничего не делают.
- Если женщине пришло предложение лучше предыдущего, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «может быть».
Шаги 1-4 повторяются, пока у всех мужчин не исчерпается список предложений. В этот момент женщины отвечают «да» на те предложения «может быть», которые у них есть в настоящий момент.
Описанный процесс интуитивно понятен, но давайте докажем, почему все пары будут стабильными. Пусть для двух пар М1;Ж1 и М2;Ж2 пара М1;Ж2 лучше. Возможны два случая:
- М1 не делал предложения Ж2. Но тогда Ж1 для него привлекательнее, что противоречит условию нестабильности.
- М1 делал предложение Ж2, но она ему отказала. Однако тогда для Ж2 М2 привлекательнее, что противоречит условию нестабильности.
Очевидно, что если предложения будут делать женщины, а не мужчины, то алгоритм тоже приведет к устойчивому результату (но возможно другому). При этом какой пол делает предложения, тот и получает лучший для себя результат.
Этот алгоритм, хоть и выведен из столь узкой задачи, очень важен и может применяться во многих сферах. Например для распределения студентов по колледжам, интернов по больницам или донорских органов по нуждающимся в них людям.
Однако жизнь – это не экономическая задача, и отношения в ней устроены гораздо сложнее. Поэтому оставьте алгоритмы для тех сфер, где они уже себя зарекомендовали, и делайте так, как вам кажется правильным! С праздником!