Яковлев В.В. Экологическая безопасность, оценка риска

Подождите немного. Документ загружается.

121

- исключением несущественных переменных,

- изменением природы переменных (например, заменой

непрерывных величин дискретными, заменой переменной на па-

раметр),

- изменением функциональных соотношений между пере-

менными,

- модификацией ограничений.

Упрощенную модель реальной конфликтной ситуации принятия ре-

шений называют игрой. От реальной ситуации игра отличается ограниче-

ниями и правилами поведения сторон (игроков). Результат

конфликта в

теории игр называется исходом. В зависимости от числа участников, игры

могут быть парными или множественными.

Общий подход к моделированию конфликтных ситуаций

Пусть имеется парная игра Ω, в которой участвуют два игрока А и В.

Чтобы игра могла быть подвергнута математическому анализу, должны

быть четко определены правила игры, т.е. сформулирована система усло-

вий, регламентирующая:

- возможные варианты действий игроков,

- объем информации каждой стороны о поведении другой,

- результат (исход) игры,

к которому приводит каждая данная совокуп-

ность ходов.

Результат игры не всегда имеет количественное выражение, но

обычно можно, хотя бы условно, выразить его числом (например, 1 – вы-

игрыш, 0 – проигрыш, ½ - ничья).

Игра называется игрой с нулевой суммой, если один игрок выигры-

вает ровно столько, сколько проигрывает другой, т.е. сумма выигрышей

сторон равна

нулю.

Введем обозначения: а – выигрыш игрока А,

b – выигрыш игрока В.

Развитие игры во времени состоит из дискретных ходов (решений).

Ходом в теории игр называется выбор одного из предусмотренных прави-

лами действий и его осуществление. Ходы бывают личными и случайны-

ми.

Личным ходом называется сознательный выбор игроком одного из

возможных

вариантов действий и его осуществление.

Случайным ходом называется выбор действия на основе случая (на-

пример, бросания монеты, непредвиденные аномалии природы, техноген-

ные аварии и т.д.).

Стратегией игрока называется совокупность правил, определяющих

выбор действий при каждом личном ходе этого игрока в зависимости от

ситуации, сложившейся в процессе игры.

В зависимости от

числа возможных стратегий игры делятся на ко-

нечные и бесконечные.

122

Целью теории игр является выработка рекомендаций для выбо-

ра оптимальной стратегии.

Оптимальной стратегией игрока называется такая стратегия, кото-

рая при многократном повторении игры обеспечивает данному игроку мак-

симально возможный средний выигрыш, в предположении о том, что про-

тивник столь же разумен. При этом не учитывается азарт, возможные про-

счеты и личные

ошибки игроков.

Выигрыш в теории игр определяется по одному единственному кри-

терию (числу), что в реальной действительности случается далеко не все-

гда, но человек не умеет решать многокритериальные задачи.

Платежная матрица игры.

Рассмотрим конечную игру, в которой игрок А имеет m стратегий, а

игрок В имеет n стратегий. Такая игра называется

игрой m×n. Предполо-

жим, что каждая сторона выбрала определенную стратегию: A

, B

. Если

игра состоит только из личных ходов, то выбранные стратегии определили

исход игры:

– выигрыш игрока А,

[

]

mi ,1

∈

, если он выбрал стратегию А

, а

игрок В выбрал стратегию B

(-a

) = b

– выигрыш игрока В,

[

]

nj ,1

∈

Значение a

может быть как положительным (выигрыш игрока А и

проигрыш игрока В), так и отрицательным (проигрыш игрока А и выиг-

рыш игрока В).

Если игра кроме личных (обдуманных) ходов содержит случайные,

то выигрыш a

будет представлять собой случайную величину, зависящую

от исходов всех случайных ходов. В этом случае естественной оценкой

ожидаемого выигрыша будет математическое ожидание случайного выиг-

рыша.

Предположим что известны значения a

при каждой паре стратегий.

Эти значения можно записать в виде матрицы.

Таблица 7.1.

Значения выигрышей стороны А при различных стратегиях.

Такая матрица называется платежной матрицей. Если число возмож-

ных стратегий велико, то задача формирования платежной матрицы стано-

вится чрезвычайно трудной, например, при игре в шахматы.

A\B

… B

… a

…

… … … …

… a

123

Пример 7.1.

Игрок А может держать монету в левой или в правой руке, игрок В

должен угадать, в какой руке находится монета, т.е. в распоряжении игро-

ка А имеется две стратегии А

и А

, любую из которых он может выбрать

по своему усмотрению.

Условия игры: если игрок В угадает, где находится монета, то игрок

А платит ему, например, 1 руб. Если игрок В не угадывает, то он платит

игроку А столько же (1 руб.).

Вид платежной матрицы представлен табл. 7.2.

Таблица 7.2.

Платежная матрица примера 7.1 (игра 2×2).

A\B

- 1 + 1

+ 1 - 1

Если игра выполняется только один раз (одноходовой вариант), то

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

жет выбрать любую из них. Но при многократном повторении игры с зара-

нее оговоренным числом ходов, положение меняется.

Игрок А может выбрать одну стратегию и не менять ее в течение

всей

игры, тогда вскоре игрок В разгадает этот план и будет действовать

таким образом, что игрок А начнет проигрывать. То же самое произойдет,

если игрок А будет менять стратегии по определенному закону.

Чтобы не оказаться в проигрыше, игроку А следует чередовать стра-

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

Для игрока

В справедливы те же особенности и ему также следует выби-

рать стратегию случайным образом.

Следовательно, интуитивно игроки приходят к выводу о необходи-

мости использования смешанных стратегий (основанных на случайном

выборе), где «чистые» (обдуманные) стратегии чередуются в случайной

последовательности с определенными вероятностями.

Пример 7.2. Игра «три пальца».

Игроки А и В одновременно

и независимо друг от друга выбрасыва-

ют один, два или три пальца (вариант ни одного пальца исключается).

Выигрыш или проигрыш решает общее число показанных пальцев.

Выигрыш (например, в рублях) равен сумме показанных пальцев и доста-

ется этот выигрыш игроку А, если сумма показанных пальцев четная, если

сумма нечетная, то выигрыш достается

игроку В.

Вид платежной матрицы представлен табл. 7.3.

124

Таблица 7.3.

Платежная матрица игры 3×3 для примера 7.2.

А\В

2 -3 4

-3 4 -5

4 -5 6

При выборе стратегии А

игрок А показывает один палец, при выбо-

ре стратегии А

– два пальца, при выборе стратегии А

– три пальца. Ана-

логично формирует свои стратегии и игрок В.

В чистых стратегиях при большом числе ходов цена игры не выгодна

ни одному из игроков, поскольку план выбора строго определенной стра-

тегии будет разгадан противником. Снова возникает желание обращения к

смешанным стратегиям, но чтобы найти оптимальный вариант решения

необходимо освоить

аппарат теории игр.

Нижняя и верхняя цена игры. Принцип минимакса.

Рассмотрим игру m×n. Буквой i будем обозначать стратегию игрока

А, буквой j – игрока В.

Вначале рассмотрим только чистые стратегии. Поставим задачу:

найти наилучшую среди стратегий А

для i∈[1, m]. Выбирая при этом кон-

курирующую стратегию, необходимо рассчитывать на то, что противник

ответит наилучшим для себя образом (или, что то же самое, наихудшим

образом для игрока А), т.е. противник выполнит ход, при котором выиг-

рыш игрока А будет минимальным.

Добавим к платежной матрице один неполный столбец и

одну не-

полную строку (табл. 7.4).

Таблица 7.4.

Определение нижней и верхней цены игры.

Таким образом, в столбце справа выписаны минимальные значения

выигрышей игрока А для каждой выбранной i-й стратегии и всевозможных

стратегиях стороны В для этой стратегии стороны А:

A\B

… B

iij

aa =min

… a

min a

… a

min a

…

… … … … …

… a

min a

jij

aa =max

max a

… max a

125

aa min=

(7.1)

Аналогично, в последней строке табл. 7.4 приведены максимальные

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

aa max

(7.2)

Нижней ценой игры или ее максиминным выигрышем или максими-

ном называют максимальное значение из всех чисел правого столбца:

aa maxminmax

, (7.3)

соответствующую стратегию А

называют максиминной стратегией.

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

цену игры, называемую минимаксом (минимальное из чисел последней

строки):

aa minmaxmin

(7.4)

Положение, при котором оба игрока пользуются только своими мак-

симинными (минимаксными) стратегиями является неустойчивым и может

быть нарушено за счет использования дополнительной информации о по-

ведении противника.

Пример. 7.3. Вновь рассмотрим пример 7.2 (игра «три пальца»).

Найдем максиминные и минимаксные решения этой игры.

Таблица 7.5.

Платежная матрица для определения цены игры.

А\В В

2 -3 4 -3

-3 4 -5 -5

4 -5 6 -5

4 4 6

Максиминная стратегия игрока А = А

, при которой гарантируется,

что игрок А не проиграет на каждом ходе больше 3 руб.

Минимаксная стратегия игрока В = В

или В

, при которых гаранти-

руется, что игрок В не проиграет более 4 руб.

Если нижняя цена игры совпадает с верхней, то соответствующие

стратегии являются устойчивыми, а такие игры называются играми с сед-

ловой точкой. В этом случае:

(7.5)

и величина

называется ценой игры.

Если

≠

, то цена игры для каждого игрока будет определяться значени-

ем α или β соответственно.

126

Для игр с седловой точкой минимаксные стратегии обладают устой-

чивостью.

Чистая цена игры в этом случае является тем значением выигрыша,

которое в чистых стратегиях игрок А не может увеличить, а игрок В не

может уменьшить.

Решение игры в смешанных стратегиях.

Смешанные стратегии представляют собой математическую модель

изменчивой гибкой тактики, при

которой противник не знает, и не может

узнать заранее, с какой обстановкой ему придется встретиться.

Пусть имеется игра m×n.

Обозначим:

),...,(

21 mA

pppS =

(7.6)

и назовем смешанной стратегией, в которой стратегии А

, А

,…А

приме-

няются с вероятностями р

, р

,…,р

, (часть из которых может быть равной

нулю). Поскольку рассматриваются только стратегии (7.6), то они обра-

зуют полную группу событий, следовательно:

∑

Аналогично для противника:

∑

jnB

qгдеqqqS

1),,..,(

Решением игры называется пара оптимальных смешанных стратегий:

{

}

∗∗

SS ,

, (7.7)

обладающих следующим свойством: если один из игроков придерживает-

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

годно отступать от своей оптимальной стратегии.

Выигрыш игрока А (проигрыш игрока В), соответствующий реше-

нию (7.7), называется ценой

игры в смешанных стратегиях.

Существует так называемая основная теорема теории игр.

Каждая конечная игра имеет, по крайней мере, одно решение, воз-

можно в области смешанных стратегий.

Из основной теоремы следует, что каждая конечная игра имеет цену,

значение которой лежит в пределах между нижней и верхней ценой игры:

≤

(7.8)

Активными называются стратегии, которые входят в оптимальную

смешанную стратегию игрока с вероятностями, отличными от нуля. Для

решения игр в смешанных стратегиях существенное значение имеет тео-

рема об активных стратегиях.

127

Теорема об активных стратегиях.

Если один из игроков придерживается своей смешанной оптималь-

ной стратегии, то выигрыш останется неизменным и равным цене игры

, независимо от того, что делает второй игрок, если только тот не

выходит за пределы своих активных действий (т.е. пользуется любой из

своих стратегий в чистом или смешанном виде).

Игра 2×2.

В этой наиболее простой игре могут встретиться два варианта:

- игра имеет седловую точу,

- игра не имеет седловой точки.

Если игра имеет седловую точку, то одна из стратегий может быть

отброшена, как заведомо невыгодная или дублирующая.

Рассмотрим случай, когда в игре 2×2 седловой точки нет, т.е. нижняя

цена игры не равна верхней:

≠

(7.9)

Решение игры должно быть найдено в смешанных стратегиях.

Если игрок А выбирает оптимальную смешанную стратегию

),(

ppS

∗

, (7.10)

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

стратегий, например, В

и В

, т.е. образуются два уравнения:

=⋅+⋅

⋅

222112

221111

papa

(7.11)

при условии:

Решением этой системы уравнений будут вероятности выбора стра-

тегий:

21122211

2122

aaaa

−−+

−

; (7.12)

21122211

1211

aaaa

−−+

−

=−=

; (7.13)

Подставив полученные выражения для вероятностей в любое из

уравнений, получим значение цены игры:

21122211

aaaa

−−+

⋅−⋅

(7.14)

Аналогично находятся оптимальные стратегии игрока В:

=⋅+⋅

⋅

222121

212111

qaqa

(7.15)

21122211

1222

aaaa

−−+

−

(7.16)

128

Пример 7.4.

Рассмотренная в примере 7.1 игра 2×2 имеет следующие данные.

Таблица 7.6.

Платежная матрица примера 7.1 (игра 2×2).

A\B

- 1 + 1

+ 1 - 1

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

чим на основе (7.12), (7.13), (7.16) решение:

;

===

∗∗

(7.17)

Следовательно, оптимальная стратегия каждого игрока состоит в

том, чтобы случайным образом чередовать свои чистые стратегии, пользу-

ясь каждой из них с вероятностью 1/2.

Игры 2×n и m×2.

По аналогии с методами поиска решений игры 2×2 столь же просто

может быть решена задача 2×n или m×2.

Рассмотрим игру 2×n. Представим ее

геометрическую интерпрета-

цию для n=4, (рис. 7.2).

Рис. 7.2. Геометрическое представление задачи 2×4.

129

Возьмем участок оси абсцисс длиной единица. Левый конец отрезка

с абсциссой х = 0 будет изображать стратегию А

, правый конец участка с

абсциссой х = 1 – стратегию А

На осях I и II будем откладывать выигрыши стратегий А

и А

соот-

ветственно при использовании игроком В всех его возможных стратегий

(В

…В

Соединим соответствующие выигрыши игрока А (при выборе стра-

тегий А

и А

) прямыми и заметим, что ордината любой точки такой пря-

мой соответствует выигрышу при использовании противником определен-

ной стратегии для соответствующей смешанной стратегии игрока А.

Нижнюю границу выигрыша игрока А при любых стратегиях игрока

В будет представлять ломаная

B1-M-N-B2. Найдем на этой ломаной точку N

с максимальной ординатой. Все промежуточные точки участка [0, 1] оси

абсцисс будут изображать смешанные стратегии, причем вероятность р

стратегии А

будет равна расстоянию от точки S

до правого конца участ-

ка. Ордината точки N и будет равна цене игры, а абсцисса точки N будет

равна вероятности р

стратегии А

в оптимальной смешанной стратегии

игрока А.

),(

ppS

∗

(7.18)

Оптимальная смешанная стратегия игрока В

),0,,0(

qqS

∗

(7.19)

состоит из двух активных стратегий В

и В

, пересекающихся в точке N.

Стратегия В

является заведомо невыгодной, а стратегия В

будет невы-

годной при выборе стороной А оптимальной стратегии

∗

S . Если сторона А

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

∗

S , то выигрыш не

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

Можно доказать, что у любой конечной игры m×n существует реше-

ние, в котором число активных стратегий не превосходит наименьшего из

чисел m и n. Т.е. в играх 2×n и m×2 строится геометрическая интерпрета-

ция и ищется пара

стратегий, пересекающихся в точке N . Если в этой точ-

ке пересекается более двух стратегий, берется любая пара. Эти стратегии

будут активными стратегиями игрока В и игра 2×n или игра m×2 будет све-

дена к игре 2×2.

Решение игр m×n.

Если размерность игры превосходит 2 для стороны с наименьшим

числом стратегий, то геометрическая

интерпретация игры становится не-

возможной.

В общем случае, при больших значениях m и n решение игры пред-

ставляет собой сложную задачу, но принципиальных трудностей ее реше-

ние не содержит.

130

Можно доказать, что решение любой конечной игры m×n может

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

Пусть в игре m×n (табл. 7.7) требуется найти решение, т.е. необхо-

димо найти две оптимальные смешанные стратегии:

),...,(;),...,(

2121 nBmA

qqqSpppS ==

∗∗

(7.20)

где

1,1

∑∑

(7.21)

Цена игры

пока неизвестна.

Не нарушая общности можно предположить,

0≥

, что вполне ре-

ально, если представить все а

≥ 0. Такого положения можно добиться, ес-

ли прибавить ко всем элементам матрицы одну и ту же достаточно боль-

шую величину М. При этом цена игры также увеличится на М, но решение

игры (номер оптимальной стратегии) не изменится.

В этих новых условиях, если сторона А применяет оптимальную

стратегию

∗

S , а сторона В – чистую стратегию, то средний выигрыш со-

ставит:

njвсехдляapapapa

mjmjjj

,...2,1

2211

⋅

+⋅

⋅= "

(7.22)

Таблица 7.7.

Расширенная платежная матрица

А\В B

… В

… B

… a

…

… … … …

… a

Поскольку оптимальная стратегия

∗

S обеспечивает стороне А выиг-

рыш не менее цены игры

, получим ряд условий:

≥⋅++⋅+⋅

≥

⋅

++⋅+⋅

mnmnn

apapap

2211

2222121

1212111

.......................................................

(7.23)

Разделим эти неравенства на положительную величину

и введем

обозначения:

=== ,,,

(7.24)

Тогда система уравнений (7.23) запишется в виде: