Методы решения матричных игр

 

х1

 

Х

 

1

 

N

 

0

 

v

 

К

 

а22

 

а21

 

а12

 

а11

 

В2

 

В2

 

В1

 

В1

 

х2

 

a = max (1,1) = 1, b = min (3,2) = 2, a ¹ b, . Игра не имеет седловой точки. Оптимальное решение следует искать в области смешанных стратегий. Построим на плоскости отрезки, соответствующие стратегиям второго игрока (см. рис.3)

 

Рисунок 3. Графическое описание задачи

 

По формулам (1) –  (3) находим  оптимальные стратегии и цену игры:

x₁ = 1/3, x₂ = 2/3; y₁ = 2/3, y₂ = 1/3; v =5/3.

Ответ. Оптимальные смешанные стратегии игроков (1/3, 2/3) и (2/3, 1/3), цена игры составляет v =5/3.

Данный ответ означает следующее:

• если первый игрок с вероятностью 1/3 будет применять первую стратегию и с вероятностью 2/3 вторую, то при достаточно большом количестве игр с данной матрицей его выигрыш в среднем составит не менее 5/3;
• если второй игрок с вероятностью 2/3 будет применять первую стратегию и с вероятностью 1/3 вторую, то при достаточно большом количестве игр с данной матрицей его проигрыш в среднем составит не более 5/3.

Второй случай. Рассмотрим игру (2 ´ n) с матрицей

 

.

 

Для каждой из n стратегий игрока В строится соответствующий ей отрезок на плоскости. Находится нижняя граница выигрыша, получаемого игроком А, и определяется точка на нижней границе, соответствующая наибольшему выигрышу. Выделяются две активные стратегии игрока В, отрезки которых проходят через данную точку. Далее рассматриваются только эти две стратегии игрока В. Игра сводится к игре с матрицей (2 ´ 2). Оптимальные стратегии и цену игры находят по формулам (1) – (3).

Пример 2. Найти решение игры, заданной матрицей

 

.

a = max (1,1) = 1, b = min (4, 3, 3,4) = 3, a ¹ b, .

 

Игра не имеет седловой точки. Оптимальное решение следует  искать в области смешанных стратегий. Построим на плоскости отрезки, соответствующие стратегиям второго игрока (см. рис.4).

х3

 

Х

 

1

 

О

 

v

 

К

 

В2

 

В4

 

В1

 

В1

 

х4

 

В4

 

В2

 

В3

 

В3

 

Рисунок 4. Графическое описание задачи

 

Нижней границей выигрыша для игрока А является ломаная В₃КВ₄. Стратегии В₃ и В₄ являются активными стратегиями игрока В. Точка их пересечения К определяет оптимальные стратегии игроков и цену игры. Второму игроку невыгодно применять стратегии В₁ и В₂, поэтому вероятность их применения равна нулю, т.е. у₁ = у₂= 0. Решение игры сводится к решению игры с матрицей (2 ´ 2)

 

.

a = max (1,1) = 1, b = min (3,4) = 3, a ¹ b, .

 

По формулам (1) –  (3) находим  оптимальные стратегии и цену игры:

 

x₁ = 2/5, x₂ = 3/5; y₃ = 3/5, y₂ = 2/5; v =11/5.

 

Ответ. Оптимальные смешанные стратегии игроков (2/5, 3/5) и (0, 0, 3/5, 2/5), цена игры составляет v =11/5.

Данный ответ означает следующее:

если первый игрок с  вероятностью 2/5 будет применять  первую стратегию и с вероятностью 3/5 вторую, то при достаточно большом  количестве игр с данной матрицей его выигрыш в среднем составит не менее 11/5;

если второй игрок с  вероятностью 3/5 будет применять  третью стратегию, с вероятностью 2/5 четвертую и не будет использовать первую и вторую стратегии, то при  достаточно большом количестве игр  с данной матрицей его проигрыш в  среднем составит не более 11/5.

Третий случай. Рассмотрим игру (m ´ 2) с матрицей

 

.

 

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

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

Далее рассматриваются только эти две стратегии игрока А. Игра сводится к игре с матрицей (2 ´ 2). Оптимальные стратегии и цену игры находят по формулам (1) – (3).

Пример 3. Найти решение игры, заданной матрицей

 

.

 

