Критерии и свойства оптимальных стратегий.

В предыдущей лекции оптимальные стратегии P⁰ и Q⁰ соответственно игроков А и В определились в виде упорядоченной пары (P⁰,Q⁰), образующей ситуацию, в которой достигается равенство V=α(P⁰)= β(Q⁰)=H(P⁰,Q⁰). В следующей теореме в терминах цены игры V, функции выигрыша Н и множеств смешанных стратегий формулируются простые категории (необходимые и достаточные условия) оптимальных стратегий каждого из игроков.

Теорема 2.10.1. Пусть V — цена игры, H(P⁰,Q⁰) — функция выигрыша, S_A и S_B— множество смешанных стратегий А и В.

1. Для того чтобы стратегия P⁰ игрока А была оптимальной необходимо и достаточно, чтобы выполнялось неравенство

H(P⁰,Q) ≥ V (2.10.1.)

для любого Q S_B, т.е. выбор игроком А оптимальной стратегии P⁰ гарантирует ему выигрыш H(P⁰,Q⁰), не меньше цены игры V, при любой стратеги Q игрока В.

2. Для того чтобы стратегия Q⁰ игрока В была оптимальной необходимо и достаточно, чтобы выполнялось неравенство

H(P,Q⁰) ≤ V (2.10.2.)

для любого Р S_А, т.е. выбор игроком В одной из своих оптимальных стратегий Q⁰

гарантирует ему проигрыш не больший цены V, при любой стратеги Р игрока А.

Доказательство: докажем утверждение 1.

Необходимость. Пусть P⁰ — оптимальная стратегия игрока А. Тогда, по теореме 2.9.1. фон Неймана показатель эффективности α(P⁰) стратегии P⁰ равен цене игры V [см.(2.9.1.)]:

V= α(P⁰) (2.10.3.)

Рассматривая α(P⁰) как показатель эффективности α(P⁰ ,S_В) стратегии P⁰ относительно множества S_В смешанных стратегий игрока В, будем иметь по определению (2.8.11)

(2.10.4.)

И равенства (2.10.3.) и (2.10.4.) получаем неравенство (2.10.1.) и необходимость доказана.

Достаточность. Пусть для некоторой стратегии P⁰ игрока А выполняется неравенство (2.10.1.). Для доказательства оптимальности стратегии P⁰ достаточно показать равенства

α(P⁰)=V (2.10.5.)

[см.(2.9.1.)].

Так как неравенство (2.10.1.) выполняется для любой стратегии игрока В, то

(2.10.6.)

Но цена игры V равна нижней цене игры , по определению (8.20) которой,

V = = α(P) ≥ α(P⁰) (2.10.7.)

Совокупность неравенств (2.10.6.) и (2.10.7.) эквивалентны равенству (2.10.5.).

Достаточность доказана.

Итак, утверждение 1. даказано.

Докажем утверждение 2. Рассуждения аналогичные.

Необходимость. Пусть Q⁰ является оптимальной стратегией игрока В. Тогда, рассматривая β(Q⁰) как показатель β(Q⁰,S_А) неэффективности стратегии Q⁰ относительно множества S_А смешанных стратегий игрока А, в силу (2.9.1.) и (2.8.12.), будем иметь:

V= β( Q⁰)= β(Q⁰,S_А) = Н(Р, Q⁰),

откуда получаем неравенство (2.10.12.)

Достаточность. Пусть для некоторой стратегии Q⁰) игрока В справедливо неравенство (2.10.2.). Поскольку это неравенство выполняется для любой стратегии Р S_А игрока А, то оно будет справедливо и для Н(Р, Q⁰), т.е.

β( Q⁰)= β(Q⁰,S_А) = Н(Р, Q⁰) ≤ V (2.10.8.)

но (см. (2.8.21.))

(2.10.9.)

Из равенства (2.10.8.) и (2.10.9.) получаем равенство β( Q⁰)= V, которое ( в силу (2.9.1.)) означает, что стратегия Q⁰ является оптимальной.

Теорема 2.10.1. остается в силе, если в ее формулировке множества смешанных стратегий S_А и S_В заменить на множество и . А именно имеет место

Теорема 2.10.2. Пусть V — цена игры, H(P,Q) — функция выигрыша, ={А₁,…,Аm} и {В₁,…,Вn}— множество чистых стратегий соответственно игроков А и В.

1) Для того чтобы стратегия Р⁰ игрока А была оптимальной необходимо и достаточно, чтобы

Н(Р, В_j)≥ V, j =1, …, n. (2.10.10.)

2) Для того чтобы стратегия Q⁰ игрока В была оптимальной необходимо и достаточно, чтобы

Н(А_i, Q⁰) ≤ V, i =1, …, m. (2.10.11.)

Доказательство. Достаточно установить эквивалентность неравенств (2.10.1.) и (2.10.10.).

Докажем эквиваленцию

(2.10.1.) (2.10.10.) (2.10.12.)

Пусть справедливо неравенство (2.10.1.). Так как это неравенство имеет место для любой стратегии Q S_B игрока В, то оно, в частности, будет справедливым и для его чистых стратегий В_j , j =1, …, n, т.е. неравенство (2.10.10.) имеет место. Таким образом, импликация (2.10.1.) (2.10.10.) доказана.

Теперь пусть имеет место неравенство (2.10.10.). Тогда по формуле (2.8.10.) с учетом, что , получим:

, Q S_B ,

т.е. доказано неравенство (2.10.1.). Таким образом, справедлива импликация (2.10.10.) (2.10.1.) и, следовательно, эквиваленция (10.12) доказана.

Теперь докажем эквиваленцию

(2.10.2.) (2.10.11.) (2.10.13.)

Поскольку S_А, то из неравенства (10.2) следует неравенство (10.11). Обратно, пусть справедливо (2.10.11.). Тогда по формуле (1.8.9.) с учетом равенства , будем иметь:

, Р=S_А ,

т.е. справедливо (2.10. 2.).

Таким образом, эквиваленция (2.10.13.) доказана.

Поскольку теоремы 2.10.1 и 2.10.2. дают необходимые и достаточные условия одного и того же утверждения, то они эквивалентны.

Пример 2.10.1. В примере 2.8.1 была рассмотрена матричная игра 2×3 с платежной матрицей

Аi Вj	В1	В2	В3
А1		1/2	5/6
А2		3/4	1/2

А=

И смешанные стратегии Р⁰ = (3/8,5/8) и Q⁰ = (1/4,0,3/4) соответственно игроков А и В. В упражнении 2.9.2 было отмечено, что из примера 2.8.3 по теореме фон Неймана следует оптимальность стратегии Р⁰ и Q⁰. Установим этот факт на основании теоремы 2.10.2.Из примера 2.8.3 вытекает, что цена игры V= = = 0,625.

В примере 2.8.3. были подсчитаны значении функции выигрыша Н(Р⁰, В₁)=0,625; Н(Р⁰, В₂)=0,656; Н(Р⁰, В₃)=0,625, а в примере 2.8.2 — следующие значения функции выигрыша Н(А₁, Q⁰)=0,625; Н(А₂, Q⁰)=0,625.

Таким образом Н(Р⁰, В_j) ≥ V, j =1,2,3, и потому по достаточной части утверждения 1) теоремы 2.10.2 (см.(10.10)), стратегии Р⁰=(3/8,5/8) является оптимальной стратегией игрока А.

Также имеют место неравенства Н(А_i, Q⁰) ≤ V, i =1, 2, ( которые на самом деле являются равенствами) и, следовательно, по достаточной части утверждения 2) теоремы 2.10.2(см. 2.10.11, стратегия Q⁰ = (1/4, 0, 3/4) является оптимальной стратегией игрока В.

Теорема 2.10.2 дает возможность установить геометрическую интерпретацию множества оптимальных стратегий игрока.

Следствие 2.10.1. Множество оптимальных стратегий игрока А является выпуклым многогранником (политопом), содержащимся в симплексе всех смешанных стратегий игрока А.

Множество оптимальных стратегий игрока В является выпуклым многогранником (политопом), содержащимся в симплексе всех смешанных стратегий игрока В.

Доказательство. Для каждой оптимальной стратегии Р⁰ = ( ) игрока А по необходимой части утверждения 1) теоремы 2.10.2 справедливо неравенство (2.10.10), которое в сочетании с формулой 2.8.8 можно переписать следующим образом:

Множество точек Р⁰ = ( ) m – мерное пространство R^m, координаты , i =1, …, m, которых удовлетворяют этому неравенству для фиксированного j {1,…,n}, является (см. пример, 12, с. 27) замкнутым полупространством, а множество точек Р⁰ = ( ), координаты , i =1, …, m, которых удовлетворяют этому неравенству для всех j =1, …, n, является пересечение конечного числа n замкнутых полупространств и называется выпуклым замкнутым полиэдром (12,с.28). А так как к тому же множество оптимальных стратегий игрока А ограничено, поскольку оно является подмножеством симплекса всех его смешанных стратегий , то является выпуклым многогранником(политопом).

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

В теоремах 2.10.1. и 2.10.2 критерии оптимальности стратегий сформулированы в предположении, что априори известна цена игры V.

В следующей теореме в терминах смешанных стратегий дается критерий решения игры (т.е. совокупности цены игры V и пары оптимальных стратегий Р⁰ и Q⁰ соответственно игроков А и В).

Теорема 2.10.3. Для того чтобы V было ценой игры, а Р⁰ и Q⁰ – оптимальными стратегиями соответственно игроков А и В, другими словами, для того чтобы { Р⁰,Q⁰ , V }было решением игры, необходимо и достаточно выполнение двойного неравенства

(2.10.14)

Для любых Р и Q .

Доказательство. Необходимость. Пусть V – цена игр и Р⁰ , Q⁰ – оптимальные стратегии. Тогда необходимой части теоремы 2.10.1. справедливы неравенства (2.10.2) и (2.10.1), которые можно записать в виде двойного неравенства (2.10.14).

Достаточность. Пусть для некоторого числа V и некоторой стратегии Р⁰ игрока А и Q⁰ игрока В выполняется двойное неравенство (2.10.14). Так как это неравенство выполняется для любых Р и Q , то в частности оно будет выполнятся и для Р= Р⁰, Q= Q⁰:

,

Т.е. (2.10.15)

Подставим это значение V в неравенство (2.10.14):

(2.10.16)

Поскольку неравенство (2.10.16) справедливо для любых Р и Q , то

,

Или, в силу (2.8.12) и (2.8.11.)

.

Отсюда по определению верхней и нижней цен игры, получим:

(2.10.17)

Но, по основной теореме матричных игр фон Неймана, и потому из (2.10.17) получаем равенство:

(2.10.18)

Из (2.10.15) и (2.10.18) следует, что V – цена игры, а также справедливость равенства

, которое по определению оптимальных стратегий, означает, что Р⁰ и Q⁰ – оптимальные стратегии соответственно игроков Аи В.

Аналогично теореме 2.10.2 в формулировке 2.10.3 множества смешанных стратегий и можно заменить соответственно на множество чистых стратегий = {A₁,…,A_m}и = {В₁,…,В_n}, т.е. справедлива

Теорема 2.10.4. Для того чтобы V была ценой игры, а Р⁰ и Q⁰ – оптимальными стратегиями соответственно игроков А и В, необходимо и достаточно выполнение двойного неравенства:

, i =1, …, m, j =1, …, n. (2.10.19)

Доказательство. Так же как и в доказанной теореме 10.2 достаточно установить эквивалентность неравенствам (2.10.14) и (2.10.19).

Пусть справедливы неравенства (2.10.14). Так как оно имеет место для любых Р и Q , то , в частности , оно справедливо и для любых чистых стратегий Р= A_i , i =1, …, m, и Q = B_j , j =1, …, n, т.е. справедливо двойное неравенство (2.10.19).

Докажем обратное следствие: (2.10.19) (2.10.14).

Пусть имеет место неравенство (2.10.19). Тогда из него, используя формулы (2.8.9), (2.8.10) и равенство , получим:

