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