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



Мы поможем в написании ваших работ!


Мы поможем в написании ваших работ!



Мы поможем в написании ваших работ!


ЗНАЕТЕ ЛИ ВЫ?

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



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

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

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

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

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


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

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

для любых

P SA и Q SB (1)

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

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

, т.е.
V=
(2)

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

,P SA и Q SB (3)

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

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

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

(5)

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


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

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

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

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

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

 

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

 

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

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

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

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

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

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

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


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

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

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

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

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



Последнее изменение этой страницы: 2016-04-23; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.236.117.38 (0.006 с.)