,

Т.е. справедливо (2.10.14).

Пример 10.2. Предположим, что в условиях примера 2.10.1 мы априори знаем, что V=0,625 –цена игры, а Р⁰=(3/8,5/8) и Q⁰(1/4,0,3/4) – оптимальные стратегии. Покажем , как можно воспользоваться достаточной частью теоремы 2.10.4. для установления цены игры и оптимальности стратегий игроков.

Расположим указанные в примере 2.10.1 значения функции выигрыша , i =1, 2; , j =1, 2,3, в неубывающем порядке:

0,625; 0,625; 0,625; 0,625; 0,656.

Из этой последовательности очевидно, что выполнение , i =1, 2, j =1, 2,3.

Тогда по достаточной части теоремы 2.10.4 значение V=0,625 является ценой игр, а Р⁰=(3/8,5/8) и Q⁰(1/4,0,3/4) – оптимальными стратегиями.

Сформулируем еще один критерий решения игры в терминах седловых точек функции выигрыша.

Теорема 2.10.5. Для того чтобы V было ценой игры, а Р⁰, Q⁰ – оптимальные стратегии соответственно игроков А и В необходимо и достаточно, чтобы (Р⁰, Q⁰) была седловой точкой функции выигрыша Н (Р, Q) и

Н(Р⁰, Q⁰)= V (2.10.20)

Доказательство. Необходимость. Пусть V-цена игры и Р⁰, Q⁰ – оптимальные стратегии. Следовательно, по необходимой части теоремы 2.10.3 выполняется неравенство (2.10.14). Но тогда, как было доказано и достаточной части теоремы 2.10.3, имеет место неравенство (2.10.16), которое, по определению (2.9.6)означает, что Р⁰, Q⁰ – седловая точка функции выигрыша Н (Р, Q).

Так как V – цена игры и Р⁰, Q⁰ – оптимальные стратегии, то равенство (2.10.20) выполняется по определению (§2.9).

Итак, необходимость доказана.

Достаточность. Р⁰, Q⁰ – седловая точка функции выигрыша Н (Р, Q) и имеет место равенство (2.10.20). По определению (2.9.6) седловой точки справедливо неравенство (2.10.16).Подставив в него равенство (10.20), получим неравенство (2.10.14), из которого, по достаточной части теоремы 2.10.3 вытекает, что V- цена игры, а Р⁰, Q⁰ – оптимальные стратегии соответственно игроков А и В.

Так как теоремы 2.10.3, 1.10.4, 2.10.5 представляют необходимые и достаточные условия решения игры, то они эквивалентны.

Пример 2.10.3. Для установления факта оптимальности стратегий Р⁰=(3/8,5/8) и Q⁰(1/4,0,3/4) и нахождения цены игры в условиях примера 2.8.1 примерим теорему 2.10.5.

Для этого надо сначала установить, что точка (Р⁰, Q⁰) является седловой точкой функции выигрыша Н(Р, Q).

В примере 2.8.1 было подсчитано, что Н(Р⁰, Q⁰)=0,625.

В примере 2.8.2. было подсчитано, что .

По (2.8.12):

.

По (2.8.11):

Таком образом имеем:

Н(Р, Q⁰)=0,625≤0,625= Н(Р⁰, Q⁰)≤ Н(Р⁰, Q), Р и Q .

Последнее неравенство по определению (2.9.6) седловых точек означает, что Р⁰, Q⁰ – седловая точка функции выигрыша Н (Р, Q). Тогда по достаточной части теоремы 2.10.5 стратегии Р⁰, Q⁰ являются оптимальными стратегиями соответственно игроков А и В, а значение Н(Р⁰, Q⁰)=0,625 является ценой игры.

Теперь рассмотрим некоторые важные свойства оптимальных стратегий.

Пусть Р⁰=( )- оптимальная смешанная стратегия игрока А. В общем случае, некоторые из вероятностей могут быть равными нулю. Если =0, где i- одно из чисел 1,…,m, то в оптимальной смешанной стратегии Р⁰=( ) чистая стратегия А_i не участвует и потому называется пассивной. Чистые стратегии А_i , входящие в оптимальную стратегию Р⁰ с положительной вероятностью, называется активной. Таким же образом определяются активные стратегии игрока В. Понятно, что оптимальная чистая стратегия является активной. Следующая теорема об активных стратегиях играет существенную роль в решении игр.

