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

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

ОГЛАВЛЕНИЕ

Следующая >>

1 + ?2 0
нарушать ?1 1 + ?2
?1 0
Проверяемый
не нарушать 0 0



ских игр с полной информацией, т. е. динамические байесовские игры (динамические игры с неполной
информацией).
В качестве примера динамической байесовской игры рассмотрим модификацию Игры 16.3 «Терро-
рист» (с. 647).
Игра 13. «Террорист»
Ситуация в данной игре такая же, как в Игре 16.3, однако террорист может быть двух типов: «нор-
мальный» и «сумасшедший». Нормальный террорист так же, как и в Игре 16.3, получает выигрыш
?100 в случае, если взорвет бомбу в Нью-Йорке. Сумасшедший же террорист получает в этом случае
выигрыш 0 . Вероятность того, что террорист окажется сумасшедшим, равна ? . Пилот не знает, с тер-
рористом какого типа он имеет дело, но сам террорист знает свой тип.

Игра схематически показана на Рис. 16.23. В игру был добавлен дополнительный фиктивный иг-
рок, природа34 . Это сделано для того, чтобы показать на схеме случайный выбор типа террориста.
Природа не имеет никакой целевой функции, поэтому на схеме показаны только выигрыши двух ис-
ходных игроков.

Природа
нормальный
сумасшедший

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

Нью-Йорк Куба Нью-Йорк
Куба
?1
Террорист
Террорист 1
?1
взорвать
1 не взрывать
не взрывать
взорвать ?100 1
1
?100 ?100 ?1
?1
0

Рис. 16.23. Игра «Террорист»

Первый ход делает природа. С вероятностью ? природа создает сумасшедшего террориста и с
вероятностью 1?? — нормального. Пунктирной рамкой показано информационное множество пилота,
соответствующее условию, что он не знает типа террориста.
Решение этой игры можно найти, применяя обратную индукцию. Сначала нужно рассмотреть по-
ведение террористов обоих типов. Нормальный террорист, как мы видели раньше в Игре 16.3, не будет
взрывать бомбу в Нью-Йорке. Сумасшедший же террорист, наоборот, предпочтет взорвать бомбу (так
как 0 больше ?1). В результате этих рассуждений (которые, как предполагается, должен проводить
рациональный пилот) получим свернутую игру, которая показана на Рис. 16.24.
Если пилот выберет Кубу, то в любом случае поучит ?1 . Если же пилот выберет Нью-Йорк, то с
вероятностью ? он получит ?100 , а с вероятностью 1 ? ? получит 1 , то есть его ожидаемый выигрыш
34
Отметим, что можно рассматривать байесовские игры (игры с неполной информацией) как игры с несо-
вершенной информацией, в которых одним из игроков является природа.
16.6. Динамические байесовские игры 671

Природа
нормальный
сумасшедший

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

Нью-Йорк Куба Нью-Йорк
Куба

?1 ?1
?100 1
1 1 ?1
0

Рис. 16.24.


составит
? · (?100) + (1 ? ?) · 1 = 1 ? 101?.
Пилот должен сравнить выигрыш ?1 с выигрышем 1 ? 101? и выбрать максимальный. Таким
образом, вид решения будет зависеть от параметра ? . Если вероятность встретить сумасшедшего
террориста мала, т. е. ? < 2/101, то пилот полетит в Нью-Йорк, а если эта вероятность велика, т. е.
? > 2/101, то он предпочтет полететь на Кубу. При ? = 2/101 пилоту все равно, куда лететь.
Заметим, что в рассмотренном примере не содержится специфических элементов, которые прида-
ют динамическим байесовским играм принципиально иной характер по сравнению с динамическими
играми с совершенной и полной информацией или статическими байесовскими играми. Поэтому здесь
для нахождения решения нам достаточно было воспользоваться обратной индукцией. Мы смогли про-
анализировать выбор пилота, поскольку знали, с какой вероятностью он мог в своем информационном
множестве оказаться в левой вершине, а с какой — в правой.
Однако зачастую такие вероятности неизвестны. Мы сталкивались уже с этой проблемой, рассмат-
ривая динамические игры с полной, но несовершенной информацией. В подобных ситуациях, коль
скоро игрок стоит перед выбором в некотором информационном множестве, состоящем более чем из
одной вершины, то ему приходится делать некоторые предположения относительно того, с какой ве-
роятностью он может оказаться в той или иной вершине. Если игрок имеет такого рода ожидания,
то на их основе он выбирает ту альтернативу, которая может обеспечить ему наибольший ожидаемый
выигрыш. Эти рассуждения приводят к понятию совершенного байесовского равновесия.
Совершенное байесовское равновесие состоит из следующих компонент:
D набор стратегий (s1 , . . . , sm ) всех игроков;
D для каждого игрока i — набор ожидаемых им стратегий остальных игроков, se ; ?i
D для каждого игрока в каждом информационном множестве, в котором ему принадлежит ход, —
ожидаемое им распределение, заданное на вершинах этого информационного множества.
Для того, чтобы описанный набор стратегий и ожиданий составлял совершенное байесовское рав-
новесие, необходимо выполнение следующих условий:
1) Ожидания любого игрока согласованы: ожидаемое распределение на вершинах информационных
множеств для каждого игрока i соответствует выбранной игроком стратегии (si ) и тем стратегиям,
которые, как он ожидает, выберут другие игроки (se ).
?i

