Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 58
Текст из файла (страница 58)
у к у В случае шумной дуэли будем иметь шах[п[Р (х, у)=шах(М(1, х); Ф(х); Е(х, 1)). к у к Аналогичное выражение будет и для пппзирР (х, у). у к Докажем теперь, что прн условии монотонности Е (х, и) и М(х, у) и неравенства Е(1, 1)<Ф(1) <М(1, 1) дуэль (бесшумная и шумная) имеет седловую точку (1; 1) и цену игры Ф(1).
Действительно, в силу монотонности при любом уФ1 Р(1, у)=М(1, у))М(1, 1))Ф(1)=Р(1, 1). Наоборот, при любом хФ[ Р(х, 1)=Е(х, 1) <Е(1, 1)< <Ф(1)=Р(1, 1). Таким образом, выполнено Р(х, 1)< Р(1, 1) <Р(1, у), что и доказывает наличие седловой точки (1; !) при цене игры Р(1, 1) =Ф(1). Не углубляясь далее в изучение решений дуэльных ситуаций в чистых стратегиях, перейдем к решению их в смешанных стратегиях. В дальнейшем мы будем предполагать, что дискретный спектр оптимальных стратегий игроков состоит из конечного числа точек, а непрерывная составляющая — дифференцируема.
Если р(х) и л(у) — смешанные стратегии игроков (т. е. законы распределения), то платеж первого игрока можно записать в виде ! ! ! ~Р(х, у)г[р(х)= ~Р(х, у) р'(х)![х+ ~ Р(х„у)Ар(х;) = о о != ! у ! = ~ Е (х, у) р' (х) ![х+ ~ М (х, у) р' (х) сЕх+ 0 у + ~ч.", Р(хо Р) ЛР(х!). (376) (=1 5 2й! ИГРЫ С ВЫВОРОМ МОМЕИТЛ ВРЕМРИИ З71 Здесь х! — точки, в которых имеется конечный скачок р(х), равный (()р(х!). Интегрируя по д(у), получим 1 у )) Р(х, у)Г(р(х)Г(д(у) = ~ ) 7.
(х, у) р'(х)й'(у)(йх((у+ о о 1 ! + Г) ~ М (х, у) р' (х) д' (у) ((х ((у+ о у .(Х )и( и1и()и"~ии(и!)». ) =! (.о т Г' (- Х ~) м(. иг)и( )илии(о)и!=! Р1 ! Ги( (. Х~1м( и)и'(и)ии)ии(*)и. 1=1 о ! Г' +Х[1 (;ь )и(.)и~ (*,)+ + ~ ~ Р(хо ут)йр(х;)й)д(у). (377) Предположим теперь, что игра имеет седловую точку, и пусть р,(х) и ди(у) ее образуют. Тогда пнп ~~ Р(х, у)Г(р,(х)((у(у) = ~~ Р(х, !!)((р,(х)((д,(у), Вол п)ах ~$ Р(х, у)(!р(х)Г(у,(у) = ) ) Р(х, у)(йро(х)((д,(у). Р (Е) Поскольку эти экстремальные свойства р, и до выполнены для любых р (х) и йи(у), то они выполнены тем более и для р(х) и д(х), имеющих те же точки скачков х; и уу и величины скачков (лР,(х!) и Ьйи(У ), что и У фУнкций р,(х) и у,(у).
Но тогда относительно функций р'(х)=~(х) и у'(у) =(р(у) имеем две задачи оптимального управления С ОПтнМаЛЬНЫЛ!И !о(Х) =р,'(Х) И (Ро(У) =йи(у) 372 игуы с пллтвжиыми оункциями члстяого видл [гл. ч 1. Отыскать максимум (здесь Ьд)= Ьдо(у~)) по 7(х) от ! у ! 1 ~ ) Е (х, у) 7 (х) !ро (у) дх Иу+ ~ ~ М (х, у) 7 (х) !ро (у) Нх г(у + оо б у ОЗ ! +Д Лд) ) Е(х, у~)) (х) Нх+ Д Ьд) ~ М (х, уу) ~(х) г(х = о ! ! ! = ~ М(1,у) гр,(у) дух ~ 7(х)Нх+ ~ Ц(Е(хх) — М(хх))гр,(х)— о о о ! к к — ~Е;(х, у)гр,(у)г(у — ~М;(х, у)!ро(у)Ну] ~~(1)Ф+ о о + ~Д Ьг()Р(х, у~)~ 1'(х)) !(х.
(378) ! В силу того, что величина ) 7(х)г(х=1 — Д Ьр7 и, знао чит, фиксирована, первый член остается постоянным. 2. Отыскать минимум по !р(у) от ! у ! ! ~ ) Е(х, у) го(х) !р(у)г(хг(у+ ) ) М (х, у)До(х) гр(у)г(хну+ о о о у Гу! ! +д м ~1 уо, о~оиг~-1го;, ю)юэ~- о .ч ! ! ! = ) Е (х, 1) 7о (х) Их Х ~ !р (у) Иу+ ) Ц(М (у, у)— о о о — Е(у, у))7о(у) — $ Еу(х, у)7о(х)г(х— о — ) М„' (х, У) (о (х) Их) $ <Р (1) г(1+ у о г ! + ~Я ЛррР (хг, у)1 !р (у)) г(у.
(379) $29) иггы с вызовом иоивнт» агвиаия зтз Используя в обоих случаях необходимые условия— принцип максимума Понтрягина †име в первом: ! и-е ([!со с) — ио. осе.!» — сс!Р, есе.сс!ссс — ! м;о, ме.!ссср) хе д хе!со, д,с„)еем, причем ре>0 и — „,'= — $е ~(Ь(~, Г) — М(Г, О) ре(~)— ! — сх'о, ссе,се!си — 1и!о. и!е,сосс1.
о Отсюда ( с есх1! е(се ~~ И (~» ~!) М Рсэ ~!)1сре(~!) Й!— о сГ ! — ~!с!!с„ссе.Ьссс+1и;о„ссе,ьссс~сс,)ес. с, о Но тогда максимум аь достигается при условии и = р') 0 в следующих случаях: а) Если ес Д ос))г(с уг)<) (с-(г ° г!) — М(г !!Иере(г!)с(гх+ о сГ! се -~ с — ! ~|с! о„с! е, ь! сс е ! и! о„„! е, ь! ь~ и„ о с, о то и = ), (8) = О. б) Если и=~,(8) ~0, то с $ лд)г((, у,) = ~ (ь((„г,) — м(~„(,)) р,(г,)ж,+с— о сГ! с, — 'с($с!о, о„ьссеесм,о„есе,ьссс1сс, о с, о 374 иго ы с пллтвжными огпкциамя частного вилл (гл. ч нли, что то же, (Т(1 1) — М(! !))Чо(1)= ! = ~ Р„.
(г, у)сро(г7)г(!7+ ~ч~', Ег))Р„(1, у7), (380) о р=! где Р„(1, у)=Е;(1, у) при у>1, Р„(1, у)=М„'(1, у) прн у(1. Отсюда же следует, что 1~у . Поэтому интервалами, где 7о(1)~0, могут быть только интервалы, не содержащие у„т. е. лежащие между последовательными у.
Совершенно аналогично получим (М(1 1) — 7-(1 1)1!'о(1)= ! ! = ~ Р' (х, 1)7о(х)г(х+ ~~~', ЬР)Р„(хг, 1) (381) о г=! всюду, где <р,(1)ФО, причем интервалы, где !ро(1)~0, не могут содержать хе Из сказанного ясно также, что !р,(1)=0 не удовлетворяет, как правило, (380), а 7о(1)=0 не удовлетворяет 381). Поэтому обычно ннтервалй равенства нулю !р,(1) и ,(1) должны совпадать, равно как н интервалы удовлетворения интегральных уравнений (380) и (381). Фиксируем теперь !'„<р„х! и у7, но будем менять Л!77 н Лрг, оставляя неизменными ! ! м ! „«~ Лр! = 1 — ~ 7о (х) Лх и Д Л!77 — — ! — ~ !ро (у)о(у. о о Тогда векторы Я=(бдЦ и Р=(бро!) образуют в силу оптимальности Р,(х) и йо(У) седловУю точкУ фУнкции м Г' о!г, о!=,г! (1г!*, ы!,ом*)оо!- — о !Г' 1 ! т + Д ~~ Р(хг, У)<Р,(У)бУ~ЛРг+ ~~~, '~~ Р(хп У7)АР!Ад,. (382) $29) ИГРЫ С ВЫВОРОМ МОМЕНТЕ ВРЕМЕНИ 375 Отсюда в качестве необходимых условий, очевидно, имеем, поскольку Гтр) > О и Лд) > О (1 т, 1<1): 1 Д Р(хь у;) бр1+) Р(х, у7)~,(х)1(х=Л=сопз(; (383) ~~.", Р(х1, у1) 640+ ~Р(хн у)1р,(у)1(у=р=сопе(.
о Получим теперь необходимые условия за счет оптимальности выбора х; и ут. Если фиксированы ~„Гр„Лр', и 64), то, поскольку р,(х) и ЕГ,(у) образуют седловую точку, векторы (х1) и у7) образуют, конечно, седловую точку платежа (382). сюда имеем для тех х, и у., которые нс совпадают с О или 1, и таких, что х1~у7'.
1 ) Р (х, у7)~,(х)Г(х+ Д Р,(хп у;)Ьр,'=О, 1 М ~ Р„(хо у)~р,(у)Г(у+ ~~".1 Р„(х1, Уу) 64) =О о (384) Р' — л РГ 1 — ВА 1 — ВН п17 = — и оЧ). )' (х) = Щ (х), ГР(д) =З1РО(д) (385) Нетрудно убедиться, что х,Фуп Действительно, пусть М(хн х,)~Ь(х1. х;) и именно М(хо х1)<7.(хо х1). Тогда, если Р(х;, х;) =Ф(х;) > М(хп х;), то, взяв вместо у ут — 6, получим вместо Р (хо ут) = Ф (х1) величину )Р1(х1, ут — 6)<Ф(х;). Устремляя 6 к О, Едким, что у7 не реалйзует минимум (382). Если же Ф(х,) < 7.(х1, х1), то, взяв вместо х; х; — 6, опять получим противоречие. В случае, когда М (хь х1) = 7.(х„ х1), но не равно Ф (х;), противоречие также очевидно.
Однако разрыв при х=у обязателен, следовательно, х,~у,. Нам осталось лишь получить необходимые условия для 1 1 величин А=) 1',(х)Г(х и В=) 1р,(у)Г(у. о 0 Для этого фиксируем х; и у. и вид ~(х) и Гр(у): 376 итРы с плАтежными ФУнкпиями чАстнОГО ВидА 1Гл. У Очевидно, что платеж (377) имеет седловую точку (1; 1) по переменным й и е, если взято (385). Но отсюда имеем необходимые условия: 1 1 А) ~ ~ Р(х, у)1о(х)(ро(у)с(хс(у+ !', Ьуо ~ Р(х, ус)с'о(х)((х— о о с=! 'о с — — А~.брс) Р(хо у) р.(у)бу— А о — — ~ч~ ~ Р(хсУ) ЛО1(1()1= О, (386) с=! с =1 ) Р(* Р)С(*)АЬ)ФФ вЂ”,дЕА()~Р(К А)С,()~ (- о с =! + ~, Ь р; ~ Р (хс, у) (р (у) с(у— о с — Р(хс, УУ) схрсоч"1=0. (387) 1=1 С=! Совокупность всех указанных необходимых условий позволяет отыскивать подозреваемые на оптимальность р,(х) и ст,(у), не предполагая монотонности М(х, у) и Ь(х, у).
Однако во многих случаях такая монотонность имеется, и это обстоятельство упрощает вид оптимальных р,(х) и а,(у). Действительно, если М„'(х, у)>0; Ь'(х, у)>0; М„'(х, у) < 0; Ц(х, у) (О, то отсюда немедленно следует, что условии (384) невыполнимы. Но это значит, что могут существовать х; и у, разве лишь равные 0 и 1. Таким образом, оптимальные ро(С) и уо(С) имеют вид: в точках 1=0 и 1=1 могут иметься скачки Лро и с)р„ Л(7о и Л(7(; пРи остальных 1 выполнено или Со (с) = Ро (с) = 'ро (с) = уо (1) = Оэ 5 29! игуы с вызовом момвнтл вувмвни 377 или [Е.(Е» Е) — М (Е» Е)) оро (Е) = 1 =- ~ Р„(Е, у)ор,(у)ду+Еву,Р„(Е, О)+Еоу,Р„(Е, 1), (388) о [М (Е, Е) †. (Е, Е)) Ео (Е) = =) Ру(х» Е)Ео(х)««+ЛроРу(О Е)+ бр»Ру(1 Е) (389) а Здесь а — максимальное из таких, что при Е< а Ео(Е) ='Ро(Е) =О.
Предположим теперь, что существует интервал [с, о(! при а < с < о(<1, для которого опять-таки ео(Е)=уо(Е) =О при с(Е(о(. В силу оптимальности р,(Е) имеем при любом у 1 ) Р(х, у)о(ро(х))о, о где о — цена игры. Отсюда из-за равенства р,'(х) = О при с ( х . оЕ и при х(а о 1 Р(«, у)ф~,(х)+) Р(.х. У)ф~.(«)~~о. В частности, справедливо ~ Р (х, у) г(ро (х) + ) Р (х, у) л(ро (х) =о во всех точках непрерывности оро(у) прн а ( у ( с.
Действительно, если бы о 1 ~ Р (х, у) о(ро (х) + ) Р (х, у) е(ро (х) > и л хоть в одной точке непрерывности, то, очевидно, это неравенство оставалось бы справедливым и в некотором 378 иГРы с ПДАтежиыми Фуикциями члстиоГО еидл [Гл, у интервале положительности «р,(у); но тогда было бы и 1 1 У) ф~. (х) ~:йР. (У) ) «1, О О что противоречит оптимальности «р, (у). Но если с 1 о = ~ р (х, у,) «[р, (х) + ~ р (х, у,) «[р, (х) в точках непрерывности «р,(у) при а < у < с, то, очевидно, это же равенство выполнено и при у, — с, т. е. с 1 о= ~ Е,(х, с)с[рс(х)+) М(х, с)«[рс(х). а е Но тогда в силу ЬР' <0 и М;, < 0 имеем, очевидно, с ! ) ) 7. (~, у) «[р, (~) + 1 М (х, у) «[р, (~) прн с < у < «[, а зто противоречит оптимальности р, (х).
Отсюда следует, что с=«[ и, таким образом, при а <1<1. должны выполняться интегральные уравнения (388) и (389), определяющие вид «р, и )О в зависимости о!и а, Ьр„«1«7„ Ьр„«1«71. Добавляя условия (383), (386) и (387), имеем количество условий, в принципе достаточное для определения всех параметров, кроме а. Однако на самом деле условие разрешимости интегральных уравнений (383) — (389) налагает требования и на величину а. Приведем для примера решение дуэли, данной в модели 1Х, поскольку оптимальные чистые стратегии для нее давались уже ранее. Произведя преобразование й« = — 1п х; О, = — 1п у (при 0<х; у<1), приведем рассматриваемую игру к виду (373), где Ь(х, у)=р( — [пх)=р,(х)=Ф(х), М(х, у)=р( — 1пх) 11 — я( — 1пу)) =р,(х) [1 — у«(у)]. э 29! ИГРЫ С ВЫВОРОМ МОМЕНТА ВРЕМЕНИ 379 Будем полагать р,(0)=а,(0)=0 и р,(Ц=а,(Ц=1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
