Решение матричных игр в смешанных стратегиях - Элементы теории игр в задачах оптимального управления экономическими процессами

Рассмотрим конечные матричные игры, в которых нет седловой точки, т. е. .

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

(48)

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

Рассмотрим матричную игру, заданную таблицей 6.

Таблица 6

Через и обозначим соответственно вероятности (относительные частоты), согласно которым игроки А и В выбирают стратегии и.

Очевидно, что

, , , .

Упорядоченные множества и полностью определяет характер игры игроков А и В и называются их смешанными стратегиями. Отметим, что любая их чистая стратегия и может быть описана как смешанная. Действительно, или.

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

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

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

Функцию называют платежной функцией игры с заданной матрицей. Как и выше, введем понятие нижней и верхней цены игры, сохраняя при этом обозначения и :

, .

Оптимальными смешанными стратегиями и называют такие стратегии, при которых. Величину называют Ценой игры V.

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

Сформулируем основную теорему теории игр.

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

Теорема 1. Для того чтобы смешанные стратегии и были оптимальными, необходимо и достаточно выполнение неравенств

(49)

(50)

Теорема 2. Пусть

и -

Оптимальные смешанные стратегии и - цена игры.

Только те вероятности, отличны от нуля, для которых

Только те вероятности

Отличны от нуля, для которых

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

В этой лекции рассматриваются матричные игры, не имеющие седловых точек.

- игры.

Рассмотрим игру с платежной матрицей

Пусть игрок A применяет набор своих оптимальных стратегий. По основной теореме теории игр это обеспечивает ему выигрыш при любых стратегиях игрока В, т. е. выполняются соотношения:

(51)

Дополняя их уравнением

(52)

Получим систему линейных уравнений относительно и. Решая ее найдем

, , , (53)

Где.

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

(54)

Ее решениями будут

, , , (55)

Пример. Молокозавод поставляет в магазин молочную продукцию () и кисломолочную продукцию (). Согласно договора между ними продукция поступает в магазин два раза в день: с 10.00 до 11.00 (1-ый срок) и с 17.00 до 18.00 (2-ой срок). Если молокозавод соблюдает сроки поставок, то магазин выплачивает премии по следующей схеме: при поставке продукции в первый срок выплачивает 5 тыс. руб., во второй срок - 3 тыс. руб.; при поставке продукции в первый срок выплачивает 2 тыс. руб., во второй срок - 3 тыс. руб. Определить оптимальные стратегии поставок и получения продукции.

Решение. Примем молокозавод за игрока А, а магазин - за игрока В. Составим платежную матрицу игры:

Сроки

Продукция

1-ый срок

2-ой срок

Или

Найдем

, седловой точки нет. Применим формулы (53) - (55) для определения оптимальных стратегий и цены игры:

, , , ,

, ,

Оптимальные стратегии:

, ,

Цена игры.

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

Матричная игра допускает простую геометрическую интерпретацию.

Нахождение цены игры и оптимальной стратегии для игрока А равносильно решению уравнения:

(56)

Для нахождения правой части (56) применим графический метод.

Пусть игрок А выбрал смешанную стратегию

, ,

А игрок В - k-ую чистую стратегию, . Тогда средний выигрыш игрока А окажется равным

при стратегии (57)

при стратегии (58)

Очевидно,

Которую называют нижней огибающей прямых I и II.

Нетрудно видеть, что

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

и цену игры.

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

На плоскости POz построим две прямые, описываемые уравнениями: и или (I) и (II).

Решая систему уравнений

Найдем, , .

Таким образом, имеем полученный выше ответ игры:

и.

Теперь покажем, как графическим методом найти стратегии игрока В.

(59)

Пусть игрок В выбрал смешанную стратегию

, ,

А игрок А - I-ую чистую стратегию, . Тогда средний выигрыш игрока В окажется равным

при стратегии (60)

при стратегии (61)

На плоскости qOz уравнения (60) и (61) описывают прямые III и IV

Очевидно,

Которую называют верхней огибающей прямых III и IV.

Нетрудно видеть, что

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

И цену игры.

Для рассмотренной выше гры с матрицей H найдем стратегии игрока В.

На плоскости QOz построим две прямые, описываемые уравнениями:

и или (III) и (IV).

Решая систему уравнений

Найдем

, , .

Таким образом, имеем

и.

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

или.

Для рассмотренного примера такими уравнениями будут

или

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

и - игры.

Решают такие игры графическим способом, описанным выше. Отличие от - игр заключается в следующем.

1) Нижняя (верхняя) огибающая семейства прямых

Содержит большее число отрезков.

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

или

3) Пусть в игре в нижней точке верхней огибающей пересекаются прямые и. Тогда при нахождении оптимальной смешанной стратегии игрока А согласно Теореме 2 полагают, что, , , , где P - решение уравнения

или.

- игры.

При решении таких игр рекомендуется предварительно уменьшить размеры платежной матрицы или упростить ее в некотором смысле. С этой целью применяют следующие правила.

Правило доминирования.

Из платежной матрицы исключают чистые стратегии заведомо невыгодные по сравнению с другими:

Например, рассмотрим игру с матрицей

Сравнивая строки, убеждаемся, что элементы 2-ой строки не больше соответствующих элементов 1-ой строки, а 3-ья строка совпадает с 4-ой. Следовательно, стратегии и невыгодные и могут быть отброшены. Матрица игры преобразуется к матрице

Сравнивая столбцы полученной матрицы, убеждаемся, что элементы 2-го столбца не меньше соответствующих элементов 1-го столбца, а элементы 3-го столбца не меньше соответствующих элементов 4-го столбца, т. е. стратегии и также могут быть отброшены. Окончательно усеченная матрица игры имеет вид

Таким образом, оптимальными стратегиями игроков А и В игры с матрицей Н будут

и, где и -

Оптимальные стратегии игры с матрицей.

Аффинное правило.

Пусть и - оптимальные смешанные стратегии игроков А и В в игре с платежной матрицей

И ценой. Тогда и будут оптимальными стратегиями и в игре с матрицей

И ценой

Например, игру с матрицей

Можно заменить игрой с матрицей

Т. к. элементы этих матриц связаны соотношениями

; ; ; ; ; . При этом оптимальные стратегии игр совпадают, а цены игр связаны соотношением

В общем случае решение игр размера в смешанных стратегиях сводят к решению двух возможно двойственных ЗЛП..

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

Здесь рассматриваются матричные игры, не имеющие седловых точек.

- игры.

Рассмотрим игру с платежной матрицей

Пусть игрок A применяет набор своих оптимальных стратегий

По основной теореме теории игр это обеспечивает ему выигрыш при любых стратегиях игрока В, т. е. выполняются соотношения:

(62)

Дополняя их уравнением

(63)

Получим систему линейных уравнений относительно и. Решая ее найдем

, , , (64)

Где.

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

(65)

Ее решениями будут

, , , (66)

Решение. Примем молокозавод за игрока А, а магазин - за игрока В. Составим платежную матрицу игры:

Сроки

Продукция

1-ый срок

2-ой срок

Или

Найдем

, седловой точки нет. Применим формулы (63) - (65) для определения оптимальных стратегий и цены игры:

, , , ,

, ,

Оптимальные стратегии:

, ,

Цена игры.

Матричная игра допускает простую геометрическую интерпретацию.

Нахождение цены игры и оптимальной стратегии для игрока А равносильно решению уравнения:

(66)

Для нахождения правой части (66) применим графический метод.

Пусть игрок А выбрал смешанную стратегию, , а игрок В - K-ую чистую стратегию, . Тогда средний выигрыш игрока А окажется равным

при стратегии (67)

при стратегии (68)

Очевидно,

Которую называют нижней огибающей прямых I и II.

Нетрудно видеть, что

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

и цену игры.

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

На плоскости POz построим две прямые, описываемые уравнениями:

и или (I) и (II).

Решая систему уравнений

Найдем

, , .

Таким образом, имеем полученный выше ответ игры:

и.

Теперь покажем, как графическим методом найти стратегии игрока В.

(69)

Пусть игрок В выбрал смешанную стратегию

, ,

А игрок А - I-ую чистую стратегию, . Тогда средний выигрыш игрока В окажется равным

при стратегии (70)

при стратегии (71)

Очевидно,

Которую называют верхней огибающей прямых III и IV.

Нетрудно видеть, что

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

и цену игры.

Для рассмотренной выше гры с матрицей H найдем стратегии игрока В.

На плоскости QOz построим две прямые, описываемые уравнениями:

и или (III) и (IV).

Решая систему уравнений

Найдем

, , .

Таким образом, имеем

и.

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

или.

Для рассмотренного примера такими уравнениями будут

или

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

и - игры.

Решают такие игры графическим способом, описанным выше. Отличие от - игр заключается в следующем.

4) Нижняя (верхняя) огибающая семейства прямых

Содержит большее число отрезков.

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

или

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

или.

- игры.

Правило доминировнаия.

Из платежной матрицы исключают чистые стратегии заведомо невыгодные по сравнению с другими:

Например, рассмотрим игру с матрицей

Таким образом, оптимальными стратегиями игроков А и В игры с матрицей Н будут и, где и - оптимальные стратегии игры с матрицей.

Аффинное правило.

Пусть и - оптимальные смешанные стратегии игроков А и В в игре с платежной матрицей и ценой. Тогда и будут оптимальными стратегиями и в игре с матрицей

и ценой.

Например, игру с матрицей

Можно заменить игрой с матрицей

Т. к. элементы этих матриц связаны соотношениями

; ; ; ; ; . При этом оптимальные стратегии игр совпадают, а цены игр связаны соотношением

В общем случае решение игр размера в смешанных стратегиях сводят к решению двух возможно двойственных ЗЛП.

Редукция матричных игр к ЗЛП.

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

Оптимальная стратегия стратегия игрока А обеспечивает ему средний выигрыш, не меньший, при любой стратегии игрока В. Поэтому все средние выигрыши игрока А можно выписать в виде системы неравенств:

(72)

Введем новые переменные:

(73)

Тогда после деления каждого неравенства из (71) на получим новую систему неравенств

(73)

Из равенства

Нетрудно получить соотношение для :

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

(74)

При условиях (73) и