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) находим оптимальные стратегии и цену игры:

  .