3. Методы решения матричных игр
3.1. Графический метод решения
Рассмотрим графический метод нахождения решений игры. Этот метод очень просто применять к играм, имеющим матрицы 2хn или mх2. Его можно также применять к играм, имеющим матрицы 3хn и mх3, но он не пригоден для матриц mxn, когда m и n больше 3.
Поясним этот метод на примере решения игр 2хn [7].
Пример 3.1. Рассмотрим платежную игру с матрицей
Здесь игрок I имеет две чистые стратегии (по строкам), а игрок II три чистые стратегии (по столбцам). Если игрок I применяет смешанную стратегию, а игрок II – свою первую чистую, то ожидаемый платеж игроку I будет
Аналогично, если игрок II применит свою чистую стратегию II? То ожидаемый платеж игроку I равен
,
а если игрок II применит чистую стратегию 3 , то ожидаемый платеж игроку I равен
.
Проведем три прямые, соответствующие этим платежам.
При каждом выборе игроком I стратегии x он может быть уверен, что получит по крайней мере наименьшую из ординат трёх прямых, соответствующих x.
Таким образом, для игрока I выбрать оптимальное x – это значит выбрать такое х, при котором наименьшая из трех ординат возможно больше. Следовательно, цена игры в приведенном примере находится следующим образом: берём максимальную ординату выпуклого множества, которое ограничено сверху прямыми линиями. Такой же способ применяется для любой игры с матрицей порядка 2хn. Для игры с матрицей порядка mх2 графическое построение аналогично, но в этом случае цена игры равна минимальной ординате выпуклого множества, ограниченного снизу прямыми линиями. Мы можем в этом частном случае найти оптимальную стратегию игрока I (на рисунке видно, что игрок имеет только одну оптимальную стратегию) и цену игры, решив совместно уравнения
Проделав вычисления, мы находим, что оптимальная стратегия игрока I и цена игры равна . Дале , из рисунка видно, что первая стратегия игрока II не войдет в его оптимальную смешанную стратегию. Значит оптимальную смешанную стратегию игрока II мы можем найти из матрицы
.
Отсюда находим, что оптимальная стратегия игрока II равна .
В случае, если игрок имеет много оптимальных стратегий (на рисунке это выразится в том, что один из графиков будет параллелен оси) это будет естественное обобщение отрезка прямой на плоскости. Тогда оптимальной стратегией будет любая пара, принадлежащая этому отрезку.
Таким образом, найдено графическое решение 2х3 игры.
3.2. Прямое решение
Вообще, любую матричную игру можно решить путём решения системы неравенств. Но с увеличением числа чистых стратегий игроков размерность растет, а следовательно, значительно увеличивается и объем вычислений. Поэтому, в первую очередь следует уменьшить размерность матрицы, исключив строго доминируемые стратегии. Затем следует проверить выполнение равенства минимаксов. Если равенство минимаксов выполняется, то это означает, что игроки имеют чистые оптимальные стратегии (наличие седловой точки в чистых стратегиях). Игрок I здесь имеет чистую максиминную, а игрок II чистую минимаксную стратегию.
В противном случае хотя бы у одного игрока оптимальные стратегии будут смешанными.
Рассмотрим пример
Пример 3.2. [1] Пусть Г = <х, у, Н> где х={1,2,3,4}, у={1,2,3,4},а функция выигрыша Н задана следующим образом:
,
где с > 0.
Прежде всего заметим, что достаточно решить игру Г1 =<х, у, Н1> , где Н1 = Н/с. В матричной форме игра Г1 определяется матрицей выигрышей
Элементы четвертой строки этой матрицы не больше соответствующих элементов третьей строки, и поэтому третья стратегия игрока I доминирует четвертую. Кроме того, элементы первого столбца матрицы Н1 не меньше соответствующих элементов второго столбца. Следовательно, вторая стратегия игрока II доминирует его первую стратегию.
Далее, можно утверждать (раздел 2.7), что всякое решение игры Г2 = <х \{4}, y \{1}, H1) является решением игры Г1. В матричной форме игру Г2 можно представить матрицей
,
в которой i-й строке матрицы соответствует i-я стратегия, а j-му столбцу — j + 1-я стратегия. Очевидно, что элементы второй строки этой матрицы не меньше полусуммы соответствующих элементов первой и третьей строк. Следовательно, вторая стратегия игрока II доминируется смешанной стратегией, которая с равными вероятностями использует первую и вторую стратегии этого игрока. Кроме того, элементы третьего столбца матрицы H2 не меньше соответствующих элементов второго столбца. Это значит, что стратегия под номером 3 доминирует стратегию под номером 4. Всякое решение игры Г3 = <x\{4, 2}, y\{1,4}, H2> является решением игры Г2, а значит, и игры Г1.
Игра Г3 определяется матрицей:
в которой первая строка соответствует стратегии под номером 1, вторая — стратегии под номером 3 первоначальной игры, а второй и третий столбцы соответствуют стратегиям 2 и 3 первоначальной игры. Матрица H3 не имеет седловой точки, так как не выполнено равенство минимаксов, а игра Г3 не имеет решения в чистых стратегиях, т. е. оптимальные стратегии игроков являются смешанными. Эти стратегии легко найти из анализа структуры матрицы H3. Поскольку матрица H3 симметрична, можно предположить, что игроки в оптимальной стратегии используют свои чистые стратегии с равными вероятностями.
Действительно, если игрок I применяет стратегию, смешивающую с равными вероятностями первую и вторую строки матрицы игры Г3, или (что то же самое) выбирает с равными вероятностями стратегии 1 и 3, то при применении любой из двух чистых стратегий игроком II математическое ожидание выигрыша игрока I будет равно либо (1/2)1+ (1/2)2 = 3/2, либо (1/2)2 +(1/2)1 =3/2. Аналогично, если игрок II использует свои чистые стратегии 2 и 3 с равными вероятностями, то математическое ожидание его проигрыша будет равно 3/2. Следовательно, указанные стратегии являются оптимальными в игре Г3, а величина 3/2 — значением игры Г3. Из предыдущего следует, что эти стратегии оптимальны и в Г1.
Таким образом, стратегия X* = (1/2, 0, 1/2, 0) является оптимальной стратегией игрока I, стратегия У* = (0, 1/2, 1/2, 0)—оптимальной стратегией игрока II в игре Г1, а значение игры Г1 равно 3/2. В силу теоремы 1.11 решением игры Г будет тройка (X*, У*, Зс/2).
При решении примера нам пришлось столкнуться с решением 2 X 2-игры. Сначала мы догадались, как выглядит решение, а потом проверили, что оно действительно является решением. Оказывается любую 2 X 2-игру можно решить по следующей стандартной схеме.
В общем виде 2 X 2-игра определяется матрицей
Прежде всего, необходимо проверить выполнение равенства минимаксов. Если оно выполняется, то игра имеет решение в чистых стратегиях, причем оптимальными стратегиями игроков I и II соответственно будут чистая максиминная и чистая минимаксная стратегии. Если же игра с матрицей выигрышей H не имеет решения в чистых стратегиях, то оба игрока имеют лишь такие оптимальные стратегии, которые используют все свои чистые стратегии с положительными вероятностями. Действительно, в противном случае один из игроков (скажем, игрок I) имеет чистую оптимальную стратегию, а другой — только смешанные. Не ограничивая общности, можно считать, что оптимальной стратегией игрока I является выбор с вероятностью единица первой строки. Далее h11= hl2 = v и матрица имеет вид:
Легко видеть, что для матриц такого вида одна из стратегий игрока II является доминируемой. Следовательно, по теореме 1.11 этот игрок имеет чистую оптимальную стратегию, что противоречит предположению.
Пусть Х* = - оптимальная стратегия игрока I. Так как игрок II имеет смешанную оптимальную стратегию, то получим H(X*t j) = v, j = 1, 2, или, в подробной записи,
(3.1)
Отсюда следует, что при v 0 столбцы матрицы H не могут быть пропорциональны с коэффициентом пропорциональности, отличным от единицы. Если же коэффициент пропорциональности равен единице, то матрица Н принимает вид
и игрок I имеет чистую оптимальную стратегию (он выбирает с вероятностью единица ту из строк, элементы которой не меньше соответствующих элементов другой), что противоречит предположению. Следовательно, если v 0 и игроки имеют только смешанные оптимальные стратегии, то определитель матрицы Н отличен от нуля. Из этого следует, что система уравнений (3.1) имеет единственное решение. Решая ее, находим
(3.2)
Аналогичные рассуждения приводят иле к тому, что оптимальная стратегия игрока II Y * = (*, 1 - *) удовлетворяет системе уравнений:
(3.3)
откуда (3.4)
Таким образом, для решения матричной 2 Х 2-игры необходимо сначала проверить равенство минимаксов, и если оно выполняется, то игроки имеют чистые оптимальные стратегии (игрок I — чистую максиминную, а игрок II — чистую минимаксную). В противном случае следует по формулам (3.2) и (3.3) найти значения, оптимальные стратегии игроков.
В некоторых случаях, когда игра имеет решение в смешанных стратегиях, из анализа структуры матрицы выигрышей можно получить некоторое представление о тех чистых стратегиях, которые должны применяться с положительной вероятностью. Другими словами, иногда можно угадать подмножества х° и у0 чистых стратегий, а затем решить систему:
H(X,j) = v, , (3.5)
H(i, Y) = v,
Если решение системы (3.5) удовлетворяет условиям равновесности ситуации, то оно является искомым решением игры Г. В противном случае можно последовательно перебирать подмножества х° и у0, решая соответствующие системы и проверяя каждое решение до тех пор, пока не будет получено решение исходной игры Г. Кроме того, можно ограничиться подмножествами, имеющими равное число элементов, то есть в матричной записи перебрать квадратные подматрицы матрицы выигрышей. Можно показать, что в этом случае обязательно при каких-нибудь х° и у0, имеющих по одинаковому числу элементов, решение системы (3.5) будет единственно и является решением игры Г = <х, у. Н>. Выше мы показали это для 2 X 2-игр.
Напомним, что рассмотренный метод непосредственного (прямого) решения годится лишь для игр небольшого размера и для игр, которые сводятся к таковым отбрасыванием доминируемых стратегий, либо для игр, которые имеют некоторую обозримую аналитическую структуру и для которых можно угадать спектр оптимальных стратегий. Поэтому если игра сложная, то лучше всего для ее решения воспользоваться численными методами линейного программирования (например, симплекс-методом).