Теория игр

                                                   a £ n £ b,

где a и b - нижняя и верхняя цена игры.

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

Пусть S_A^* = (p₁^*, p₂^*,…,р_m^*)  и S_B^* = (q₁^*, q₂^*, … q_n^*) – пара оптимальных стратегий. Если чистая стратегия входит в оптимальную смешанную стратегию с отличной от нуля вероятностью, то она называется активной.

Справедлива теорема об активных стратегиях: если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остаётся неизменным и равным цене игры n, если второй игрок не входит за пределы своих активных стратегий.

Эта теорема  имеет большое практическое значение – она даёт конкретные модели нахождения оптимальных стратегий при отсутствии седловой точки.

Рассмотрим игру размера 2×2, которая является простейшим случаем конечной игры. Если такая игра имеет седловую точку, то оптимальное решение – это пара чистых стратегий, соответствующих этой точке.

Игра, в  которой отсутствует седловая точка, в соответствии с основной теоремой теории игр оптимальное решение существует и определяется парой смешанных стратегий  S_A^* = (p₁^*, p₂^*) и S_B^* = (q₁^*, q₂^*).

Для того чтобы их найти, воспользуемся теоремой об активных стратегиях. Если игрок А придерживается своей оптимальной стратегии S_A^*, то его средний выигрыш будет равен цене игры n, какой бы активной стратегией ни пользовался игрок В. Для игры 2×2 любая чистая стратегия противника является активной, если отсутствует седловая точка. Выигрыш игрока А (проигрыш игрока В) – случайная величина, математическое ожидание (среднее значение) которой является ценой игры. Поэтому средний выигрыш игрока А (оптимальная стратегия) будет равна n и для 1-й, и для 2-й стратегии противника.

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

 

Средний выигрыш игрока А, если он использует оптимальную смешанную стратегию , а игрок В – чистую стратегию В₁ (это соответствует 1-му столбцу платёжной матрицы Р), равен цене игры n:

a₁₁p₁^* = a₂₁p₂^* =n.

Тот же выигрыш  получает игрок А, если 2-й игрок применяет стратегию В₂, т.е. а₁₂р₁^* = а₂₂р₂^* = n. Учитывая, что р₁^* + р₂^* = 1, получаем систему уравнений для определения оптимальной стратегии S_A^* и цены игры n:

                                                  (1)

Решая эту систему, получим оптимальную  стратегию

,

и цену игры    

.

Применяя  теорему об активных стратегиях при  отыскании S_B^* -оптимальной стратегии игрока В, получаем, что при любой чистой стратегии игрока А (А₁ или А₂) средний проигрыш игрока В равен цене игры n, т.е.

 

                                                    (2)

 

тогда оптимальная  стратегия S_B^*(q₁^*,q₂^*) определяется формулами:

,

 

 Геометрическая интерпретация игры 2´2

Решение игры 2´2 допускает наглядную геометрическую интерпретацию. Пусть игра задана платёжной матрицей P=( ), где i, j = 1, 2. По оси абсцисс (рис.1) отложим единичный отрезок ; точка (х=0) изображает стратегию , а все промежуточные точки этого отрезка – смешанные стратегии первого игрока, причём расстояние от до правого конца отрезка – это вероятность стратегии , расстояние до левого конца – вероятность стратегии . На перпендикулярных осях I–I и II–II откладываем выигрыши при стратегиях и соответственно. Если второй игрок примет стратегию B1, то она даёт выигрыши и на осях I–I и II–II , соответствующие стратегиям и .  Обозначим эти точки на осях I–I и II–II буквой . Средний выигрыш n₁, соответствующий смешанной стратегии , определяется по формуле математического ожидания n₁= и равен ординате точки , которая лежит на отрезке и имеет абсциссу (рис. 1).

   Аналогично строим отрезок  , соответствующий применению вторым игроком стратегии (рис. 2). При этом средний выигрыш n₂= – ордината точки .В соответствии с принципом минимакса оптимальная стратегия такова, что минимальный выигрыш игрока А (при наихудшем поведении игрока В) обращается в максимум. Ординаты точек, лежащих на ломаной (рис. 3), показывают минимальный выигрыш игрока А при использовании им любой смешанной стратегии (на участке N – против стратегии , на участке – против стратегии ). Оптимальную стратегию определяет точка N, в которой минимальный выигрыш достигает максимума; её ордината равна цене игры ν. На рис. 3 обозначены также верхняя и нижняя цены игры и .

Применим геометрический метод  для решения следующей задачи.

► Задача. Решить графически игру, заданную платёжной матрицей

.

  

Р е ш е н и е. Откладываем по оси абсцисс (рис. 4) единичный отрезок . На вертикальной оси I–I откладываем отрезки: 1.5, соответствующий стратегии , и = 3, соответствующий стратегии . На вертикальной оси II – II отрезок = 2 соответствует стратегии , отрезок = 2 соответствует стратегии (см. рис. 4). Нижняя цена игры = =1.5. Верхняя граница игры = =2, седловая точка отсутствует. Из рис. 4 видно, что абсцисса точки N  определяет оптимальную стратегию , а ордината – цену игры ν. Точка N является точкой пересечения прямых и . Уравнение прямой , проходящей через точки (0;1.5) и (1;2):

  или 

Уравнение прямой , проходящей через точки (0; 3) и (1; 1):

  или 

Точка пересечения прямых является решением системы

Или x=0.6; y=1,8, т.е.

Таким образом, =0,6, =1-0,6=0,4; оптимальная стратегия =(0,6;0,4), цена игры ν = 1,8.

Геометрически можно также определить оптимальную  стратегию игрока B, если поменять местами игроков А и В и вместо максимума нижней границы в соответствии с принципом минимакса (рис. 5) рассмотреть минимум верхней границы.

Абсцисса  точки M определяет в оптимальной стратегии игрока B, ордината этой точки – цена игры. Прямая , проходящая через точки (0;1.5) и (1; 3), удовлетворяет уравнению

y = 1,5x + 1,5.

Прямая , проходящая через точки (0; 2) и (1; 1), удовлетворяет уравнению y = -x +2.

Координаты  их точек пересечения М – это решение системы уравнений:

откуда x = 0,2; y = 1,8, т.е. = 0,2, = 1- = 0,8, x = y = 1,8, = (0.8; 0.2).

Оптимальное решение найдено.

 

Из решения  этой задачи следует, что геометрически  можно определять оптимальную стратегию  как игрока А, так и игрока В; в обоих случаях используется принцип минимакса, но во втором случае строится не нижняя, а верхняя граница выигрыша и на ней определяется не максимум, а минимум. Если платёжная матрица содержит отрицательные числа, то для графического решения задачи лучше перейти к новой матрице с неотрицательными элементами; для этого к элементам исходной матрицы достаточно добавить соответствующее положительное число. Решение игры при этом не изменится, а цена игры увеличится на это число. В данной задаче платёжная матрица не имела седловой точки ( _).

При наличии  седловой точки графическое решение даёт варианты, изображённые на рис. 6 и 7. На рис. 6 наибольшей ординатой на ломаной обладает точка , поэтому оптимальной является чистая стратегия для игрока А ( – для игрока В), т.е. оптимальное решение: = (0; 1),        = (0; 1). Игра имеет седловую точку = ν.

Чистая  стратегия  (рис. 7) не выгодна для игрока В, поскольку при любой стратегии игрока А она даёт последнему больший выигрыш, чем чистая стратегия . На основании принципа минимакса выделим прямую и на ней точку с наибольшей ординатой на оси I – I. Чистая стратегия является оптимальной для игрока  А, а чистая стратегия – для игрока В. Оптимальное решение: = (0; 1), = (1; 0), цена игры ν = , т.е. имеется седловая точка.

Графический метод можно применять при  решении игры 2 × п и m × 2.

Приведение матричной игры к  задаче линейного программирования

Игра m×n в общем случае не имеет наглядной геометрической интерпретации. Её решение достаточно трудоёмко при больших m и п, однако принципиальных трудностей не имеет, поскольку может быть сведено к решению задачи линейного программирования. Покажем это. Пусть игра m×n задана платёжной матрицей р= ( ), i = 1, 2, …, m; j = 1, 2, …, n. Игрок  А обладает стратегиями , игрок В – стратегиями . Необходимо определить оптимальные стратегии и , где – вероятности применения соответствующих чистых стратегий ;

, .

Оптимальная стратегия  удовлетворяет следующему требованию. Она обеспечивает игроку А средний выигрыш, не меньший, чем цена игры v, при любой стратегии игрока В и выигрыш, равный цене игры v, при оптимальной стратегии игрока В. Без ограничения общности полагаем v > 0; этого можно добиться, сделав все элементы 0. Если игрок А применяет смешанную стратегию против любой чистой стратегии игрока В, то он получает средний выигрыш, или математическое ожидание выигрыша , 1, 2, …, п (т.е. элементы j-го столбца матрицы почленно умножаются на соответствующие вероятности стратегий результаты складываются).

Для оптимальной стратегии  все средние выигрыши не меньше цены игры v, поэтому получаем систему неравенств:

                                    (3)

Каждое из неравенств можно  разделить на число v > 0. Введём новые переменные:

/v, /v, …, /v.

Тогда система примет вид:

                                    (4)

Цель игрока А – максимизировать свой гарантированный выигрыш, т.е. цену игры v.

Разделив на 0 равенство , получаем, что переменные (i =1, 2, …, т) удовлетворяют условию: 1/v. Максимизация цены игры v эквивалентна минимизации величины 1/v, поэтому задача может быть сформулирована следующим образом: определить значения переменных 0, i =1, 2, …, т, так чтобы они удовлетворяли линейным ограничениям и при этом линейная функция

                                           (5)

 обращалась  в минимум. Это задача линейного   программирования. Решая задачу (3)-(4), получаем оптимальное решение и оптимальную стратегию .

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

                                   (6)

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

Если  обозначить

/v, 1, 2, …, п,                                        (7)

то получим  систему неравенств:

                                   (8)

Переменные  (j= 1, 2, …, n,) удовлетворяют условию .

Игра  свелась к следующей задаче.

Определить  значения переменных 0, j=1, 2, …, n, которые удовлетворяют системе неравенств и максимизируют линейную функцию

                                          ₍₉₎

Решение задачи линейного программирования определяет оптимальную стратегию  . При этом цена игры

v =1/max =1/min .                                      (10)

Составив  расширенные матрицы для задач (4), (5) и (8), (9), убеждаемся, что одна матрица  получилась из другой транспортированием:

 

                                                 ≥                                            ≤

Таким образом, задачи линейного программирования (4), (5) и (6), (9) являются взаимно-двойственными. Очевидно, при определении оптимальных  стратегий в конкретных задачах  следует выбрать ту из взаимно-двойственных задач, решение которой менее  трудоёмко, а решение второй задачи найти с помощью теорем двойственности.

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

1. Исключить из платежной матрицы заведомо невыгодные стратегии по сравнению с другими стратегиями. Такими стратегиями для игрока A (игрока B) являются те, которым соответствуют строки (столбцы) с элементами, заведомо меньшими (большими) по сравнению с элементами других строк (столбцов).
2. Определить верхнюю и нижнюю цены игры и проверить имеет ли игра седловую точку. Если седловая точка есть, то соответствующие ей стратегии игроков будут оптимальными, а цена совпадет с верхней (нижней) ценой.
3. Если седловая точка отсутствует, то решение следует искать в смешанных стратегиях. Для игр размером рекомендуется симплексный метод, для игр размером 2х2, 2хn, nх2 возможно геометрическое решение.