2) Выбранная стратегия последовательно оптимальна при данных ожиданиях, то есть выбор в каждом
информационном множестве должен быть таким, чтобы максимизировать ожидаемый выигрыш в
предположении, что после этого информационного множества игра будет идти в соответствии с
набором стратегий (si , se ).
?i

3) Ожидаемые стратегии совпадают с фактически выбранными стратегиями: se = s?i .
?i

Первое условие требует специального пояснения. Поясним сначала это условие для случая чистых
стратегий. Рассмотрим некоторого игрока i и информационное множество, в котором этому игроку
принадлежит ход. Какими должны быть его ожидания в данном информационном множестве? Пред-
положим, что траектория, соответствующая набору стратегий (si , se ) и выходящая из начальной
?i
вершины, проходит через одну из вершин данного информационного множества. В таком случае, если
игрок рационален, то он должен ожидать, что будет находиться именно в этой вершине, коль скоро
игра достигнет данного информационного множества и ему придется делать в нем выбор.
16.6. Динамические байесовские игры 672

1-й
2-й




Рис. 16.25.


В качестве примера рассмотрим статическую игру, изображенную на Рис. 16.25. Если второй иг-
рок ожидает, что первый игрок выберет правую стратегию, то он должен ожидать также, что будет
находиться в правой вершине своего информационного множества. Следует отметить, что если вто-
рой игрок будет исходить из сформированных таким способом ожиданий, то, выбирая свои действия
оптимальным образом, он повторит ту функцию отклика, которую мы рассматривали при анализе
равновесия Нэша.
В случае смешанных стратегий общего вида рассуждения должны быть похожими. Следует вы-
числить, с какой вероятностью будет достигаться каждая из вершин некоторого информационного
множества в процессе игры, если игра будет происходить в соответствии с набором стратегий (si , se ).
?i
Тогда ожидаемая вероятность того, что игрок может находиться в некоторой вершине рассматривае-
мого информационного множества, равна вероятности достижения этой вершины деленной на сумму
вероятностей достижения вершин рассматриваемого информационного множества. Указанная сумма
вероятностей есть просто вероятность достижения рассматриваемого информационного множества, ес-
ли игра будет происходить в соответствии с набором стратегий (si , se ). Понятно, что эта вероятность
?i
не должна быть равна нулю, чтобы можно было произвести деление. (Если же вероятность равна нулю,
т. е. данное информационное множество не может быть достигнуто, то указанное правило не приме-
нимо.) Описанный способ вычисления вероятностей соответствует классическому правилу Байеса для
условных вероятностей.
Напомним, что правило Байеса применимо к событиям A и Bj (j = 1, . . . , m ), таким что:
(1) Bj (j = 1, . . . , m ) — несовместные события, т. е.

Bj ? Bk = ?, ?j, k = 1, . . . , m;

(2) тот факт, что произошло одно из событий Bj гарантирует, что произошло также событие A,
т. е.
m
A? Bj .
j=1

При этом верна следующая формула Байеса:

Pr{Bj } Pr{A | Bj } Pr{Bj } Pr{A | Bj }
Pr{Bj | A} = = .
m
Pr{Bk } Pr{A | Bk } Pr{A}
k=1

