Основные понятия и определения теории игр
Ситуация называется конфликтной, если в ней участвуют стороны, интересы которых полностью или частично противоположны.
Игра — это действительный или формальный конфликт, в котором имеется по крайней мере два участника (игрока), каждый из которых стремится к достижению собственных целей.
Допустимые действия каждого из игроков, направленные на достижение некоторой цели, называются правилами игры.
Количественная оценка результатов игры называется платежом.
Игра называется парной, если в ней участвуют только две стороны (два лица).
Парная игра называется игрой с нулевой суммой, если сумма платежей равна нулю, т. е. если проигрыш одного игрока равен выигрышу второго.
Однозначное описание выбора игрока в каждой из возможных ситуаций, при которой он должен сделать личный ход, называется стратегией игрока.
Стратегия игрока называется оптимальной, если при многократном повторении игры она обеспечивает игроку максимально возможный средний выигрыш.
Пусть имеется два игрока, один из которых может выбрать i-ю стратегию из m своих возможных стратегий (i= ), а второй, не зная выбора первого, выбирает j-ю стратегию из п своих возможных стратегий (j= ). В результате первый игрок выигрывает величину аij, а второй проигрывает эту величину.
Из чисел аij составим матрицу
Строки матрицы A соответствуют стратегиям первого игрока, а столбцы — стратегиям второго. Эти стратегии называются чистыми.
Матрица А называется платежной (или матрицей игры).
Игру, определяемую матрицей А, имеющей m строк и n столбцов, называют конечной игрой размерности m×n.
Число α = называется нижней ценой игры или максимином, а соответствующая ему стратегия (строка) — максиминной.
Число β = называется верхней ценой игры или минимаксом, а соответствующая ему стратегия игрока (столбец) — минимаксной.
Теорема 1.Нижняя цена игры всегда не превосходит верхней цены игры.
Если α = β = υ, то число υ называется ценой игры.
Игра, для которой α = β, называется игрой с седловой точкой.
Для игры с седловой точкой нахождение решения состоит в выборе максиминной и минимаксной стратегий, которые являются оптимальными.
Если игра, заданная матрицей, не имеет седловой точки, то для нахождения ее решения используются смешанные стратегии.
Вектор, каждая из компонент которого показывает относительную частоту использования игроком соответствующей чистой стратегии, называется смешанной стратегией данного игрока.
Из данного определения непосредственно следует, что сумма компонент указанного вектора равна единице, а сами компоненты не отрицательны. Обычно смешанную стратегию первого игрока обозначают как вектор U = (u1, u2 ..., um), а второго игрока — как вектор Z = (z1, z2 ..., zn), где ui ≥ 0 (i= ), zi ≥ 0 (j= ),
Если U* — оптимальная стратегия первого игрока, a Z* — оптимальная стратегия второго игрока, то число
является ценой игры.
Определение оптимальных стратегий и цены игры и составляет процесс нахождения решения игры.
Теорема 2 Всякая матричная игра с нулевой суммой имеет решение в смешанных стратегиях.
Теорема 3 Для того чтобы число v было ценой игры, a U* и Z* — оптимальными стратегиями, необходимо и достаточно выполнение неравенств
и
Если теорема 2 дает ответ на вопрос о существовании решения игры, то следующая теорема дает ответ на вопрос, как найти это решение для игр 2×2, 2×n и n×2, примеры которых приведены ниже.
Теорема 4 Если один из игроков применяет оптимальную смешанную стратегию, то его выигрыш равен цене игры υ вне зависимости от того, с какими частотами будет применять второй игрок стратегии, вошедшие в оптимальную (в том числе и чистые стратегии).
Рассмотрим примеры.
Пример1. Найти решение игры, заданной матрицей и дать геометрическую интерпретацию этого решения.
Решение. Прежде всего проверим наличие седловой точки в данной матрице. Для этого найдем минимальные элементы в каждой из строк (2 и 4) и максимальные элементы в каждом из столбцов (6 и 5). Значит, нижняя цена игры α = mах (2; 4) =4, а верхняя цена игры β = min (6; 5) = 5. Так как α = 4 ≠ β = 5, то решением игры являются смешанные оптимальные стратегии, а цена игры v заключена в пределах 4≤ υ ≤!5.
Предположим, что для игрока А стратегия задается вектором U = (u1; u2). Тогда на основании теоремы 4 при применении игроком В чистой стратегии В1 или В2 игрок А получит средний выигрыш, равный цене игры, т. е.
(при стратегии В1),
(при стратегии В2).
Помимо двух записанных уравнений относительно и добавим уравнение, связывающее частоты и .
+ = 1.
Решая полученную систему трех уравнений с тремя неизвестными, находим =2/5; =3/5; υ = 22/5.
Найдем теперь оптимальную стратегию для игрока В. Пусть стратегия для данного игрока задается вектором Z=(z1; z2).
Тогда
Решая систему уравнений, состоящую из каких-нибудь двух уравнений, взятых из последней системы, получим =1/5; =4/5. Следовательно, решением игры являются смешанные стратегии U* = (2/5; 3/5) и Z* = (1/5; 4/5), а цена игры υ = 22/5.
Дадим теперь геометрическую интерпретацию решения данной игры. Для этого на плоскости uOz введем систему координат и на оси Оu отложим отрезок единичной длины А1А2, каждой точке которого поставим в соответствие некоторую смешанную стратегию U= (u1, u2) = (u1, 1- u1)
(рис. 1). В частности, точке А1 (0; 1) отвечает стратегия A1, точке А2 (1; 0) —стратегия А2 и т. д.
|
Пример 2. Швейное предприятие планирует к массовому выпуску новую модель одежды. Спрос на эту модель не может быть точно определен. Однако можно предположить, что его величина характеризуется тремя возможными состояниями (I, II, III). С учетом этих состояний анализируются три возможных варианта выпуска данной модели (А, Б, В). Каждый из этих вариантов требует своих затрат и обеспечивает в конечном счете различный эффект. Прибыль (тыс. руб.), которую получает предприятие при данном объеме выпуска модели и соответствующем состоянии спроса, определяется матрицей
Требуется найти объем выпуска модели одежды, обеспечивающий среднюю величину прибыли при любом состоянии спроса.
Решение. Прежде всего проверим, имеет ли исходная матрица седловую точку. Для этого находим минимальные элементы в ее строках (22; 21; 20) и максимальные— в столбцах (22; 23; 24). Максимальным среди минимальных элементов строк является число а = 22, а минимальным среди максимальных элементов столбцов — число р = 22. Таким образом, а = |3 = 22. Число 22 является ценой игры. Игра имеет седловую точку, соответствующую 1 варианту выпуска модели одежды. Объем выпуска модели, соответствующей данному варианту, обеспечивает прибыль в 22 тыс. руб. при любом состоянии спроса.
Используя геометрическую интерпретацию, найдите решение игр, определяемых следующими матрицами.