5580

Полученная матрица содержит седловую точку

α = β = 1 = а11.

Поэтому решение первоначальной игры, заданной матрицей P3,

Оптимальной для игрока А является комбинация стратегий А1, А2, А3, а для игрока В – комбинация стратегий В1 и В2. Вероятность применения стратегий А1, А2 и А3 равны между собой (Σ рi = 1). Аналогично для второго игрока, Σ qj = 1.

Рассмотрим простейший случай конечной игры 2х2, в которой каждый игрок имеет две стратегии. Платёжная матрица игры

Ра11 а12 . Если такая игра имеет седловую точку, то оптимальное

а21 а22

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

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

S*A , то его средний выигрыш будет равен цене игры v при любой активной стратегии игрока В. Для игры 2х2 любая чистая стратегия противника является активной, если отсутствует седловая точка. Выигрыш игрока А (проигрыш игрока В) – случайная величина, математическое ожидание (среднее значение) которой является ценой игры. Поэтому средний выигрыш игрока А (оптимальная смешанная стратегия) будет равен v и для первой и для второй стратегий.

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

91

(это соответствует первому столбцу матрицы Р), равен цене игры v:

Решая эту систему, получим оптимальную стратегию

седловой точки. По формулам (7.8 – 7.11) находим оптимальные стратегии и цену игры:

92

7.4 Геометрическая интерпретация игр 2х2

Игру 2х2 можно решить графическим методом.

На оси абсцисс (рисунок 7.1) отложим единичный отрезок А1А2. Точка А1 (х = 0) изображает стратегию А1, а все промежуточные точки этого отрезка – смешанные стратегии SA первого игрока, причём расстояние от SA до правого конца отрезка – это вероятность р1 стратегии А1, расстояние до левого конца – вероятность р2 стратегии А2.

На перпендикулярных осях I – I и II – II откладываем выигрыш при стратегиях А1 и А2 соответственно. Если 2-й игрок примет стратегию В1, то она даёт выигрыш а11 и а21 на осях I – I и II – II, соответствующие стратегиям А1 и А2. Обозначим эти точки на осях I – I и II – II буквой В1. Средний выигрыш v1, соответствующий смешанной стратегии SA, определяется по формуле математического ожидания v1 а11 р1 а21 р2 и равен ординате точке М, которая лежит на отрезке В1В1 и имеет абсциссу SA (рисунок 7.1).

93

v2 a12 p1 a22 p2 – ордината точки М2.

В соответствии с принципом минимакса оптимальная стратегия S*A такова, что минимальный выигрыш игрока А (при наихудшем поведении игрока В) обращается в максимум. Ординаты точек, лежащих на ломаной (рис. 7.3), показывают минимальный выигрыш игрока А при использовании им любой смешанной стратегии (на участке B1N – против стратегии B1, на участке NB2 – против стратегии В2). Оптимальную стратегию S*A ( p1*, p2* ) определяет точка N, в которой минимальный выигрыш достигает максимума. Её ордината равна цене игры v. На рисунке 7.3 обозначены также верхняя и нижняя цены игры α и β.

Решение. Откладываем на оси абсцисс (рисунок 7.4) единичный отрезок А1А2. На вертикальной оси I – I откладываем отрезки a11 = 1,5, соответствующий стратегии В1, и а12 = 3, соответствующий стратегии В2. На вертикальной оси II – II отрезок а21 = 2, соответствующий стратегии В1, отрезок а22 = 1 соответствует стратегии В2. Нижняя цена игры α = а11 = 1,5. Верхняя цена игры β = а21 = 2, седловая точка отсутствует. Из рисунка 7.4 видно, что абсцисса точки N определяет оптимальную стратегию S*A , а ордината – цену игры v. Точка N является точкой пересечения прямых В1В1 и В2В2.

Уравнение прямой В1В1, проходящей через точки (0; 1,5) и (1; 2):

94

Уравнение прямой В2В2, проходящей через точки (0; 3) и (1; 1):

Точка пересечения прямых является решением системы

или х = 0,6, у = 1,8, т.е. N(0,6; 1,8).

Таким образом, р1* = 0,6, р2* = 1 – 0,6 = 0,4, оптимальная стратегия

SА* = (0,6; 0,4), цена игры v = 1,8.

Геометрически можно также определить оптимальную стратегию игрока В, если поменять местами игроков А и В и вместо максимума

Абсцисса точки М определяет q2* в оптимальной стратегии игрока В, ордината этой точки – цена игры. Прямая А1А1, проходящая через точки (0; 1,5) и (1; 3) удовлетворяет уравнению у = 1,5х + 1,5.

