В течение жизни мы постоянно взаимодействуем с другими людьми. Маленькие дети, пытаясь добиться того, чтобы родители купили понравившуюся конфетку, часто шантажируют родителей своими слезами. Принимая решение заплакать, ребенок рискует — он не знает, как поведут себя папа с мамой. В чуть более взрослом возрасте абитуриенты, выбирающие вуз, принимают сложное решение о том, в какие университеты подать документы. Ошибка может стоить дорого: при неправильной стратегии можно оказаться в слабом университете или вообще остаться без заветного студенческого билета. Окончив вуз, юноши и девушки начинают искать работу. Перед интервью с работодателем они штудируют статьи в интернете о том, что можно и чего нельзя говорить на интервью, — они пытаются найти наилучшую стратегию своего поведения, исходя из ожиданий компании, в которую они устраиваются. Все эти ситуации объединяет то, что решения, которые принимают одни люди, оказывают влияние на других людей. Такие взаимодействия называются стратегическими. Именно их изучает теория игр. Чтобы проанализировать ту или иную реальную жизненную ситуацию стратегического взаимодействия и найти оптимальный вариант поведения в ней, необходимо сделать две вещи. Во-первых, необходимо формально записать ситуацию на языке теории игр, то есть создать модель (игру). Во-вторых, после того как модель (игра) составлена, ее необходимо решить. Этому мы будем учиться в течение курса. Мы разберем основные виды игр (одновременные и последовательные, с совершенной и несовершенной информацией, коалиционные и некоалиционные), приведем способы их решения и обсудим их на многочисленных примерах. Курс будет интересен желающим разобраться в том, как конкурируют друг с другом несколько компаний и можно ли гарантированно выиграть в шашки, есть ли смысл угрожать на переговорах и с кем стоит объединяться в коалиции в парламенте. FAQ В: Требуется ли предварительная подготовка для прохождения курса? О: Курс является базовым, поэтому он не требует специальной подготовки. Для его успешного освоения достаточно уверенных знаний курса математики в объеме школьной программы. В одном-двух примерах могут пригодиться знания начал математического анализа (дифференцирование функций одной переменной, необходимое условие экстремума) и знания начал теории вероятностей (понятие математического ожидания случайной величины). В: Что требуется для успешного окончания курса? О: Итоговая оценка за курс складывается из результатов 10 оцениваемых тестов. Для успешного окончания курса необходимо дать не менее 80 % правильных ответов на каждый из этих тестов.
Свойства алгоритма отсроченного принятия предложения
Loading...
來自 National Research University Higher School of Economics 的課程
Теория игр (Game Theory)
658 個評分
從本節課中
Задача о стабильных мэтчингах
Добро пожаловать на девятую неделю курса, друзья! Эта неделя полностью посвящена задаче о стабильных мэтчингах (паросочетаниях). Всплеск интереса к этой теме произошел в 2012 году, когда Нобелевскую премию по экономике получили Ллойд Шепли и Эл Рот за теоретические исследования в области стабильных мэтчингов и практику дизайна рынков. Вместе с видеороликами опубликован новый тест, а также подборка дополнительных материалов. Успехов и хорошего настроения!
與講師見面
Dmitry DagaevAssociate Professor, Deputy Vice Rector
Department of Higher Mathematics
Теперь давайте изучим несколько свойств этого алгоритма.
Самое главное свойство, которое, собственно,
и доказывает, что у нас для любого набора предпочтений найдется
по крайней мере один стабильный мэтчинг.
Оказывается, что в результате работы алгоритма отсроченного принятия
предложения гарантированно получится стабильный мэтчинг.
Для того чтобы это доказать, нужно проверить два свойства.
Во-первых, что выполняется свойство индивидуальной рациональности,
и во-вторых, что выполняется свойство парной рациональности.
Давайте проверим свойство индивидуальной рациональности.
Предположим противное: пусть оно не выполняется.
Тогда найдется какой-то мужчина или какая-то женщина,
которым было бы выгоднее остаться одному.
Ну, давайте предположим для определенности, что нашелся мужчина m,
которому было бы выгоднее остаться одному,
чем быть вместе с той альтернативой, которая получилась в результате работы
алгоритма отсроченного принятия предложения.
Но это невозможно.
В алгоритме мужчина m не мог сделать предложение женщине μ(m),
то есть той женщине, которая у него получилась в этом мэтчинге μ,
потому что она хуже в списке его предпочтений,
чем альтернатива «остаться одному», а это означает, по определению алгоритма,
по описанию алгоритма, что мужчина m никогда бы не сделал
предложение этой женщине μ(m).
Точно так же, если бы вдруг в этом мэтчинге нашлась бы женщина w,
которая оказалась в паре с мужчиной, который хуже,
чем альтернатива «остаться одной», мы бы получили,
что это невозможно, потому что, по описанию алгоритма отсроченного
принятия предложения, женщина отказывает любому мужчине,
который хуже, чем альтернатива «остаться одной».
Таким образом, мэтчинг μ обладает свойством индивидуальной рациональности.
Теперь проверим, что мэтчинг μ обладает свойством парной рациональности.
Снова предположим противное.
Пусть нашлась такая пара m и w, такие мужчина и женщина,
что им было бы лучше вместе, чем с теми парами, которые
получились в результате работы алгоритма отсроченного принятия предложения.
Но если для мужчины m женщина w лучше,
чем та женщина, которая находится в паре в соответствии
с мэтчингом μ, то это означает, что мужчина m
обязан был раньше сделать предложение
вот этой вот женщине w, и раз они не остались в паре,
то это означает, что женщина w отказалась от этого предложения.
Но тогда получается,
что для женщины w альтернатива,
которая у нее есть в мэтчинге μ, лучше альтернативы «быть вместе с мужчиной m».
А это противоречие тому предположению, которое мы сделали до этого:
что для мужчины m и женщины w быть вместе друг с другом было бы лучше,
чем вместе с теми парами, которые у них есть в мэтчинге μ.
Полученное противоречие доказывает,
что мэтчинг μ обладает свойством парной рациональности.
Мы рассмотрели алгоритм отсроченного принятия предложения,
в котором делали первыми предложения мужчины.
Естественно, может возникнуть вопрос: а почему же первыми не могут делать
предложения женщины?
Могут, тогда получится в каком-то смысле симметричный алгоритм.
Мы будем называть соответственно M-proposing DAA — тот алгоритм,
в котором первыми предложения делают мужчины, а W-proposing DAA — алгоритм,
в котором первыми делают предложения женщины.
Если применить W-proposing DAA к предыдущему примеру,
то получится мэтчинг, в котором мужчина m1 будет в паре с женщиной w1,
мужчина m2 будет в паре с женщиной w3, а мужчина m3 будет в паре с женщиной w2.
Естественно, выполняется свойство, аналогичное свойству 1, то есть мэтчинг,
который получается в результате работы W-proposing DAA, тоже является стабильным.
Еще одно определение.
Давайте называть женщину w достижимой
для мужчины m, если существует по крайней мере один стабильный мэтчинг,
в котором мужчина m находится в паре с женщиной w.
В предыдущем примере существовало два стабильных мэтчинга.
Мужчина m1 в этих стабильных мэтчингах находился оба раза с женщиной w1,
поэтому она является единственной достижимой для него женщиной.
Для мужчины m2 и m3 достижимыми являются женщины w2 и w3,
поскольку найдутся такие стабильные мэтчинги,
в которых m2 и m3 могут претендовать на w2 и на w3.
Другими словами, пара не является достижимой в тех случаях,
если она слишком хороша или, наоборот,
слишком плоха, чтобы встретиться вместе в стабильном мэтчинге.
Можно дать и симметричное определение достижимости мужчины m для женщины w.
В предыдущем примере для женщины w1 был достижимым только мужчина m1,
в то время как для женщин w2 и w3 были достижимы мужчины m2 и m3.
Давайте рассмотрим еще несколько свойств
алгоритма отсроченного принятия предложения.
В результате работы M-proposing DAA каждый
мужчина получает наилучшую из достижимых для него женщин,
то есть этот алгоритм приводит к такому
стабильному мэтчингу, в котором все мужчины оказываются довольными.
Каждый из них оказывается в паре с той женщиной,
которая является наилучшей из достижимых для него.
Наоборот, симметричное свойство.
В результате работы W-proposing DAA каждая женщина
получает наилучшего из достижимых для нее мужчин.
В каком-то смысле это свойство является хорошей новостью.
Существует рецепт успеха: та сторона, которая делает предложение,
получает наилучшего возможного, достижимого, партнера.
То есть нужно не ждать, а делать предложения первыми.
Еще одно свойство.
Если есть два стабильных мэтчинга μ1 и μ2,
причем эти мэтчинги можно сравнить с точки зрения предпочтений мужчин,
то есть предположим, что в мэтчинге μ1
у всех мужчин в паре стоит не худшая альтернатива, чем в мэтчинге μ2.
Тогда оказывается, что для всех женщин мэтчинг μ1 будет не лучше мэтчинга μ2,
то есть, наоборот, для женщин в мэтчинге μ1
будет в паре стоять не лучший мужчина,
чем в мэтчинге μ2.
То есть если есть два каких-то стабильных мэтчинга, которые можно сравнить с точки
зрения предпочтений мужчин, — один из них лучше другого, то с точки зрения женщин,
эти два стабильных мэтчинга будут сравниваться с точностью до наоборот.
Лучшим будет тот, который хуже для мужчин.
И это в каком-то смысле плохая новость.
Не получится сделать хорошо абсолютно всем.
Интересы мужчин и женщин оказываются противоположными.
В стабильных мэтчингах чем лучше пара,
которая есть у мужчин, тем хуже пара, которая есть у женщин.
Подчеркну, что речь идет о сравнении только стабильных мэтчингов.
Давайте рассмотрим такой пример свадебного рынка.
Даны 4 мужчины,
4 женщины и их предпочтения на множестве соответствующих альтернатив.
Можно проверить,
что при таком наборе предпочтений существует 4 стабильных мэтчинга.
Эти мэтчинги μ1, μ2, μ3 и μ4 перечислены на слайде.
Мэтчинг μ1 получается в результате работы алгоритма
отсроченного принятия предложения, в котором предложения делают мужчины.
Он является наилучшим из стабильных мэтчингов для мужчин и наихудшим
из стабильных мэтчингов для женщин.
Можно проверить, что мэтчинг μ4 получается в результате работы алгоритма
отсроченного принятия предложений, в котором предложения делают женщины.
И он является наилучшим из стабильных мэтчингов для женщин
и наихудшим из стабильных мэтчингов для мужчин.
Мэтчинги μ2 и μ3 хуже для мужчин,
чем мэтчинг μ1, но лучше, чем мэтчинг μ4.
Обратим внимание, что мы не можем сравнить между собой
мэтчинги μ2 и μ3, потому что нельзя про них сказать,
что в одном из них для всех мужчин альтернативы,
которые у них есть, не хуже, чем в другом мэтчинге.
Точно так же мэтчинги μ2 и μ3 хуже для женщин,
чем мэтчинг μ4, но лучше для женщин, чем мэтчинг μ1.
При этом мы снова не можем сравнить мэтчинги μ2 и μ3 с точки зрения женщин.
Получается, что все стабильные мэтчинги можно упорядочить в виде вот
такой вот решетки, в которой чем выше располагается мэтчинг,
тем он лучше для мужчин и тем хуже для женщин.
Если оказалось, что один из стабильных мэтчингов выше другого,
то есть можно спуститься по цепочке, от одного к другому, то тот,
который выше, является более предпочтительным для мужчин,
но менее предпочтительным для женщин.
Вот какими бы ни были предпочтения,
все стабильные мэтчинги можно упорядочить в виде такой решетки,
в которой интересы мужчин оказались противоположными интересам женщин.
