Решение матричных игр в смешанных стратегиях

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

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

(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-го столбца, т.е. стратегии и также могут быть отброшены. Окончательно усеченная матрица игры имеет вид

.

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

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

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

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

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