Основные теоремы матричных игр

Если игрок А выбирает смешанную стратегию , а игрок В смешанную стратегию , то средний выигрыш математическое ожидание выигрыша игрока А (проигрыша игрока В) определится суммой

,

которая может рассматриваться в качестве характеристики выбранных S _А и S _B.

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

. (3.7)

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

. (3.8)

Весьма важным для теории и практики является вопрос о том, связаны ли между собой v _А и v_B. Ответ на него дает теорема о максимине.

Теорема о максимине. В конечной игре двух игроков (коалиций) с нулевой суммой (матричной игре) при имеет место равенство

. (3.9)

Теорема о максимине указывает на существование равновесия для случая v _А= v _B, при и, следовательно, существования оптимальных смешанных стратегий.

Поэтому другая формулировка теоремы о максимине, называемая основной теоремой матричных игр, определяется следующим образом.

Основная теорема матричных игр. Любая матричная игра имеет, по крайней мере, одно оптимальное решение, в общем случае, в смешанных стратегиях и соответствующую цену v.

Обе эти теоремы эквивалентны. Из этих теорем следует, что любая матричная игра имеет цену n. Цена игры n всегда удовлетворяет условию

, (3.10)

т.е. лежит между нижней a и верхней b ценами игры.

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

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

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

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

Теорема об активных стратегиях. Если один из участников матричной игры G (m ´ n) придерживается своей оптимальной смешанной стратегии, то это обеспечивает ему максимальный средний выигрыш, равный цене игры n, независимо от того, какие действия предпринимает другой игрок, если только он не выходит за пределы своих активных стратегий (т.е. пользуется любой из них в чистом виде или смешивает их в любых пропорциях), причём число активных стратегий каждого игрока, входящих в их оптимальные смешанные стратегии, не превосходит L, где L = min(m, n).

Использование данной теоремы позволяет в частности, упрощать решение матричных игр 2´ n и m ´ 2.

3.3.5. Решение матричной игры (2´ 2)

Пусть матричная игра G (2´ 2) имеет платёжную матрицу

Предположим, что игра не имеет седловой точки, т.е. . При наличии седловой точки решение очевидно.

В соответствии с основной теоремой игра имеет оптимальное решение в смешанных стратегиях и , где вероятности применения (относительные частоты применения) чистых стратегий удовлетворяют соотношениям

; (3.11)

. (3.12)

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

, (3.13)

а при использовании игроком В чистой активной стратегии В ₂, выигрыш будет равен

. (3.14)

Уравнения (3.11), (3.13) и (3.14) образуют систему трех линейных алгебраических уравнений с тремя неизвестными: .

Решая её, находим, что

; (3.15)

; (3.16)

. (3.17)

Если игрок В использует свою оптимальную смешанную стартегию, а игрок А – свою чистую активную стратегию А ₁, то цена игры n равна

, (3.18)

а при использовании игроком А чистой активной стратегии А ₂, выигрыш будет равен

. (3.19)

Уравнения (3.12), (3.18) и (3.19) образует систему трех линейных алгебраических уравнений с тремя неизвестными: .

Решая её, находим, что

. (3.20)

. (3.21)

. (3.22)

Естественно, что в обоих случаях цена игры (выражения (3.17) и (3.22)) получилась одна и та же.

Решения системы уравнений (3.15), (3.16), (3.17) и (3.20), (3.21), (3.22), полученные алгебраическим методом, удобно получать и графическим методом (рис. 3.5, 3.6). Для нахождения вероятностей и цены игры n в прямоугольной системе координат по оси абсцисс откладывается вероятность , а по оси ординат – соответствующие этой вероятности – выигрыши игрока А.

Рис. 3.5. Графическое изображение игры для игока А

