Проблема
Я слышала, что феминистки переименовали это в Задачу о Стабильном Паросочетании, но я представляю Задачу о Стабильном Браке в её оригинальной, традиционной, основательной формулировке:
Есть N мужчин и N женщин.
Каждый мужчина ранжирует всех женщин в порядке предпочтения, с на ком он хотел бы больше всего жениться, и каждая женщина аналогично ранжирует всех мужчин. (Важно для результата: каждый предпочитает быть женатым на ком-то, чем оставаться одиноким)
Цель — поженить всех с кем-то противоположного пола таким образом, чтобы все N получившихся браков были стабильными. Это означает, что не существует никаких двух браков, назовем их Алиса-Боб и Кэрол-Дэйв, где Алиса и Дэйв (или Боб и Кэрол) взаимно предпочитают друг друга своим нынешним супругам. Если Алиса ставит Дэйва выше Боба, а Дэйв ставит Алису выше Кэрол, то мы предполагаем, что Алиса и Дэйв расторгнут свои браки и сойдутся друг с другом — то есть их браки нестабильны.
Например, представим мир с тремя мужчинами (Адам, Боб и Чарльз) и тремя женщинами (Алиса, Бетти и Кэрол) со следующими предпочтениями:
Женщины
Алиса: Адам > Боб > Чарльз
Бетти: Адам > Чарльз > Боб
Кэрол: Боб > Адам > Чарльз
Мужчины
Адам: Бетти > Алиса > Кэрол
Боб: Бетти > Кэрол > Алиса
Чарльз: Кэрол > Алиса > Бетти
В этой ситуации следующим набор из трех браков является стабильным:
- Адам женится на Бетти
Оба оказываются со своим наилучшим выбором.
- Боб женится на Кэрол
Кэрол оказывается со своим наилучшим выбором. Боб предпочел бы расстаться с Кэрол, чтобы быть с Бетти, но Бетти отказала бы, потому что она со своим наилучшим выбором, Адамом.
- Чарльз женится на Алисе
Алиса предпочла бы расстаться с Чарльзом, чтобы быть с Адамом или Бобом, но Адам и Боб уже с женщинами, которые им нравятся больше, чем Алиса. Чарльз предпочел бы расстаться с Алисой, чтобы быть с Кэрол, но Кэрол уже со своим наилучшим выбором, Бобом.
По мере роста чисел не сразу очевидно, что можно всегда найти полный стабильный набор браков. Представьте деревню из 1300 мужчин и 1300 женщин, которые создают между собой 1 690 000 точек данных о предпочтениях, которые могут быть произвольно неудобными и несовместимыми: возможно, Боб любит Алису, но Алиса едва думает о Бобе и влюблена в Карла, который не обращает на неё внимания, так как тоскует по Диане, которая не думает ни о ком, кроме Эдмунда... представьте, что вы сваха, вручную подбирающая 1300 браков, которые все совместимы друг с другом.
На самом деле, вы всегда можете создать N стабильных браков при абсолютно любом наборе упорядочений предпочтений. Самый простой способ доказать это — продемонстрировать алгоритм, который можно запустить, чтобы надёжно сгенерировать валидный набор браков.
Решение
Классическое решение, алгоритм Гейла-Шепли, работает в течение серии дней (оказывается, не более N^2 дней).
В первый день каждый мужчина предлагает встречаться женщине, стоящей первой в его списке, и каждая женщина начинает встречаться с тем мужчиной, который нравится ей больше всего из предложивших. В нашем примере Адам и Боб попытались бы предложить Бетти, а Чарльз — Кэрол. Бетти начала бы встречаться с Адамом (отвергнув Боба), Кэрол начала бы встречаться с Чарльзом (единственное предложение), а Алиса осталась бы одна (ей никто не предложил).
В каждый последующий день все отвергнутые мужчины спускаются к следующей женщине в их списке, которая ещё их не отвергла, независимо от того, встречается ли она уже с другим мужчиной. Все женщины получают возможность выбрать: остаться со своим текущим парнем (если он есть) или принять одно из новых предложений. В нашем примере:
- На второй день Боб (которого отвергла Бетти) попытался бы предложить встречаться Кэрол (которая сейчас встречается с Чарльзом). Поскольку Кэрол нравится Боб больше, чем Чарльз, она рассталась бы с Чарльзом и стала бы встречаться с Бобом.
- На третий день Чарльз (которого только что отвергла Кэрол) попытался бы предложить встречаться Алисе. Поскольку она сейчас одна, она принимает.
- На четвёртый день не остается отвергнутых мужчин, и алгоритм завершается.
Как только не остается больше отвергнутых мужчин, все текущие романтические отношения становятся постоянными. В нашем примере мы получаем сочетание из предыдущего раздела: Адам-Бетти, Боб-Кэрол, Чарльз-Алиса.
Можно доказать, что этот алгоритм всегда завершается с тем, что все поженятся, и что браки, сгенерированные в конце, всегда стабильны.
Но какое решение?
Хорошо, мы знаем, что этот алгоритм всегда приводит всех в какой-то брак, где все эти браки стабильны по отношению друг к другу. Но большинство упорядочений предпочтений допускают несколько различных наборов взаимно стабильных браков — какой из них он находит? Рассмотрим эти предпочтения:
Женщины
Диана: Дэйв > Эд > Фрэнк
Эмма: Эд > Фрэнк > Дэйв
Флора: Фрэнк > Дэйв > Эд
Мужчины
Дэйв: Эмма > Флора > Диана
Эд: Флора > Диана > Эмма
Фрэнк: Диана > Эмма > Флора
Существует три разных решения, которые все составляют полный набор стабильных браков:
1. Дэйв-Диана, Эд-Эмма, Фрэнк-Флора. Эти браки стабильны, потому что все женщины получили свой наилучший выбор.
2. Дэйв-Эмма, Эд-Флора, Фрэнк-Диана. Эти браки стабильны, потому что все мужчины получили свой наилучший выборй.
3. Дэйв-Флора, Эд-Диана, Фрэнк-Эмма. Все получили свой второго выбора, но все браки стабильны, потому что притяжение никогда не бывает взаимным.
Что сделал бы наш алгоритм? Что ж, в первый день Дэйв предложил бы Эмме, Эд предложил бы Флоре, а Фрэнк предложил бы Диане... и всё. Все женщины приняли бы, ни один мужчина не был бы отвергнут, и все поженились бы в первый же день. Все мужчины получили своего наилучший выбор, а все женщины — свой наихудший.
На самом деле, алгоритм Гейла-Шепли всегда является оптимальным для мужчин. «Оптимальный для мужчин» не означает, что мужчины в среднем получают лучшее, чем женщины в среднем: это означает, что все мужчины одновременно получают наилучшую возможную жену, которую они могли бы получить в любом возможном стабильном расположении.
Это чрезвычайно сильное свойство.
Представьте Нью-Йорк, где примерно 1,5 миллиона неженатых мужчин и женщин. Существуют потенциально тысячи стабильных брачных расположений, согласующихся с их предпочтениями. Представьте, что мы запустили алгоритм Гейла-Шепли, и он нашел один конкретный набор из 1,5 миллиона браков.
Теперь рассмотрим одного единственного парня, Джейка, который в итоге женится на Джейн.
Джейку Джейн достаточно нравится, но она максимум 7 из 10, думает он, и иногда он задумчиво размышляет, мог ли он в каком-то другом мире быть с девяткой своей мечты. Затем однажды, прямо как в плохом фильме с Адамом Сэндлером, Сам Бог спускается и говорит: «Знаешь что, Джейк, я сейчас расторгну все браки и лично устрою все браки в Нью-Йорке так, чтобы ты лично оказался с наилучшей возможной для тебя женщиной... хотя, конечно, мы не хотим, чтобы она бросила тебя сразу после этого, поэтому я поищу любое стабильное паросочетание, которое ставит тебя, Джейк, лично в наилучшем положении из всех миллионов мужчин и женщин в этом городе».
Оказывается, Он потерпел бы неудачу. И Он также потерпел бы неудачу, чтобы сделать лучше для Адама, Брэта, Кевина, Эзры или любого другого парня — даже если бы всё, о чем Он заботился, это помочь этому одному чуваку!
И в то же время алгоритм всегда наихудший для женщин: из всех возможных валидных стабильных браков каждая отдельная женщина получает своего наихудшего возможного стабильного мужа. Любая перестановка, которую попробует Бог, вероятно, оставит Джейн в стабильном браке с мужчиной, который нравится ей больше, чем Джейк!
Просите то, что хотите
Я не вижу этот алгоритм здесь как по своей сути «мужской»-оптимальный и «женский»-пессимальный: он является оптимальным для просящего и пессимальным для того, к кому обращаются. Проблема вознаграждает активность и наказывает пассивность до поразительно сильной степени.
Проработка всех этих доказательств и миллиона вариантов в Сода Холле в 3 часа ночи, когда мне было девятнадцать, действительно повлияла на то, как я подходила к остальной своей жизни. Я инициировала почти все свои романтические отношения. Когда я увидел, что GiveWell ищет студентов предпоследнего курса для летней стажировки, я написала им имейл и спросила: «Я студент третьего курса, но могу ли я всё равно это сделать?». Впоследствии я работал в Open Phil (отпочковавшейся от GiveWell) девять лет. Я жила в четырёх групповых домах и инициировал все из них. Совсем недавно я предложила паре с двумя детьми жить со мной и моим мужем после того, как мы знали друг друга всего около года, что даже я считала немного безумным — они не только основали с нами удивительный дом, но и сказали мне, что у них никогда не хватило бы смелости просить нас.
Существует много способов достичь такого мышления, которые включают гораздо меньше математики. Некоторые предположения задачи уменьшают силу результата (хотя другие, на мой взгляд, усиливают его). Я на 70% просто хотел рассказать вам о крутой математике. Но я думаю, что основная динамика в доказательстве оптимальности для просящего и пессимальности для того, к кому обращаются, действительно применима к реальной жизни. Если вы выбираете только из предложений, которые получаете, вы никогда не пробуете ничего, пока кто-то там уже не узнал вас и не симпатизировал вам достаточно, чтобы потрудиться прийти к вам. Если вы просите что-то, вы получаете возможность выбирать из всей вселенной потенциальных вариантов, теоретически доступных вам — и кто знает, возможно, это сработает.
Это перевод статьи Аджеи Котрры. Оригинальное название: "The stable marriage problem".