Как найти доминирующую стратегию

Доминирование стратегий

В ряде случаев часть чистых стратегий
игроков может быть исключена после
анализа платежной матрицы путем
вычеркивания соответствующих строк
или столбцов. При этом стратегии,
являющиеся оптимальными в игре с
сокращенной матрицей, будут оптимальными
стратегиями и для исходной игры. В основе
такого анализа лежит принцип доминирования.
Он исходит из того факта, что если одна
из стратегий игрока заведомо лучше
другой, то при анализе стратегий на
оптимальность худшая может не
рассматриваться. Игрок не будет ее
использовать, так как это противоречит
принципу рациональности его поведения.
Приведем соответствующие определения.

Чистая стратегия А_i первого
игрока доминирует его чистую
стратегию А_k,
если выполнены неравенства:

a_ij
≥ a_kj
для всех

,
причем

для некоторого индекса j₀,

т.е. все элементы i-й строки платежной
матрицы игры А не меньше соответствующих
элементов ее k-й строки и хотя бы
один элемент строго больше. В этом случае
стратегия А_k
называется доминируемой.

Соответственно, чистая стратегия B_j
второго игрока доминирует его чистую
стратегию B_l,
если выполнены неравенства:

a_il
≥ a_ij
для всех

;
причем

для некоторого индекса i₀,

т.е. все элементы j-го
столбца платежной матрицы А не
больше соответствующих элементов ее
l-го столбца и хотя бы
один элемент строго меньше. В этом случае
стратегия B_l
также называется доминируемой.

Чистые стратегии игроков А_i
и А_k первого
игрока называются дублирующими,
если a_ij
= a_kj
для всех

,
т.е. i-я и k-я строки платежной
матрицы совпадают.

Соответственно, чистые стратегии игроков
B_j
и B_l
второго игрока называются дублирующими,
если a_il
= a_ij
для всех

;
т.е. j-й и l-й
столбцы платежной матрицы совпадают.

Оказывается, что если вычеркнуть из
платежной матрицы игры все строки и
столбцы, соответствующие доминируемым
и дублирующим стратегиям игроков, то
по решению игры с уменьшенной матрицей
легко определить решение исходной игры.
Активные стратегии в сокращенной игре
будут входить в оптимальные смешанные
стратегии исходной игры с теми же
вероятностями, а исключенные стратегии
— с нулевыми вероятностями. Эта процедура
вычеркивания может применяться не
только к исходной матрице, но и к
получаемым сокращенным матрицам.

Пример 3.4. Рассмотрим игру 3х4
с платежной матрицей

Стратегия А₂ первого игрока
доминирует стратегию А₁,
поэтому первую строку можно вычеркнуть.
Сокращенная матрица имеет такой вид:

В этой игре стратегия В₃ второго
игрока доминирует стратегию В₁;
следовательно, первый столбец можно
вычеркнуть. Стратегии В₂ и В₄
являются дублирующими, так как
соответствующие столбцы содержат
одинаковые элементы. Значит любой из
них также можно вычеркнуть. Пусть это
будет четвертый столбец. Итак, после
отбрасывания доминируемых и дублирующих
стратегий получаем игру 2х2
с платежной матрицей

Ее решение:

Следовательно, решение исходной игры
таково:

В следующем примере использование
принципа доминирования также позволяет
существенно сократить размерность
платежной матрицы.

Пример 3.5. На аукционе продаются
контрольные пакеты акций двух предприятий.
За них борются два банка, один из которых
располагает капиталом $4 млн., а другой
— $3 млн. Можно предлагать лишь цену,
кратную $1 млн. Выигрывает банк, предложивший
большую сумму. Если оба банка предложили
одинаковую сумму, то никто не выигрывает.

Платежная матрица формируется таким
образом: если банк выиграл пакет акций,
то ему начисляется очко, а в матрицу
записывается разность между выигрышами
первого и второго банка. Нужно найти
решение этой игры.

Первый банк имеет пять чистых стратегий:
(4, 0), (3, 1), (2, 2), (1, 3), (0, 4), а второй — четыре
чистые стратегии: (3, 0), (2, 1), (1, 2), (0, 3).
Здесь первая цифра означает сумму,
предложенную банком за первое предприятие,
а вторая цифра — сумму, предложенную
за второе предприятие. Сформируем
платежную матрицу игры:

Стратегия А₂ доминирует
стратегию А₁, а стратегия А₄
доминирует стратегию А₅.
Следовательно, первую и пятую строку
можно вычеркнуть. Получаем новую матрицу:

В этой игре стратегия В₁ доминирует
стратегию В₂, а стратегия В₄
доминирует стратегию В₃.
Значит, второй и третий столбцы можно
вычеркнуть. Получаем следующую матрицу
игры:

