книги / Математические методы принятия решений

по одной оси координат и точкой максимума по другой оси, называ­ ют седловой точкой. Соответствующий элемент а^- = а (или = Р) платежной матрицы игры называют седловой точкой (седловым эле­ ментом) матрицы. О такой игре говорят, что она имеет седловую точку. В этой ситуации каждый из игроков должен придерживаться максиминной (минимаксной) стратегии. Любое отклонение от этой стратегии будет невыгодно для игрока, допустившего отклонение. Если игра не имеет седловой точки (см. табл. 4.7), то ни одна из стратегий Ai или Bj не является оптимальной. Рассмотренные стратегии игроков А и В называют чистъши. Чистые стратегии не дают устойчивости решения.

Пример. Рассмотрим некоторую матричную игру размерностью 3 x 3 , платежная матрица которой приведена в табл. 4.8. Здесь мак-

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

§ 4.7. Поиск оптимальной смешанной стратегии

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

Введем обозначения X i= pi/v, i = 1,2, ... , т, и перепишем со­ отношения (4.5), (4.6) в виде

Цена игры v должна быть как можно больше, следовательно, ве­ личина 1/v должна быть как можно меньше. Таким образом, поиск оптимальной смешанной стратегии свелся к решению задачи ли­ нейного программирования: найти неотрицательные величины

i = 1,2.....т, такие, чтобы они удовлетворяли неравенствам (4.7),

(4.8) и при этом обращали в минимум сумму (целевую функ-

771

цию) 2 x i- Сформулируем следующую теорему. г=1

Теорема. Чтобы стратегия (р*, q*) была оптимальной, необ­ ходимо и достаточно выполнения неравенств

771

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

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

§4.8. Решение матричных игр размерностью т х п

Впроцедуре решения матричных игр можно выделить следую­ щие этапы.

I. Необходимо проверить, существует ли седловая точка в пла­ тежной матрице игры. Если седловая точка есть, то оптимальное

1

не проиграет больше v при любой чистой стратегии игрока А, при оптимальной стратегии игрока А проигрыш игрока В равен v. Сформулируем данную задачу как задачу линейного программиро-

стратегия должна обеспечить ему выигрыш не менее v при любой стратегии игрока В и равный v при оптимальной стратегии игро­ ка В . Из необходимого и достаточного условий следует

771

Xi = Pi/v и перейдем к задаче ЛП:

772

^хг min;

2=1

Решаем эту задачу также симплекс-методом.

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

Общий метод решения матричных игр размерностью т х п — сведение их к задачам ЛП — не всегда оказывается самым про­ стым. В ряде случаев, особенно при малой размерности задач, удается решить игру более простыми методами, если заранее опре­ делить, какие стратегии являются активными. Например, для случая полностью усредненной игры с квадратной матрицей ( т = п) нера­ венства (4.7) преобразуются в равенства, т. е. получаем системы т линейных уравнений с т неизвестными х* или у* соответствен­ но, i = 1,2, ... ,m . Решая их, найдем положительные значения х* или yi, цену игры v и вероятности Pi в оптимальной смешан­ ной стратегии S^: Pi = vx*, i = 1,2, ... , m. Так, в данном примере, заменив неравенства на равенства, можно непосредственно полу­ чить 2 д* + 5^2 = v.

В смешанных стратегиях матричных игр размерностью т х п могут присутствовать стратегии с вероятностью, равной нулю. Чис­ ло активных стратегий в таком случае не превосходит m in {т ;п}. Оптимальная стратегия находится с помощью решения соответ­ ствующей системы уравнений. Пусть вектор р содержит г вероятно­ стей, отличных от нуля, а вектор q содержит s таких вероятностей;

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

Наиболее просто смешанная оптимальная стратегия находится

Пусть игрок В использует стратегию В \, тогда цена игры бу­

можно дать геометрическую интерпретацию. Рассмотрим решение игры с платежной матрицей размерностью 2 х п, т. е.

Диаграмма для цены игры размерностью 2 х 2 с позиции игро­ ка А представлена на рис. 4.15.

По оси абсцисс отложим отрезок длиной, равной единице. Ле­ вый край с координатой, равной нулю, будет отражать страте­ гию правый — стратегию А 2. На вертикальных линиях, выхо­ дящих из нуля и единицы, будем откладывать выигрыши игрока А при стратегиях В\ и В 2 игрока В, т. е. на левой линии отложим значения оц и 012, на правой— <221 и а 22. Точки на вертикальных линиях, соответствующие одной из стратегий B j , j = 1,2, соединим

Рис. 4.15. Диаграмма матричной игры размерностью 2 x 2 с позиции игрока А

прямыми линиями—линиями выигрыша. В большинстве случаев эти прямые пересекаются в точке N . Абсцисса точки N делит еди­ ничный отрезок пропорционально вероятностям р\ и р 2,ъ ордината точки N —это цена игры v. На диаграмме отмечены а и (3 — нижняя и верхняя цены игры. Поскольку стратегия вд требует, чтобы ми­ нимальный выигрыш игрока А обращался в максимум, то строим нижнюю границу выигрыша, отмеченную жирной линией. Линии выигрыша могут не пересекаться. Это значит, что игрок В имеет заведомо невыгодную стратегию. Однако если игрок А имеет одну заведомо выгодную стратегию, то формальный анализ пересечения линий выигрыша может привести к ошибке. Чтобы избежать ошиб­ ки, необходимо предварительно исключить заведомо невыгодные стратегии игрока А.

Для игрока В цена игры определяется следующим образом:

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

Рис. 4.16. Диаграмма матричной игры размерностью 2 x 2 с позиции игрока В

Поскольку любая конечная игра размерностью т х п имеет решение, в котором число активных стратегий каждой стороны не превосходит наименьшего из чисел т и п , то игра размерностью 2 х п всегда имеет решение, при котором с каждой стороны участ­ вует не более двух активных стратегий. Поэтому для решения игры размерностью 2 х п строится геометрическая интерпретация игры и ищется пара стратегий, пересекающихся в точке N (рис. 4.17). Если в точке N пересекаются больше двух стратегий, то берется из них любая пара и ищется максимум на нижней границе выиг­ рыша.

Рис. 4.17. Диаграмма матричной игры размерностью 2 х п

Для игры размерностью m х 2 строится такая же диаграмма, в шторой ищется минимум на верхней границе выигрыша.

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