Глава 2. Теория игр

1. Основные понятия теории игр

Ситуация называется конфликтной, если в ней участвуют стороны, интересы которых полностью или частично противоположны.

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

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

Количественная оценка результатов игры называется платежом.

Игра называется парной, если в ней участвуют только две стороны (два лица).

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

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

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

Пусть имеется два игрока, один из которых может выбрать i-ую стратегию из m возможных стратегий ( ), а второй, не зная выбора первого, выбирает j-ую стратегию из n своих возможных стратегий ( ). В результате первый игрок выигрывает величину , а второй проигрывает эту величину. Из чисел составим матрицу

Строки матрицы А соответствуют стратегиям первого игрока, а столбцы – стратегиям второго. Эти стратегии называются чистыми. Матрица А называется платёжной (или матрицей игры).

Игру, определяемую матрицей А, имеющей m строк и n столбцов, называют конечной игрой размерности .

Число называется нижней ценой игры или максимином, а соответствующая ему стратегия (строка) – максиминной.

Число называется верхней ценой игры или минимаксом, а соответствующая ему стратегия (строка) – минимаксной.

Теорема 1. Нижняя цена игры всегда не превосходит верхней цены игры.

Если  =  = v, то число v называется ценой игры.

Игра, для которой  = , называется игрой с седловой точкой. Для этой игры нахождение решения состоит в выборе максиминной и минимаксной стратегий, которые являются оптимальными.

Пример 1. Швейное предприятие планирует к массовому выпуску новую модель одежды. Спрос на эту модель не может быть точно определён. Однако, можно предположить, что его величина характеризуется тремя возможными состояниями (I, II, III). С учётом этих состояний анализируются три возможных варианта данной модели (А, Б, В). Каждый из этих вариантов требует своих затрат и обеспечивает в конечном счёте различный эффект. Прибыль (в тыс. руб.), которую получает предприятие при данном объёме выпуска модели и соответствующем состоянии спроса определяется матрицей:

I II III

.

Требуется найти объём выпуска модели одежды, обеспечивающей среднюю величину прибыли при любом состоянии спроса.

Решение.

= max (22, 21, 20) = 22;

= min (22, 23, 24) = 22.

 =  = 22 – седловая точка, то есть цена игры. Игра имеет седловую точку, соответствующую варианту А выпуска модели одежды. Объём выпуска модели, соответствующей данному варианту, обеспечивает прибыль в 22 тыс. руб. при любом состоянии спроса.

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

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

Из данного определения следует, что сумма компонент указанного вектора равна 1, а сами компоненты неотрицательны.

Обычно смешанную стратегию первого игрока обозначают как вектор U =(u₁, u₂, , u_m), а второго игрока – как вектор Z =(z₁, z₂, , z_n), где , , , .

Если U^* - оптимальная стратегия первого игрока, а Z^* - оптимальная стратегия второго игрока, то число

является ценой игры.

Теорема 2 (теорема фон Неймана). Всякая матричная игра с нулевой суммой имеет решение в смешанных стратегиях.

Теорема 3. Для того, чтобы число v было ценой игры, а U^* и Z^* - оптимальными стратегиями, необходимо и достаточно, чтобы выполнялись неравенства

Если теорема 2 даёт ответ на вопрос о существовании решения игры, то следующая теорема даёт ответ на вопрос, как найти решение для игр , и , примеры которых приведены ниже.

Теорема 4. Если один из игроков применяет оптимальную смешанную стратегию, то его выигрыш равен цене v игры, вне зависимости от того, с какими частотами будет принимать второй игрок стратегии, вошедшие в оптимальную (в том числе и чистые стратегии).

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

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

Решение.

Прежде всего, проверим наличие седловой точки в данной матрице. Для этого найдём минимальные элементы в каждой из строк (2 и 4) и максимальные элементы в каждом из столбцов (6 и 5). Значит, нижняя цена игры  = max(2; 4) = 4, а верхняя цена игры min(6; 5) = 5. Так как  = 4 ≠  = 5, то решением игры являются смешанные оптимальные стратегии, а цена игры заключена в пределах 4 ≤ v ≤ 5.

Предположим, что для игрока А стратегия задаётся вектором U = (u₁, u₂). Тогда, на основании теоремы 4, при применении игроком В чистой стратегии В₁ или В₂ игрок А получит средний выигрыш, равный цене игры, то есть

(при стратегии В₁)

(при стратегии В₂).

Помимо двух записанных уравнений относительно, добавим уравнение, связывающее частоты и :

.

; .

; v = .

Найдём теперь оптимальную стратегию для игрока В. Пусть стратегия для данного игрока задаётся вектором Z = (z₁, z₂). Тогда

.

Решая систему уравнений, состоящую из каких-нибудь двух уравнений, взятых из этой системы, получим:

; ; ; ; .

Следовательно, решением игры являются смешанные стратегии и , а цена игры v = .

Дадим теперь геометрическую интерпретацию решения данной игры. Для этого на плоскости uOz отложим отрезок единичной длины А₁А₂, каждой точке которого поставим в соответствие некоторую смешанную стратегию U = (u₁,u₂) = =(u₁,1 - u₁). В частности, точке А₁(1;0) отвечает стратегия А₁, точке А₂(0;1) - стратегия В точках А₁ и А₂ восстановим перпендикуляры и на полученных прямых будем откладывать выигрыш игроков. На одном перпендикуляре (в данном случае он совпадёт с осью Oz) отложим выигрыш игрока А при стратегии А₂, а на другом – при стратегии. Если игрок А применяет стратегию А₂, то его выигрыш при стратегии В₁ игрока В равен 6, а при при стратегии В₂ он равен 4. Числам 6 и 4 на оси Z cоответствуют точки В₁ и В₂. Если же игрок А применяет стратегию А₁, то его выигрыш при стратегии В₁ игрока В равен 2, а при при стратегии В₂ он равен 5. Эти два числа определяют две точки и на перпендикуляре, восстановленном в точке А₁. Соединяя между собой точки В₁ и , В₁ и , получим две прямые, расстояние от которых до оси Ou определяет средний выигрыш при любом сочетании соответствующих стратегий. Например, расстояние от любoй точки отрезка [В₁ ] до оси Ou определяет средний выигрыш v при любом сочетании стратегий А₁ и А₂ (c частотами u₁ и u₂) и стратегии В₁ игрока В. Это расстояние равно . Аналогично, средний выигрыш при применении стратегии В₂ определяется ординатами точек, принадлежащих отрезку [В₂ ]. Таким образом, ординаты точек, принадлежащих ломаной МВ₁, определяют минимальный выигрыш игрока А при применении им любых смешанных стратегий. Эта минимальная величина является максимальной в точке М, следовательно, этой точке соответствует стратегия , а её ордината равна цене игры v.

Рис. 2.

Координаты точки М находим как координаты точки пересечения прямых В₁ и В₂ . Соответствующие три уравнения имеют вид:

.

Решая эту систему уравнений, получаем ; ; .

Аналогично находится оптимальная стратегия для игрока В. Для её определения имеем уравнения:

,

откуда находим ; .

Следовательно, решением игры являются смешанные стратегии и , а цена игры v = .

Алгоритм решения матричных игр размерности 2×n (n×2), n>2.

1. Cтроят прямые, соответствующие стратегиям второго (первого) игрока.

2. Определяют нижнюю и верхнюю границы выигрыша.

3. Выделяется нижняя (верхняя) огибающая семейства построенных прямых.

4. Верхняя (нижняя) точка построенной нижней (верхней) огибающей определяет цену игры и оптимальную стратегию первого (второго) игрока.

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

.

Решение.

= max (-1, -2) = -1;

= min (6, 4, 3, 1, 5, 4) = 1.

-1 ≤ v ≤ 1.

Рис. 3.

Прямые В_i , , соответствуют стратегиям, а нижняя огибающая В₅КLM - нижней границе выигрыша игрока В. Верхняя точка К этой ломаной и будет определять цену игры и оптимальную стратегию игрока А. Координаты точки К находим как координаты точки пересечения прямых В₄ и В₅ .

; .

; v = .

Найдём оптимальную стратегию игрока В.

.

; .

Игра имеет решение ; ;

v = .

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

.

Решение.

= max (1, -4, -6, 2, -3) = 2;

= min (5, 4) = 4.

2≤ v ≤ 4.

Рис. 4.

Матрица имеет размерность 5×2. Строим прямые В_i , , соответствующие стратегиям игрока А. Верхняя огибающая построенного семейства прямых А₃КLM соответствует верхней границе выигрыша игрока А. Нижняя точка этой ломаной будет определять цену игры и оптимальную стратегию игрока В. В данном случае нижних точек бесконечно много – они заполняют весь отрезок [LM]. Цена игры равна ординате точек L и M: v = 2.

Найдём координаты точек L и M.

Координаты точки L находим из системы:

; ; v = .

;

Координаты точки М находим из системы:

; ;

; .

Таким образом, - множество оптимальных стратегий игрока В. Стратегии и являются крайними оптимальными стратегиями.

Найдём оптимальные стратегии игрока А.

1) .

;

;

2) .

;

;

Игра имеет множество решений:

, , v = 2.