Теория игр и обеспечение безопасности

Сильная согласованность требует, чтобы вера являлась пределом последовательности вер, полученных из сходящихся к стратегии σ профилей стратегий. Дадим определение:

Пара (σ, μ) является сильно секвенциальным равновесием, если σ секвенциально рациональна относительно μ, и μ сильно согласована с σ.

Мы сформулировали понятие секвенциального равновесия. Оно обобщает понятие совершенства по подыграм для динамических игр с неполной информацией.

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

Пусть G — игра в нормальной форме. Пусть σ — профиль стратегий, причем существует последовательность σ n вполне смешанных профилей стратегий, таких, что

1.

2. Для всех k, для всех i, является наилучшим ответом на .

Будем называть σ совершенным (или совершенным относительно дрожащей руки) равновесием.

Верно следующее утверждение:

Пусть G — конечная игра в нормальной форме. Тогда в этой игре существует равновесие, совершенное относительно дрожащей руки.

Рассмотрим игру Γ в развернутой форме. Пусть — совершенное равновесие.

Пусть Γ — игра в развернутой форме, G — игра в нормальной форме, соответствующая ей. Пусть — совершенное равновесие в G. Тогда существует вера μ, такая, что (μ, σ) — сильно секвенциальное равновесие в Γ.

Таким образом, любое совершенное равновесие является сильно секвенциальным. Обратное неверно: существуют случаи, когда равновесие является сильно секвенциальным, но не совершенным.

Сигнальные игры. Байесово равновесие.

Рассмотрим один из важнейших типов динамических игр с несовершенной информацией – сигнальные игры, однако сначала надо дать определение классу игр с наблюдаемыми действиями:

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

Формально, мы можем дать такое определение:

Пусть Γ — игра в развернутой форме с совершенной информацией, — множество типов игроков, P = P1 × · · · × PN — распределение вероятностей на T, — функция полезностей игрока i, определяющая его выигрыш в зависимости от конечной вершины и его типа . Тогда — игра с наблюдаемыми действиями.

Пусть (μ, σ) — система вер и поведенческая стратегия для игры с наблюдаемыми действиями. Назовем систему вер μ разумной относительно σ если выполняется следующее:

1. μ слабо согласована  с σ.

2. Пусть h и h′ — информационные  множества, такие, что в множество h′ можно попасть одним ходом из множества h. Пусть игрок k не делает ход ни в h, ни в h′ . Тогда .

3. Пусть h — информационное  множество, в котором делает ход  игрок i. Тогда . Если o — начальная вершина, i — игрок, делающий первых ход, то .

Третье требование означает, что в каждом информационном множестве, веры игрока i относительно типов остальных игроков являются независимыми. В совокупности со вторым требованием, это означает, что пока какой-то игрок не делает хода, остальные игроки не узнают про него ничего нового; таким образом, делая ход, игрок может менять представления игроков только о своем типе, но не о типах остальных игроков.

 Пусть (σ, μ) — профиль  поведенческих стратегий и система  вер, такие, что μ является разумной относительно σ, а σ — секвенциально рациональна относительно μ. Тогда (σ, μ) — совершенное байесово равновесие.

Байесово равновесие — намного более удобное для работы опрелеление, чем сильное секвенциальное равновесие. Доказать, что система вер μ является разумной относительно σ гораздо легче, чем доказать сильную согласованность, так как нам не требуется доказывать что-то относительно сходящихся последовательностей. С другой стороны, сильное секвенциальное равновесие отвечает довольно строгому критерию реализма: если равновесие является сильно секвенциальным, то оно не будет «паталогическим». Поэтому представляется интересным такой вопрос: в каком случае мы, найдя совершенное байесово равновесие, можем быть уверены, что это равновесие является сильно секвенциальным? На этот вопрос отвечает теорема, сформулированная Тиролем и Фаденбергом:

Теорема. Пусть Γ — игра с наблюдаемыми действиями, (σ, μ) — совершенное байесово равновесие. Тогда (σ, μ) — сильно секвенциальное равновесие, если в игре Γ не более двух ходов, либо у каждого игрока есть не более двух типов.

Вернемся к определению сигнальной игры:

Итак, сигнальная игра – это игра с наблюдаемыми действиями, в которой

1. Два игрока — ведущий S и получатель R,

2. У получателя один  тип, у ведущего — больше одного,

3. Первый ход делает  ведущий, второй ход — получатель.

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