При , игрок А применяет чистую стратегию А ₂. Если при этом игрок В применяет чистую стратегию В ₁, то выигрыш игрока А равен а ₂₁ (уравнение (3.13)), а если игрок В применяет чистую стратегию В ₂, то выигрыш игрока А равен а ₂₂ (уравнение (3.14)). При , игрок А применяет чистую стратегию А ₁.

Если при этом игрок В применяет чистую стратегию В ₁, то выигрыш игрока А равен а ₁₁, а при применении чистой стратегии В ₂ – а ₁₂. Так как значения лежат в пределах [0, 1], то соединяя крайние точки для стратегий В ₁ и В ₂ (строя графики функций n_А = (a ₁₁ – a ₂₁) p ₁ + a ₂₂₁ и n_А = (a ₁₂ – a ₂₂) p ₁ + a ₂₂, получаем значения выигрышей игрока А для всех промежуточных значений р ₁.

В соответствии с принципом максимина, игрок А должен выбрать такую смешанную стратегию, при которой его минимальный выигрыш максимален. Точка N пересечения отрезков прямых (рис. 3.5) и определяет как оптимальную цену игры n_opt, так и оптимальные вероятности p _1opt и
p _2opt = 1 – p _1opt, соответствующие оптимальной смешанной стратегии игрока А, т.е. дает решения системы уравнений (3.11), (3.13), (3.14).

Для графического решения системы уравнений (3.12), (3.18), (3.19) отложим по оси абсцисс вероятность , а по оси ординат соответствующие этой вероятности выигрыши игрока В:

n_B = (a ₁₁ – a ₁₂) q ₁ + a ₁₂; (3.23)

n_B = (a ₂₁ – a ₂₂) q ₁ + a ₂₂. (3.24)

Решением являются координаты точки М пересечения прямых (рис. 3.6), описываемых уравнениями (2.23) и (2.24): q _1opt; q _2opt = 1 – q _1opt и n_opt.

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

Рис. 3.6. Графическое изображение игры для игрока В

Для игры G (2х2) с седловой точкой геометрическая интерпретация решения может быть представлена, например, следующим образом (рис.3.7).

Стратегия В ₂ игрока В является для него явно невыгодной, так как, применяя её, он в любом случае проигрывает больше, чем при применении стратегии В ₁. В данной игре ; ; , т.е. игра имеет седловую точку N и решается в чистых стратегиях. Игрок А должен применять стратегию А ₁, а игрок В – стратегию В ₁.

Рис. 3.7. Решение игры в чистых стратегиях

На рис. 3.8 показан случай, в котором решением игры для игрока А является чистая стратегия А ₂, а для игрока В – стратегия В ₁. Игра имеет седловую точку N.

Рис. 3.8. Решение игры в чистых стратегиях

Пример. Найти алгебраическим и геометрическим методами решение игры, платёжная матрица которой имеет вид

В данной игре нижняя цена игры a = 1 не равна верхней цене игры b = 3, поэтому игра не имеет седловой точки и, в соответствии с основной теоремой матричных игр, имеет оптимальное решение в смешанных стратегиях.

Для игрока А, в соответствии с формулами (3.15) и (3.16), оптимальные вероятности применения стратегий А ₁ и А ₂ равны

;

.

Для игрока В, в соответствии с формулами (3.20) и (3.21), оптимальные вероятности применения стратегий В ₁ и В ₂ равны

;

.

Таким образом, оптимальные смешанные стратегии игроков ; , а цена игры в соответствии с формулой (3.22) равна

.

Так как , то игра выгодна для игрока А.

Графическое изображение игры для игрока А показано на рис. 3.9.

Рис. 3.9. Графическое изображение игры для игрока А

Нижняя граница выигрыша игрока А определяется ломаной CND. Оптимальное решение, определяется точкой N, и естественно, дает тоже решение, что и алгебраический метод: , .

Геометрическое изображение игры для игрока В показано на рис.3.10.

Рис. 3.10. Графическое изображение игры для игрока В

Оптимальное решение, определяемое точкой М, дает решение , .