Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 56
Текст из файла (страница 56)
е) Если бы Р(и)=О и Р()е) > О, то /=е(Р— и)-(-ипри е сколь угодно малых и отрицательных даст Р (7) ( О; но зто противоречит тому, что 7 сколь угодно близка к и, и, значит, ТЕР, поскольку и — внутренняя точка Р. гг 356 иггы с пллтежными вгнкциямя члстного зндл [гл. ч Произведя соответствующую нормировку Р (с соответствующим изменением 6), можно считать Р(и) = 1. По лемме 3 существует такой вектор т[ ~ Е", что Р Я) = Я (ц); Р (Р) = Р (г[).
Тогда в силу неравенства Р(Р))0 мы имеем Р(ц))0. С другой стороны, ЫР(Р)=0, поскольку Р содержит нулевой вектор. Но тогда [г (т[)+6=РЯ)+ба-.[п[Р(Р)=0, т. е. Я(т[)( — 6. Однако по лемме 4 т[Ез, ибо Р(т[)= 'О. Этим и завершено доказательство. Лемма 6. Если для некоторого семейства ([,) и всех т[Ез имеет место зпр[а (ц) ) О, ою при соопметстеующим образом выбранных Л;)О (~чРХ~ — — 1) и гц (1 =1, ..., и+1) функция а+1 ~= ~ч-, принадлежит множеству Р, т. е. ~(в))0.
Доказательство. Для каждого ц~з имеется по условию номер а, при котором 1„(т[) > О. Но если 1а (т[) > 0 для фиксированных а и т[, то можно найти открытое множество, содержащее т[, в котором все еще имеет место строгое неравенство для данного а. Тогда по теореме о покрытиях компактных множеств можно найти конечное покрытие этими открытыми множествами, т. е. конечное семейство (1,.), для которого шахг,(ц) >0 для каждого с т[Ез (т. е. для любого 1[Ел найдется хоть одно из ин для которого ~„,. (т[) ) 0).
Обозначим через [г линейную оболочку семейства (['„,). Множества Р и Я пересекаются, ибо иначе по лемме 5 существовало бы ц, Ез, для которого Я (ц,) ( — 6 и, значит, ~„(ц,) < — 6, т. е. шах Г„,(т[,) (0 вопреки определе- НИЮ (1аи). Множество [г, как образованное из точек ~р;~щ при ~р;=1 (р;) 0), очевидно, ограничено. Нас~~рот, множество Р неограничено, ибо вместе с любой [" содержит все с[ при с > О. Поэтому некоторая граничная точка 1, из Я должна принадлежать и Р. Множество Я есть, очевидно, многогранник в пространстве 2, имеющем размерность (и+ 1). Граница Я состоит из многогранников размерности не выше л; следовательно, такую же размерность имеет грань, к которой принадлежит ~,.
Эта грань является з 28) нггы с выпуклой пльтнжной еьнкцней 857 также линейной оболочкой некоторого подмножества множества ((гч), ибо состоит из точек (1, для которых некоторые фиксированные рг,=О. Но тогда по лемме 1И из 5 27 точка !'е представима в виде и+1 (е= У,)ьг ~ч, где У,)ьг =1, )ьг )О.
) ( / ' У Из )еЕР следует, наконец, что ч~', Рг ~гч (з) = ~, (з) ) О. Лемма 7. Пусть (гр,) — семейство непрерывных выпуклых функций, определенных на выпуклом, ограниченном и замкнутом и-мерном множестве в. Тогда для любого заданного 6 > 0 суи(еспмуют такие аг и Лг, что л+! ХЛ;грег(Ч)) (п1 зпр ~р„(Ч) — 8 гг чег а о+! длл всех ЧЕз, где Лг)0; ДЛ,=-1. Доказательство. Рассмотрим семейство всех линейных функций (!р), удовлетворяющих условию (гр — ~ ] (з) ) 0 для какого-либо а (т.
е. условию (грф — ! )(Ч)) )О при всех Ч~в). Люоеая касательная к гро плоскость удовлетворяет этому условию. Действительно, касательная плоскость к сг„в точке Че=(Чет...Че) опРеделаегсЯ с помощью опоРной гипеР- плоскости к выпуклому '), замкнутому, ограниченному (и+ 1)-мерному множеству Т точек $ = (Ч, !/Ч Е з, !) )гро (Ч)), пРоходЯщей чеРез точкУ (Ч„гРо(Че)), т. е. с помощью линейной связи л ДагЧ,+Ы=г(, ° ) Замкнутость н ограниченность Т следуют на таках же свойств в с учетом непрерыеностн ю,. Выпуклость Т следует не ныпуклостн еню нбо Лгь+(1 — Л) (е Эь ЛФ (Ч1)+(! — Л) Ф (Че)ж(ЛЧь+(! ! ) Че) 358 иггы с пллтзжными функциями '!летного видз [гл. ч облада!ощей свойствами ф а!Ч1+ Ьф„(Ч,) = т[, [п[ (Д атЧт+Ы) = т[=ДатЧт+Ьф„(Ч,) (в силу леммы 1 настоящего раздела такая опорная гиперплоскость всегда существует). В уравнении опорной гиперплоскости всегда можно считать Ь)О (при необходимости можно все коэффициенты умножить на — 1).
Но отсюда, очевидно, при 1=ф„(Ч) ~ арй+ ьф. (ч) ) ~ ар!1 + ьф„(ч,) = т[ = '.«; атч;+ ы (ч), ГЙЧ где 1(Ч) определяется для данного Ч уравнением гиперплоскости и является выражением касательной 1(ч). Отсюда имеем при всех ЧЕз ф. (ч) - 1(ч) =1(ч), что и означает [ф [т[) — 1(т[)) (з))О. Итак, семейство (1з) заведомо содержит все касательные плоскости ко всем тр (т[) при любых ЧЕз. Но тогда при всех т[ба зпр1 (ч)) зпр!р (ч)) с=[п[зпрфи(ч), з ~ а ч и так как касательная к ф„ в точке Ч совпадает с ф„(Ч).
Рассмотрим для некоторого 6 ) О семейство Ф'! = (1„— (с — 6) и). Поскольку для любого ЧЕз зпр1 (Ч)= с, то и а зпр[1 — (с — 6) и|(т[))6) О, и мы находимся в условиях в леммы б. Следовательно, имеются Ц, ..., Х„„такие, что л+! 1= Х ) т1з!(ч))с — 6 т=! з 281 иггы с вы!гуклой пллтежаой еующигй 359 для всех !) Е з. Но если а! соответствуют 11,.
в силу определения (7'), то л+! к+! ;~ ЕЛ(ф„!(т1)) ~ ЦЗ!(О)) с — 6 для всех т!Ез при Л!)О, ~; Л;=1, что и требовалось. 1=! Теперь можно уже доказать вторую часть утверждения теоремы Х1Ч. Семейство функций <р, (у) =г" (х, р) и множество !у', очевидно, удовлетворяют условиям леммы 7. Следовательно, для каждого в > 0 мы можем выбрать (Л,'-) н (х!) так, что ~л+ ! „~ Л!Р(хк., у) ) !п1 зир Р(х, у — е) $=1 уел кум для всех уЕУ, где Л=(Л!) и х~! принадлежат компактным т+1 множествам Е=(Л/Л!~)0, ~ Л;=1) и М. При а- 0 к=! мы можем выбрать для каждого ! предельные точки ЛУ = ( Л1 ) и хУ, удовлепюряющие условиям Л) ) 0; а+! Л'=1; х~ЕМ и 3=1 ки.
1 ~ ЛЗг'(х7, у)) 1п1 зпр г'(х, у) ю=! у!у! кем при всех у~!у'. Поскольку по первой части теоремы 1п1 зпр г (х, у) укл кум есть цена игры о, то, указав смешанную стратегию (Л1), основанную на и+1 чистой стратегии х,' и обеспечивающую получение платежа, не меньше о при любом у, мы уже полностью доказали теорему Х1Ч.
Рассматривая непрерывные игры г (х, у), заданные на скалярных х и у, при 0<х<1 и 0<у<1, Карлик обобщил свойства выпуклых платежей на так называемые обобщенно-выпуклые игры, определение которых 360 игеы с пллтгжиыии ьуикпияии члстного вилл [гл. ч сводится к выполнению для некоторого и неравенства „' У ~)0; 0(х~(1; 0(у(1, (359) ду" или неравенства (О, 0(х(1, 0(у(1. (ЗоО) где закон распределения р, (у) =о «ру<ьь (у) = 1 при у < у~л ', при у Ъ у'„'. Для таких игр (и даже несколько более общих) имеет место следующая теорема. Т е о р е м а Х1Ч1. Пусть дана непрерывная игра г" (х, у), где 0(у(1, а х пробегает компактное множеспмо М любой природы. Если для некоторого п)1 д"г (х, у) , „' У э О, то в оптимальную стратегию первого игрока входят с положительной вероятностью не более чем и чистых стратегий, а в оптимальную стратегию второго игрока — не более чем и/2 чистых стратегий, причем каждая чистая стратегия у, внутренняя для 10; Ц, засчитывается за единицу, а концевые пючки — за половину.
Как и в предыдущей теореме, утверждение для первого игрока оказывается значительно более трудно доказуемым. Ограничимся поэтому доказательством только второй половины теоремы, отослав интересующихся к монографии Карлина. Разумеется, аналогичная теорема имеет место при наличии (360).
Доказательство. Достаточно доказать теорему для случая, когда (359) есть строгое неравенство. В самом деле, если теорема справедлива для таких игр, то для игры с нестрогим условием (359) можно найти последовательность игр с платежами р (х, у), равномерно схо- длЯ (х у) дящимися к Г(х, у), причем „* " ) О.
По предположению в этих играх есть оптимальные стратегии второго игрока вида (л/2) ~р (у) ~ глльььгре т> (у), з 28] яггы с выпхклой платежной еьнкцией 36] Можно найти подпоследовательность т такую„что аь (т!) у1 ]сходятся для всех Й к а, и дь~ 10; Ц при условии, [л!2] что а2) О,,Я~ аь — — 1. 2=! В силу равномерной сходимости (см.
теорему ХХ1Х в $ 18) стратегия [л/2] [р(у) = ~ а„[р„, (у) 2=! будет оптимальной для второго игрока в игре с платежом Р(х, у). Итак, пусть, „' ~ >О (хЕМ; уЕ (О; Ц). Будем Дул предполагать для простоты, что цена игры о=О. Этого всегда можно достигнуть без изменения условий теоремы, вычитая из Р(х, у) соответствующую постоянную. Пусть, далее, ~л(х) — оптимальная стратегия первого игрока и Ь(у)= ) Р(х, у)д[' (х). Очевидно, — „л > О. ФУнкциЯ Ь(У) в 10; Ц может обРа][лл (л] щаться в нуль (с учетом кратности нулей) не более п раз из-за положительности и-й производной.
Действительно, если бы имелся и+ 1 корень, то у Ь'(у) было бы не менее и корней; у Ь" (у) — не менее п — 1-го корня; у Ь'"'(у)— не менее одного, а между тем Ь"о(у)> 0 при всех у. Кроме того, поскольку 1 (х) оптимальна и о=О при всех уЕ 10; Ц, имеем Ь(у)>0. Но тогда любой внутренний корень Ь(у) должен иметь четную кратность (ибо иначе Ь(у) при переходе через корень меняла бы знак). Но поскольку общее число корней с учетом кратности не превышает п, то возможное число различных корней не может превышать 1п/2], если, конечно, корни в концевых точках засчитываются каждый за половину. Пусть, далее, [рл(у) — оптимальная стратегия второго игрока. Тогда ( ~ Р (х, у)[]]".л (х) Йрл (у) = о = О.
Отсюда, поскольку Ь(у) неотрицательна, стратегия !р (у) должна давать отличные от нуля [][у (у) только в тех точках, в которых обращается в нуль функция Ь(д). 362 яггн с пллтзжнымя фгнкцяямя члстного ввдл (гл. ч Так как последних только (л/2), то вторая половина теоремы Х1.Ч! доказана. Следует отметить, что для я=2 последняя теорема является очевидным следствием теоремы Х1.Ч, ибо условие (369) при и = 2 гарантирует выпуклость г'(х, у) по у. Прн п=1 теорема ХЬЧ! есть следствие более общей теоремы из 3 16, так как условие Рэ(х, у))0, т. е.
монотонность платежа по у при всех х гарантирует неизменность знака г'(х, у,) — г" (х, р,) для любой пары у, и у, при изменении х по М. Специальное большое внимание к выпуклым платежам, проявляемое исследователями игр, несомненно, оправдано сравнительной частотой появления таких платежей в практике исследования операций. В тех моделях, которые рассматривались в $ 2, это обстоятельство хорошо видно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
