В течение жизни мы постоянно взаимодействуем с другими людьми. Маленькие дети, пытаясь добиться того, чтобы родители купили понравившуюся конфетку, часто шантажируют родителей своими слезами. Принимая решение заплакать, ребенок рискует — он не знает, как поведут себя папа с мамой. В чуть более взрослом возрасте абитуриенты, выбирающие вуз, принимают сложное решение о том, в какие университеты подать документы. Ошибка может стоить дорого: при неправильной стратегии можно оказаться в слабом университете или вообще остаться без заветного студенческого билета. Окончив вуз, юноши и девушки начинают искать работу. Перед интервью с работодателем они штудируют статьи в интернете о том, что можно и чего нельзя говорить на интервью, — они пытаются найти наилучшую стратегию своего поведения, исходя из ожиданий компании, в которую они устраиваются. Все эти ситуации объединяет то, что решения, которые принимают одни люди, оказывают влияние на других людей. Такие взаимодействия называются стратегическими. Именно их изучает теория игр. Чтобы проанализировать ту или иную реальную жизненную ситуацию стратегического взаимодействия и найти оптимальный вариант поведения в ней, необходимо сделать две вещи. Во-первых, необходимо формально записать ситуацию на языке теории игр, то есть создать модель (игру). Во-вторых, после того как модель (игра) составлена, ее необходимо решить. Этому мы будем учиться в течение курса. Мы разберем основные виды игр (одновременные и последовательные, с совершенной и несовершенной информацией, коалиционные и некоалиционные), приведем способы их решения и обсудим их на многочисленных примерах. Курс будет интересен желающим разобраться в том, как конкурируют друг с другом несколько компаний и можно ли гарантированно выиграть в шашки, есть ли смысл угрожать на переговорах и с кем стоит объединяться в коалиции в парламенте. FAQ В: Требуется ли предварительная подготовка для прохождения курса? О: Курс является базовым, поэтому он не требует специальной подготовки. Для его успешного освоения достаточно уверенных знаний курса математики в объеме школьной программы. В одном-двух примерах могут пригодиться знания начал математического анализа (дифференцирование функций одной переменной, необходимое условие экстремума) и знания начал теории вероятностей (понятие математического ожидания случайной величины). В: Что требуется для успешного окончания курса? О: Итоговая оценка за курс складывается из результатов 10 оцениваемых тестов. Для успешного окончания курса необходимо дать не менее 80 % правильных ответов на каждый из этих тестов.
Определение смешанной стратегии
Loading...
From the course by National Research University Higher School of Economics
Теория игр (Game Theory)
584 оценки
From the lesson
Смешанные стратегии
Добро пожаловать на восьмую неделю курса! На восьмой неделе мы изучим смешанные стратегии, попробуем найти равновесия Нэша в смешанных стратегиях и узнаем о том, что в процессе поиска равновесий можно исключать стратегии, доминируемые смесью нескольких других стратегий. После просмотра видеолекций приглашаем вас выполнить очередной еженедельный тест. Удачи и успехов в обучении!
Meet the Instructors
Dmitry DagaevAssociate Professor, Deputy Vice Rector
Department of Higher Mathematics
[ЗАСТАВКА] [ЗАСТАВКА]
Теперь давайте обратимся, собственно, к теории игр.
Давайте рассмотрим игру, про которую мы уже говорили, — «Орлянку».
Как всегда, в нее играют двое игроков: Вася и Петя.
Каждый из игроков независимо друг от друга
пишет на бумаге одно из двух слов: либо «Орел», либо «Решка».
Затем они сравнивают сделанный ими одновременно и независимо друг от
друга выбор.
Если на бумаге оказываются написаны одинаковые слова,
то побеждает Вася, а если разные, то Петя.
Предположим, что они играют на 1 рубль.
У каждого из игроков есть две чистые стратегии: либо написать слово «Орел»,
либо написать слово «Решка».
Матрица платежей устроена следующим образом.
Давайте посмотрим на отдельные профили в этой игре.
Если ребята написали разные слова, то тогда по условию выиграл Петя.
Но тогда Васе выгодно отклониться и написать такое же слово, что и Петя,
и победить.
Если ребята написали одинаковые слова, то тогда уже Пете было бы
выгодно отклониться и написать слово, отличное от васиного.
Значит, равновесия Нэша в чистых стратегиях в этой игре нет.
Однако, предположим,
что теперь ребята договорились сыграть в эту игру 100 раз подряд.
Какую стратегию выбрать игроку в этой игре?
Давайте предположим, что Васе.
Если Вася все время будет играть стратегию «Орел»,
то рано или поздно Петя разгадает его план и найдет стратегию,
которая будет обыгрывать эту стратегию.
Значит, наверное, 100 раз подряд писать «Орел» не
является оптимальной стратегией Васи.
Поэтому чтобы запутать соперника, Вася поступает следующим образом.
Он достал шестиграный кубик и перед каждой следующей игрой подкидывает его.
Он решил, что если на кубике выпадет число от 1 до 4, то он напишет слово «Орел»,
а если на кубике выпадет число 5 или число 6, то он напишет «Решку».
Петя тоже понял, что если он все время будет писать одно и то же слово,
то проиграет,
поскольку Вася разгадает его план и найдет хороший ответ против такой стратегии.
Поэтому Петя решил поступить следующим образом: он тоже хочет запутать Васю,
он достал сто бумажек, на пятидесяти из них написал слово «Орел»,
на других пятидесяти написал слово «Решка»,
и перед каждым раундом игры он вытягивает из этой кучи бумажек одну-единственную,
смотрит, что на ней написано и играет ту стратегию,
которую предписывает ему написанное на этой бумажке слово.
На какие ожидаемые платежи могут рассчитывать в этой игре ребята?
С вероятностью 1/2 Петя напишет слово «Орел»,
с вероятностью 1/2 — «Решку».
Вася в 4 случаях из 6 напишет «Орел» и в 2 случаях их 6 — «Решку».
Таким образом, игра может закончиться в разных профилях, в разных исходах.
Это означает, что выигрыш Васи и выигрыш Пети в этой
игре является случайной величиной, а значит,
мы будем ориентироваться на принятие решений Васи и Пети о своих стратегиях,
исходя из предположения, что они максимизируют свой ожидаемый платеж.
С какой вероятностью будет сыгран каждый из профилей?
Профиль «Орел–Орел» будет сыгран с вероятностью 1/3,
потому что с вероятностью 4/6 Вася напишет «Орел»,
с вероятностью 1/2 Петя напишет «Орел».
Они делают это решение, они принимают это решение независимо друг от друга,
поэтому вероятность того, что они оба одновременно напишут «Орел» — это просто
произведение вероятностей того, что каждый из них пишет «Орел».
А соответственно, 4/6 умножить на 1/2 — это 1/3.
Игра закончится в одном отдельном раунде в профиле «Орел–Орел» с вероятностью 1/3.
Точно так же найдем вероятности,
с которыми закончится игра в каждом из оставшихся профилей.
В профиле «Орел – Решка» игра закончится
с вероятностью 4/6 умножить на 1/2, то есть с вероятностью 1/3.
В профиле «Решка – Орел» игра закончится с вероятностью 2/6
умножить на 1/2, то есть с вероятностью 1/6.
Наконец, в профиле «Решка – Решка» игра закончится с вероятностью
2/6 умножить на 1/2, то есть с вероятностью 1/6.
С какой вероятностью ребята напишут одинаковые слова?
Они напишут одинаковые слова в одном из двух случаев: либо в
профиле «Орел – Орел», либо в профиле «Решка – Решка».
Как мы только что подсчитали, профиль «Орел – Орел» будет сыгран с вероятностью
1/3, а профиль «Решка – Решка» — с вероятность 1/6.
Значит, сумарная вероятность того, что ребята напишут одинаковые слова,
равна 1/3 плюс 1/6, то есть 1/2.
Вероятность того, что они напишут разные слова,
соответственно, равна 1/6 плюс 1/3 — тоже 1/2.
Давайте посчитаем, какой платеж получит Вася.
С вероятностью 1/2 ребята пишут одинаковые слова,
и по условиям игры тогда Вася выигрывает.
С вероятностью 1/2 ребята пишут разные слова,
и по условиям игры в этом случае Вася проигрывает.
Значит ожидаемый платеж Васи будет равен 1/2
× 1 + 1/2 × (−1), то есть ноль.
В среднем Вася в этой игре будет получать ноль,
если игроки выбрали именно такие стратегии.
Ожидаемый платеж Пети можно посчитать точно таким же образом.
С вероятностью 1/2 ребята пишут разные слова, и тогда Петя выигрывает,
с вероятностью 1/2 ребята пишут одинаковые слова, и тогда Петя проигрывает.
И ожидаемый платеж Пети равен 1/2 × 1 + 1/2 × (−1) — тоже ноль.
Вообще говоря, платеж Пети можно было посчитать и по-другому.
Поскольку эта игра с нулевой суммой, то есть антагонистическая игра,
в которой в любом профиле платеж Пети противоположен платежу Васи,
то несложно показать, что если ожидаемый платеж Васи равен нулю,
то и ожидаемый платеж Пети в такой игре будет равен нулю.
Давайте заметим, что стратегии, выбранные Васей и Петей, вообще говоря,
отличаются от чистых стратегий, которые мы рассматривали на всех предыдущих лекциях.
Раньше мы запрещали игрокам использовать кубик при принятии своих решений.
Теперь же Петя смешивает две свои чистые стратегии с весами 1/2,
а Вася играет чистую стратегию «Орел» с весом
2/3 и чистую стратегию «Решка» — с весом 1/3.
Таким образом, мы расширили множество возможных стратегий каждого из игроков.
Такие стратегии, которые сейчас использовали Вася и Петя,
называются смешанными.
Давайте дадим формальное определение: пусть у нас зафиксировано
множество всех чистых стратегий игрока, давайте будем обозначать его S,
и оно состоит из чистых стратегий {s1, s2, ..., sn} и так далее.
Для любых весов α1,
α2, ..., αn, таких, что каждый из этих
весов лежит в интервале от 0 до 1 включительно,
и сумма этих весов равна 1,
так вот для любых таких весов стратегия вида
«играем чистую стратегию s1 с вероятностью α1,
играем чистую стратегию s2 с вероятностью α2, и так далее,
играем чистую стратегию sn с вероятностью αn»,
так вот такая стратегия называется смешанной стратегией игрока.
Обозначать эту смешанную стратегию мы будем
в виде суммы α1s1 +...
+ αnsn.
Множество всех смешанных стратегий игрока,
построенное по множеству всех чистых стратегий игрока s,
будем обозначать через ΔS.
Смешанную стратегию можно интерпретировать следующим образом: если
у нас есть стратегия α1s1 +...
+ αnsn, то перед тем как сделать свой выбор,
игрок достает генератор случайных чисел,
программирует этот генератор случайных чисел так,
чтобы он с вероятностью α1 выдавал стратегию s1,
с вероятностью α2 выдавал стратегию s2, и так далее,
с вероятностью αn выдавал стратегию sn.
И вот он после того как запрограммировал этот генератор случайных чисел,
запускает его один раз, и играет ту стратегию,
которую предписывает ему сыграть реализация случайной величины,
запрограммированной в этом генераторе случайных чисел.
Веса α1, ..., αn можно трактовать как вероятности,
с которыми игрок играет ту или иную свою чистую стратегию.
Именно поэтому мы наложили ограничение на эти веса α1, ..., αn.
Все они лежат в интервале от 0 до 1, и сумма этих коэффициентов должна равняться
1, потому что уж точно мы всегда должны выбрать одну из чистых стратегий,
и мы не можем сыграть ту или иную стратегию,
с вероятностью меньшей нуля или с вероятностью, большей единицы.
Заметим, что чистые стратегии являются частным случаем смешанных стратегий.
Например, если игрок программирует свой генератор случайных чисел так,
что α1 равно единице, а все остальные коэффициенты равны нулю,
то он фактически играет чистую стратегию s1.
А если он программирует свой генератор случайных чисел так,
что αn равно единице, а все остальные веса равны нулю,
то он играет чистую стратегию sn.
Таким образом, мы расширили
множество возможных стратегий, которые есть у игрока.
К тем возможностям, которые у него были раньше,
когда он мог играть только чистые стратегии,
мы добавили возможность использовать этот самый генератор чисел.
Ну принесли ему, и теперь перед каждым запуском игры он имеет
право программировать этот генератор случайных чисел таким образом,
в зависимости от того, какую смешанную стратегию он хочет сыграть,
какие веса той или иной чистой стратегии придать,
и вот эта вот программа, вот эта вот реализация случайной
величины и будет сыгранной чистой стратегией игрока.
[ЗАСТАВКА] [ЗАСТАВКА]
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