Вторую строку в ней можно вычеркнуть.
Окончательно имеем такую платежную
матрицу:

Эта матрица не имеет седловой точки.
Поэтому для нахождения ее решения нужно
использовать смешанные стратегии. Ее
решение:

Значит, оптимальная стратегия первого
банка

= (0, 0.5,
0, 0.5, 0), оптимальная стратегия второго
банка

=
(0.5, 0, 0, 0.5), а цена игры

Таким образом, первый банк должен
применять свою вторую и четвертую чистую
стратегию с вероятностью, равной 0.5, а
второй банк — первую и четвертую чистую
стратегию с такой же вероятностью. В
этом случае выигрыш первого банка будет
равен 0.5.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Стратегия является доминирующей если всегда существует образ действий, который приводит к более высокой выплате, независимо от того, что делает противник. Выявление стратегического доминирования в игре важно для определения ее равновесия по Нэшу, результата, который ни один игрок не захочет менять.

Как найти доминирующую и доминируемую стратегию?

Используйте стратегическое превосходство, чтобы управлять своими действиями

1. Если стратегия A приводит к лучшим результатам, чем стратегии B и C, то стратегия A является доминирующей, и вы должны использовать ее.
2. Если стратегия A приводит к такому же результату, как и стратегия B, но обе приводят к лучшим результатам, чем стратегия C, то стратегия C доминирует, и вам следует избегать ее.

Как определить доминируемую стратегию в теории игр?

Согласно теории игр, доминирующей стратегией является оптимальный ход для отдельного человека независимо от действий других игроков. Равновесие Нэша описывает оптимальное состояние игры, когда оба игрока делают оптимальные ходы, но теперь учитывают ходы своего противника.

Что такое доминируемая стратегия в теории игр?

Доминирующая стратегия в теории игр относится к ситуации, когда один игрок имеет лучшую тактику, независимо от того, как его противник может играть. … Это означает, что независимо от стратегий, используемых противником, доминирующий игрок всегда будет диктовать исход.

Может ли строго доминируемая стратегия быть лучшим ответом?

Стратегия строгого доминирования никогда не будет лучшим ответом, независимо от мнения игрока о действиях других игроков.

Теория игр 101 (3): Повторное исключение строго доминируемых стратегий

Game Theory 101 (3): Iterated Elimination of Strictly Dominated Strategies

