Основные понятия и определения теории игр

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

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

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

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

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

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

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

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

Пусть имеется два игрока, один из которых может выбрать 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 и т. д.

 

       
   
 
 

 

 


 

 
 
Рис.1


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

 

 

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

Решение. Прежде всего проверим, имеет ли исходная ма­трица седловую точку. Для этого находим минимальные эле­менты в ее строках (22; 21; 20) и максимальные— в столбцах (22; 23; 24). Максимальным среди минимальных элементов строк является число а = 22, а минимальным среди максимальных эле­ментов столбцов — число р = 22. Таким образом, а = |3 = 22. Чи­сло 22 является ценой игры. Игра имеет седловую точку, соответ­ствующую 1 варианту выпуска модели одежды. Объем выпуска модели, соответствующей данному варианту, обеспечивает при­быль в 22 тыс. руб. при любом состоянии спроса.

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