Глава IV. Экономико-математические методы и модели теории игр

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

Предмет теории игр. Основные понятия

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

Отметим основные ее понятия:

игра – упрощенная математическая модель конфликтной ситуации, отличающаяся от реальной темы, что ведется по определенным правилам, при этом каждый из участников принимает такие решения, которые, как он полагает, обеспечат ему наилучший исход;

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

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

партией называют каждый вариант реализации игры. В партии игроки совершают конкретные ходы;

ход – выбор и реализация игроком одного из допустимых вариантов поведения.

Целью теории игр является определение оптимальной стратегии для каждого игрока.

Игры можно классифицировать по разным признакам:

- по количеству стратегий игры делятся на конечные и бесконечные;

- по взаимоотношению участников на бескоалиционные (без права заключения соглашения), некооперативные, и коалиционные (кооперативные);

- по характеру выигрышей на игры с нулевой суммой (общий капитал игроков не меняется, а лишь перераспределяется в ходе игры, при этом сумма выигрышей равна 0, а проигрыш есть отрицательный выигрыш и с ненулевой суммой;

- по виду платежной функции на матричные и непрерывные;

- по количеству ходов игры на одноходовые и многоходовые (многоходовые игры подразделяются на стохастические и дифференциальные уравнения).

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

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

Пусть у игроков А и В соответственно m и n чистых стратегий, которые обозначим через и .

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

Платежную матрицу удобно также представить в виде таблицы

Таблица 11.1

			¼
			¼
			¼
¼	¼	¼	¼	¼
			¼

В ее строках расположены чистые стратегии игрока А, а в столбцах – чистые стратегии игрока В.

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

Число a называют нижней ценой игры и является гарантированным выигрышем игрока А.

Очевидно, a находится в одной из строк матрицы H, к примеру в строке . Тогда стратегию называют максиминной, т. к. .

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

Рассмотрим примеры нахождения и .

Пример 1. Пусть игра задана платежной матрицей :

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

Верхняя и нижняя цены игры совпали: .

Пример 2. Задана платежная матрица

Находим

и

Здесь .

Справедлива следующая теорема.

Теорема 1. В любой матричной игре нижняя цена игры не превосходит верхней цены игры, т. е. .

Обозначим через и номера чистых стратегий, при котором . Пару чистых стратегий и при этом называют седловой точкой игры, а – седловым элементом платежной матрицы.

Число называют чистой ценой игры.

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

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

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

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

(11.1)

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

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

Таблица 11.2

		¼
			¼
			¼
¼	¼	¼	¼	¼	¼
			¼
			¼

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

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

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

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

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

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

, .

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

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

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

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

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

(11.2)

(11.3)

Теорема 3. Пусть и – оптимальные смешанные стратегии и – цена игры.

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

.

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

.

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

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

– игры

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

.

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

(12.1)

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

(12.2)

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

, , , (12.3)

где .

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

(12.4)

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

, , , (12.5)

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

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

Таблица 12.1

Сроки Продукция	1-ый срок	2-ой срок

или

.

Найдем

,

,

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

, , , ,

, ,

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

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

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

По Теореме 2 из Лекции 11 нахождение цены игры и оптимальной стратегии для игрока А равносильно решению уравнения:

(12.6)

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

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

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

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

На плоскости pOz уравнения (12.7) и (12.8) описывают прямые I и II, изображенные на рис. 12.1

Рис. 12.1

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

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

(см. рис. 12.1)

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

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

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

Рис. 12.2

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

найдем , , .

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

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

Вновь по Теореме 2 из Лекции 11 имеем

(12.9)

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

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

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

На плоскости qOz уравнения (12.10) и (12.11) описывают прямые III и IV, изображенные на рис. 12.3

Рис. 12.3

Очевидно, , которую называют верхней огибающей прямых III и IV.

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

(см. рис. 12.3)

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

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

На плоскости qOz построим две прямые, описываемые уравнениями: и или (III) и (IV).

Рис. 12.4

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

найдем , , .

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

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

или .

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

или

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

и – игры

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

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

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

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

или .

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

или .

– игры

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

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

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

а) для игрока А такими стратегиями являются те, которым соответствуют строки с элементами не большими по сравнению с элементами других строк;

б) для игрока В такими стратегиями являются те, которым соответствуют столбцы с элементами не меньшими по сравнению с элементами других столбцов.

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

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

.

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

.

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

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

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

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

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

Редукция матричных игр к задачам линейного программирования

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

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

(13.1)

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

(13.2)

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

(13.3)

Из равенства

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

.

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

(13.4)

при условиях (13.3) и

(13.5)

Сформулированная задача (13.3) – (13.5) является ЗЛП.

Повторим с естественными изменениями предыдущие рассуждения для определения оптимальной стратегии игрока В.

Игрок В стремиться минимизировать гарантированный проигрыш . Все средние проигрыши игрока В запишем в виде системы неравенств:

, (13.6)

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

В обозначениях

система неравенств (13.6) примет вид

(13.7)

Применение удовлетворяют соотношению

.

Минимизация равносильна максимизации .

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

(13.8)

при условиях (13.7) и

(13.9)

Задача (13.7) – (13.9) также является ЗЛП.

Таким образом, игра свелась к двум ЗЛП, которые запишем в матричном виде

, , ,

Очевидно, задачи I и II являются двойственными ЗЛП.

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

Таблица 13.1

Спрос Продукция

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

Решение. Задача сводится к игровой модели, в которой игрок А – предприятие, имеющее три стратегии: , и ; игрок В – спрос, имеющий четыре стратегии: , , и ; платежная матрица – заданная таблица.

Выполним анализ игры:

Седловой точки нет: , . Игра в смешанных стратегиях.

Составим взаимнодвойственные ЗЛП:

Решим задачу (II) симплекс-методом

Таблица 13.2

Базисные неизвестные	Свободные члены
f		–1	–1	–1	–1
f
f

Из итоговой симплекс-таблицы находим решение задачи (II):

,

, , , , , , .

Перейдем к решению задачи (I).

По первой теореме двойственности

По второй теореме двойственности справедливо соответствие между переменными задач (I) и (II):

,

где – балансовые переменные задачи (I), и из строки f итоговой симплекс-таблицы находим

, , , , , , .

Возвращаясь к исходной игре, имеем

,

, .

Ответ: оптимальные пропорции выпускаемой предприятием продукции составляют по 50 % продукции и , гарантирующие 4 ед. прибыли при оптимальном спросе % в состоянии и % в состоянии .