Теорема 2.10.6. (об активных стратегиях) Пусть V – цена игры, Р⁰=( ) и Q⁰=( ) – оптимальные стратегии соответственно игроков А и В. Тогда

1) Для любой активной стратегии игрока А выполняется равенство

(2.10.21)

2) Для любой активной стратегии игрока B выполняется равенство

(2.10.22)

Доказательство: Докажем утверждение 1) теоремы. Допустим противное этому утверждению, т.е. допустим, что найдется активная стратегия А_к игрока А такая, что

(2.10.23)

Так как Q⁰ – оптимальная стратегия игрока В, а V- цена игры, то, по необходимой части теоремы 2.10.2,

(2.10.24)

В частности неравенство (2.10.24) будет справедливым и для i=k, т.е.

Из этого неравенства и предположения (10.23) следует строгое неравенство.

H(A_k,Q⁰) < V (2.10.25)

Так как Ак - активная стратегия, то, по определению, >0 и , тогда из неравенства (2.10.25) получаем

H(A_k,Q⁰) < V (2.10.26)

Для остальных номеров I, отличных от к, из неравенства (2.10.24), учитывая, что =0, имеем

H(A_k,Q⁰) < V, (2.10.27)

Суммируя неравенства 2.10.26 и 2.10.27 и, помня, что , получим

H(A_k,Q⁰) < V = V = V (2/10/28)

Но по формуле (2.8.9)

H(A_i,Q⁰) = Н(Р⁰, Q⁰)

И потому неравенство (2.10.28) можно переписать в виде неравенства

Н(Р⁰, Q⁰)< V

Но так как V – цена игры, Р⁰, Q⁰ – оптимальные стратегии, то, по их определению должно выполняться равенство

Н(Р⁰, Q⁰) = V

Полученное противоречие доказывает утверждение 1) теоремы.

Утверждение 2) доказывается аналогично. В предложении противго утверждению 2) найдется активная стратегия В_l игрока В, для которого

(2.10.29)

Поскольку Р⁰- оптимальная стратегия игрока А, а V- цена игры, то по необходимой части теоремы 2.1.2,

(2.10.30)

Из этого неравенства при j=l и предположения (2.10.29) следует неравенство

H(Р⁰,В_l) > V

Из которого, в силу >0, получаем

H(Р⁰,В_l) > V (2.10.31)

Из неравенства (2.10.30)

H(Р⁰,В_l) ≥ V, j l (2.10.31)

Просуммировав неравенства 2.10.31 и 2.10.31 и, использовав формулу 2.8.10, получим неравенство

Н(Р⁰, Q⁰) = H(Р⁰,В_j) > V = V = V

Которое противоречит равенству Н(Р⁰, Q⁰) = V, определяющему оптимальные стратегии Р⁰ и Q⁰. Утверждение 2) доказано.

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

Заметим, что активная стратегия A_k игрока А, для которой по теореме 2.10.6, хотя и выполняется равенство H(A_k,Q⁰) = V, может не быть оптимальной по причине невыполнения равенства . Аналогичное замечание имеет место и для активных стратегий В_l игрока В.

Пример 2.10.4. Вернемся к игре, рассмотренной в примере 2.8.1. В примере 2.10.3. было установлено, что Р⁰ = ( = 3/8, = 5/8) и Q⁰ = ( =1/4, = 0, = 3/4) являются оптимальными стратегиями, V = 0,625, цена игры.

Так как все стратегии ≥ 0, то по определению, чистые стратегии А₁ и А₂ являются активными стратегиями игрока А, а чистые стратегии В₁ и В₃ - активные стратегии игрока В. Тогда по теореме 2.10.6 об активных стратегиях,

H(A₁,Q⁰) = H(A₂,Q⁰) = V = 0,625

Что подтверждается прямыми вычислениями в примере 8.2, и

