Теорема о геометрической интерпретации множества стратегий игрока В, оптимальных во множестве смешанных стратегий

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

Док-во: Для каждой оптимальной стратегии P⁰=() игрока A из теоремы об оптимальности смешанных стратегий игрока А справедливо неравенство Н(Р⁰, ) V, j=1,…,n.
Н(Р⁰, ) можно переписать как . Тогда , j=1,…,n.

Множество точек P⁰=() m-мерного пространства R^m, координаты i=1,…,m, которых удовлетворяют этому неравенству для фиксированного j {1,…,n}, является замкнутым полупространством, а множество точек P⁰=(), координаты i=1,…,m которых удовлетворяют этому нер-ву для всех j=1,…,n является пересечением конечного числа n замкнутых полупространств и называется выпуклым замкнутым полиэдром.

Так как к тому же множество оптимальных стратегий игрока A ограничено, поскольку оно является подмножеством симплекса всех его смешанных стратегий S_A, то О является выпуклым многогранником (политопом).

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

35. Критерий в терминах множеств смешанных стратегий игроков А и В того, что число V – цена игры в смешанных стратегиях, а P⁰, Q⁰ – стратегии, оптимальные во множестве смешанных стратегий соответственно игроков А и В

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

для любых

P S_A и Q S_B (1)

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

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

, т.е.
V= (2)

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

, P S_A и Q S_B (3)

Т.к. неравенство (3) имеет место при любых P S_A и Q S_B, то ó

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

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

(5)

Из (2) и (5) следует, что V – цена игры, а также справедливость рав-ва , кот. по определению оптимальных стратегий, означает, что и –оптимальные стратегии соответственно игроков А и В.

36. Критерий в терминах множеств чистых стратегий игроков А и В того, что число V – цена игры в смешанных стратегиях, а Р⁰ и Q⁰ – стратегии, оптимальные во множестве смешанных стратегий соответственно игроков А и В

Пусть = и = – множества чистых стратегий игроков А и В.

Для того, чтобы V была ценой игры, Р⁰ и Q⁰- оптимальными стратегиями игроков А и В, необходимо и достаточно выполнение двойного нер-ва
Н(А_i, Q⁰) V≤Н(Р⁰,В_j), i=1,…,m, j=1,…,n (1)

Док-во: пусть справедливо нер-во (2). Т.к. оно имееи место для любых стратегий P S_A и Q S_B, то, в частности, оно справедливо для любых чистых стратегий Р=А_i, i=1,…,m и Q=B_j, j=1,…,n, т.е. справедливо нер-во (1). Теперь докажем, что из нер-ва (1) следует нер-во (2). Пусть имеет место (1). Используя формулы и равенства получим

P S_A и Q S_B, т.е. справедливо рав-во (2)

 

37. Критерий в терминах седловых точек выигрыш-функции того, что число V – цена игры в смешанных стратегиях, а Р⁰ и Q⁰ – стратегии, оптимальные во множестве смешанных стратегий соответственно игроков А и В

 

Для того, чтобы V была ценой игры, а 𝑃⁰, 𝑄⁰ – оптимальными стратегиями соответственно игроков А и В, необходимо и достаточно, чтобы (𝑃⁰, 𝑄⁰) была седловой точкой функции выигрыша 𝐻(𝑃,𝑄) и 𝐻(𝑃⁰, 𝑄⁰)=𝑉

Доказательство:

1) Необходимость. Пусть V – цена игры и 𝑃⁰, 𝑄⁰ – оптимальные стратегии. Следовательно, по необходимой части критерия цены игры и оптимальных смешанных стратегий игроков в терминах множеств смешанных стратегий выполняется неравенство

𝐻(𝑃, 𝑄⁰)≤𝑉≤𝐻(𝑃⁰,𝑄)

Но тогда имеет место неравенство 𝐻(𝑃,𝑄⁰)≤𝐻(𝑃⁰,𝑄⁰)≤𝐻(𝑃⁰,𝑄), 𝑃𝜖𝑆𝐴 и 𝑄𝜖𝑆𝐵, которое означает, что (𝑃⁰, 𝑄⁰) – седловая точка функции выигрыша 𝐻(𝑃,𝑄) (по определению седловой точки).

Так как V – цена игры и 𝑃⁰, 𝑄⁰ – оптимальные стратегии, то равенство 𝐻(𝑃⁰, 𝑄⁰)=𝑉 выполняется по определению.

2) Достаточность. Пусть (𝑃⁰, 𝑄⁰) – седловая точка функции выигрыша 𝐻(𝑃,𝑄) и имеет место равенство 𝐻(𝑃⁰, 𝑄⁰)=𝑉. По определению седловой точки справедливо неравенство 𝐻(𝑃, 𝑄⁰)≤𝐻(𝑃⁰, 𝑄⁰)≤𝐻(𝑃⁰,𝑄), 𝑃𝜖𝑆𝐴 и 𝑄𝜖𝑆𝐵. То есть 𝐻(𝑃, 𝑄⁰)≤𝑉≤𝐻(𝑃⁰,𝑄), 𝑃𝜖𝑆𝐴 и 𝑄𝜖𝑆𝐵. Отсюда по достаточной части критерия цены игры и оптимальных смешанных стратегий игроков в терминах множеств смешанных стратегий вытекает, что V – цена игры и 𝑃⁰, 𝑄⁰ – оптимальные стратегии игроков А и В.

Определения активных и пассивных чистых стратегий и теорема об активных стратегиях

Пусть 𝑃0=(𝑝₁₀,…,𝑝_m0) – оптимальная смешанная стратегия игрока А. В общем случае, некоторые из вероятностей 𝑝₁₀,…,𝑝_m0 могут быть равными нулю. Если 𝑝_i0=0, где i – одно из чисел 1,…,m, то в оптимальной смешанной стратегии 𝑃⁰=(𝑝₁₀,…,𝑝_m0) чистая стратегия 𝐴𝑖 не участвует и потому называется пассивной. Чистые стратегии 𝐴𝑖, входящие в оптимальную стратегию 𝑃0 с положительной вероятностью 𝑝_i0>0, называются активными стратегиями игрока А. Аналогично определяются активные стратегии игрока В.

Теорема (об активных стратегиях). Пусть V – цена игры и 𝑃⁰=(𝑝₁₀,…,𝑝_m0), 𝑄⁰=(𝑞₁₀,…,𝑞_n0) - оптимальные стратегии соответственно игроков А и В. Тогда справедливы следующие утверждения.

1. Для любой активной стратегии 𝐴_k,(𝑘𝜖{1,…,𝑚}) игрока А выполняется равенство 𝐻(𝐴_k,𝑄⁰)=𝑉

2. Для любой активной стратегии 𝐵_l (𝑙𝜖{1,…,𝑛}) игрока В выполняется равенство 𝐻(𝑃⁰,𝐵_l)=𝑉