Тема 4. Нахождение оптимальных смешанных стратегий игры с нулевой суммой

На практике часто приходится сталкиваться с ситуациями, в которых две или более стороны преследуют различные цели. Такие ситуации называются конфликтами. Математическая теория конфликтных ситуаций называется теорией игр.

Парной игрой с нулевой суммой называется игра, в которой участвуют два игрока (две стороны) причем, выигрыш одного игрока равен проигрышу другого. Каждый из игроков может применять стратегии, то есть совокупности определённых правил действий в зависимости от сложившейся ситуации. Если игрок А имеет m стратегий A₁,…,A_m, а игрок B – n стратегий B₁,…,B_n, то говорят, что игра имеет размерность m×n.

Каждая пара стратегий (Ai, Bj) однозначно определяет исход игры, то есть выигрыш aij игрока A ( и проигрыш (- aij) игрока B.

Матрица

P =

называется платежной матрицей игры.

Число

называется нижней ценой игры.

Число

j=1,…n i=1,…,m

называется верхней ценой игры.

Если , то число ν = называется ценой игры.

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

Смешанной стратегией S_A игрока А называется применение его чистых стратегий А₁,…, А_mc вероятностями p₁,…,p_m, то есть

S_A= (

Аналогично определяется смешанная стратегия S_B игрока B:

S_B=

Вероятности p_i или q_jвыражают доли применения игроками A и B соответствующих чистых стратегий A_i или B_j.

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

Рассмотрим игру разности 2×2 с платёжной матрицей

Р= .

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

стратегий находятся из систем уравненений

(4,1)

, (4,2)

где ν – неизвестная цена игры. Рассмотренный метод решения игры называется аналитическим.

Геометрический метод решения базируется на принципах максимина и минимакса при определении нижней и верхней цены игры. На оси Оу и вертикальной прямой, пересекающей ось Ох в точке (1,0), откладываются отрезки, соответствующие элементам aij платёжной матрицы P. Для нахождения оптимальной стратегии на оси Oу и вертикальной прямой откладываются значения соответственно, а для нахождения оптимальной стратегии соответственно. Соединяя точки на этих прямых, как показано на рис. 4.1 и 4.2, находим точку пересечения наклонных отрезков.

у y

a₂₁B₁¹ a₁₂

B₂a₁₂A₂ a₁₂A₁^I

М N

B₁a₁₁ B₂¹ A₁ A₂^I

a₂₂ a₁₁ q₂^*q₁^*

A₁ v A₂ х B₁ v B₂ x

Рис. 4.1 Pис.4.2

Из рис. 4.1 видно, что точка М имеет координаты следовательно, может быть найдена оптимальная смешанная стратегия и цена игры . Аналогично, в соответствии с рис. 4.2 точка N имеет координаты , а значит, можно найти оптимальную смешанную стратегию и цену игры .

Пример 4.1.

Предприятие выпускает скоропортящуюся продукцию, которую можно сразу отправить потребителю (стратегия А₁) или подвергнуть дополнительной обработке для длительного хранения (стратегия А₂). Потребитель может немедленно приобрести продукцию (стратегия В₁) или после длительного периода времени (стратегия В₂), Проверить имеет ли данная игра 2×2 седловую точку и если нет, то найти решение игры в смешанных стратегиях. Матрица затрат (платёжная матрица) Р = .

Решение.

Найдем нижнюю и верхнюю цены игры:

min(1,5;3); min(2;1))=max (1,5;1)=1,5,

= min (max (1,5;2); max(3;1)) = min (2;3) =2

Поскольку , то есть седловая точка отсутствует, необходимо искать решение игры в смешанных стратегиях. Будем искать оптимальную смешанную стратегию S_A^*= аналитическим методом.

Согласно формуле (4.1) имеем

, (4.3)

откуда p₁^*= , p₂^*= , v = .

Таким образом, S_A^*= , а значит, продукции следует сразу отправить потребителю а продукции подвергнуть дополнительной обработке. Оптимальную смешанную стратегию S_B^*= найдем геометрическим методом.

Построим декартову систему координат и выберем одинаковый масштаб на оси Оу и вертикальной прямой, проходящей через точку (1,0), после чего сделаем построение в соответствии с рис. 4.2.

A₁^I

A_{2 2 2}

A₁N

q₂^* q₁^*A₂^ll 1

B₁ v B₂x

Рис.4.3

Из рис. 4.3. видно, что точка N(q₂^*,v) является точкой пересечения прямых A₁A₁^l и A₂A₂^l, соответствующих стратегиях A₁ и А₂ игрока А. Используя вид уравнения прямой на плоскости, проходящей через две заданные точки, логично показать, что прямая А₁А₁¹ проходящая через точки (0; 1,5) и (1; 3), удовлетворяет уравнению y=1,5x+1,5, а прямая , проходящая через точки (0;2) и (1,1), удовлетворяет уравнению у= -х+2. Координата их точки пересечения N – это решение системы уравнений