2015-05-18
1349
Рассмотрим конечные матричные игры, в которых нет седловой точки, т.е. 
.
Нетрудно доказать, что 
. Если игра одноходовая, то по принципу минимакса игроку А гарантирован выйгрыш 
, а игроку В – проигрыш 
. Таким образом, для цены игры 
справедливо соотношение
(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-го столбца, т.е. стратегии и 
также могут быть отброшены. Окончательно усеченная матрица игры имеет вид
.
Таким образом, оптимальными стратегиями игроков А и В игры с матрицей Н будут 
и 
, где 
и 
– оптимальные стратегии игры с матрицей 
.
Аффинное правило.
Пусть и – оптимальные смешанные стратегии игроков А и В в игре с платежной матрицей 
и ценой . Тогда и будут оптимальными стратегиями и в игре с матрицей 
и ценой 
.
Например, игру с матрицей 
можно заменить игрой с матрицей 
, т.к. элементы этих матриц связаны соотношениями 
: 
; 
; 
; 
; 
; 
. При этом оптимальные стратегии игр совпадают, а цены игр связаны соотношением 
.
В общем случае решение игр размера в смешанных стратегиях сводят к решению двух возможно двойственных ЗЛП. Изучению этого вопроса посвящена следующая лекция.