Мы знаем, что наличие только двух ходов в игре с наблюдаемыми действиями — достаточное условие для того, чтобы совершенное байесово равновесие было секвенциальным. Переформулируем понятие равновесия для сигнальной игры. Обозначим за T все типы игрока S. Пусть M – множество  действий (или сигналов) для этого игрока. Пусть m : T → M — стратегия игрока S, предписывающее определенное действие в зависимости от типа.

У игрока R будет M информационных множеств, по одному для каждого возможного сигнала, который может послать игрок S. Пусть — вера игрока R относительно того, что игрок S имеет тип при условии, что его первый ход был . Обозначим за A множество действий игрока R. Пусть a : M → A — стратегия игрока R, предписывающее действие в зависимости от сигнала, испущенного игроком S. Обозначим за и полезности двух игроков.

Байесово равновесие, определенное выше, можно переформулировать следующим образом:

Совершенное байесово равновесие в чистых стратегиях в сигнальной игре есть набор , такой, что

1. Для любого  максимизирует ожидаемый выигрыш игрока R при системе вер μ(·|·), то есть для всех

 

2. Для всех t ∈ T , действие игрока S максимизирует его выигрыш при условии, что игрок R будет играть равновесную стратегию :

 

для всех m′ ∈ M .

3. Для всех m ∈ M , таких, что если существует t ∈ T , такой, что m∗ (t) = m, вера игрока R

после хода m определяется по правилу Байеса:

 

где p(t) — вероятность, что игрок S имеет тип t ∈ T .

Первые два требования в этом равновесии — секвенциальная рациональность игроков. Третье требование — согласованность системы вер со стратегиями игроков. 
Практическая часть

Пример 1

Немного расширим тематику работы, включив в понятие обеспечения безопасности игры по обороне города при нападении, чтобы на красивом примере из комментариев к книге Сун Цзы «Искусство войны» проиллюстрировать сигнальные игры.

Дело было в Древнем Китае в эпоху Троецарствия. Великий полководец Чжугэ Лян (реальная личность, годы жизни 181–234) оказался в одном пограничном городе с небольшим отрядом, когда ему доложили, что на город движется огромная вражеская армия, ведомая опытным военачальником Сыма И. Что сделал Чжугэ Лян? Вместо того, чтобы бежать, он приказал открыть ворота города. Своих немногих солдат от переодел в горожан и приказал им подметать улицы перед воротами, а сам, в сопровождении двух оруженосцев, поднялся на городскую стену и достал свой любимый музыкальный инструмент - цитру с выгнутой декой.

Когда Сыма И во главе отряда разведчиков подъехал ближе, он увидел идиллическую картину - пустой город с открытыми воротами и Чжугэ Ляна, мирно играющего на цитре на городских стенах. Сыма И подумал: «Это ловушка. Наверняка в городе прячется большое войско, и если мы войдем в город, то можем оказаться в западне. Не станет же такой хитрый и осторожный полководец, как Чжугэ Лян, вести себя столь безрассудно, чтобы с малым отрядом оставаться в городе. Нет, у него должно быть столь же большое войско, как и у меня!» Поразмыслив немного, он приказал отступить.

Эту история легко представима как игра двух игроков с неполной информацией. Первый игрок — Чжугэ Лян — может быть двух типов. Он может обладать большим войском (тип 1), либо маленьким отрядом (тип 2). Пусть λ — вероятность того, что Чжугэ Лян имеет тип 1. В начале игры у Чжугэ Ляна есть два варианта действий. Он может либо отступить (R), либо остаться с городе (D). Если он отступает, то теряет город, проигрывая c. Поскольку идет война, выигрыш второго игрока равен проигрышу первого.

Если же первый игрок остается в городе, то второй игрок решает: атаковать ему, или отступить (a или r). Если он отступает, то оба игрока получают нулевой выигрыш. Если он атакует, то выигрыш игроков зависит от типа первого игрока. Если первый игрок имеет тип 2, то первый игрок проигрывает x > c (так как помимо потери города гибнет его отряд, а он сам попадает в плен). Если же первый игрок имеет тип 1, то в сражении он одержит победу, и его выигрыш составит w > 0.

Найдем совершенное байесово равновесие в этой игре. Сразу заметим, что если первый игрок имеет тип 1, то его доминирующая стратегия - остаться в городе. Нам остается найти p — вероятность того, что игрок 1 сыграет D, имея тип 2, и q — вероятность того, что второй игрок выберет действие A. Вера второго игрока в его информационном множестве всегда вычислима

