<< Предыдущая

стр. 158
(из 165 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

0 0
[1??]
[?] Пилот

Нью-Йорк Куба Нью-Йорк
Куба
[µ3 ] [µ3 ]
?1 ?1
?100 1
1 1
0 ?1

Рис. 16.28.


хочет ли он проводить операцию. Если он не станет осуществлять задуманную акцию, то вне зависи-
мости от типа выигрыш террориста составит 0 , и выигрыш пилота составит 0 . Дерево игры показано
на Рис. 16.28. Как и прежде, первый элемент вектора — выигрыш пилота. Поскольку выбор террори-
ста в Нью-Йорке можно предсказать однозначно, то будем рассматривать «частично свернутую» игру.
Совершенное байесовское равновесие должно состоять из следующих величин:
1) вероятность, с которой сумасшедший террорист проводит операцию, µ1 ? [0, 1];
2) вероятность, с которой нормальный террорист проводит операцию, µ2 ? [0, 1];
3) вероятность, с которой пилот ожидает встретить сумасшедшего террориста, ? ? [0, 1];
4) вероятность, с которой пилот летит в Нью-Йорк, µ3 ? [0, 1].
Этого достаточно для описания равновесия. Все остальные вероятности очевидным образом рас-
считываются как функции указанных.
Рассмотрим сначала поведение пилота при ожиданиях, заданных параметром ? . Ожидаемые вы-
игрыши пилота от двух возможных действий равны:

?1
Куба:
? · (?100) + (1 ? ?) · 1
Нью-Йорк:

Таким образом, если ?1 < ? · (?100) + (1 ? ?) · 1, т. е. ? < 2/101, то пилот предпочтет полететь в
Нью-Йорк ( µ3 = 1), если ? > 2/101 , то на Кубу (µ3 = 0), а в случае, когда ? = 2/101, ему все равно,
куда лететь (µ3 любое). Т. е. зависимость стратегии от ожидания имеет вид:
?
?1, если ? < 2/101,
?
?
µ3 (?) = [0, 1], если ? = 2/101,
?
?0, если ? > 2/101.
?


Далее рассмотрим, какими должны быть ожидания пилота, ? , в зависимости от вероятностей µ1 и
µ2 . Если µ1 = 0 или µ2 = 0, то можно использовать формулу Байеса. В рассматриваемой игре можно
считать, что события следующие: B1 — террорист сумасшедший, B2 — террорист нормальный, A —
в процессе игры пилот получил ход и должен выбирать, куда ему лететь. (Проверьте, что эти события
удовлетворяют требованиям, необходимым для использования правила Байеса.) При этом, используя
введенные обозначения,

Pr{B1 } = ?, Pr{B2 } = 1 ? ?, Pr{B1 | A} = ?,
Pr{A | B1 } = µ1 , Pr{A | B2 } = µ2 .
16.6. Динамические байесовские игры 675

Получаем по формуле Байеса, что
?µ1
?(µ1 , µ2 ) = .
?µ1 + (1 ? ?)µ2
при µ1 = 0 или µ2 = 0. Если µ1 = 0 и µ2 = 0, то, согласно принятому нами определению байесовского
равновесия, ожидания пилота ? могут быть любыми: ?(µ1 , µ2 ) = [0, 1].
Рассмотрим теперь выбор каждого из типов террориста. Если террорист сумасшедший, то его
ожидаемый выигрыш от задуманной акции при стратегии пилота, заданной вероятностью µ3 , равен

(1 ? µ3 ) · 1 + µ3 · 0 = 1 ? µ3 .

Он сравнивает этот выигрыш с 0. Таким образом,

1, если µ3 < 1,
µ1 (µ3 ) =
[0, 1], если µ3 = 1.

выигрыш от задуманной акции равен 1 ? 2µ3 . Он
Если террорист нормальный, то его ожидаемый
тоже сравнивает этот выигрыш с 0 , т. е.
?
?1, если µ3 < 1/2,
?
?
µ2 (µ3 ) = [0, 1], если µ3 = 1/2,
?
?0, если µ3 > 1/2.
?

Набор вероятностей (µ? , µ? , µ? , ?? ), задает совершенное байесовское равновесие, если выполнены
1 2 3
четыре условия:

µ? ? µ3 (?? ), ?? ? ?(µ? , µ? ),
3 1 2
µ? ? µ1 (µ? ), ? ?
µ2 ? µ2 (µ3 ).
1 3