ЛЕКЦИЯ 2. Доминирующие и доминируемые стратегии
План лекции:
1. Решение игр
2. Равновесие в доминирующих стратегиях
3. Равновесие, получаемое исключением доминируемых стратегий
4. Связь между концепциями
Цели лекции:
Понять, что означает «решить игру»
Изучить концепцию решения игр, основанную на выявлении “равновесия в
строго (слабо) доминирующих стратегиях”
Изучить концепцию решения игр на основе выявления “равновесия, получаемого
исключением строго (слабо) доминируемых стратегий”
ВВЕДЕНИЕ
В предыдущей лекции и практических занятиях мы научились
формализовывать реальные жизненные ситуации в виде теоретико-игровых
моделей.
Мы обсудили, как одновременные стратегические взаимодействия могут быть
формализованы с помощью так называемых игр в нормальной форме, а
последовательные стратегические взаимодействия – в виде игр в развёрнутой
форме.
Теперь, мы обсудим, как эти игры можно решить, что означает решить игру и
какие концепции могут быть использованы для того, что бы решить игру.
1. Решение игр
Под решением игры мы будем понимать такой профиль стратегий, который
будет сыгран с наибольшей вероятностью.
Предполагая какое-то поведение игроков, мы поймём, какой профиль стратегий
они будут выбирать.
Давайте представим, что у нас есть два игрока, Таня и Вова, и они играют в
очень простую игру. У каждого из них есть две возможные стратегии: Тане
доступны стратегии a1 и a2, а Вове доступны стратегии b1 и b2.
Давайте подумаем, – они принимают решения одновременно, – какую
стратегию выберет Таня?
Она должна задуматься о том, а что может сыграть её партнёр. Если Вова будет
играть стратегию b1, то тогда Тане имеет смысл сыграть свой наилучший ответ
на стратегию b1, то есть такую из своих двух стратегий, которая приносит её
наибольший платёж. Таня сравнивает, какой платёж в ответ на стратегию b1
принесёт ей стратегия a1, какой платёж в ответ на стратегию b1 принесёт ей
стратегия a2, и сыграет ту из своих стратегий, которая приносит больший
платёж.
Этот ответ мы будем обозначать через best responce BR («наилучший ответ»),
BR от той стратегии, которую играет Вова. Здесь мы использовали
предположение о том, что Таня знает, какую стратегию Вова сыграет.
В жизни, однако, всё несколько сложнее. Таня может не знать, какую стратегию
будет играть Вова. Она не умеет читать его мысли, ну и, кроме того, вообще
говоря, редко встречаются ситуации, редко встречаются игры, в которых
заранее известно, что у Тани всегда наилучший ответ на одну и ту же
стратегию: может оказаться так, что на стратегию Вовы b1 оптимальным
ответом Тани будет стратегия a1, а в ответ на стратегию Вовы b2 оптимальным
ответом Тани будет стратегия a2.
Поэтому для того, чтобы понять, какую стратегию сыграет Таня, нам нужно
сделать какие-то дополнительные предположения о её поведении.
Мы будем говорить, что мы используем для решения ту или иную теоретикоигровую концепцию. В зависимости от того, какие предположения лежат в
рамках этой концепции, мы можем получать разные решения, то есть разные
стратегии, которые будет играть Таня.
В данной лекции мы рассмотрим с вами две теоретико-игровые концепции
решения игр:
— равновесие в доминирующих стратегиях,
— исключение доминируемых стратегий.
2. Равновесие в доминирующих стратегиях
2.1. Строго доминирующие стратегии
Для примера рассмотрим следующую игру.
Пусть у первого игрока есть две стратегии: 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 первого игрока —
строго доминирующая для него.
2.2. Слабо доминирующие стратегии
На определение строго доминирующей стратегии очень похоже определение
слабо доминирующей стратегии.
Давайте обсудим его.
Стратегия 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-му игроку больший платеж, чем любая другая его стратегия в ответ на любой
набор стратегий всех остальных игроков, то тогда заведомо верно и нестрогое
неравенство, что эта стратегия приносит ему не меньший платеж, чем любая
другая стратегия.
То есть любая строго доминирующая стратегия является в том числе и слабо
доминирующей.
2.3. Равновесие в строго (слабо) доминирующих стратегиях
Теперь мы готовы сформулировать определение первой концепции решения
игр, с которой мы познакомимся — равновесие в строго (слабо) доминирующих
стратегиях.
Говорят, что профиль (s1, …., sn) называется равновесием в строго
доминирующих стратегиях, если для каждого игрока i стратегия si является его
строго доминирующей стратегией.
Другими словами, профиль является равновесием в строго доминирующих
стратегиях, если он образован из строго доминирующих стратегий всех
игроков.
В нашем примере, который мы рассматривали с самого начала, профиль
стратегий (a1, b1) является равновесием в строго доминирующих стратегиях,
поскольку и стратегия a1 является строго доминирующей для первого игрока, и
стратегия b1 является строго доминирующей стратегией для второго игрока.
Однако в матрице с исправленными платежами профиль (a1, b1) не является
равновесием в строго доминирующих стратегиях, поскольку стратегия b1 уже
не является строго доминирующей стратегией второго игрока.
Аналогично можно сформулировать определение равновесия в слабо
доминирующих стратегиях.
Профиль (s1, sn) называется равновесием в слабо доминирующих стратегиях,
если каждая из стратегий si является слабо доминирующей стратегией i-го
игрока.
В нашем примере профиль (a1, b1) является равновесием в слабо
доминирующих стратегиях, и в примере с исправленными платежами профиль
(a1, b1) снова является равновесием в слабо доминирующих стратегиях,
поскольку эти профили образованы из слабо доминирующих стратегий первого
и второго игрока.
Почему вообще нам важно, что игроки играют строго доминирующие или
слабо доминирующие стратегии?
Дело в том, что если у игрока есть стратегия, которая приносит ему
максимальный из возможных платежей в ответ на любую из стратегий
соперников, то тогда есть все основания полагать, что именно ее игрок и будет
играть.
Это очень… очень мощное условие. Нет никакого резона для игрока играть
стратегию, отличную от доминирующей. Она не принесет ему большего
выигрыша, что бы ни сделали остальные игроки.
Поэтому, если вдруг у нас игра обладает тем свойством, что у каждого игрока
есть строго доминирующая стратегия, то есть все основания полагать, что
именно равновесие в строго доминирующих стратегиях и будет сыграно.
Можно сказать, что нам очень повезло, и мы нашли в этой игре очень простое
решение.
Тем не менее проблема заключается в том, что, как правило, наилучший ответ
каждого из игроков зависит от того, какую стратегию сыграл другой игрок, а
значит, у игроков может не быть строго доминирующих стратегий, и для таких
игр мы использовать эту концепцию не сможем.
2.4. Дилемма заключенного
Давайте рассмотрим несколько игр, которые помогут нам глубже понять, что
такое доминирующие стратегии и как с ними обращаться.
Пожалуй, самой известной игрой в теории игр является «Дилемма
заключенного».
Эта игра была описана в 1950 году американскими математиками Дрешером и
Фладом.
История такая: полиция поймала двух подозреваемых в совершении серьезного
преступления — ограбления банка.
Однако у полиции недостаточно улик для того, чтобы доказать ограбление.
Видно, что стекло разбито, однако где деньги, которые хранились в банке,
непонятно. Что делать? Полиция разводит заключенных по разным частям
следственного изолятора и предлагает каждому из них пойти на сделку со
следствием, а именно: выдать улики на своего напарника в обмен на
сокращение собственного срока пребывания в тюрьме.
При этом, естественно, полиция запрещает обмен информацией между
заключенными. И мы увидим, что с помощью этого ей удается добиться.
Значит, у каждого из двух игроков, а именно заключенные в нашей игре
являются игроками, есть на допросе две стратегии: это либо промолчать, либо
пойти на сделку со следствием и сдать своего напарника, выдать на него улики,
тем самым надеясь уменьшить свой собственный срок.
Как устроены платежи игроков в этой игре?
Если оба игрока будут молчать, и не будут выдавать улики друг на друга, то
тогда полиция отправит каждого из них в тюрьму всего лишь на 1 год: за
мелкое хулиганство, за разбитое окно в банке.
Если один из заключенных выдаст второго, а второй промолчит, то тогда вся
тяжесть совершения данного преступления ляжет на того игрока, на того
подозреваемого, который промолчал. На него улики выданы, соответственно,
он сядет в тюрьму за ограбление банка на 10 лет, а вот второй заключенный, на
которого и так не выданы улики, еще и получит возможность уменьшить свой
срок. Его бы посадили за мелкое хулиганство на 1 год, но поскольку он пошел
на сделку со следствием, то будем считать, что полиция его прощает и
отпускает домой. В этом случае его платеж будет равен нулю.
И, наконец, если оба заключенных пойдут на сделку со следствием, то тогда
улики у полиции будут на каждого из них, каждый из них будет обвинен в
ограблении банка. И это светило бы им наказанием в размере 10 лет
заключения в тюрьме.
Однако вспоминаем, что каждый из них пошел на сделку со следствием.
Значит, полиция тоже выполняет условия этого контракта, уменьшает каждому
из них срок, и каждый отправляется в тюрьму на 5 лет.
Матрица этой игры представлена ниже.
Игра два на два. Давайте попытаемся эту игру проанализировать.
Мы научились решать игры с помощью равновесия в строго доминирующих
стратегиях.
Есть ли в этой игре доминирующие стратегии у кого-либо из игроков?
Давайте представим, как рассуждает первый заключенный.
Он думает: «Так, какую стратегию мне выбрать?
Если мой напарник будет молчать, а я тоже буду молчать, то я получу платеж
равный минус 1, отправлюсь в тюрьму на 1 год.
А если предам его, то получу платеж равный нулю, выйду на свободу. Мне
лучше его предавать».
Если я подозреваю, если первый заключенный подозревает, что напарник его
предаст, то тогда в случае, если первый заключенный будет молчать, то он
отправится в тюрьму на 10 лет. А если предаст, то тогда на 5 лет.
Значит, наилучший ответ в ответ на стратегию «Предать» — снова стратегия
«Предать».
Таким образом, у первого заключенного есть строго доминирующая стратегия
— «Предать».
То же самое, естественно, можно сказать и про второго заключенного. Они у
нас симметричные.
Значит, у второго заключенного тоже есть доминирующая стратегия. И она —
предавать первого.
Таким образом, по определению профиль (Предать, Предать) является
равновесием в строго доминирующих стратегиях.
В силу замечания, которое мы с вами высказали раньше, этот же профиль будет
и равновесием в слабо доминирующих стратегиях.
Сейчас сделаем небольшое отвлечение от равновесия в строго доминирующих
стратегиях.
Дадим еще одно определение, чтобы получше понять свойства профилей
стратегий в «Дилемме заключенного».
Мы будем говорить, что профиль стратегий s Парето-доминирует профиль
стратегий sʼ, если платежи, которые получают игроки в профиле s не меньше
платежей, которые получают игроки в профиле sʼ. И, по крайней мере, для
одного игрока платеж, который он получает в профиле s, больше платежа,
который он получает в профиле sʼ.
Мы будем говорить, что профиль стратегий s* называется Паретооптимальным, если не существует никакого другого профиля стратегий sʼ,
который бы доминировал, Парето-доминировал, профиль стратегий s*.
Давайте снова посмотрим на «Дилемму заключенного».
Какие из профилей являются Парето-оптимальными? Профиль (Предать,
Предать), который, как мы знаем, является равновесием в строго
доминирующих стратегиях. Является ли он Парето-оптимальным?
Ответ — нет, потому что существует профиль (Молчать, Молчать), в котором
оба игрока получают платеж, больший, чем в профиле (Предать, Предать).
Значит, профиль (Молчать, Молчать) Парето-доминирует профиль (Предать,
Предать) и, соответственно, равновесие в строго доминирующих стратегиях не
является Парето-оптимальным.
Это немножечко странно, казалось бы, потому что мы считали, что каждый
игрок использует свою оптимальную стратегию, которая является наилучшим
ответом игрока в ответ на любую из стратегий других игроков. В данном случае
на любую из стратегий второго игрока.
Второй игрок действует точно так же. Играет стратегию, которая является
наилучшим ответом на любую из стратегий первого игрока. Однако, тем не
менее, платежи, которые они получают в результате этого, оказываются
меньше платежей, которые бы они получали, если бы договорились и молчали,
в то время как полиция предложила бы им пойти на сделку со следствием.
То есть профиль (Молчать, Молчать) является Парето-оптимальным.
Почему?
Потому что ни один из трех других профилей не Парето-доминирует профиль
(Молчать, Молчать).
Профиль (Молчать, Предать) является Парето-оптимальным, потому что
второй игрок никогда не может получить платеж, больший нуля. И это
означает, что невозможно увеличить платеж первого игрока, не уменьшив
платеж, который получает второй игрок.
Профиль (Предать, Молчать) тоже является Парето-оптимальным.
Получается совершенно фантастическая история. В игре есть равновесие
(Предать, Предать), однако Парето-оптимальными являются все профили,
кроме равновесия.
В этом и есть некоторое нехорошее свойство равновесия. На самом деле, с
точки зрения общественного благосостояния, равновесие ничего не означает.
Те платежи, которые могут получать игроки в этом равновесии, могут быть
меньше, чем платежи, которые бы они могли получить в каких-то других
профилях.
2.5. Игры, похожие на дилемму заключенного
Давайте рассмотрим еще один пример.
Поговорим про олигополистическую конкуренцию.
Давайте рассмотрим рынок некоторого товара, на котором присутствуют две
фирмы.
Фирмы продают товар по одинаковой цене.
И вдруг, в какой-то момент, они одновременно задумываются над тем, чтобы
повысить цену на этот товар. Они принимают это решение одновременно и
независимо друг от друга.
Будем считать, что это товар первой необходимости, поэтому покупатели будут
готовы покупать его по любой цене.
И про каждую из фирм, как всегда в теории игр, предположим, что она
стремится получить максимально возможную прибыль.
Значит, как устроены платежи фирм в этой игре?
Давайте считать, что если обе фирмы оставят цену на начальном уровне, то
тогда они останутся «при своих», и их платеж будет равен нулю.
Если обе фирмы повысят цену на свой товар, то тогда каждая их них сможет
получить дополнительную прибыль за счет более высокой цены. Количество
покупателей не изменилось.
Мы считаем, что при одинаковых ценах покупатели делятся пополам между
этими фирмами — каждая из них обслуживает половину рынка. А цена на
товар выросла, и, соответственно, прибыль, которую получает фирма, выросла.
Если же одна фирма повышает цену на товар, а другая оставляет ее на
предыдущем уровне, то тогда потребители видят это и полностью переходят к
той фирме, которая продает товар по наименьшей цене.
Поэтому фирма, повысившая цену, понесет некоторые убытки: она сможет
ничего продать, ну и плюс, она несет какие-то издержки от производства того
товара, который она не может продать. А другая фирма получает
дополнительную прибыль.
Причем будем считать, что эта дополнительная прибыль существенна — она
больше той прибыли, которую получают обе фирмы в случае повышения цен.
Это игра.
И эта игра может быть записана в виде матрицы 2х2.
У каждого из игроков есть две стратегии. Первая фирма может либо повысить
цену на товар, либо не повышать ее, вторая фирма может либо повысить цену
на товар, либо не повышать ее, и в матрице представлены соответствующие
платежи.
Давайте попробуем эту игру решить.
Есть ли у игроков строго доминирующие стратегии?
Ищем оптимальные ответы.
Давайте представим себя на месте топ-менеджмента первой фирмы.
Мы находимся на стадии принятия решения, мы думаем: «Что может сделать
вторая фирма?»
Если вторая фирма повысит цену, то для нас оптимальным ответом будет не
повышать ее, потому что тогда мы сможем получить весь рынок, и наш общий
платеж существенно увеличится.
Если мы думаем, что другая фирма не будет повышать цену, то тогда для нас
оптимальным является тоже оставить цену на текущем уровне, потому что в
случае повышения цены мы начнем получать отрицательный платеж, а в случае
неповышения — останемся «при своих».
Таким образом, стратегия «Не повышать» является строго доминирующей для
каждой из двух фирм.
А профиль стратегий, образованный этими стратегиями, – это равновесие в
строго доминирующих стратегиях.
Именно из-за этой причины, которую мы только что обсудили, и существуют
антимонопольные органы.
На самом деле, эта игра — это не что иное, как «Дилемма заключенного».
В равновесии обе фирмы получают меньше, чем если бы они договорились, и
вместо неповышения цен одновременно и синхронно повысили цену на
некоторую величину. Тогда бы они получили бы дополнительную прибыль за
счет потребителей.
Однако государство, которое, как правило, стремится заботиться об
общественном благосостоянии, а не только о прибыли фирм, будет
использовать инструменты в виде антимонопольных органов, для того чтобы
предотвращать такие сговоры. Такие сговоры, на самом деле, возможны только
на рынках, на которых присутствует небольшое число фирм. Такие рынки
называют олигополистическими. Именно в условиях таких рынков возможно
стратегическое взаимодействие между этими фирмами.
На рынках совершенной конкуренции, где есть очень много фирм,
производящих один и тот же товар, такое стратегическое взаимодействие
невозможно, и цена формируется естественными рыночными механизмами.
Именно этим и отличается олигополистический рынок. Именно поэтому мы
именно его рассматриваем в нашем курсе.
3. Равновесие, получаемое исключением доминируемых стратегий
3.1. Строгое и слабое доминирование
Теперь перейдём к ещё одной концепции решения игр – исключению
доминируемых стратегий.
Давайте рассмотрим другой пример.
Матрица игры представлена в следующем виде.
Разумно ли в этой игре второму игроку играть стратегию b1?
Если он подозревает, что первый игрок сыграет стратегию a1, то тогда выбор
стратегии b1 для второго игрока не является правильным, тогда лучше было бы
сыграть стратегию b3.
Если второй игрок подозревает, что первый может сыграть стратегию a2, то
тогда для второго игрока стратегия b1 является наилучшим ответом на
стратегию a2, и именно она была бы оптимальной.
Поэтому про стратегию b1 нельзя сказать, что она является наилучшим ответом
на любую из стратегий первого игрока.
Второму приходится анализировать, что может сыграть первый, для того чтобы
принять верное решение о своей стратегии.
Разумно ли второму игроку играть стратегию b3 в этой игре?
Опять: ответ «да», если первый игрок будет играть стратегию a1, и ответ «нет»,
если первый игрок сыграет стратегию a2.
Не будучи полностью уверенным в том, какую стратегию сыграет первый
игрок, второй не может однозначно утверждать, что стратегия b3 является для
него оптимальной.
Теперь посмотрим на стратегию b2.
Предположим, что второй игрок подозревает, что первый будет играть
стратегию a1. Тогда для второго игрока стратегия b2 не является оптимальной,
потому что вместо стратегии b2 уж лучше бы он сыграл стратегию b3, тогда бы
он получил платёж, равный девяти, вместо платежа, равного шести.
Если второй игрок подозревает, что первый будет играть стратегию a2, то тогда
стратегия b2 снова не является оптимальной, потому что уж лучше бы вместо
стратегии b2 он сыграл ту же самую стратегию b3, и тогда бы он получил
платёж, равный единице, вместо нуля.
Получается, что что бы ни сделал первый игрок, для второго игрока стратегия
b2 приносит строго меньший платёж, чем стратегия b3.
Про такую ситуацию говорят, что стратегия b3 строго доминирует стратегию
b2.
Формальное определение: говорят, что стратегия si i-го игрока строго
доминирует стратегию si’, если для любого набора стратегий всех остальных
игроков s минус i платёж, который получает i-й игрок, если он играет
стратегию si, больше платежа, который получает i-й игрок, если он играет
стратегию si’.
Верно и такое определение: стратегия si i-го игрока строго доминируется
стратегией si’, если для любого набора стратегий всех остальных игроков
платёж, который получает i-й игрок, если он играет стратегию si, меньше
платежа, который получает i-й игрок, если он играет стратегию si’.
Обозначение для такой ситуации: si меньше, или хуже, стратегии si’.
Аналогичное определение можно сформулировать и для слабого
доминирования: стратегия si i-го игрока слабо доминирует стратегию si’, если
платёж, который получает i-й игрок, играя стратегию si, при любых стратегиях
остальных игроков s минус i, не меньше платежа, который получит i-й игрок,
если он играет стратегию si’.
И, наконец, стратегия si i-го игрока слабо доминируется стратегией si’, если для
любого набора стратегий всех остальных игроков платёж, который получает i-й
игрок, играя стратегию si, не больше платежа, который получает i-й игрок, если
он играет стратегию si’.
Давайте вернёмся к той игре, которую мы уже начали рассматривать.
В этой игре для первого игрока стратегия a2 слабо доминирует стратегию a1.
Сравниваем платежи: если вдруг второй игрок играет стратегию b1, то, играя
a2, второй получает не меньше, чем играя a1.
Если второй игрок будет играть b2, то первый игрок, играя a2, получает не
меньше, чем играя a1.
И, наконец, если второй игрок будет играть b3, первый, играя a2, получит не
меньше, чем играя a1.
Тем самым стратегия a2 слабо доминирует стратегию a1.
В обратную сторону: говорят, что стратегия a1 слабо доминируется стратегией
a2.
Теперь для второго игрока. Мы поняли, что стратегия b3 строго доминирует
стратегию b2. Ну и в обратную строну это можно сказать так: стратегия b2
строго доминируется стратегией b3.
Говорят, что стратегия si i-го игрока называется строго доминируемой, если
существует какая-то стратегия si’ i-го игрока, которая строго доминирует
стратегию si.
Стратегия si i-го игрока называется слабо доминируемой, если существует
другая стратегия si’ i-го игрока, которая слабо доминирует стратегию si.
И снова вернёмся к той игре, которую мы рассматриваем.
В этой игре стратегия a1 – это слабо доминируемая стратегия первого игрока, а
стратегия b2 – строго доминируемая стратегия второго игрока.
3.2. Исключение строго (слабо) доминируемых стратегий
Исключение строго доминируемых стратегий — это еще один инструмент
решения игр, который позволяет проанализировать поведение игроков.
Давайте задумаемся, имеет ли смысл второму игроку в уже рассмотренной
нами игре играть стратегию b2?
Нет, потому что он, играя стратегию b2, будет получать меньший платеж, чем
он бы получил, если бы сыграл стратегию b3 при любых возможных стратегиях
первого игрока.
То есть из каких бы вдруг соображений в голову второму игроку не взбрело бы
сыграть стратегию b2, уж лучше бы он вместо этого сыграл стратегию b3.
Тогда бы он получил больший платеж. Значит, второй игрок не будет играть
стратегию b2. И это понимает как второй игрок, так и первый.
Значит, на самом деле, оба игрока понимают: стратегия b2 играться не будет —
эту стратегию можно исключить.
Давайте редуцируем эту матрицу, то есть вычеркнем стратегию b2 и сведем эту
матрицу к матрице 2 х 2, которая состоит уже из стратегий а1 и а2 первого
игрока и стратегий b1 и b3 второго игрока.
Теперь в этой игре, которая получилась после вычеркивания стратегии b2, у
первого игрока появилась строго доминируемая стратегия.
Это стратегия а1. Ее мы исключим на втором шаге.
Оба игрока сейчас понимают, что первый игрок в такой игре не будет играть
стратегию а1 — исключим ее и сведем эту матрицу к матрице размера 1 х 2,
состоящую из стратегии а2 первого игрока и стратегий b1 и b3 второго игрока.
Но и в этой матрице у второго игрока есть строго доминируемая стратегия.
Стратегия b3 строго доминируется стратегией b1.
Исключаем строго доминируемую стратегию и получаем матрицу размера 1 х
1.
Она состоит из профиля (а2, b1), и этот профиль называется равновесием,
полученным исключением строго доминируемых стратегий.
Делая последовательные умозаключения о том, что тот или иной игрок не будет
играть ту или иную стратегию, мы поняли, что в этой игре будет сыгран именно
профиль (а2, b1).
И такой подход, такой анализ, позволяет решать некоторый новый класс игр.
Формальное определение: если в некоторой конечной игре, то есть в игре, в
которой у каждого из игроков есть конечное множество стратегий, так вот, если
в конечной игре в нормальной форме в результате последовательного
исключения строго доминируемых стратегий останется матрица размера 1 х 1,
то этот оставшийся профиль называется равновесием, получаемым
исключением строго доминируемых стратегий.
Если в результате исключения строго доминируемых стратегий мы свели
матрицу к матрице большего размера, то эта матрица возможно обладает
какими-то хорошими свойствами, но если она не редуцируется к матрице
размера 1 х 1, мы не считаем, что мы нашли это равновесие.
В любой ли вообще игре в нормальной форме можно прийти к матрице 1 х 1,
последовательно исключая строго доминируемые стратегии?
Нет, если мы вспомним, например, «Битву полов», которую мы рассматривали
на предыдущей лекции, то в этой игре ни у мужа, ни у жены нет строго
доминируемой стратегии.
Таким образом, эту игру нельзя решить ни с помощью равновесия в
доминирующих стратегиях, ни с помощью равновесия, получаемого
исключением доминируемых стратегий, то есть вот этот вот инструмент
исключения доминируемых стратегий пока еще не позволит решать нам все
возможные игры, но тем не менее, он позволит решать некоторый
дополнительный класс игр по сравнению с той концепцией, которую мы
изучили раньше.
Еще один важный вопрос, который нужно обсудить в связи с исключением
доминируемых стратегий, состоит в том, а важно ли, в каком порядке
исключать доминируемые стратегии.
Оказывается, что если мы исключаем строго доминируемые стратегии, то
порядок их исключения не важен. Действительно, после уменьшения матрицы,
мы, исключая доминируемую стратегию, не изменяем свойство другой
стратегии быть доминируемой.
То есть если у нас в какой-то момент времени было две доминируемые
стратегии, то после исключения одной из них другая продолжит быть
доминируемой.
А это означает, что в каком бы порядке мы эти стратегии ни исключали, то в
итоге мы всегда прийдем к одному и тому же профилю, ну или к одной и той
же матрице.
Однако, если исключать слабо доминируемые стратегии, то результат, который
мы можем получить в результате такого исключения, может различаться.
В качестве простого примера, давайте рассмотрим игру 2 х 2, в которой
платежи, которые получают все игроки, одинаковы в любом профиле.
Ну, например, давайте считать, что платеж первого и платеж второго игрока
равен пяти независимо от того, какую стратегию играет первый игрок, какую
стратегию играет второй игрок.
Любая из стратегий в этой игре является слабо доминируемой.
Исключая слабо доминируемые стратегии в различных порядках, мы можем
свести эту матрицу к матрице размера 1 х 1.
И вот этим вот оставшимся профилем может быть любой из четырех профилей
в зависимости от порядка их исключения.
Это не очень хорошо, исключение слабо доминируемых стратегий с этой точки
зрения хуже, чем исключение строго доминируемых стратегий, потому что,
исключая строго доминируемые стратегии, мы всегда будем получать один и
тот же результат, а исключая слабо доминируемые стратегии, решение зависит
от порядка исключения.
Именно поэтому, если есть возможность решать игру, используя исключение
строго доминируемых стратегий, то тогда нужно использовать именно эту
концепцию.
4. Связь между концепциями
Теперь давайте обсудим, как связано равновесие в строго доминирующих
стратегиях и равновесие, получаемое исключением строго доминируемых
стратегий.
Если в игре есть равновесие в строго доминирующих стратегиях, то по
определению это означает, что у каждого из игроков есть строго
доминирующая стратегия.
Это означает, что она доминирует любую из стратегий этого игрока, но тогда,
последовательно вычеркивая доминируемые стратегии игроков, мы сначала
сведем матрицу к размеру вида 1 х n, вычеркнув по очереди все стратегии
первого игрока, а потом, воспользовавшись тем, что у второго игрока тоже есть
строго доминирующая стратегия, а следовательно все остальные стратегии
являются строго доминируемыми, так вот, исключив их, мы сведем матрицу к
матрице размера вида 1 х 1.
И по определению этот профиль будет являться равновесием, получаемым
исключением строго доминируемых стратегий.
Таким образом, если в игре есть равновесие в строго доминирующих
стратегиях, то в этой игре обязательно есть и равновесие, получаемое
исключением строго доминируемых стратегий.
Однако обратное утверждение неверно.
Если в игре есть равновесие, получаемое исключением строго доминируемых
стратегий, то оно не обязательно является равновесием в строго
доминирующих стратегиях.
Давайте рассмотрим снова игру, которую мы уже с вами изучили.
В этой матрице есть равновесие, получаемое исключением строго
доминируемых стратегий, но в этой матрице нету равновесия в строго
доминирующих стратегиях, потому что ни у одного из игроков нету строго
доминирующих стратегий.
Это означает, что обратное утверждение неверно, и связь между этими двумя
концепциями устроена примерно так: с помощью равновесия в строго
доминирующих стратегиях можно решить более узкий класс игр, чем с
помощью равновесия, получаемого исключением строго доминируемых
стратегий, но зато свойства решения, которое получается в результате
использования концепции равновесия в строго доминирующих стратегиях,
сильнее свойств, которые получаются в результате решения с помощью
исключения доминируемых стратегий.