КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Критерии и свойства оптимальных стратегий
Тема 3. Лекция 9. Антагонистические игры.
Теорема 1. Пусть V — цена игры, H(P0,Q0) — функция выигрыша, SA и SB— множество смешанных стратегий А и В. 1. Для того чтобы стратегия P0 игрока А была оптимальной необходимо и достаточно, чтобы выполнялось неравенство H(P0,Q) ≥ V (1.) для любого QSB, т.е. выбор игроком А оптимальной стратегии P0 гарантирует ему выигрыш H(P0,Q0), не меньше цены игры V, при любой стратеги Q игрока В. 2. Для того чтобы стратегия Q0 игрока В была оптимальной необходимо и достаточно, чтобы выполнялось неравенство H(P,Q0) ≤ V (2.) для любого РSА, т.е. выбор игроком В одной из своих оптимальных стратегий Q0 гарантирует ему проигрыш не больший цены V, при любой стратеги Р игрока А. Теорема 1 остается в силе, если в ее формулировке множества смешанных стратегий SА и SВ заменить на множество и . А именно имеет место Теорема 2. Пусть V — цена игры, H(P,Q) — функция выигрыша, ={А1,…,Аm} и {В1,…,Вn}— множество чистых стратегий соответственно игроков А и В. 1) Для того чтобы стратегия Р0 игрока А была оптимальной необходимо и достаточно, чтобы Н(Р, Вj)≥ V, j =1, …, n. (10.) 2) Для того чтобы стратегия Q0 игрока В была оптимальной необходимо и достаточно, чтобы Н(Аi, Q0) ≤ V, i =1, …, m. (11.)
В теоремах 1. и 2 критерии оптимальности стратегий сформулированы в предположении, что априори известна цена игры V. В следующей теореме в терминах смешанных стратегий дается критерий решения игры (т.е. совокупности цены игры V и пары оптимальных стратегий Р0 и Q0 соответственно игроков А и В). Теорема 3. Для того чтобы V было ценой игры, а Р0 и Q0 – оптимальными стратегиями соответственно игроков А и В, другими словами, для того чтобы { Р0,Q0, V } было решением игры, необходимо и достаточно выполнение двойного неравенства
(.14) Для любых Р и Q . Аналогично теореме 2 в формулировке 3 множества смешанных стратегий и можно заменить соответственно на множество чистых стратегий = {A1,…,Am}и = {В1,…,Вn}, т.е. справедлива Теорема 4. Для того чтобы V была ценой игры, а Р0 и Q0 – оптимальными стратегиями соответственно игроков А и В, необходимо и достаточно выполнение двойного неравенства: , i =1, …, m, j =1, …, n. (19)
Пример 1. Установить цену игры V и оптимальность смешанных стратегий Р ° = (0,4; 0,6) и Q ° = (0; 0; 0,6; 0,4) для игры с платежной матрицей 2x4
Пример2. Предположим, что в условиях примера 1 мы априори знаем, что V=0,625 –цена игры, а Р0=(3/8,5/8) и Q0(1/4,0,3/4) – оптимальные стратегии. Покажем, как можно воспользоваться достаточной частью теоремы 4 для установления цены игры и оптимальности стратегий игроков. Расположим указанные в примере 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. Тогда по достаточной части теоремы 4 значение V=0,625 является ценой игр, а Р0=(3/8,5/8) и Q0(1/4,0,3/4) – оптимальными стратегиями.
Сформулируем еще один критерий решения игры в терминах седловых точек функции выигрыша.
Теорема 5. Для того чтобы V было оценкой игры, а Р0, Q0 – оптимальные стратегии соответственно игроков А и В необходимо и достаточно, чтобы (Р0, Q0) была седловой точкой функции выигрыша Н (Р, Q) и Н(Р0, Q0)= V (20) Так как теоремы 3, 4, 5 представляют необходимые и достаточные условия решения игры, то они эквивалентны.
Теперь рассмотрим некоторые важные свойства оптимальных стратегий. Пусть Р0=()- оптимальная смешанная стратегия игрока А. В общем случае, некоторые из вероятностей могут быть равными нулю. Если =0, где i- одно из чисел 1,…,m, то в оптимальной смешанной стратегии Р0=() чистая стратегия Аi не участвует и потому называется пассивной.
Чистые стратегии Аi , входящие в оптимальную стратегию Р0 с положительной вероятностью, называется активной. Таким же образом определяются активные стратегии игрока В. Понятно, что оптимальная чистая стратегия является активной. Следующая теорема об активных стратегиях играет существенную роль в решении игр. Теорема 6. (об активных стратегиях) Пусть V – цена игры, Р0=() и Q0=() – оптимальные стратегии соответственно игроков А и В. Тогда 1) Для любой активной стратегии игрока А выполняется равенство (21) 2) Для любой активной стратегии игрока B выполняется равенство (22)
Теорема об активных стратегиях означает, что если один из игроков действует по своей оптимальной смешанной стратегии, то выигрыш не изменится и останется равным цене игры V, при условии, что другой игрок придерживается любой своей чистой активной стратегии.
Заметим, что активная стратегия Ak игрока А, для которой по теореме 6, хотя и выполняется равенство H(Ak,Q0) = V, может не быть оптимальной по причине невыполнения равенства . Аналогичное замечание имеет место и для активных стратегий Вl игрока В.
Теорему 6 эквивалентным образом сформулировать в терминах так называемых «смесей чистых активных стратегий». Определим это понятие. Пусть Р0=() – смешанная оптимальная стратегия игрока А, I – произвольное непустое подмножество множества {>0}= {}: Ai – активная стратегия} номеров активных стратегий игрока А относительно данной смешанной оптимальной стратегии Р0. Смешанная стратегия Р0=() такая, что (33) Называется смесью чистых активных стратегий игрока А. Если, в частности {>0}, то смесь Р0=() активных стратегий называется полной. Если же множество I состоит из единственного номера к, то смесь активных стратегий превращается в активную стратегию Ак Аналогичным образом определяются смеси чистых активных стратегий игрока В. Теорема 7. (о смесях активных стратегий) Пусть V – цена игры, Р0=() и Q0=() – оптимальные смешанные стратегии. Тогда 1) Для любой смеси активных стратегий Р=() игрока А справедливо равенство H(Р,Q0) = V (34) 2) Для любой смеси активных стратегий Q=() игрока В справедливо равенство
Н(Р0, Q) = V (35)
Теорема о смесях активных стратегий говорит о том, что если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры V, если только другой игрок применяет смеси своих стратегий в произвольных пропорциях.
Пример 2.10.5. Рассмотрим игру в примере 2 с оптимальными стратегиями Р0 (= 3/8, = 5/8) и Q0 (=1/4, = 0, = 3/4) соответственно игроков А и В. Множество номеров чистых стратегий В, которые входят в оптимальную стратегию Q0 с положительными вероятностями, J= {1, 3}. Рассмотрим смешанную стратегию Q0 = (=3/5, = 0, = 2/5) игрока В. Поскольку То смешанная стратегия Q является смесью активных стратегий В1и В3 игрока В в пропорциях соответственно 3/5 и 2/5. Тогда, по теореме 7 о смесях активных стратегий,
H(Р,Q0) = V = 0,625.
В этом можно убедиться и прямым подсчетом:
Наконец, отметим, что смесь Q не является оптимальной стратегией игрока В, так как показатель неэффективности стратегии Q отличается от цены игры: > V. В самом деле: Тогда > 0,625 = V.
Дата добавления: 2014-01-04; Просмотров: 2116; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |