Москвин Б.В. Теория принятия решений

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

281

а значения верхней и нижней цены игры называют просто ц е -

н о й игры

max min f

= min max f

= С. (13.16)

i j j i

Соответствующие гарантирующие стратегии в этой ситуа-

ции являются о п т и м а л ь н ы м и и целесообразно выбирать

именно такие стратегии.

Так как данная ситуация соответствует наличию седловой

точки у платежной функции f(x,y) (функции двух векторных аргу-

ментов), то и игру называют и г р о й

с с е д л о в о й т о ч -

к о й. Причем седловая точка определяется парой оптимальных

чистых стратегий. Характерной особенностью такой игры являет-

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

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

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

только к большому проигры-

шу (в лучшем случае выигрыш останется без изменений). Так,

например, в игре с платежной матрицей

0 1 4 1

F = 5 0 1 3

4 2 3 4

имеется седловая точка (x

). Совокупность соответствующих

стратегий является решением игры, при этом цена игры равна 2.

Соответствующие чистые стратегии являются устойчивы-

ми, так как отклонение каждого из игроков от оптимального реше-

ния приводит к худшим для этого игрока результатам.

Следует отметить, что имеется большое число ситуаций,

когда матричная игра не разрешима в чистых стратегиях. Так

рассмотренном ранее примере верхняя цена игры равна 6, а

нижняя цена игры равна 3. Таким образом, седловая точка отсут-

ствует. Тогда чистые стратегии становятся неустойчивыми, и вы-

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

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

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

ным. Очевидно, что

в одношаговой игре целесообразно выбирать

гарантирующую стратегию. В то же время в многошаговых играх

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

комбинации чистых стратегий, в том смысле, что бы выбирать их

на каждом шаге с определенной вероятностью или частотой.

282

С м е ш а н н о й с т р а т е г и е й первого игрока называ-

ется упорядоченная последовательность m чисел p = (p

,..

.,p

)

, удовлетворяющих условиям

≥ 0, i=1,...,m;

∑

= 1. (13.17)

При этом числа p

, i=1,...,m интерпретируются как вероятности

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

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

Аналогично смешанной стратегии первого игрока вводится

смешанная стратегия второго игрока q = ( q

,...,q

)

Следует отметить, что смешанная стратегия позволяет

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

=0, i = 1,...,m, i≠j, а p

= 1, смешанная стратегия соответствует

чистой стратегии с номером j.

Смешанных стратегий у каждого игрока может быть доста-

точно много (бесконечно много), в этой связи целесообразно ста-

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

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

диться, существует ли она - оптимальная смешанная стратегия.

Ответ на

этот вопрос дает основная теорема теории игр.

О с н о в н а я т е о р е м а т е о р и и и г р (теорема о

минимаксе). Любая матричная игра разрешима в смешанных

стратегиях.

Таким образом, у первого игрока (соответственно и у второ-

го

игрока) с у щ е с т в у е т оптимальная смешанная стратегия,

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

рыш в многошаговой матричной игре.

max min p

F q = min max p

F q = C . (13.18)

p q q p

Поясним приведенную основную теорему теории игр. За-

пишем матрицу игры в виде F = { f

}, где i = 1,...,m, j = 1,...,n. Сме-

шанные стратегии первого игрока обозначим через p, смешанные

стратегии второго игрока - через q. Тогда на каждом шаге 1-ый

игрок выбирает свою i-ю чистую стратегию с вероятностью p

, а 2-

ой игрок выбирает свою j-ю чистую стратегию с вероятностью q

В этом случае среднее значение величины выигрыша (ма-

тематическое ожидание) определяется как

283

С =

∑

= p

F q. (13.19)

Средний выигрыш является скалярной функцией двух векторных

аргументов p и q. Тогда существует седловая точка функции

среднего выигрыша.

Итак, оптимальная смешанная стратегия существует. Не-

обходимо решить вопрос о том, как ее найти.

Пусть оптимальная смешанная стратегия p известна. Ана-

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

компоненты можно разделить на две группы:

равные нулю и

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

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

ся п а с с и в н ы м и (неактивными) чистыми стратегиями. Дей-

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

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

предписывает на каждом шаге выбирать некоторые

стратегии с

вероятностью 0, то такие стратегии естественно назвать пассив-

ными.

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

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

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

Компоненты смешанной стратегии ассоциируются с веро-

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

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

нения в многошаговой игре. Соответственно пассивные чистые

стратегии можно не рассматривать вообще, что создает основу

для упрощения игры. Для выделения пассивных стратегий вво-

дится понятие доминирующих (доминируемых) стратегий.

Чистая стратегия первого игрока с номером i д о м и н и -

р у е т чистую стратегию с номером k, если для элементов

платежной матрицы выполняется условие f

≥ f

, j = 1,...,n, и хотя

бы одно неравенство строгое. Тогда говорят, что i-ая стратегия,

доминирует стратегию k-ую, или k-ая стратегия, доминируется

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

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

полняется условие f

≤ f

, i = 1,...,m.

Говорят, что i-я чистая стратегия первого игрока доминиру-

ется л и н е й н о й к о м б и н а ц и е й некоторого подмноже-

ства L других его чистых стратегий, если выполняется условие

284

≤

∑

∈Lk

, j = 1,...,n, L ⊆ {1,..., m}

и хотя бы одно неравенство строгое. Здесь λ

- коэффициенты,

удовлетворяющие условиям

≥0, k∈L;

∑

∈Lk

= 1.

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

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

стратегией, или линейной комбинацией стратегий.

Например, пусть задана платежная матрица в виде

2 5 6 2

F = 8 2 1 5

3 4 2 3

Анализ матрицы F показывает, что 3-я стратегия первого

игрока доминируется линейной комбинацией 1-ой и 2-ой страте-

гий с коэффициентами 2/3 и 1/3; 1-я стратегия второго игрока до-

минируется его 4-ой стратегией, а 2-я стратегия доминируется

линейной комбинацией 3-ей и 4-ой стратегий с коэффициентами

0.75 и 0.25. Тогда игровая модель с платежной матрицей F экви-

валентна модели

с матрицей

6 2

1 5

П р и м е ч а н и е. Сравнивая выражение, записанное при

определении смешанной стратегии, и выражение для линейной

комбинации стратегий, заметим, что элементы смешанной стра-

тегии, по существу, представляют собой коэффициенты линейной

комбинации всех чистых стратегий соответствующего игрока.

Существует следующее утверждение, имеющее важное

прикладное значение.

Утверждение (об активных стратегиях). Выигрыш от ис-

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

против любой активной стратегии или линейной комбинации ак-

тивных стратегий, равен цене игры .

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

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

тивника (даже, если тот применяет оптимальную смешанную

285

стратегию) он не проиграет больше цены игры (может проиграть

меньше). В том случае, если он использует пассивные стратегии,

то проигрыш может быть больше цены игры.

Тогда, если p

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

игрока, то выигрыш первого игрока при использовании p

против

некоторой j-ой чистой стратегии второго игрока вычисляется как

*т

F e

≥ C , (13.20)

где e

- вектор, такой что его компоненты e

=0, i=1,...,n, i≠j, а e

=1.

Утверждение (о числе активных стратегий). В любой мат-

ричной игре с платежной матрицей F размерности (m×n) количе-

ство активных стратегий каждого игрока не превосходит min {m, n}

(наименьшего из чисел m и n).

13.3.3. Методы нахождения оптимальных смешанных

стратегий.

Процедура нахождения оптимальных чистых или смешан-

ных стратегий соответствует выявлению рациональной линии

поведения противников в конфликтной ситуации, описываемой

игровой моделью. Поэтому такую процедуру часто называют

р е ш е н и е м и г р ы (интерпретируя ее как процесс), а пару

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

нием

игры, рассматривая ее как результат.

В качестве п о д г о т о в и т е л ь н о г о этапа при реше-

нии игры рассматривается этап упрощения игры, в ходе которого

выполняется:

- преобразование платежной матрицы к более простому виду;

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

результате преобразования платежная матрица сводится

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

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

1). Если ко всем элементам платежной матрицы добавить не-

которое число P, то решение игры не изменится, но цена игры

увеличится на P.

2). Если все элементы платежной матрицы умножить на неко-

торое число Q, то

решение игры останется тем же, но цена игры

увеличится в Q раз.

Тогда, например, игра с платежной матрицей

286

0.5 0.6 0.9 эквивалентна игре 014

F = 0.7 0.5 0.5 с платежной матрицей F

=200

0.9 0.7 0.8 4 2 3

При этом все элементы F были домножены на 10 и из элементов

полученной матрицы вычли 5, соответственно изменилась и цена

игры. Решение игры осталось прежним - седловая точка (3,2); т.е.

оптимальны 3-я стратегия первого игрока и 2-я стратегия второго

игрока.

Если цену игры, равную 2, подвергнуть обратным преоб-

разованиям (добавить 5 и разделить на 10), то получим исходное

значение цены игры 0.7.

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

линейного программирования.

Пусть задана игра с платежной матрицей F = { f

}, в которой

у первого игрока m чистых стратегий, а у второго игрока n чистых

стратегий. Требуется найти решение игры, т.е. определить опти-

мальные смешанные стратегии игроков.

Приведем игру к виду, когда в платежной матрице содер-

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

вестна оптимальная смешанная стратегия 1-го игрока p=(p

,..

...,p

)

. Тогда, используя утверждение об активных стратегиях

(13.20), можно записать n неравенств вида

F e

≥ C , j = 1,...,n.

Это эквивалентно p

F ≥ C, или F

p ≥ C .

Последние неравенства можно записать в виде

+ f

+ ... + f

≥ C,

+ f

+ ... + f

≥ C,

………...........................…...

+ f

+ ... + f

≥ C.

Т.е. оптимальная смешанная стратегия, примененная про-

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

ны игры. Если стратегия противника активная - выигрыш равен

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

игры.

Разделим правую и левую часть неравенств на С (т.к. эле-

менты платежной матрицы

неотрицательны, то С ≥ 0, и характер

неравенств сохранится); введем обозначения x

= p

/ C, i=1,. ..,m.

Тогда

287

+ f

+ ... + f

≥ 1,

+ f

+ ... + f

≥ 1,

………............................... (13.21)

+ f

+ ... + f

≥ 1,

≥ 0, i = 1,...,m.

Последнее условие следует из того, что p

и C положитель-

ны. Все эти условия задают множество возможных смешанных

стратегий первого игрока. Из этого множества целесообразно вы-

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

вому игроку, или, что одно и то же, стратегию, максимизирующую

цену игры. Рассмотрим для этого линейную форму

L(x) = x

+ x

+ ... + x

. (13.22)

Подставим значения x

= p

/C) и получим,

L(x) = 1/C ( p

+ p

+ ... + p

) = 1/C.

Действительно, сумма p

, i=1,...,m равна 1 ( из определения сме-

шанной стратегии).

Следовательно, минимизируя L(x) на множестве допусти-

мых x, которое задается (13.21), можно найти оптимальную сме-

шанную стратегию p, доставляющую максимум цене игры. В силу

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

решаться методами линейного программирования. Решение этой

задачи всегда существует, т.к. значения F неотрицательны и

ищется минимум

суммы неизвестных переменных.

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

/L, i = 1,...,m; цена игры C = 1/L.

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

дится в результате решения задачи, двойственной к поставлен-

ной задаче. Тогда использование метода обратной матрицы (см.

3.5), позволяющего одновременно получать решения задач двой-

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

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

Метод итераций (Брауна - Роббинсон).

Метод итераций является приближенным методом решения

игровых задач. При большой размерности решаемых задач и в

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

шений, данный метод достаточно эффективен.

Метод представляет собой своеобразную имитацию игры.

Многократно проигрываются партии игры, при этом партнеры по-

288

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

тен предыдущий ход противника. Итак,

1) игра многократно проигрывается;

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

сложившихся условиях чистая стратегия;

3) при оценке условий анализируется суммарный, накоплен-

ный за все предыдущие итерации выигрыш;

4) при выборе стратегии игрок предполагает, что будущее бу-

дет

похоже на прошлое.

В результате проведения ряда итераций относительные

частоты применения чистых стратегий приближенно можно при-

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

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

Итак, пусть 1-ый игрок выбирает некоторую стратегию (на-

пример, гарантирующую, на которой достигается нижняя цена

игры), в этих условиях 2-

ой игрок отвечает ему такой своей стра-

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

сделанного 2-м игроком хода, 1-ый игрок выбирает такую чистую

стратегию, при которой его суммарный выигрыш за все итерации

максимален. Аналогичным образом поступает 2-ой игрок с той

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

денные итерации выигрыш 1-го игрока (свой проигрыш).

Пусть матричная игра задается платежной матрицей F = {f

}

размерности (m×n). Результаты всех итераций записываются в

таблицу вида

Таблица

к i Z

...... Z

j Z

...... Z

Здесь

к - номер итерации (номер розыгрыша партии игры);

i - номер чистой стратегии 1-го игрока, выбранной им на к-ой

итерации;

- суммарный выигрыш 1-го игрока при применении r-ой чис-

той стратегии 2-м игроком на к итерациях при различных страте-

гиях (r) 2-го игрока; r = 1,...,n;

j - номер чистой стратегии 2-го игрока,выбранной им на к-ой

итерации;

- суммарный проигрыш 2-го игрока при применении s-ой

чистой стратегии 1-м игроком на к итерациях при различных стра-

тегиях (s) 1-го игрока; s = 1,...,m;

289

- средний выигрыш 1-го игрока на к итерациях (его суммар-

ный выигрыш деленный на к);

- средний проигрыш 2-го игрока на к итерациях;

С = (С

+ С

) / 2; представляет собой среднюю цену игры.

В результате проведения (к) итераций компоненты опти-

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

частоты появления соответствующих чистых стратегий. Иначе

говоря, оценивается количество появлений в столбцах i и j таб-

лицы чистых стратегий, выбираемых первым и вторым игроком, и

полученные числа делятся на (к).

Особенность итерационного метода заключается

в том,

что, несмотря на довольно медленную сходимость метода, объем

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

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

вания. Кроме того, объем данных, необходимых для запоминания

при реализации метода, растет линейно с ростом размерности

задачи. В этой связи итерационный метод достаточно легко

реа-

лизуется на цифровых вычислительных машинах.

На основании изложенного можно сформулировать после-

довательность действий, которые целесообразно проводить для

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

туаций.

1. На первом этапе перечисляются и изучаются существенные

возможности (альтернативы) по принятию решения, имеющиеся у

каждой из оперирующих сторон.

2. Оцениваются последствия выбора альтернатив

оперирую-

щих сторон. Решение этого вопроса зависит от содержания зада-

чи и представляет известные трудности в определении числен-

ных значений такой оценки. Для этого целесообразно использо-

вать методы экспертного анализа.

3. Составляется платежная матрица игры (матрица эффектив-

ности выбора).

4. Оценивается возможность существования седловой точки

игры. Если седловая точка существует, то выбор

оптимальной

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

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

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

5. Производится упрощение платежной матрицы на основе ис-

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

ному виду (в матрице отсутствуют отрицательные элементы

290

6. На основе использования одного из методов решения игры

находятся смешанные стратегии оперирующих сторон и цена иг-

ры.

7. Заключительный шаг состоит в интерпретации полученных

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

выдаче практических рекомендаций по их применению при при-

нятии решения.

13.4. Принятие решений в условиях неизвестной среды

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

для предположений о том, какие значения будут принимать пара-

метры, характеризующие состояние среды на рассматриваемом

временном интервале. При этом возможно два направления соз-

дания информационной базы для принятия решения.

П е р в о е направление связано с наблюдением за изме-

нением состояний

среды, и затем на основе собранной информа-

ции (статистики) строится вероятностное распределение состоя-

ний среды. После этого возникает возможность использования

методов выбора в условиях стохастической среды. Здесь можно

различать две ситуации: а) имеются достаточные объективные

предпосылки для априорного задания вида закона вероятностно-

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

лить

(на основе сбора и статистической обработки информации)

параметры этого закона (параметрические статистики); б) в ходе

наблюдения за изменением состояний среды необходимо вы-

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

(непараметрические статистики).

При анализе возможностей принятия решения в рамках

данного направления следует учитывать следующее:

1) для сбора и обработки статистики необходим

ресурс време-

ни, который на практике довольно часто отсутствует;

2) изменение состояний среды должно обладать свойством

статистической устойчивости, т.е. состояния повторяются с опре-

деленной частотой в массовых явлениях. Вместе с тем в сложных

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

люди, такое свойство довольно часто не выполняется.

В т о

р о е направление связано с получением экспертной

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