Прямая А2А2, проходящая через точки (0; 2) и (1; 1), удовлетворяет уравнению у = – х + 2. Координаты точки пересечения М являются решением системы уравнений

у 1,5х 1,5,

у х 2.

95

Решив систему, получаем х=0,2; у= 1,8, т.е. q2* = 0,2; q1* = 1 – q2*=0,8,

υ = у = 1,8, SВ* = (0,8; 0,2).

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

Если платёжная матрица содержит отрицательные числа, то для графического решения задачи нужно перейти к новой матрице с неотрицательными элементами; для этого к элементам исходной матрицы достаточно добавить соответствующее положительное число. Решение игры при этом не изменится, а цена игры увеличится на это число. В примере 7.4 платёжная матрица не имела седловой точки (α ≠ β). При наличии седловой точки графическое решение дают варианты, изображённые на рисунках 7.6 и 7.7.

На рисунке 7.6 наибольшей ординатой на ломаной B1NB2 обладает точка B2, поэтому оптимальной стратегий является чистая стратегия А2 для игрока А (B2 – для игрока В), т.е. оптимальное решение: SА* = (0; 1), SВ* = (0; 1). Игра имеет седловую точку а22 = v.

Чистая стратегия B2 (рисунок 7.7) не выгодна для игрока В, поскольку при любой стратегии игрока А она даёт последнему больший выигрыш, чем чистая стратегия B1. На основании принципа минимакса выделим прямую B1B1 и на ней точку B1 с наибольшей ординатой на оси I – I.

96

Чистая стратегия А2 является оптимальной для игрока А, а чистая стратегия игрока B1 – для игрока В. Оптимальное решение: SА* = (0; 1), SВ* = (1; 0), цена игры v = а21 = α = β, т.е. имеется седловая точка.

Графический метод можно применять при решении игры 2хn и mx2.

7.5 Приведение матричной игры к задаче линейного программирования

Пусть игра задана платёжной матрицей Р размером m x n:

Матрица Р не имеет седловой точки, поэтому решение игры представлено в смешанных стратегиях.

Игрок А обладает стратегиями А1, А2, ..., Аm, игрок В – стратегиями В1, В2, ..., Вn. Необходимо определить оптимальные стратегии SА*=(р1*, р2*, ..., рm*) и SВ*=(q1*, q2*, ..., qn*), где рi*, qj* – вероятность применения соответствующих чистых стратегий Аi, Вj, причём

р1* + р2* + ... + рm* = 1, q1* + q2* + qn* = 1.

Оптимальная стратегия SА* удовлетворяет следующему требованию. Она обеспечивает игроку А средний выигрыш, не меньший, чем цена игры, при любой стратегии игрока В и выигрыш, равный цене игры v, при оптимальной стратегии игрока В. Величина v (цена игры) неизвестна. Будем считать v > 0, этого можно добиться, прибавляя ко всем элементам матрицы некоторое положительное число. Если игрок А применяет смешанную стратегию SА* = (р1*, р2*, ..., рm*) против любой чистой стратегии Вj игрока В,

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

аj = a1j p1 + a2j p2+ … + amj pm, j 1, n .

Для оптимальной стратегии SА* все средние выигрыши не меньше цены игры, поэтому получаем систему неравенств:

97

поэтому задача может быть сформулирована следующим образом:

обращалась в минимум. Это задача линейного программирования. Решая задачу (7.13) – (7.14), получаем оптимальные значения хi* и величину 1v ,

затем находим рi* = v ∙ хi* и оптимальную стратегию SА* = (р1*, р2*, ..., рm*). Для определения оптимальной стратегии SВ*=(q1*, q2*, ..., qn*) игрок В

стремится минимизировать гарантированный выигрыш, т.е. найти max 1v .

Переменные q1, q2, ..., qn удовлетворяют неравенствам

98

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

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

Пример 7.5. Предприятие может выпускать три вида продукции (А1, А2 и А3), получая при этом прибыль, зависящую от спроса, который может быть в одном из четырёх состояний (В1, В2, В3, В4). Дана матрица (таблица 7.4), её элементы aij характеризуют прибыль, которую получит предприятие при выпуске i-й продукции с j-м состоянием спроса.

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

99

Решение. Задача сводится к игровой модели, в которой игра предприятия А против спроса В задана платёжной матрицей (таблица 7.4). Таблица 7.4 – Платёжная матрица

Определим нижнюю и верхнюю цены игры: α = max(2, 3, 1) = 3, β = min(4, 5, 6, 5) = 4. Так как α ≠ β, то матрица не имеет седловой точки и оптимальное решение следует искать в смешанных стратегиях игроков

Решим каноническую задачу симплексным методом в симплексных таблицах (таблица 7.5).

100