3 Решение матричной игры в смешанных
стратегиях.
Основная теорема теории игр
Итак, если игровая матрица содержит седловую
точку, то решение игры известно. Возникает вопрос нахождения решения для игр,
матрицы которых не содержат седловой точки. В этих
играх a < b. Применение минимаксных стратегий для каждого из
игроков обеспечивает выигрыш, не превращающий a, и
проигрыш, не меньший b. Для
каждого игрока естествен вопрос увеличения выигрыша (уменьшения проигрыша).
Поиски такого решения состоят в том, что игроки применяют не одну, а несколько
стратегий. Выбор стратегий осуществляется случайным образом. Случайный выбор
игроком своих стратегий называется смешанной
стратегией.
В игре, матрица которой имеет размерность
, стратегии игрока А задаются
наборами вероятностей Х = (х1,
х2, … , хm), с которыми
игрок применяет свои первоначальные чистые стратегии. Эти наборы можно рассматривать
как m-мерные
векторы, для компонент которых выполняется условия
(5)
Аналогично для игрока В определяют n-мерные векторы
, соответствующие его смешанным стратегиям. Стратегии игроков А и В, для которых вероятности
и
отличны от нуля, называются
активными.
Выигрыш
игрока А при
использовании смешанных стратегий определяется как математическое ожидание
выигрыша, т. е. равен
или (в
векторно-матричной записи)
.
Существует
так называемая основная теорема теории игр, состоящая в следующем: каждая конечная игра имеет, по крайней мере,
одно решение, возможно, в области смешанных стратегий.
Применение оптимальной стратегии позволяет получить
выигрыш, равный цене игры:
.
Для оптимальных стратегий игроков имеет место
соотношение
(6)
Применение игроком А оптимальной стратегии
должно обеспечивать
ему при любых действиях игрока В
выигрыш не меньше цены игры v. Поэтому
выполняются следующие соотношения:
(7)
Аналогично, для игрока В оптимальная стратегия
должна обеспечивать
при любых стратегиях игрока А
проигрыш, не превышающий величину v, т. е.
справедливо соотношение
(8)
В дальнейшем соотношения (7) и (8) используются для
решения игры.
Вообще, задача решения игры, если её матрица не
содержит седловой точки, тем сложнее, чем больше
значения m и n. Поэтому в теории матричных игр рассматриваются
способы, с помощью которых решение одних игр сводится
к решению других, более простых (в частности, с помощью сокращения размерности
матрицы). Сократить размерность матрицы можно, исключая дублирующие и заведомо
невыгодные доминирующие стратегии.
Дублирующими называются
стратегии, которым соответствуют одинаковые значения элементов в платежной
матрице, т. е. матрица содержит одинаковые строки (столбцы). Если же все
элементы i-й строки матрицы меньше соответствующих элементов k-й строки, то i-я стратегия для игрока А называется
доминирующей.
Если же
элементы r-го столбца
матрицы больше соответствующих элементов j-го столбца,
то для игрока В
стратегия Вr –
доминирующая. Например, в матрице А2 для игрока В заведомо невыгодна четвертая стратегия, так как все значения
превышают соответствующие значения первого и
второго столбца. Четвертый столбец матрицы можно исключить (игрок В никогда не
воспользуется этой стратегией).
Можно
сократить размер матрицы, разбив её на подматрицы, в которых суммы элементов по
столбцам и строкам равны. Тогда вместо чистых стратегий в матрицу включаются смешанные. Элементы матрицы, соответствующие смешанным
стратегиям, получаются делением соответствующих сумм элементов на число чистых
стратегий, объединенных в смешанную.
Рассмотрим матрицу А3, разбитую на четыре
подматрицы, для которых выполняется условие равенства сумм элементов по строкам
и столбцам:
.
Объединяя стратегии А1, А2 и А3, А4 и А3,
В1 и В2, В3
и В4, приводим матрицу к
виду
.
Полученная матрица содержит седловую
точку. Поэтому решение первоначальной игры, заданной матрицей А3,
таково: Х* = (1/3; 1/3; 1/3; 0; 0), Y* = (1/2; 1/2;
0; 0). Цена игры равна единице. В результате упрощения игры решение ее стало
очевидным.
Оптимальной для игрока А является комбинация стратегий А1, А3 и А3, а для игрока В – комбинация стратегий В1 и В2. Вероятности применения стратегий А1, А2
и А3 равны между собой,
сумма их равна 1, поэтому Х* = (1/3; 1/3; 1/3; 0; 0). Аналогично,
оптимальная стратегия игрока В имеет вид Y* =(1/2;
1/2; 0; 0).
Таким образом, при решении игры
следует:
а) проверить, не содержит ли матрица седловой точки;
б) если седловой
точки нет, то нужно сравнить между собой элементы строк и столбцов для
исключения дублирующих и доминирующих стратегий;
в) рассмотреть возможность разбиения
матрицы на подматрицы для замены некоторых групп чистых стратегий смешанными.
Наиболее простая матричная игра – это игра,
в которой каждый из игроков имеет две стратегии. Матрица А игры имеет вид
.
Если седловой точки нет, то
решением игры являются смешанные стратегии
,
.
Согласно основной теореме теории игр, применение
оптимальной стратегии
обеспечивает для
игрока А получение выигрыша v при любых стратегиях игрока В. Поэтому, если игрок А применяет свою оптимальную стратегию,
то при этом игрок В может
использовать одну из чистых стратегий, величина выигрыша игрока А останется неизменной. Запишем систему
уравнений
(4.9)
Так как
, то решение таково
,
. (4.10)
Подставляя
значения
и
в одно из уравнений (4.8),
получаем
. (4.11)
Составляя аналогичную систему уравнений, можно найти
оптимальную стратегию для игрока В:
,
. (4.12)
Пример 2 Найти решение игры, заданной матрицей
.
Решение. Имеем
; матрица не имеет седловой точки.
По формулам (4.10)-(4.12) находим оптимальные стратегии и цену игры:
.