Для того, чтобы найти решения этой системы, следует разобрать несколько случаев. По-видимому,
проще всего проанализировать по отдельности следующие три возможности:
(i) нормальный террорист не проводит операцию (µ2 = 0 );
(ii) нормальный террорист проводит операцию (µ2 = 1);
(iii) у нормального террориста невырожденная смешанная стратегия (µ2 ? (0, 1)).
(i) Рассмотрим случай, когда µ2 = 0. Предположим, что при этом µ1 = 0. Тогда пилот наверняка
будет знать, что он может иметь дело только с сумасшедшим террористом ( ? = 1 ). Зная это, пилот
выберет Кубу (µ3 = 0). Но в таком случае нормальному террористу тоже выгодно проводить операцию.
Мы пришли к противоречию. Значит, единственная возможность состоит в том, что сумасшедший
террорист не проводит операцию ( µ1 = 0 ). Но такое может быть только если он знает, что пилот
полетит в Нью-Йорк (µ3 = 1 ). Однако, такое поведение пилота возможно только в том случае, если
вероятность того, что он имеет дело с сумасшедшим террористом мала (? 2/101 ).
Мы нашли в рассматриваемой игре одно из равновесий (точнее, семейство равновесий одного типа):

µ? = 1, ?? ? [0, 2/101], µ? = 0, µ? = 0.
3 1 2

Это равновесие поддерживается уверенностью пилота, что вероятность встречи с сумасшедшим терро-
ристом мала. Заметим, что эти ожидания ни на чем не основаны, ведь в рассматриваемом равновесии
пилот не может сформировать свои ожидания на основе правила Байеса.
(ii) Рассмотрим теперь случай, когда µ2 = 1 . Такое поведение нормального террориста возможно
только, если пилот с достаточно большой вероятностью полетит на Кубу, а именно, если µ3 1/2. При
такой стратегии пилота сумасшедшему террористу выгодно проводить операцию (µ1 = 1). Но если оба
террориста проводят операцию, то для пилота вероятность встретить сумасшедшего террориста сов-
падает с вероятностью, с которой такие террористы встречаются вообще, т. е. ? = ? . Пилот может
выбрать µ3 1/2 только если ? 2/101. Таким образом, равновесие может достигаться только при
? 2/101. При ? > 2/101, имеем µ3 = 0. Таким образом, если сумасшедшие террористы встреча-
ются на свете достаточно часто, т. е. если ? > 2/101, то в рассматриваемой игре может иметь место
следующее равновесие:
µ? = 0, ?? = ?, µ? = 1, µ? = 1.
3 1 2
16.7. Игры и Парето-оптимальность 676

В вырожденном случае, когда ? = 2/101, получаем следующее множество равновесий:

µ? = 1, µ? = 1,
1 2
? ?
µ3 ? [0, 1/2], ? = ? = 2/101.

(iii) И, наконец, рассмотрим случай, когда нормальный террорист использует невырожденную сме-
шанную стратегию (µ2 ? (0, 1)). Условием использования такой стратегии является то, что обе альтер-
нативы дают ему одинаковую полезность, то есть то, что пилот летит в Нью-Йорк с вероятностью 1/2
(µ3 = 1/2). Такая стратегия пилота может поддерживаться только ожиданиями ? = 2/101. Учитывая,
что сумасшедшему террористу выгодно участвовать в акции (µ1 = 1), из формулы Байеса получим
следующее уравнение:
2 ?
?= = .
? + (1 ? ?)µ2
101
Значит, пилот может сформировать такие ожидания только если
99?
µ2 = .
2(1 ? ?)
Поскольку вероятность µ2 должна быть меньше единицы, то вероятность, с которой природа порож-
дает сумасшедших террористов должна быть достаточно мала: ? < 2/101.
Таким образом, при ? < 2/101 следующие вероятности определяют равновесие:
1 2 99?
µ? = ?? = µ? = 1, µ? =
, , .
3 1 2
2(1 ? ?)
2 101
Поскольку проанализированы все три возможных случая, то мы нашли все возможные равновесия
игры.

Задачи
 708. Найдите совершенные байесовские равновесия в игре, изображенной на Рис. 16.18.
 709. «Карточный блеф»