В этой формуле Pr{Bj } — вероятность события Bj , Pr{Bj | A} — вероятность события Bj при
условии, что произошло событие A , Pr{A} — вероятность события A, Pr{A | Bj } — вероятность со-
бытия A при условии, что произошло событие Bj . В знаменателе первой дроби стоит формула полной
вероятности для Pr{A} . Чтобы можно было применить правило Байеса, нужно чтобы знаменатель не
был равен нулю ( Pr{A} = 0 ).
В применении к рассматриваемой проблеме можно считать, что событие Bj означает, что процесс
игры привел в определенную вершину, а событие — A, что процесс игры привел в данное инфор-
мационное множество. Если брать только такие вершины, которые содержатся в рассматриваемом
информационном множестве, то Pr{A | Bj } = 1 и формула упрощается:

Pr Bj
Pr{Bj | A} = ,
Pr A
m
где Pr{A} = k=1 Pr{Bk }.
Поясним сказанное на примере игры, изображенной на Рис. 16.26. Если 3-й игрок считает, что 1-й
игрок выбирает левую сторону с вероятностью 0,4 , и что 2-й игрок выбирает левую и правую сторону
16.6. Динамические байесовские игры 673

с равными вероятностями, то он должен считать, что вершина ˜ будет достигаться в процессе игры с
вероятностью 0,4·0,5 = 0,2 , а вершина ? — с вероятностью 0,6 . Таким образом, он должен сопоставить
вершине ˜ вероятность
0,2/(0,2 + 0,6) = 0,25,
а вершине ? — вероятность
0,6/(0,2 + 0,6) = 0,75.


? 1-й
[0,4] [0,6]
2-й ?
[0,5] [0,5]
˜ 3-й ?



Рис. 16.26.

Это только одно из требований. Даже если при наборе стратегий (si , se ) процесс игры никогда не
?i
может привести в некоторое информационное множество, ожидания игрока в данном информационном
множестве должны соответствовать (si , se ). Так в игре изображенной на Рис. 16.27а, при указанных
?i
ожиданиях относительно стратегий 1-го и 2-го игроков 3-й игрок должен ожидать, что может оказать-
ся в левой вершине с вероятностью 0,1 , а в правой вершине с вероятностью 0,9 , хотя вероятность
достижения информационного множества равна нулю. Ограничимся только этими пояснениями и не
станем давать более точного определения.
Заметим, что не всегда можно по данному набору стратегий сформировать ожидания. Например,
в игре изображенной на Рис. 16.27б, при указанных ожиданиях о стратегии 1-го игрока 2-й игрок не
может сформировать ожиданий в своем информационном множестве. Второй игрок может получить
ход только в результате ошибки первого игрока и трудно судить, какая из ошибок более вероятна. В
таких случаях мы будем только требовать, чтобы у игрока были некоторые ожидания, и он выбирал
стратегию на основе этих ожиданий35 .

1-й 1-й
б)
а)
[0] [1]
[1]
[0]
[0]
2-й
[0,1] [0,9] 2-й
3-й




Рис. 16.27.

Отличительной особенностью совершенного байесовского равновесия является то, что для его по-
иска в общем случае невозможно использовать обратную индукцию, кроме случая игр с почти совер-
шенной информацией. Если в игре нет подыгр, то совершенное байесовское равновесие приходится
находить как решение системы уравнений: ожидаемые распределения на вершинах информационных
множеств находятся в соответствии с равновесным набором стратегий, а равновесная стратегия выби-
рается каждым игроком на основе предположений об ожидаемых распределениях на вершинах инфор-
мационных множеств.
Для иллюстрации использования совершенного байесовского равновесия рассмотрим модифика-
цию Игры 16.6 (с. 670) с двумя типами террористов, в которой террорист предварительно решает,
35
Для таких случаев в теории игр к настоящему времени разработано насколько различных концепций ре-
шений. Однако все они являются в той или иной степени спорными. Интересующийся читатель, владеющий
английским языком, может обратиться к соответствующей литературе.
16.6. Динамические байесовские игры 674

Природа
сумасшедший нормальный
[?] [1??]


[µ1 ] [µ2 ]
0 0

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

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

ОГЛАВЛЕНИЕ

Следующая >>