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

Теоретико-практическая работа

по предмету «Теория игр»

на тему

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

 

 

 

 

 

 

 

 

 

 

Москва – 2013 г. 
Оглавление

 

 

 

Введение. Постановка задачи

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

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

Постановка задачи:

В данной теоретико-практической работе в теоретической её части будет рассмотрен упомянутый выше подкласс игр, а также определены методы их решения.

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

 

Теоретическая часть

Понятие динамической игры

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

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

Дерево игры.

Во-первых, нам (как и в статической игре) нужно определить множество игроков. Для того, чтобы моделировать случайные события, влияющие на выигрыш игроков, нам необходимо определить еще одного игрока — природу. Таким образом, мы имеем I = {1, · · · , N }∪{природа}.

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

Наконец, в-третьих, нам надо определить, как выигрыши игроков зависят от ходов, которые были сделаны. Формально, для каждой конечной вершины дерева игры мы определяем выигрыши для каждого игрока.

Каждому ходу, который игрок делает в какой-то вершине, соответствует вершина, в которой игра оказывается после сделанного хода. В любом дереве игры, для любой вершины, кроме начальной, однозначно задается история игры — то есть последовательность вершин, через которые игра уже успела пройти. В частности, для любой вершины (опять же, кроме начальной) существует ровно одна вершина, непосредственно предшествующая данной. Это исключает «деревья» вроде графа. Необходимость наличия начальной вершины также исключает возможность циклов.

 

 

Информационные множества и стратегии в динамической игре. Равновесие Нэша.

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

1. Каждая вершина игрока i содержится в одном и ровно  одном информационном множестве.

2. Пусть  — информационное множество игрока i. Во всех вершинах, входящих в hi , игроку доступен один и тот же набор действий .

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

 

В игре Γ в развернутой форме множество чистых стратегий игрока i есть

 

где — информационные множества, в которых делает ход игрок i.

При этом число чистых стратегий у игрока i будет

 

Например, если в некой игре у некого игрока есть 3 информационных множества, в которых возможно по 3, 4 и 5 действий, то число его чистых стратегий равно 3 × 4 × 5 = 60.

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

 

 

 

Здесь стоит уточнить понятие равновесия Нэша – концепции, широко применяемой в решении игр двух и более игроков:

Пусть — игра в нормальной форме. Тогда — равновесие Нэша, если для всех i, для всех , мы имеем

 

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

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

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

Игры с совершенной информацией.                                                             Равновесие, совершенное по подыграм

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

Пусть каждое информационное множество в игре Γ содержит ровно одну вершину. Такая игра называется игрой с совершенной информацией.

Примерами данного класса игр могут служить такие настольные игры, как шашки, шахматы и крестики-нолики.

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

Пусть Γ — игра в развернутой форме. Подыгра Γ(x) — это часть дерева игры, которая начинается с некоторой вершины x, и удовлетворяет следующим свойствам:

1. x — единственный элемент  в своем информационном множестве.

2. Информационные множества, содержащие вершины из подыгры Γ(x), не содержат других вершин.

Тогда равновесием, совершенным по подыграм, называется такой профиль стратегий из динамической игры Г, который является равновесным для каждой из подыгр Г.

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

Игры с несовершенной информацией

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

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

Для примера рассмотрим игру двух игроков, у каждого из которых есть по две чистые стратегии. Предположим, что первый игрок ходит первым, второй — вторым. Есть две вершины, в которых ход принадлежит 2-му игроку, однако сам он не может различить, выбирая свои действия, в какой вершине он находится; другими словами, эти две вершины находятся в одном и том же информационном множестве.

                                           L           H

 

 

                   m                     n     m                    n

 

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

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

Равновесие в играх с несовершенной информацией.

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

Для иллюстрации рассмотрим игру, изображенную на рисунке:

Формально, в этой игре всего одна подыгра, соответствующая всему дереву игры. Таким образом, получается, что любое равновесие в этой игре будет совершенным по подыграм, в том числе и равновесие (R, r). Однако очевидно, что это равновесие неадекватно. Почему игрок II сделает ход r в своем информационном множестве? Конечно, это информационное множество лежит вне траектории игры, которая заканчивается на первом же ходе игрока I. Однако будет ли игрок II делать ход r если по какой-то причине игрок I не сыграет R? Пусть μ — вероятность того, что игрок I сделал ход L при условии того, что он сделал либо ход L, либо ход M . Тогда условное мат.ожидание полезности игрока II при ходе l будет равна μ + 2(1 − μ), при ходе l — 1 − μ. Выходит, что при любом μ ∈ [0, 1], игроку II выгодно делать ход l в том случае, если игрок I все-таки не сыграл R. Равновесие (R, r) не соответствует критерию, очень похожему на критерий совершенства по подыграм. Обещая играть r, игрок II фактически выставляет игроку I невыполнимую угрозу. При этом формально равновесие является совершенным по подыграм; очевидно, что нам необходимо более сильное условие равновесности для того, чтобы отсечь такие нежелательные «равновесия»

Введем понятия слабого и сильного секвенциального равновесия:

Пусть Γ — игра в развернутой форме, h — информационное множество в этой игре. Назовем верой распределение вероятностей на вершинах, входящих в h. Обозначим за = веру (или систему вер) в игре Γ — распределение вероятностей для каждого информационного множества.

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

Пусть Γ — игра в развернутой форме, σ — профиль поведенческих стратегий в этой игре. Пусть μ — система вер. Будем говорить, что μ слабо согласована с σ если для всех информационных множеств h, таких, что при σ существует положительная вероятность попадания игры в h, для всех вершин a ∈ h, верно следующее:

 

где P (a|σ) — вероятность того, что траектория игры пройдет через вершину a, — вероятность того, что траектория игры пройдет через информационное множество h.

Если система вер согласована с поведенческой стратегией, то для всех информационных множеств, через которые траектория игры проходит с положительной вероятностью, вера вычисляется по правилу Байеса.

В каждом информационном множестве, оптимальное действие игрока должно зависить от веры в этом информационном множестве. Пусть σ – профиль поведенческих стратегий, μ – система вер. Пусть h – информационное множество, в котором игрок i делает ход. Определим за ожидаемый выигрыш игрока i при условии, что игра достигла множества h. Будем говорить, что секвенциально рациональна относительно μ, если для всех ,

 

Можно дать следующее определение равновесия:

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

В примере, профиль стратегий (R, r) не согласован ни с какой системой вер: при любом μ, игрок II должен выбрать действие l. Однако определение слабой согласованности вер ничего не говорит про те случаи, когда одно из информационных множеств лежит вне траектории игры. Такое может произойти только если в некоторых информационных множествах какие-то действия играются с нулевой вероятностью; соответственно, потребуется сформулировать более жесткий критерий в отношении системы вер, чем слабая согласованность.

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

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