В начале игры игроки ( A и B ) вносят по 1 д. е. После этого с равной вероятностью игрок A
получает одну из двух возможных карт, «старшую» или «младшую». Далее игрок может A повысить
ставку, добавив 2 д. е. Если он этого не сделает, то игра заканчивается и деньги забирает игрок B .
Если A повышает, то делает ход игрок B . Он либо уравнивает, добавляя 2 д. е., либо пасует. В
первом случае карта открывается и деньги забирает игрок A, если карта старшая, и игрок B , если
карта младшая. Во втором случае деньги забирает игрок A.
Покажите, что в этой игре нет совершенного байесовского равновесия в чистых стратегиях. Най-
дите равновесие в смешанных стратегиях. Как часто игрок A будет блефовать, т. е. повышать, имея
младшую карту? Как часто игрок B будет уравнивать?



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

G = I, {Xi }I , {ui }I .

Напомним определение Парето-оптимальности.
Определение 96:
Исход y ? X доминирует по Парето исход x ? X (является Парето-улучшением по сравнению с x),
если в нем каждый игрок получает выигрыш не меньше, чем в исходе x, а хотя бы один из игроков
получает выигрыш строго больше, чем в x, т. е.

ui (xi ) ?i ? I,
ui (yi )
16.7. Игры и Парето-оптимальность 677

и
?j ? I : uj (yi ) > uj (xi ).
Исход x ? X называется Парето-оптимальным, если не существует другого исхода x ? X , такого
? ?
?
что он доминирует x по Парето.
Множество всех Парето-оптимальных точек называют границей Парето.

Рассмотренные выше решения (равновесия) не являются в общем случае Парето-оптимальными,
что, в частности, показывает следующая игра.
Игра 14. «Игра Ауманна»36
Перед двумя участниками игры стоит следующий выбор. Каждый может потребовать, чтобы органи-
затор игры дал сто долларов другому игроку, либо потребовать, чтобы он дал один доллар ему самому.
Участники одновременно и независимо делают выбор, после чего организатор игры исполняет их тре-
бования.

Игру можно представить с помощью следующей матрицы (см. Таблицу 16.20).

Таблица 16.20. Игра Ауманна

Игрок 2
$100 другому $1 ему
100 101
$100 другому 100 0
0 0
Игрок 1
$1 ему 101 0

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

16.7.1 Сотрудничество в повторяющихся играх
Ситуации, аналогичные той, которая описана в игре Ауманна, являются примерами фиаско коор-
динации. Одно из объяснений этого фиаско состоит в том, что в игре Ауманна игроки только один
раз должны сделать выбор. В ситуациях, когда игра повторяется и игроки, играя в игру, «помнят»
всю все принятые ими ранее решения (предысторию игры), между ними вполне может возникнуть
сотрудничество.
Чтобы проанализировать эту догадку формально, введем понятие повторяющейся игры. Под по-
вторяющейся игрой понимают такую динамическую игру, которая является последовательным повто-
рением некоторой исходной игры (неважно, статической или динамической). Чтобы получить дерево
дважды повторяющейся игры, следует к каждой конечной вершине исходной игры «прикрепить» де-
рево исходной игры. Рис. 16.29 показывает как это сделать на примере игры Ауманна.
Аналогично, чтобы получить дерево n раз повторяющейся игры, следует к каждой конечной вер-
шине n ? 1 раз повторяющейся игры «прикрепить» дерево исходной игры. Конечно, для описания
повторяющейся игры не обязательно задавать все дерево игры, достаточно указать исходную игру и
сколько раз она повторяется. В отличие от обычных игр, в повторяющихся играх принято сопостав-
лять выигрыши не только конечным вершинам, но и тем промежуточным, которые соответствуют
конечным вершинам исходной игры. Общий выигрыш рассчитывается суммированием выигрышей в
36
Эта игра представляет собой вариант известнейшей игры «Дилемма заключенных». Сюжет «Дилеммы
заключенных» следующий. Двух человек арестовали по подозрению в совершении некоторого преступления.
Судья предложил каждому следующую сделку. Если он сознается в преступлении, а другой нет, то сознавшийся
получает 1 год наказания, а не сознавшийся — 10 лет. Если сознаются оба, то каждый получит по 7 лет.
Заключенным также известно, что если никто из них не сознается, то оба получат по 3 года. (Цифры у разных
авторов разные.)
16.7. Игры и Парето-оптимальность 678

1-й


2-й
100 1
100 1
1-й 1-й


2-й 2-й


0 101
100 0 101 1 100 0 101 1
101 0

<< Предыдущая

стр. 158
(из 165 стр.)

ОГЛАВЛЕНИЕ

Следующая >>