a = max (3, 2, 0, -1) = 3, b = min (4,6) = 4, a ¹ b, . Игра не имеет седловой точки. Оптимальное решение следует искать в области смешанных стратегий. Построим на плоскости отрезки, соответствующие стратегиям первого игрока(см. рис.5).

 

 

v

 

1

 

y2

 

y1

 

О

 

Y

 

А4

 

А4

 

А3

 

А3

 

А2

 

А2

 

А1

 

А1

 

K

 

Рисунок 5. Графическое описание задачи

 

Верхней границей проигрыша  для игрока В является ломаная А₁КА₄. Стратегии А₁ и А₄ являются активными стратегиями игрока А. Точка их пересечения К определяет оптимальные стратегии игроков и цену игры. Первому игроку невыгодно применять стратегии А₂ и А₃, поэтому вероятность их применения равна нулю, т.е. x₂ = x₃= 0. Решение игры сводится к решению игры с матрицей (2 ´ 2)

 

.

a = max (3, – 1) = 3, b = min (4,6) = 4, a ¹ b, .

 

По формулам (1) –  (3) находим  оптимальные стратегии и цену игры:

x₁ = 7/8, x₄ = 1/8; y₁ = 3/8, y₂ = 5/8; v =27/8.

Ответ. Оптимальные смешанные стратегии игроков (7/8, 0, 0, 1/8) и (3/8, 5/8), цена игры составляет v =27/8.

Данный ответ означает следующее:

если первый игрок с  вероятностью 7/8 будет применять  первую стратегию, с вероятностью 1/8 четвертую и не будет использовать вторую и третью стратегии, то при достаточно большом количестве игр с данной матрицей его выигрыш в среднем составит не менее 27/8;

если второй игрок с  вероятностью 3/8 будет применять  первую стратегию и с вероятностью 5/8 вторую, то при достаточно большом  количестве игр с данной матрицей его проигрыш в среднем составит не более 27/8.

 

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

 

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

 

.

 

Если платежная матрица  не имеет седловой точки, т.е. a <b и , то решение игры представлено в смешанных стратегиях (x₁, x₂,..., x_m) и (y₁, y₂,..., y_n). Применение первым игроком оптимальной стратегии _опт должно обеспечить ему при любых действиях второго игрока выигрыш не меньше цены игры:

 

, .

 

Рассмотрим задачу отыскания оптимальной стратегии игрока А, для которой имеют место ограничения:

 

 

Величина v неизвестна, однако можно считать, что цена игры v > 0. Последнее условие выполняется всегда, если все элементы платежной матрицы неотрицательны, а этого можно достигнуть, прибавив ко всем элементам матрицы некоторое положительное число.

Преобразуем систему ограничений, разделив все члены неравенств на v.

 

                                 (1)

 

где         

, .                                       (2)

 

По условию x₁ + x₂ + … +x_m = 1.

Разделим обе части  этого равенства на v:

 

.

 

Оптимальная стратегия  (x₁, x₂,..., x_m) игрока А должна максимизировать величину v, следовательно, функция

 

                                                  (3)

 

должна принимать минимальное  значение.

Таким образом, получена задача линейного программирования: найти  минимум целевой функции (3) при  ограничениях (1), причем на переменные наложено условие неотрицательности (2). Решая ее, находим значения , и величину 1/v, затем отыскиваются значения x_i = vt_i.

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

 

, .

 

Рассмотрим задачу отыскания  оптимальной стратегии игрока B, для которой имеют место ограничения

 

 

Преобразуем систему ограничений, разделив все члены неравенств на v.

 

                                   (4)

 

 где 

 

,                                                (5)

 

По условию y₁ + y₂ + … +y_n = 1. Разделим обе части этого равенства на v

 

.

 

Оптимальная стратегия  (y₁, y₂,..., y_n) игрока В должна минимизировать величину v, следовательно, функция

 

                                             (6)

 

должна принимать максимальное значение.

Получена задача линейного программирования: найти максимум целевой функции (6) при ограничениях (4), причем на переменные наложено условие неотрицательности (5).

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

Пример. Найти решение  игры, заданной матрицей

 

.

 

a = max (2, 3,1) = 3, b = min (4, 5, 6,5) = 4, a ¹ b, .

Игра не имеет седловой точки. Оптимальное решение следует  искать в области смешанных стратегий.

Для определения оптимальной  стратегии игрока А имеем следующую  задачу линейного программирования:

,

, .

 

Для нахождения оптимальной  стратегии игрока В имеем следующую задачу линейного программирования: