Лепронавеянное
Право выбора мужчины - выбрать женщину. Право выбора женщины - выбрать мужчину из тех, что выбрали ее.
Этот алгоритм был математически исследован ещё в 62-м году. То есть, когда одна половина игроков делают предложения второй половине начиная с самых предпочтительных кандидатов, а каждый игрок второй половины рассматривает поступившие ему предложения и "держится" за самое предпочтительное, а на каждом следующем "раунде" может сменить его на какое-то из новых поступивших ему предложений.
Было показано, что алгоритм действительно даёт "устойчивое решение", т.е. в конце его работы никакая пара игроков уже не желает расторгнуть образовавшиеся связи и заключить связь с другим игроком. Но таких устойчивых решений существует много, и на практике этот алгоритм всегда приходит к решению максимально в пользу той стороны, которая делает предложения.
Есть строгое доказательство, но если грубо, "на пальцах", то идея вот в чём: легко видеть, что каждый "предлагающий" начинает с максимально предпочтительного для него кандидата, и раунд за раундом вынужден "снижать планку". В то время как каждая "принимающая" начинает с "минимальной планки" в первом раунде и в каждом следующем раунде её итоговый "избранник" строго не хуже "избранника" по итогу предыдущего раунда. То есть, удовлетворенность "предлагающих" движется от максимума вниз, а удовлетворенность "принимающих" движется от минимума вверх. Отсюда очевидно, что когда алгоритм завершит работу (не останется никого кто бы продолжал делать предложения), то удовлетворенность "предлагающих" окажется как можно ближе к начальному максимуму, а удовлетворённость "принимающих" - как можно ближе к начальному минимуму. Конечный расклад удовлетворит "предлагающих" как можно сильнее, и как можно слабее огорчит "принимающих".
Такой алгоритм обычно называют "алгоритм Гейла-Шепли" (Gale-Shapley). Он широко используется и даёт превосходные результаты при распределении выпускников-интернов по госпиталям, при распределении донорских органов по больным, при распределении детей по начальным школам, и так далее. Этот практический успех был даже отмечен Нобелевской Премией по экономике за 2012-й год.
Меня лично умиляет, как некоторые женщины искренне считают, что раз это мужчины обычно делают женщинам предложения, то преимущество на стороне женщин, и, дескать. женщины - более привилегированый класс. Потеха в том, что всё с точностью до наоборот: результат всегда максимально оптимален для "предлагающей стороны".
Видимо, это коварный заговор против женщин: мужчины им подыгрывают, мол, "Мы насмерть дерёмся за вашу благосклонность, милые принцессы!" а сами, небось, втихаря укатываются со смеху. Это как Том Сойер, который убедил мальчишек, что белить забор - это великая честь, и, так уж и быть, разрешил им делать это вместо него.
Кратко:
http://www.nobelprize.org/nobel_prizes/economics/laureates/2012/popular-economicsciences2012.pdf
Подробнее:
http://www.nobelprize.org/nobel_prizes/economics/laureates/2012/advanced-economicsciences2012.pdf
Этот алгоритм был математически исследован ещё в 62-м году. То есть, когда одна половина игроков делают предложения второй половине начиная с самых предпочтительных кандидатов, а каждый игрок второй половины рассматривает поступившие ему предложения и "держится" за самое предпочтительное, а на каждом следующем "раунде" может сменить его на какое-то из новых поступивших ему предложений.
Было показано, что алгоритм действительно даёт "устойчивое решение", т.е. в конце его работы никакая пара игроков уже не желает расторгнуть образовавшиеся связи и заключить связь с другим игроком. Но таких устойчивых решений существует много, и на практике этот алгоритм всегда приходит к решению максимально в пользу той стороны, которая делает предложения.
Есть строгое доказательство, но если грубо, "на пальцах", то идея вот в чём: легко видеть, что каждый "предлагающий" начинает с максимально предпочтительного для него кандидата, и раунд за раундом вынужден "снижать планку". В то время как каждая "принимающая" начинает с "минимальной планки" в первом раунде и в каждом следующем раунде её итоговый "избранник" строго не хуже "избранника" по итогу предыдущего раунда. То есть, удовлетворенность "предлагающих" движется от максимума вниз, а удовлетворенность "принимающих" движется от минимума вверх. Отсюда очевидно, что когда алгоритм завершит работу (не останется никого кто бы продолжал делать предложения), то удовлетворенность "предлагающих" окажется как можно ближе к начальному максимуму, а удовлетворённость "принимающих" - как можно ближе к начальному минимуму. Конечный расклад удовлетворит "предлагающих" как можно сильнее, и как можно слабее огорчит "принимающих".
Такой алгоритм обычно называют "алгоритм Гейла-Шепли" (Gale-Shapley). Он широко используется и даёт превосходные результаты при распределении выпускников-интернов по госпиталям, при распределении донорских органов по больным, при распределении детей по начальным школам, и так далее. Этот практический успех был даже отмечен Нобелевской Премией по экономике за 2012-й год.
Меня лично умиляет, как некоторые женщины искренне считают, что раз это мужчины обычно делают женщинам предложения, то преимущество на стороне женщин, и, дескать. женщины - более привилегированый класс. Потеха в том, что всё с точностью до наоборот: результат всегда максимально оптимален для "предлагающей стороны".
Видимо, это коварный заговор против женщин: мужчины им подыгрывают, мол, "Мы насмерть дерёмся за вашу благосклонность, милые принцессы!" а сами, небось, втихаря укатываются со смеху. Это как Том Сойер, который убедил мальчишек, что белить забор - это великая честь, и, так уж и быть, разрешил им делать это вместо него.
Кратко:
http://www.nobelprize.org/nobel_prizes/economics/laureates/2012/popular-economicsciences2012.pdf
Подробнее:
http://www.nobelprize.org/nobel_prizes/economics/laureates/2012/advanced-economicsciences2012.pdf