XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 45
Текст из файла (страница 45)
Для второго игрока имеем П;=ПИ вЂ” — 2; Пз = Пзг = 2' Пз= П1з = 1, у =1,4; П4 = П14 = 11 л Верхняя цена игры равна П*= П„= 1, а второй игрок располаг т двумя минимаксными стратегиями 3 4. Хз Хз В данном случае верхняя и нижняя цены игры совпадают и равны единице. Это означает, что при и спользовании системой ПВО любой из максиминных стратегий она гарантированно сбивает один самолет, а при использовании пр отивником любой из своих минимаксных стратегий, он гарантированно теряет лишь один самолет. В теории игр оптимальность решения связывают с ситуацией, в которой ни одному из игроков невыгодно изменять свою стратегию. В этом случае игра считается стнабняьной, или наяодяилейся в соснзояннн равновесна.
В примере 8.3 рассмотрена игра, для которой нижняя цена равна верхней: П„= шахпппПО = пппшахП, = П'. 1 1 1 Ф Это равенство является проявлением свойсуава усчнойчнвосуан минимаксных (максиминных) с4нрапзеанй. Свойство устойчивости заключается в том, что если один из игроков придерживается своей минимаксной (максиминной) стратегии, то другой игрок никак не может улучшить свое положение, отступая от своей максиминной (минимаксной) стратегии. Игры, в которых нижняя цена равна верхней, занимают особое место в теории игр, их называют нарами с седяовой пзочкой. В платежной матрице любой игры с седловой точкой всегда существует элемент, являющийся одновременно минимальным в своей строке и максимальным в своем столбце.
Такой элемент называется седловой уаочной. Заметим, что седловая точка может быть и не единственной. Так, платежная матрица игры иэ примера 8.3 имеет четыре седловые точки, расположенные на пересечении двух ее последних строк и двух последних столбцов. В играх с седловой точкой общее значение нижней и верхней цены о=П,=П" называют частной ценой игры. Очевидно, что седловой точке соответствует максиминная стратегия первого игрока и минимаксная стратегия второго. До тех пор пока игроки будут придерживаться этих стратегий, выигрыш остается постоянным и равным чистой цене игры. Если второй игрок отклонился от своей минимаксной стратегии, то первый игрок сразу получает преимущество, так как элемент р является минимальным в своей строке и подобное отклонение не может быть выгодным для второго игрока. Проводя аналогичные рассуждения для 8.3. Решение игр с нулевой суммой в смешанных стратегиях 327 32б 8.
ЭЛЕМЕНТЫ ТЕОРИИ ИГР первого игрока, приходим к выводу: в играх с седловой точкой макснмннная стратегия первого игрока и мнннмакснзя стратегия второго являются оптимальными. Поэтому совокупность этих двух стратегий называют решением меры. Из мнннмаксного и макснмннного критериев следует (Х1У], что верхняя цена игры всегда не меньше ее нижней цены, т.е. П, = шах ппп П, < ппп пзах П; = П*, ! ! 1 В причем это неравенство превращается в равенство для игры с седловой точкой. Чтобы убедиться в том, что существуют и игры с нулевой суммой без седловой точки, т.е.
П. < П, достаточно вновь обратиться к примеру 8.2. Пример 8.4. Продолжим анализ игры „три пальца" нз примера 8.2 и определим нижнюю и верхнюю цены игры с помощью платежной матрицы. Для первого игрока имеем Пз = Пзз= Пг — Пзз = — 5, П!*=Пш= — 3 Таким образом, нижняя цена игры равна П, = — 3, и ей соот! ветствует максимннная стратегия Х! первого игрока. Для второго игрока имеем П*,=Пз, =4, Пз=Пзз=4 Пз= Пзз=б Верхняя цена равна П' = 4, и ей соответствуют две мннимаксные стратегии Х!з и Хзз второго игрока. В рассматриваемой игре П = — 3 <4=П*, что означает отсутствие седловой точки. Для наглядности нашего анализа предположим, что каждый нз игроков делает свой ход в порядке очередности. Пусть второй игрок выбрал минимаксную стратегию Х!з.
В ответ на это первый игрок, отступая от своей максимкиной стратегии, может воспользоваться стратегией Х' и выиграет 4. Тогда второй игрок, продолжая игру, реализует вторую мнннмаксную стратегию Хз и выигрывает 5, на что первый игрок отвечает стратегией Хз' и выигрывает 4. Таким образом, если один нз игроков будет придерживаться своей мнннмаксной (максимкиной) стратегии, то другой игрок может улучшить свое положение, отступив от своей макси- минной (мнннмаксной) стратегии. В рассматриваемом случае мнннмаксные (максимннные) стратегии не обладают свойством устойчивости.
В играх двух участников с нулевой суммой выигрыш одного нз ннх равен проигрышу другого. Поэтому, если целью одного нз игроков является максимизация своего выигрыша, то целью другого игрока является минимизация своего проигрыша. Если фиксированная стратегия одного нз игроков (допустнм, первого) не обладает свойством устойчивости, то она не может быть оптимальной, так как в этом случае второй игрок может улучшить свое положение (увелнчнть свой выигрыш нлн уменьшить свой проигрыш) за счет улучшения положения первого игрока. Итак, среди игр двух лнц с нулевой суммой существуют игры без седловых точек.
В таких играх нижняя цена игры строго меньше ее верхней цены, а мнннмаксные и макси минные стратегии не являются оптимальными, т.е. нх совокупность не является решением игры. Анализу подобных нгр и посвящен следующий параграф. 8.3. Решение игр двух участников с нулевой суммой в смешанных стратегиях В теории игр элементы множеств допустимых решений игроков принято называть чистыми стратвееилми. Как мы уже знаем, в иере двух участников с нулевой суммой прн наличии седловых точек решение игры находится в чистых 8.3. Решение игр с нулевой суммой в смешанных стратегивх 329 328 8. ЭЛЕМЕИТЫ ТЕОРИИ ИГР с р е т ат гиях а опт мальными являются максиминная и минимаксная стратегии, На практике в играх двух участников с нулевой суммой гораздо чаще встречается случай, когда седловых точек нет, т.е. верянлл П* и ниж лл П.
цены игры различаются. Если искать Р ешения подобных задач в чистых стратегиях, то в расчете на разумного противника мы должны воспользоваться минимаксным (максиминным) критерием. В этом случае первый игрок гарантирует себе выигрыш, равный нижней цене игры П,. При этом естественное желание первого игрока гарантировать себе выигрыш больше чем П, и естественное желание второго игрока гарантировать себе проигрыш меньше чем П' при использовании чистых стратегий приводят к нарушению стабильности игры, что мы и наблюдали в примере 8.4.
Для преодоления нестабильности игры используют смеиламные стпратпегии, которые заключаются в случайном чередовании чистых стратегий. С вероятностной точки зрения, если р' > Π— вероятность выбора первым игроком чистой е ирь стратегии Хь, й = 1, т, где 1 и~ ~:Рь =1, в=! то его смешанная стратегия — зто т-мерный вектор 1 1 1 8Х! (Р1 Р2 .. Рш) Таким образом, множество смешанных стратегий содержит в себе и все чистые стратегии, так как для любой чистой стратегии Хь можно записать вектор вх„с координатами 1, !со !с; р,-1 = О, ! ф й, Фактически смешанные стратегии представляют собой математическую модель гибкой, изменчивой тактики; при применении этой тактики противник не знает и не может знать заранее, с какой ситуацией ему предстоит столкнуться.
и Р! .2 = 1 п — вероятности выбора первым и вторым игроками чистых стратегий Х,' и Х2, т.е. 8Х! = (Р! Р2 " Рш) смешанная стратегия первого игрока, а 2 т 8Х, — (Р2 Р2 р ) смешанная стратегия второго игрока. При этом р1=Р(Х ] >О, 1=1,т; 1 1=1 ~ р,'=1. Р,'=Р[Х,'] >О, 1 = 1,п; В этом случае платежная матрица игры имеет следующий вид: П„П1, ... Пго (П ) = П21 П22 ... П2о П1П,...П„„ При использовании смешанных стратегий выигрыш первого игрока есть дискретная случайная величина, множество возможных значений которой представлено матрицей (П; ). Игроки выбирают свои смешанные стратегии независимо друг от друга. Поэтому вероятность того, что первый игрок выберет стратегию Х;, а второй игрок — стратегию Х2, равна про- 1 изведению р;Р .
Так как этой паре стратегий соответствует 1 2 выигрыш П, первого игрока, то для определения ожидаемого выигрыша первого игрока и ожидаемого проигрыша второго в случае использования ими смешанных стратегий ех! и вхо достаточно вычислить математическое ожидание дискретной случайной величины. Таким образом, ожидаемый выигрыш 8.3.
Решение нгр с нулевой суммой в смешанных стратегиях 331 ззо 8. ЭЛЕМЕНТЫ ТЕОРИИ ИГР первого игрока (и ожидаемый проигрыш второго игрока) равен т и % % ) 2 р(ВХ глХ ) =~~Р;Р,и;,. )=1 )=1 Мы предполагаем, что в игре участвуют разумные противники. Поэтому первому игроку целесообразно выбирать свою смешанную стратегию, т.е. набор вероятностей р), ! = 1, и), ! выбора чистых стратегий Х;), исходя из условия максимальности своего наименьшего ожидаемого выигрыша. А так как в множестве его смешанных стратегий содержатся и все чистые стратегии, то ожидаемый выигрыш П не может быть мень- 1 ше нижней цены игры безотносительно к действиям второго игрока: П„< П' = шахш)п(~ Р1П,)).
) )=) Второму игроку целесообразно выбирать свою смешанную стратегию, исходя из условия минимальности своего наибольшего ожидаемого проигрыша. Проведя аналогичные рассуждения, мы приходим к выводу о том, что этот проигрыш не может быть больше верхней цены игры: п П* > П = ппп шах(~~ ргП; ). 2 ") з=г При этом можно доказать, что, как и в случае чистых страте- гий, выполняются неравенства П. < П' < П < П'. Мы можем также утверждать следующее. Если вероятности выбора чистых стратегий Р,", ! = 1, т, и Рг", у' =1, и, определяют оптимальные решения игроков, то ожидаемый максиминный выигрыш П) первого игрока и ожидаемый минимаксный проигрыш Пг второго равны между собой и равны ог)сидае- мом меме мерим р = р(вх),вх!) = П = П = лг лл Р! Ру ПИ, ! 2 х ~Ч ~ 1 ° 2* )=1 ум) т 8Х! = (Р) Рг "° Р„) т 8Х) = (Р) Рг " Рт) Известно не так много методов нахождения оптимальных смешанных стратегий в', и в*х„т.е.
оптимальных вероятностей Р,' и Рг* выбора чистых стратегий в играх двух участников с нулевой суммой. Рассмотрим некоторые из них, начав с простейших. П))р)*+Пг)рг*= и, П)2Р) +П22рг)л=и~ Р)! +Р2* 1 откуда при Пы + Пгг ф Пгг+ Пм следует, что ! и„— и, (П)) + Пгг) — (П)2+ Пг) ) ' г (П)! + Пгг) — (П)2+ Пм) ' П))П2г — П)2Пм (и„+ и„) — (и„+ и„) Аналитический метод для игр с платежной матрицей второго порядка.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
