Есть такая задача: выйти замуж за любимого человека. Очень жизненно, правда? Вот краткое саммари работы нобелевских лауреатов Гейли и Шепли, которые предложили и доказали математический принцип наиболее успешного сочетания предпочтений.
Они решали задачу из области кооперативных игр, её называют задачей о марьяже. Человеческим языком: как составить семейные пары из женихов и невест таким образом, чтобы мужа из одной семьи и жену из другой не тянуло друг к другу сильнее, чем к своим законным супругам? Иначе – ищем стабильные соответствия между элементами двух множеств, имеющих свои предпочтения.
Представим себе:
Встречаются три девушки и три юноши, скажем, на вечеринке. Каждому (-ой) из них предлагается отметить свои предпочтения в порядке значимости. Далее проверяют соответствие: у кого-то совпали «лучшие выборы» (им повезло), а у кого-то – первый выбор совместился с третьим номером его визави, например. Есть ли решение у такой задачи, чтобы все три пары остались довольны и счастливы?
Есть. Вот чистая математика. Все претензии – к дядюшкам Гейли и Шепли:
- мужчины делают предложение наиболее предпочитаемой женщине;
- каждая женщина из всех поступивших предложений выбирает наилучшее и отвечает на него «может быть», на все остальные отвечает «нет»;
- мужчины, получившие отказ, обращаются к следующей женщине из своего списка предпочтений, мужчины, получившие ответ «может быть», ничего не делают;
- если женщине пришло предложение лучше предыдущего, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «может быть»;
- шаги повторяются, пока у всех мужчин не исчерпается список предложений, в этот момент женщины отвечают «да» на те предложения «может быть», которые у них есть в настоящий момент.
Для алгоритма требуется порядка n² шагов, где n — число мужчин и женщин. То есть если вас шесть человек – придётся 36 раз сделать перевыборы, чтобы найти правильные соответствия.
Самое важное: алгоритм Гейла-Шепли не ищет ответ, как найти наилучший вариант для конкретного человека. Он объясняет, как в целом можно улучшить ситуацию каждого. То есть не надо искать того самого идеального. Нужно не усугублять ситуацию в целом (кидаться на первого встречного, бросаться в руки тому, кто выберет тебя, непременно делать выбор самому, лишь бы выбрать, и прочие глупости, которые мы все время от времени совершаем…); и тогда найдётся пара каждому (-ой).
Есть и статистика: если следовать этой логике, то шансы найти подходящего супруга около 38,4% (1 из 20 кандидатов). Если выбирать рандомно, то только в 5% случаев мы найдём настоящую любовь «методом тыка». И следствие: оптимальная стратегия – отказать первым 37% кандидатов, которые обращаются к вам, и незамедлительно выйти замуж за следующего после них, который вам приглянётся. Скорее всего, он не будет
вашим идеальным принцем на белом коне. Но он определённо составит с вами оптимально гармоничную пару на данный момент.
Альтернативный сценарий. Если у вас всего три месяца в запасе на выполнение цели (например, познакомиться для счастливых отношений в течение трёх летних месяцев) – то нужно отклонять все «заявки» в первый месяц, а затем незамедлительно принять первое понравившееся предложение. Аналогично работает и в рекрутинге, и в распределении спортсменов по командам.
Пойдёмте проверять на практике уже что ли!
Екатерина Иноземцева,
15.07.2015
__________________________________________________________________________________
Поддержите нас голосом за новый формат осознанных знакомств в Парке Горького здесь
Подробнее об алгоритме Гейла-Шепли здесь
