Понятие стратегии, оптимальной во множестве смешанных стратегий. Основная теорема матричных игр Дж. Фон Неймана



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


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



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


ЗНАЕТЕ ЛИ ВЫ?

Понятие стратегии, оптимальной во множестве смешанных стратегий. Основная теорема матричных игр Дж. Фон Неймана



Если нижняя и верхняя цены игры в смешанных стратегиях совпадают, то их общее значение V= =v называется ценой игры в смешанных стратегиях, а стратегии и , для которых выполняется равенство называются оптимальными смешанными стратегиями соответственно игроков А и В. Оптимальные смешанные стратегии и обладают тем свойством, что если один из игроков придерживается своей оптимальной стратегии, то противнику невыгодно отклоняться от своей оптимальной стратегии. Обозначим через множества оптимальных стратегий игроков А и В. Очевидно, что множество оптимальных стратегий каждого из игроков является подмножеством множества смешанных стратегий:

, то есть цена игры в смешанных стратегиях не меньше нижней цены игры в чистых стратегиях α и не больше верхней цены игры в чистых стратегиях β.

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

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

v =

 


 

Критерий оптимальности смешанной стратегии игрока А в терминах, задаваемых цены игры в смешанных стратегиях, выигрыш-функции и множества смешанных стратегий игрока В

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

Пусть V-цена игры, Н(Р,Q) – выигрыш-функция, SB– множества смешанных стратегий игрока В.

Для того чтобы стратегия Р0 игрока А была оптимальной, необходимо и достаточно, чтобы выполнялось нер-во Н(Р0,Q) V для любого Q SB, (1)

т.е. выбор игроком А оптимальной стратегии Р0 гарантирует ему выигрыш Н(Р0,Q), не меньший цены игры V, при любой стратегии Q игрока В.

Док-во:

Необходимость.Пусть Р0- опт стратегия игрока А. тогда по т. Фон Неймана показатель эфф-ти α(Р) стратегии Р0 равен цене игры V : (2)

Рассматривая как пок-ль эф-ти стратегии Р0 относит множ-ва SB смеш стр-гий игрока В, будем иметь по опр-нию: (3)

Из равенств (2)-(3)получаем (1)

Достаточность. Пусть для некоторой стр-гииР0 игрока А выполнется нер-во (1)

Для док-ва оптимальности стратегии Р0 достаточно показать справедливость равенства: (4)

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

Но цена игры V равна нижней цене игры , по опр кот. (6)

Совокуп (5) и (6) эквивалентна рав-ву (4).

Достаточность доказана. Теорема доказана.

 

 

Критерий оптимальности смешанной стратегии игрока В в терминах задаваемых цены игры в смешанных стратегиях, выигрыш-функции и множества смешанных стратегий игрока А

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

Пусть V-цена игры, Н(Р,Q) – выигрыш-функция, SA – множества смешанных стратегий игрока А.

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

Н(Р0,Q) V для любого Р SA, (1)

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

Док-во:

Необходимость. ПустьQ0- опт стратегия игрока B. тогда по т. Фон Неймана показатель эфф-ти β(Q)стратегии Q0 равен цене игры V : (2)

Рассматривая как пок-ль эф-ти стратегии Q0 относит множ-ва SA смеш стр-гий игрока A, будем иметь по опр-нию: (3)

Из равенств (2)-(3)получаем (1)

Достаточность. Пусть для некоторой стр-гииQ0 игрока B выполнется нер-во (1)

Для док-ва оптимальности стратегии Q0 достаточно показать справедливость равенства: (4)

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

Но цена игры V равна верхней цене игры , по опр кот. (6)

Совокуп (5) и (6) эквивалентна рав-ву (4).

Достаточность доказана. Теорема доказана.


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

Теорема

Пусть V-цена игры, Н(Р,Q) – выигрыш-функция, = – множества чистых стратегий игрока В.

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

Док-во:

Достаточно установить эквивалентность нер-в
(1) и Н(Р0,Q) V для любого Q SB (2)

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

Теперь пусть имеет место быть нер-во (1). Тогда по ф-ле с учетом того, что получим

Q SB , т.е. доказано нер-во (2). Т.о., справедлива импликация(1)=>(2) => эквивалентны




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

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