H(Р⁰,В₁) = H(Р⁰,В₃) = V = 0,625

Что подтверждается прямыми вычислениями в примере 8.1.

Отметим, что ни одна из этих активных стратегий не является оптимальной, поскольку из платежной матрицы игры для показателей эффективностей активных стратегий игрока А имеем:

< V=0,625; = min {1, ¾, 1/2}= ½ < V = 0.625

Теорему 2.10.6 эквивалентным образом сформулировать в терминах так называемых «смесей чистых активных стратегий». Определим это понятие.

Пусть Р⁰=( ) – смешанная оптимальная стратегия игрока А, I – произвольное непустое подмножество множества { >0}= { }: Ai – активная стратегия} номеров активных стратегий игрока А относительно данной смешанной оптимальной стратегии Р⁰.

Смешанная стратегия Р⁰=( ) такая, что

(2.10.33)

Называется смесью чистых активных стратегий игрока А.

Если, в частности { >0}, то смесь Р⁰=( ) активных стратегий называется полной. Если же множество I состоит из единственного номера к, то смесь активных стратегий превращается в активную стратегию А_к

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

Теорема 2.10.7. (о смесях активных стратегий) Пусть V – цена игры, Р⁰=( ) и Q⁰=( ) – оптимальные смешанные стратегии. Тогда

1) Для любой смеси активных стратегий Р⁰=( ) игрока А справедливо равенство

H(Р,Q⁰) = V (2.10.34)

2) Для любой смеси активных стратегий Q⁰=( ) игрока В справедливо равенство

Н(Р⁰, Q) = V (2.10.35)

Доказательство. Докажем утверждение 1). По формуле 2.8.9

Н(Р⁰, Q) = Н(А_i, Q⁰) = Н(А_i, Q⁰) + Н(А_i, Q⁰) (2.10.36)

Так как Р⁰=( ) – смесь активных стратегий, то = 0 для и потому вторая сумма в правой части равенства 2.10.36 равна 0. В первой части равенства 2.10.36 суммирование ведется по индексу и потому > 0, а, следовательно , А_i, , - активные стратегии игрока А. Тогда, на основании утверждения 1) теоремы 2.10.6 активных стратегиях, Н(А_i, Q⁰) = V, . Поэтому из 2.10.36 получаем неравенство 2.10.34.

H(Р,Q⁰) = V = V = V

Аналогичным образом доказывается утверждение 2). А именно, по формуле 2.8.10.

Н(Р⁰, Q) = Н(А_i, Bj) = Н(Р⁰, Bj) + Н(Р⁰, Bj) = Н(Р⁰, Bj) = V = V = V

Т.е. неравенство 2.10.35 доказано.

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

В доказательстве теоремы 2.10.7 мы использовали теорему 2.10.6. Поэтому теорему 2.10.7 можно считать следствием теоремы 2.10.6. С другой стороны, если смесь в частности представляет собой активную стратегию, то теоремы эквивалентны.

Пример 2.10.5. Рассмотрим игру в примере 2.8 с оптимальными стратегиями Р⁰ = ( = 3/8, = 5/8) и Q⁰ = ( =1/4, = 0, = 3/4) соответственно игроков А и В.

Множество номеров чистых стратегий В, которые входят в оптимальную стратегию Q⁰ с положительными вероятностями, J= {1, 3}.

Рассмотрим смешанную стратегию Q⁰ = ( =3/5, = 0, = 2/5) игрока В. Поскольку

То смешанная стратегия Q является смесью активных стратегий В₁и В₃ игрока В в пропорциях соответственно 3/5 и 2/5. Тогда, по теореме 2.10.7 о смесях активных стратегий,

H(Р,Q⁰) = V = 0,625.

В этом можно убедиться и прямым подсчетом, например, по матричной формуле 2.8.4:

Наконец, отметим, что смесь Q не является оптимальной стратегией игрока В, так как показатель неэффективности стратегии Q отличается от цены игры: > V.

В самом деле, по формуле 2.8.5:

Тогда по формуле 2.8.17:

> 0,625 = V.