по правилу Байеса:

 

Мы можем выписать функции полезностей обоих игроков в зависимости от p и q:

 

 

Найдем функции реакции игроков. Мы имеем

 

и

 

Здесь возможно три случая:

1. Если , то в равновесии мы имеем смешивающее равновесие p = 1 и q = 0. В таком случае, Чжугэ Лян принимает решение остаться в городе с малым отрядом. При этом вероятность того, что у него малый отряд, достаточно мала для того, чтобы Сыма И отступил, увидев Чжугэ Ляна на городских стенах.

2. Если , то у нас наблюдается гибридное равновесие. Чжугэ Лян всегда остается вгороде с большой армией и остается с вероятностью с малым отрядом. Сыма И нападает с вероятностью .

3. Если , то у нас континуум равновесий. Мы всегда имеем p∗ = 1, но нам подойдет любой .

Говорят, что Чжугэ Лян действовал безрассудно, но своим безрассудством смог обмануть противника. Однако в этой истории оба военачальника могли поступать абсолютно рационально. Сыма И, видя открытые городские ворота, понимал, что, скорее всего, Чжугэ Лян находится во главе большого войска и предлагает ему положить руку в капкан. Сыма И мог допускать возможность того, что Чжугэ Лян пытается его обмануть, но мог посчитать слишком малой вероятность того, что у Чжугэ Ляна окажется так мало солдат. Чжугэ Лян, предвидя стратегию Сыма И, решился остаться в городе с малым отрядом. Таково теоретико-игровое объяснение этой древней легендарной истории.

Пример 2

Рассмотрим игру, где рассматривается обеспечение безопасности на контрольно пропускном пункте некоего объекта, например аэропорта.

Предположим, что число работников службы охраны (игрок 2) недостаточно для того, чтобы проверить всех посетителей. Таким образом, у охраны есть две чистые стратегии: проверить пассажира (p) или нет (n).

Пассажиры (игрок 1) же могут быть двух типов: мирный (M) и террорист (T), который стремится пронести на режимный объект некое устройство. У пассажиров есть две чистые стратегии: взять с собой небольшую ручную кладь (K) или объемный рюкзак (R). За разрешение пронести рюкзак на борт приходится платить денежных единиц, однако для террориста эти издержки не играют роли, так как устройство настолько большое, что не помещается в кладь, поэтому террористу приходится привлекать сообщника, неся при этом издержки денежных единиц, если он все же решил нести ручную кладь. Для упрощения предположим, что издержки равны, то есть .

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

Определим выигрыши игроков:

Игрок 1 выигрывает 1, если его не проверили, и 0 в противном случае. Игрок 2, в свою очередь, выигрывает 1, если охрана проверила террориста или не проверила мирного, и 0, если она ошиблась с выбором.

Дерево этой игры представлено на следующем рисунке:

                     p                      Мирный (тип 1)                       p

                                       R                                     K                             

  (1-с,1)        n                                                                         n          (1,1)

                                       

                         

    (0,1)         p                                                                   p         (-c,1)

 

где – вероятность, что пассажир окажется мирным.

Пусть s(1), s(2) ∈ {R, K} — ходы первого игрока в зависимости от его типа. Пусть o(R), o(K) ∈ {p, n} — ходы второго игрока в зависимости от того, каким был ход первого игрока.

Найдем совершенное байесово равновесие.

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

 

 

 

 

2. Найдем, каким условиям удовлетворяет стратегия игрока 2, если она рациональна относительно системы вер Ожидаемый выигрыш охраны в информационном множестве R — то есть если ход игрока 1 был R — при собственном ходе (p) равен

,

а при собственном ходе (n) –

.

Аналогично получим выигрыши в информационном множестве K.

Следовательно, для s ∈ {R,K} мы должны иметь

 

 

3. Каким должна быть стратегия игрока 1, в зависимости от стратегии игрока 2? При c < 1 мы получим

 

При c > 1 мы будем иметь (s(1), s(2)) = (R, K) вне зависимости от o(R) и o(K).

Равновесием в этой игре является набор , удовлетворяющий всем трем перечисленным выше условиям. Число и тип равновесий зависят от значения параметра c:

 

1. Если c < 1 и p ≥ 1/2, то равновесия два:

 

 

 

2. Если c < 1 и p < 1/2, то равновесия в чистых стратегиях нет.

3. Если c > 1, то равновесие  в чистых стратегиях одно: