Платёжная матрица. Нижняя и верхняя цена игры

Рассмотрим парную конечную игру. Пусть игрок А располагает m личными стратегиями А₁, А₂, ..., А_m, а игрок В имеет n личных стратегий В₁, В₂, ..., В_n. В этом случае говорят, что игра имеет размерность m х n. В результате выбора игроками любой пары стратегий А_i и B_j ( ) однозначно определяется исход игры, т.е. выигрыш a_ij игрока А (положительный или отрицательный) и проигрыш (– a_ij) игрока В. Предположим, что значения a_ij известны для любой пары стратегий (А_i; B_j)

Матрица  элементами которой являются выигрыши, соответствующие стратегиям А_i и B_j, называется платёжной матрицей или матрицей игры. Общий вид этой матрицы представлен в таблице 7.1.

Таблица 7.1 – Платёжная матрица

Строки этой таблицы соответствуют стратегиям игрока А, а столбцы – стратегиям игрока В.

Пусть игрок А выбирает некоторую стратегию А_i, тогда в наихудшем случае (например, если выбор станет известным игроку В) он получит наименьший выигрыш .                                                        (7.1)

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

                                                                 (7.2)

Величина α – гарантированный максимальный выигрыш игрока А, называется нижней ценой игры или максимином.

Стратегия, соответствующая максимуму, называется максиминной стратегией. Игрок В, выбирая стратегию, исходит из следующего: при выборе некоторой стратегии В_j, его проигрыш не превысит максимума из значений элементов j-го столбца матрицы.

                                    .                                   (7.3)

Рассматривая множество β_j для различных значений j, игрок В выберет такое значение j, при котором его максимальный проигрыш минимизируется.

                                                      (7.4)

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

Стратегия, соответствующая минимаксу, называется минимаксной стратегией.

Если α = β = v,                                                                                 (7.5)

то выигрыш игрока А – вполне определённое число, игра называется вполне определённой, а выигрыш v (7.5) называется ценой игры и равен элементу матрицы, который одновременно является наибольшим в своём столбце и наименьшим в своей строке. Этот элемент называется седловой точкой (по аналогии с поверхностью седла, которая искривляется вверх в одном направлении и вниз в другом).

    Седловой точке соответствуют вполне определённые (чистые) стратегии игроков. Совокупность чистых стратегий А^* игрока А и В^* игрока В называют решением игры, которое обладает следующим свойством: если один из игроков придерживается своей оптимальной стратегии, то для другого отклонение его от его оптимальной стратегии не может быть выгодно.

    Пример 7.1. Определить нижнюю и верхнюю цены для игр, заданных платёжными матрицами

    Решение. Все расчёты удобно проводить в таблице, в которой кроме матрицы Р введены столбец α_i и строка β_j (табл. 7.2) и (табл. 7.3).

Таблица 7.2 – Платёжная матрица Р₁′ Таблица 7.3 – Платёжная матрица Р₂′

Вj Аi	В1	В2	В3	В4	αi
A1	4	3	4	2	2
A2	3	4	6	5	3
A3	2	5	1	3	1
βj	4	5	6	5

Вj Аi	В1	В2	В3	В4	αi
A1	1	0	3	5	0
A2	3	2	4	3	2
A3	0	1	– 1	4	–1
βj	3	2	4	5

    Решение. Минимальные значения a_ij в строках матрицы Р₁ равны соответственно (2, 3, 1). Максимальное значение из них равно 3. Следовательно, α₁ = 3 – нижняя цена игры. Для определения верхней цены данной матрицы найдём максимальное значение элементов в столбцах матрицы Р₁. По столбцам имеем (4, 5, 6, 5). Следовательно, β₁ = 4. Поскольку α₁ ≠ β₁, то матрица Р₁ не имеет седловой точки.

    Аналогично, для матрицы P₂ , . Таким образом, α₁ = β₂ = v = 2 – цена игры. Решение данной игры состоит в выборе игроком А стратегии А₂, при этом его выигрыш не меньше 2; для игрока В оптимальной является стратегия В₂, позволяющая ограничить его проигрыш этим же числом.

    а₂₂ = 2 – седловая точка матрицы Р₂. А₂, В₂ – чистые стратегии игроков А и В соответственно. Отклонение одним из игроков от оптимальной стратегии приводит к уменьшению выигрыша (для игрока А) и увеличению проигрыша (для игрока В).

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

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

    Смешанной стратегией S_A игрока А называется применение чистых стратегий А₁, А₂, ..., А_i, ..., А_m с вероятностями р₁, р₂, ..., р_i, ..., p_m, причём . Смешанные стратегии игрока А записываются в виде матрицы

,

или в виде строки .

    Аналогично для игрока В

,

или , где .

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

                                                      α ≤ v ≤ β                                           (7.6)

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

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

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

    Эта теорема имеет большое практическое значение, она даёт конкретные модели нахождения оптимальных стратегий при отсутствии седловой точки. Чем больше размерность матрицы, не содержащей седловой точки, тем сложнее решение. Поэтому в теории матричных игр рассматриваются способы, с помощью которых решение одних игр сводится к решению других, более простых (в частности с помощью сокращения размерности матрицы). Сократить размерность матрицы можно, исключая дублирующие и заведомо невыгодные доминирующие стратегии. Например, в матрице P₂ для игрока В заведомо невыгодной является четвёртая стратегия, так как все значения а_i4 превышают соответствующие значения элементов первого и второго столбца. Четвёртый столбец матрицы можно исключить (игрок В не воспользуется этой стратегией).

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

    Пример 7.2. Сократить размерность матрицы

    Решение. В матрице P₃ для подматриц выполняется условие равенства сумм элементов по строкам и столбцам. Объединяя стратегии А₁ А₂ А₃; А₄ А₅; В₁ В₂; В₃ В₄, получим

    Полученная матрица содержит седловую точку

α = β = 1 = а₁₁.

    Поэтому решение первоначальной игры, заданной матрицей P₃, имеет вид , , т.к. стратегии А₁, А₂, А₃ для игрока А и стратегии В_1, В₂ для игрока В чистые и равноправные. Стратегии А₄, А₅ и В₃, В₄ не применяются. Цена игры равна 1. Оптимальной для игрока А является комбинация стратегий А₁, А₂, А₃, а для игрока В – комбинация стратегий В₁ и В₂. Вероятность применения стратегий А₁, А₂ и А₃ равны между собой (Σ р_i = 1). Аналогично для второго игрока, Σ q_j = 1.

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

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

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

.

    Тот же средний выигрыш получит игрок А, если 2-й игрок применяет стратегию В₂, т.е. . Учитывая, что , получаем систему уравнений для определения оптимальной стратегии  и ценой игры v:

                                                                                  (7.7)

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

                               ,                              (7.8)

и цену игры                                  

                         .                                    (7.9)

    Составляя аналогичную систему уравнений, можно найти оптимальную стратегию для игрока В:

           .    (7.10)

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

    Решение.  Матрица не имеет седловой точки. По формулам (7.8 – 7.11) находим оптимальные стратегии и цену игры: