В течение жизни мы постоянно взаимодействуем с другими людьми. Маленькие дети, пытаясь добиться того, чтобы родители купили понравившуюся конфетку, часто шантажируют родителей своими слезами. Принимая решение заплакать, ребенок рискует — он не знает, как поведут себя папа с мамой. В чуть более взрослом возрасте абитуриенты, выбирающие вуз, принимают сложное решение о том, в какие университеты подать документы. Ошибка может стоить дорого: при неправильной стратегии можно оказаться в слабом университете или вообще остаться без заветного студенческого билета. Окончив вуз, юноши и девушки начинают искать работу. Перед интервью с работодателем они штудируют статьи в интернете о том, что можно и чего нельзя говорить на интервью, — они пытаются найти наилучшую стратегию своего поведения, исходя из ожиданий компании, в которую они устраиваются. Все эти ситуации объединяет то, что решения, которые принимают одни люди, оказывают влияние на других людей. Такие взаимодействия называются стратегическими. Именно их изучает теория игр. Чтобы проанализировать ту или иную реальную жизненную ситуацию стратегического взаимодействия и найти оптимальный вариант поведения в ней, необходимо сделать две вещи. Во-первых, необходимо формально записать ситуацию на языке теории игр, то есть создать модель (игру). Во-вторых, после того как модель (игра) составлена, ее необходимо решить. Этому мы будем учиться в течение курса. Мы разберем основные виды игр (одновременные и последовательные, с совершенной и несовершенной информацией, коалиционные и некоалиционные), приведем способы их решения и обсудим их на многочисленных примерах. Курс будет интересен желающим разобраться в том, как конкурируют друг с другом несколько компаний и можно ли гарантированно выиграть в шашки, есть ли смысл угрожать на переговорах и с кем стоит объединяться в коалиции в парламенте. FAQ В: Требуется ли предварительная подготовка для прохождения курса? О: Курс является базовым, поэтому он не требует специальной подготовки. Для его успешного освоения достаточно уверенных знаний курса математики в объеме школьной программы. В одном-двух примерах могут пригодиться знания начал математического анализа (дифференцирование функций одной переменной, необходимое условие экстремума) и знания начал теории вероятностей (понятие математического ожидания случайной величины). В: Что требуется для успешного окончания курса? О: Итоговая оценка за курс складывается из результатов 10 оцениваемых тестов. Для успешного окончания курса необходимо дать не менее 80 % правильных ответов на каждый из этих тестов.
Строго доминирующие и слабо доминирующие стратегии
Loading...
Из курса от партнера National Research University Higher School of Economics
Теория игр (Game Theory)
612 оценки
Из урока
Доминирующие и доминируемые стратегии
Добро пожаловать на вторую неделю курса! На первой неделе мы разобрались с тем, как игры можно моделировать, а теперь мы начинаем изучать способы решения теоретико-игровых моделей. Вторая неделя будет посвящена доминирующим и доминируемым стратегиям. Мы рассмотрим первые концепции решения игр: равновесие в строго (слабо) доминирующих стратегиях и равновесие, получаемое исключением строго (слабо) доминируемых стратегий, а также поговорим о том, как эти концепции связаны между собой.
Познакомьтесь с преподавателями
Dmitry DagaevAssociate Professor, Deputy Vice Rector
Department of Higher Mathematics
Итак, давайте для примера рассмотрим следующую игру.
Пусть у первого игрока есть две стратегии: a1 и a2.
У второго игрока — четыре стратегии: b1, b2, b3 и b4.
Какую стратегию сыграет первый игрок в этой игре?
Он должен подумать, что может выбрать второй игрок.
Если второй игрок выберет стратегию b1,
то тогда у первого игрока есть выбор между стратегиями a1 и a2.
Если первый игрок сыграет стратегию a1, то он получит платеж равный двойке,
а если стратегию a2, то платеж равный единице.
Значит, наилучшим ответом первого игрока на стратегию
второго игрока b1 является стратегия a1.
Мы сравнили платежи первого игрока в первом столбце, то есть в том столбце,
который соответствует стратегии второго игрока b1, нашли максимальный из них.
В данном случае этот максимальный платеж получается в результате стратегии a1.
И давайте помечать такие профили специальными символами.
Давайте в данном случае отметим точечкой профиль (a1, b1).
Эта точечка будет символизировать, что стратегия a1 первого игрока
является наилучшим ответом на стратегию b1 второго игрока.
В нашей нотации это можно записать так: наилучший ответ
(best response) первого игрока (индекс 1) на стратегию
b1 второго игрока — это стратегия a1 первого игрока.
Теперь точно так же поступим со всеми остальными стратегиями второго игрока.
Представим себя на месте первого игрока и подумаем о том, какую стратегию ему
было бы выгодно сыграть в ответ на каждую из оставшихся стратегий второго игрока.
Если второй игрок играет стратегию b2 — предположим, нам стало
откуда-то это известно, — мы рассматриваем второй столбец нашей матрицы.
Из него видно, что если мы сыграем стратегию a1, то наш платеж
будет равен трем, а если сыграем стратегию a2, то наш платеж будет равен двум.
Выбираем наилучший ответ — в данном случае это снова стратегия a1, —
и помечаем этот профиль снова точечкой.
Итак, наилучший ответ первого игрока на стратегию второго b2 — это стратегия a1.
Точно так же поступаем с анализом стратегий b3 и b4.
Если нам известно откуда-то, что второй игрок будет играть стратегию b3,
то мы будем уверенны в том, что наилучшим ответом для нас будет стратегия a1.
Точно так же наилучшим ответом на стратегию b4 снова будет стратегия a1.
Оказалось, что матрица этой игры устроена так,
что какую бы стратегию ни сыграл второй игрок,
оптимальной для нас стратегией будет стратегия a1.
Такие стратегии в теории игр называются доминирующими.
Теперь давайте посмотрим на второго игрока.
Найдем его наилучший ответ в ответ на стратегию первого игрока a1.
Фиксируем первую строчку и смотрим на вторые числа в первой строчке.
Если второй игрок играет b1, то он получит платеж равный семи.
Если b2, то платеж равный двум.
Если b3, то платеж равный пяти.
Если b4, то платеж равный шести.
Выбирая максимальный из этих платежей, мы получаем, что наилучшим
ответом второго игрока на стратегию первого a1 является стратегия b1.
Аналогично найдем наилучший ответ второго игрока на стратегию a2 первого игрока.
Теперь, сравнивая вторые числа во второй строчке и находя максимальные из них,
мы увидим, что наилучшим ответом второго игрока в ответ на
стратегию a2 первого игрока снова является стратегия b1.
У второго игрока тоже есть доминирующая стратегия — стратегия b1.
Давайте введем некоторые обозначения и дадим формальные определения.
Предположим, что у нас задана игра n лиц в нормальной форме.
И пусть (s1, ..., sn) — это некоторый профиль стратегий.
Будем для любого i от 1 до n обозначать через
s с индексом -i набор стратегий всех остальных игроков, кроме i-го.
Нам будет очень удобно в дальнейшем использовать в качестве обозначения,
короткого обозначения, набор всех игроков кроме одного конкретного.
Таким образом, s-i — это набор всех стратегий
игроков из профиля (s1, ..., sn) кроме стратегии si i-го игрока.
Давайте рассмотрим снова тот пример, который мы уже обсудили.
В этой игре у нас два игрока.
Для любого профиля стратегий (s1, s2) через s-2 в данном
случае будет обозначаться стратегия первого игрока s1.
Множество S (большое) -2 в данном случае будет иметь вид a1,
a2, то есть оно будет состоять из всех стратегий первого игрока.
Будем говорить, что стратегия si i-го игрока называется строго доминирующей,
если для любой стратегии si' (штрих) i-го игрока и для любого
набора стратегий всех остальных игроков s-i выполняется неравенство.
Какое неравенство?
Платеж, который получает i-й игрок, если он играет стратегию si,
больше платежа, который получает i-й игрок,
если он вместо нее сыграет вот эту вот другую стратегию s’i,
при том что все остальные игроки продолжают играть те же самые стратегии s-i.
То есть при любых стратегиях других игроков платеж,
который получает i-й игрок, играя свою доминирующую стратегию si,
должен быть больше, чем платеж, который получает этот игрок,
если он сыграет не доминирующую стратегию si' (штрих).
Вот если это верно,
то тогда мы говорим, что стратегия si называется строго доминирующей.
В том примере, который мы с вами уже рассматриваем,
стратегия b1 второго игрока — строго доминирующая для него,
стратегия a1 первого игрока — строго доминирующая для него.
На определение строго доминирующей стратегии очень
похоже определение слабо доминирующей стратегии.
Давайте обсудим его.
Стратегия si i-го игрока называется слабо доминирующей,
если для любой другой стратегии si' (штрих) i-го
игрока и любого набора стратегий s-i всех остальных
игроков выполняется неравенство, очень похожее неравенство на то, которое
было в предыдущий раз с одним исключением: теперь это неравенство не строгое.
То есть платеж, который получает i-й игрок,
если он играет стратегию si, а все остальные — стратегию s-i.
Так вот, платеж, который получает i-й игрок,
должен быть больше или равен платежа, который получает i-й игрок,
если он вместо стратегии si сыграет стратегию si' (штрих),
при том что все остальные игроки продолжают играть те же самые стратегии.
Вот если стратегия si удовлетворяет этому условию,
мы будем называть ее слабо доминирующей.
То есть условие на самом деле слабого доминирования, оно несколько слабее,
чем условие сильного, строгого доминирования.
Давайте изменим нашу предыдущую игру, исправим всего лишь один платеж.
В профиле (a1, b2) давайте исправим платеж второго игрока на семерку.
Что тогда получится?
Наилучший ответ второго игрока на стратегию a1 — это не стратегия b1,
это любая из двух стратегий: b1 или b2.
Вот давайте их тоже обе пометим.
Вопрос: верно ли теперь, что в этой новой игре с исправленными
платежами стратегия b1 второго игрока является строго доминирующей?
Нет, неверно, потому что теперь стратегия b1 не приносит максимально
возможный платеж в ответ на любую из стратегий первого игрока, а именно,
если вдруг первый игрок решит сыграть стратегию a1, то стратегия b1 приносит
платеж равный семи, но это не максимальный из всех платежей, потому что стратегия b2
в ответ на стратегию первого игрока a1 также принесет платеж равный семи.
Значит, условие,
которое содержится в определении строго доминирующей стратегии, не выполняется.
Однако про стратегию b1 всё равно можно сказать что-то хорошее,
а именно, можно сказать, что она является слабо доминирующей, потому что,
какую бы стратегию ни сыграл первый игрок, стратегия b1 не хуже для второго игрока,
чем любая из оставшихся стратегий второго игрока.
Заметим, что, вообще говоря,
любая строго доминирующая стратегия является и слабо доминирующей, потому что,
ну, уж если верно, что стратегия приносит i-му игроку больший платеж,
чем любая другая его стратегия в ответ на любой набор стратегий всех остальных
игроков, то тогда заведомо верно и нестрогое неравенство,
что эта стратегия приносит ему не меньший платеж, чем любая другая стратегия.
То есть любая строго доминирующая стратегия является в том числе
и слабо доминирующей.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
