В течение жизни мы постоянно взаимодействуем с другими людьми. Маленькие дети, пытаясь добиться того, чтобы родители купили понравившуюся конфетку, часто шантажируют родителей своими слезами. Принимая решение заплакать, ребенок рискует — он не знает, как поведут себя папа с мамой. В чуть более взрослом возрасте абитуриенты, выбирающие вуз, принимают сложное решение о том, в какие университеты подать документы. Ошибка может стоить дорого: при неправильной стратегии можно оказаться в слабом университете или вообще остаться без заветного студенческого билета. Окончив вуз, юноши и девушки начинают искать работу. Перед интервью с работодателем они штудируют статьи в интернете о том, что можно и чего нельзя говорить на интервью, — они пытаются найти наилучшую стратегию своего поведения, исходя из ожиданий компании, в которую они устраиваются. Все эти ситуации объединяет то, что решения, которые принимают одни люди, оказывают влияние на других людей. Такие взаимодействия называются стратегическими. Именно их изучает теория игр. Чтобы проанализировать ту или иную реальную жизненную ситуацию стратегического взаимодействия и найти оптимальный вариант поведения в ней, необходимо сделать две вещи. Во-первых, необходимо формально записать ситуацию на языке теории игр, то есть создать модель (игру). Во-вторых, после того как модель (игра) составлена, ее необходимо решить. Этому мы будем учиться в течение курса. Мы разберем основные виды игр (одновременные и последовательные, с совершенной и несовершенной информацией, коалиционные и некоалиционные), приведем способы их решения и обсудим их на многочисленных примерах. Курс будет интересен желающим разобраться в том, как конкурируют друг с другом несколько компаний и можно ли гарантированно выиграть в шашки, есть ли смысл угрожать на переговорах и с кем стоит объединяться в коалиции в парламенте. FAQ В: Требуется ли предварительная подготовка для прохождения курса? О: Курс является базовым, поэтому он не требует специальной подготовки. Для его успешного освоения достаточно уверенных знаний курса математики в объеме школьной программы. В одном-двух примерах могут пригодиться знания начал математического анализа (дифференцирование функций одной переменной, необходимое условие экстремума) и знания начал теории вероятностей (понятие математического ожидания случайной величины). В: Что требуется для успешного окончания курса? О: Итоговая оценка за курс складывается из результатов 10 оцениваемых тестов. Для успешного окончания курса необходимо дать не менее 80 % правильных ответов на каждый из этих тестов.
Равновесие Нэша в смешанных стратегиях
Loading...
Из курса от партнера National Research University Higher School of Economics
Теория игр (Game Theory)
588 оценки
Из урока
Смешанные стратегии
Добро пожаловать на восьмую неделю курса! На восьмой неделе мы изучим смешанные стратегии, попробуем найти равновесия Нэша в смешанных стратегиях и узнаем о том, что в процессе поиска равновесий можно исключать стратегии, доминируемые смесью нескольких других стратегий. После просмотра видеолекций приглашаем вас выполнить очередной еженедельный тест. Удачи и успехов в обучении!
Познакомьтесь с преподавателями
Dmitry DagaevAssociate Professor, Deputy Vice Rector
Department of Higher Mathematics
Теперь, опираясь на этот факт, который мы только что вывели,
давайте попробуем проанализировать, а какие, собственно,
смешанные стратегии в этой игре ребята в равновесии могут играть?
Давайте зафиксируем смешанную стратегию Васи αO + (1 – α)P.
То есть с вероятностью α Вася играет стратегию «Орел»
и с вероятностью (1 – α) Вася играет стратегию «Решка».
Тогда, если Петя сыграет чистую стратегию «Орел»,
то ожидаемый выигрыш Пети можно посчитать.
И он будет равен (1 – 2α),
потому что с вероятностью α игра закончится в профиле (Орел, Орел),
и тогда Петя получит платеж, равный –1.
С вероятностью (1 – α) игра закончится
в профиле (Решка, Орел), и тогда Петя получит платеж, равный 1.
Сумма равна (1 – 2α).
В зависимости от α, то есть в зависимости от веса,
с которым Вася смешивает обе свои стратегии,
ожидаемый платеж Пети будет различаться.
Если Петя сыграет стратегию «Решка»,
то мы тоже можем посчитать ожидаемый платеж, который он получит.
Тогда с вероятностью α игра закончится в профиле (Орел, Решка),
и, соответственно, Петя получит платеж, равный 1.
С вероятностью (1 – α) игра закончится в профиле (Решка, Решка),
и тогда Петя получит –1.
Поэтому ожидаемый платеж Пети, в случае, если он играет чистую стратегию «Решка»,
в ответ на смешанную стратегию Васи
αO + (1 – α)P равен (2α – 1).
При разных значениях α либо стратегия «Орел»,
либо стратегия «Решка» может приносить ему больший выигрыш.
Соответственно, если α таково, что одна из этих стратегий приносит больше,
чем другая, то есть если Вася играет такую смесь,
что Пете выгоднее использовать одну из своих чистых стратегий,
смешивать свои стратегии Пете не будет иметь никакого смысла.
Единственная возможная ситуация, при которой Пете имеет смысл
смешивать две свои чистые стратегии «Орел» и «Решка» — это ситуация,
в которой обе эти чистые стратегии приносят одинаковый ожидаемый платеж.
Но тогда мы можем просто записать уравнение
2α – 1 = 1 – 2α,
то есть ожидаемые платежи, которые Пете приносит
чистая стратегия «Орел» и чистая стратегия «Решка», равны,
и отсюда мы находим, что α равно 1/2.
Значит, только лишь при одной стратегии Васи, а именно, при стратегии,
в которой Вася смешивает обе свои чистые стратегии с вероятностью 1/2,
Пете будет выгодно смешивать свои стратегии.
Во всех остальных случаях, при всех остальных α,
Пете будет выгодно играть одну из своих чистых стратегий.
Еще одно наблюдение.
Если Вася играет стратегию 1/2 О + 1/2 Р,
то тогда любая смешанная стратегия Пети принесет ему одинаковый платеж.
Потому что как стратегия «Орел», так и стратегия «Решка»
будет приносить Пете ровно 0.
Значит, любая смесь будет приносить Пете ровно 0.
Теперь зафиксируем стратегию Пети.
Пусть Петя с вероятностью β играет стратегию «Орел»,
а с вероятностью (1 – β) играет стратегию «Решка».
Давайте поймем, когда Васе может иметь смысл смешивать свои чистые стратегии?
Если Вася сыграет чистую стратегию «Орел»,
то тогда Васин ожидаемый платеж можем вычислить точно так же.
С вероятностью β игра закончится в профиле (Орел, Орел),
и Вася получит платеж, равный 1.
С вероятностью (1 – β) игра закончится в профиле (Орел, Решка),
и Вася получит платеж, равный –1.
И значит, ожидаемый платеж Васи будет равен (2β – 1).
Если Вася сыграет чистую стратегию «Решка»,
то тогда с вероятностью β игра закончится в профиле (Решка, Орел),
и Вася получит –1.
С вероятностью (1 – β) игра закончится
в профиле (Решка, Решка), и Вася выиграет — получит 1.
Значит, ожидаемый платеж Васи будет равен (1 – 2β).
Снова используем наше золотое правило, касающееся смешанных стратегий, а именно,
что смешивать имеет смысл только в том случае, если каждая из чистых стратегий,
входящих в смесь, приносит игроку одинаковый ожидаемый платеж.
Составляем уравнение 1 – 2β = 2β – 1 и получаем,
что смешивать Васе имеет смысл в одном единственном случае:
если Петя смешивает свои стратегии с вероятностью 1/2.
Но если Петя смешивает свои стратегии с вероятностью 1/2,
то любая стратегия Васи принесет ему одинаковый ожидаемый платеж.
С какими бы весами Вася ни смешивал свои чистые стратегии,
его ожидаемый платеж не изменится,
потому что каждая из чистых стратегий приносит одинаковый ожидаемый платеж.
Итак, давайте подытожим те результаты, которые мы получили.
Чтобы Васе было выгодно смешивать свои стратегии,
Петя должен играть стратегию 1/2 О + 1/2 Р.
Чтобы Пете было выгодно смешивать свои стратегии,
Вася также должен играть стратегию 1/2 О + 1/2 Р.
В этом случае ни одному из игроков
не будет выгодно отклониться и сыграть другую стратегию.
Действительно, в профиле, в котором оба мальчика смешивают каждую
из своих чистых стратегий с вероятностью 1/2, любая смешанная
стратегия Васи будет приносить ему одинаковый ожидаемый платеж, равный 0.
Любая смешанная стратегия Пети будет приносить ему одинаковый
ожидаемый платеж, равный 0, в ответ на стратегию Васи.
Поэтому отклоняться от этого профиля, в котором оба смешивают
каждую из своих чистых стратегий с вероятностью 1/2, не имеет смысла.
Таким образом, мы нашли равновесие Нэша в смешанных стратегиях.
Определение равновесия Нэша остается точно таким же, как и раньше.
Профиль называется равновесием Нэша,
если для любого игрока i и для его любой его
стратегии из множества его возможных стратегий —
только теперь это множество возможных стратегий включает не только чистые
стратегии, но в том числе и все смешанные стратегии —
так вот, какую бы другую стратегию si из множества
его возможных стратегий ни сыграл i-й игрок,
отклоняясь от профиля, он не должен получить больше,
чем играя стратегию из рассматриваемого профиля стратегий.
То есть если каждый из игроков играет оптимально при фиксированных
стратегиях всех остальных игроков,
то такой профиль называется равновесием Нэша в смешанных стратегиях.
Итак, что мы сделали на текущий момент?
Мы нашли равновесие Нэша в смешанных стратегиях.
Это профиль, в котором каждый из игроков смешивает каждую из двух своих чистых
стратегий с вероятностью 1/2.
Мы доказали, что никаких других равновесий Нэша в смешанных стратегиях,
в которых каждый из игроков смешивает обе свои стратегии с ненулевыми весами, нету.
И теперь единственное, что нам остается проверить, —
что в этой игре нет равновесий Нэша,
в которых игроки играют чистые стратегии, или равновесий Нэша, в которых один
из игроков играет чистую стратегию, а другой — смешивает свои стратегии.
Дело в том, что мы существенным образом в нашем решении
использовали тот факт, что каждый из игроков смешивает каждую из двух
своих стратегий с ненулевыми весами, когда составляли уравнение.
Это уравнение верно только в том случае, если обе эти стратегии,
обе чистые стратегии, игрок действительно играет.
Если он играет только одну стратегию, то ожидаемые платежи,
которые получает он от играемой стратегии и от той стратегии, которую он не играет,
то есть играет с вероятностью 0, они не обязаны быть равны.
Итак, давайте теперь проверим, что, во-первых,
в нашей игре нет равновесий в чистых стратегиях.
Это мы на самом деле поверили еще раньше.
И, второе, в нашей игре нет равновесий, в которых один из ребят
играет чистую стратегию, а другой смешивает обе свои чистые.
Действительно, если, предположим, Вася играет чистую стратегию «Орел»,
то тогда одна из чистых стратегий будет приносить Пете платеж, равный 1,
а другая стратегия — платеж, равный –1.
Соответственно, Пете нет никакого смысла смешивать хорошую стратегию,
которая приносит 1, и плохую стратегию, которая приносит –1.
Поэтому, аналогично, проверив, что нет равновесий,
в которых Вася играл чистую стратегию «Решка»,
а Петя смешивал бы обе свои чистые стратегии,
и проверив, что нет равновесий,
в которых Петя играл бы какую-либо из своих чистых стратегий,
а Вася смешивал, мы можем сделать вывод,
что в этой игре есть всего одно равновесие в смешанных стратегиях.
И это равновесие, в котором каждый из игроков смешивает обе
свои стратегии с вероятностью 1/2.
Обратите внимание: в чистых стратегиях равновесий нет, в смешанных оно появилось.
Оказывается, что равновесие в смешанных стратегиях есть в любой
конечной игре в нормальной форме.
Этот результат доказал Джон Нэш,
он носит его имя, «Теорема Нэша», и, в частности,
за это Джон Нэш в 1994 году
получил Нобелевскую премию совместно с Зелтеном и Харшаньи.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
