Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 55
Текст из файла (страница 55)
Докажем это. В силу определения а>ь> имеем для любой р: 350 игьы с пл»темными фьякциями ч»стяого вид» [гл. ч Но отсюда, очевидно, Р, (а>м р>«>) = ш[п Р> (а>«> р) = шах Р> (а, р>«>) а и т. е. (а'", р>«>) — седловая точка и, следовательно, а>м и р>«> — оптимальны. Не следует, конечно, думать, что рассмотренный случай достаточно типичен; скорее, наоборот,— хотя бы одна из критических точек, как правило, не входит в соответствующее из множеств и, ш 3. При решении (353) часто можно использовать следующий прямой прием (конечно, при небольших л> и л). Для каждого а находится множество о(сс) точек [», на котором реализуется пппР,(а, р) (см.
(353)). Точно а так же пусть иф) — множество точек а, на котором реализуется п>ахР,(сс, 5). Если найдена пара а'", рм> такая, а о(ам>) Э Р>«' и ф"') Э а>м то а>»> и р>«> — оптимальные стратегии. Действительно, по определению о(а"') н и ф"'), Р ( <о> [)>е>) ш и Р ( м> Р) шах Р ( Р>«>) а м т. е. (а"', р>«>) — седловая точка игры (353). Отыскание таких а«ц и р>«> может производиться путем нахождения неподвижных точек в преобразовании а — о(а) - (иф)/[) Ео(а)) =и'(а), т. е.
точек, для которых ахи*(а). Аналогично обстоит дело и с поиском р. Действительно, пусть а>«>Еи«(а>«>); тогда найдется ф'>Ес>(а), для кото- рого как раз иф"')Эа"', но тогда пара а'", р>«> и удов- летворяет только что сформулированному свойству. Многочисленные примеры применения этого приема даны в книге Карлина, а также в учебнике Мак-Кинси «Введение в теорию игр» и в книге М. Дрешера «Страте- гические игры». $281 яггы с выпзклой плктвжяой взякцяей 351 в 28. Игры с выпуклой и обобщенно-выпуклой платежной функцией В предыдущих разделах мы довольно часто сталкивались с выпуклыми по у платежными функциями, т.
е. с платежами Р(х, у), удовлетворяющими при любом х е М и 0 < Х < 1 условию Р !х, Ху,+(1 — Х)у,) < ХР(х, у,)+(1 — Х)Р(х, у,) для любых у„и у„принадлежащих множеству стратегий У. Платежи, вогнутые по х, удовлетворяющие неравенству Р(кх, +(1 — к) х„у) ) ХР(х„у)+(1 — к) Р(х„у), приводятся к выпуклым платежам при обычной перемене знака платежной функции и перемене игроков местами. Поэтому в дальнейшем будем рассматривать только выпуклые платежи. Основной результат теории выпуклых платежей принадлежит Карлнну, Бонненбласту и Шэпли (см. монографию Карлина) и утверждает конечность числа чистых стратегий, входящих в оптимальные смешанные стратегии сторон в игре с выпуклым платежом. теорема Х(.Ч.
Пусть Р(х, у) — выпуклый по у платеж, заданный на множествах М и )ч', где М вЂ” компактное замкнутое выпуклое множество любого пространства, а !ч' — замкнутое ограниченное выпуклое множеспыо т-мерного пространства. Если Р(х, у) непрерывна на М хЛГ, то у второго игрока (выбираюи(его у) имеется среди оптимальных стратегий чистая стратегия, а у первого игрока — оптимальная стратегия, соспюящоя не баме чем из (т+ 1)-й чистой стратегии. Цена игры равна ппп шах Р (х, у).
его хам Часть этой теоремы, относящаяся к цене игры и наличию оптимальной чистой стратегии у второго игрока, была уже по существу сформулирована и доказана ввиде теоремы ХЧ для вогнутых по х платежей и теоремы ХЧП для выпуклых $15); доказательство повторять не будем. Стоит только отметить, что приведенное там простое доказательство без изменения переносится на множества М Збй вггы с пллтгжвммя вгнвцвямв члствого ввдл !гл. ч и !Ч любой природы (а не только в конечномерных пространствах); если только они выпуклы и замкнуты, определено понятие смешанных стратегий на них и выполнена основная теорема теории игр (в этом тоже могут быть сделаны некоторые послабления, можно ограничиться при компактности М утверждением (279)). Таким образом, для утверждения о наличии чистой оптимальной стратегии у второго игрока в теореме Х1.Ч не нужна конечномерность !Ч. Иначе дело обстоит со второй частью теоремы †утверждением о том, что у первого игрока есть оптимальная стратегия, состоящая не более чем из т+ 1 чистых стратегий; здесь т-мерность пространства стратегий у использована уже в самом утверждении.
Доказательство второй половины теоремы, видимо, довольно легко получить из теоремы ХХЧП. Покажем это для частного случая, когда оптимальная у, есть внутренняя точка й7. Тогда по упомянутой теореме существуют не более чем (т+1) точка х, и числа р!)Отакие, что !л+ ! '!( р,=1; Р(хиу,)=шахР(х, у,), Х м+! и градиент функции Д р!Р(хп у)=Ф(у) равен нулю при у=у,. Поскольку Ф(у) выпукла, то отсюда следует, что у, реализует ш!и Ф(у). вен Но тогда смешанная стратегия, состоящая в принятии х, с вероятностью рп оптимальна, так как а+! в+! :Я р, Р (хп у) ) ч~~' ,р;Р (х!, у,) = и!ах Р (х, у,) = Гй.! =пппшахР(х, у), у к а последняя величина и есть цена игры.
Дадим теперь полное доказательство, следуя Карлину, на основе нескольких лемм, имеющих и большое самостоятельное значение. Лемма 1. Пусть Х вЂ” выпуклое мнажес«мо (в и-л!ерном пространстве), а «ючка у лежит на границе Х (т. е. ф 28! нггы с ныпкклой пллтгжной вкнкцннй 353 у с Х (Š— Х)). Тогда существует опорная плоскость, проходящая через у, т. е. существует такой ненулевой вектор а, что 1п1 (а, х) = (а, у) = ~ а,уь ««Х г=! Доказательство. Пусть последовательность у' точек„не принадлежащих к Х, такова, что!пп у=у' (по М Ф определению точки на границе). По лемме 1 из 2 27 существуют векторы а, для которых 1п1 (а', х) > (а", у'). «чх Для предельной точки а последовательности а' и для любого хЕХ имеем (а, х) = !пп (а', х) ) 1пп (а , у") = (а, у), У а УЯФ откуда и следует утверждение леммы, поскольку, с другой стороны, уЕХ и, значит, (а, у))1п1(а, х).
«чх Ле м м а 2. Если Х и !« — два выпуклых множества, не имеющие общих внутренних точек, то существует гиперплоскость Н, которая разделяет Х и г, т. е. существуют гпакой ненулевой вектор а и скаляр а, что (а, х) )а для всех х~ Х и (а, у) ~а для всех уа У. Если же Х и !«замкнуты и вообще не имеют общих точек и по крайней мере одно из них ограничено, то существует гиперплоскость, строго разделяющая Х и 1', т. е. (а, х) > а для всех х ч Х и (а, у) ( а для зеехунд У.
Доказательство. Рассмотрим множество Х вЂ” г =(х — у/хЕХ, у~!г). Это множество выпукло вместе с Х и !«и не содержит нулевую точку в качестве внутренней (нбо иначе была бы общая внутренняя точка Х н У). Согласно лемме 1 $27 и лемме 1 настоящего раздела существует а, для которого при всех хЕХ н уау (а, х — у) ~(а, 0)=0. 12 ю, Б. Герм«лев 354 иГРы с плАтежными Функциями члстноГо Вилл [Гл. у Отсюда (а, х) ~(а, у) для любых хЕ Х и уф)'. Вводя а = 1п1 (а, х) ((а, х), получим, очевидно, а) (а, у), у Е 1', хех и, значит, первое утверждение леммы доказано. Во втором случае Х вЂ” Г' замкнуто и не содержит нуля, и поэтому второе утверждение прямо следует из леммы 1 $ 27. Пусть теперь з — компактная выпуклая область в л-мерном пространстве Е", являющаяся областью значений переменной т). Будем рассматривать линейные функции 7(т(), т.
е. те, для которых 7~~ч~" ЛГЧГ)= ч~РЛ;)(т)Г) при ,х'Л;=1. Очевидно, функция 1(Г1) = 1 лннейна; обозначим ее через и. Множество всех линейных функций образует (а+1)-мерное пространство Е, элементы которою будем обозначать через ~. Пространство Ее определим как пространство линейных форм ') (линейных функционалов, равных нулю при ) =О), определенных на Е, а его элементы будем обозначать через Р.
Лемма 3. Если Р(и) =1, то существует такая пачка т)ЕЕ", что Рф=~(т1) для всех ~ЕЕ. Доказательство. ПУсть фУнкции ~ы ..., Г„+, линейно-независимы, причем у,=и. Поскольку эти функции образуют базис Е, то достаточно показать, что система уравнений РИ=6Г(Ч); 1=1, ..., и+1, имеет решение. Но первое уравнение в силу определения и и Р(и) является тождеством. Оставшаяся система н уравнений с л неизвестными — координатами вектора т), имеет решение, нбо )à †линей-независимы (т. е. линейно независимы векторы из коэффициентов этих линейных функций).
Лемма 4. ГИножество Р всех элементов ~ЕЕ, которые неотрицательны на з, вьтукло, замкнуто, содерлсит нулевую функцию, а функцию и содержит в качестве внутренней точки. е) Эги линейные формы равносильны однородным линейным функ циям от коэффициентов линейных фующий 1(~). з 28] иггы с выпуклой платижной еьнкцикй 355 Если обозначить через Р(т)) совокупность всех)(т)) при (ч Р, то область т), для которой Р(т)) >О, совпадает с мнолсеством з.
Доказательство. Первая часть леммы очевидна. Обозначим через 7(з) совокупность всех 7(ч) при т)сз. Пусть т) (з. Тогда в силу леммы 1 8 27 точку т) можно отделить гиперплоскостью от з, т. е. существует линейный функционал )' такой, что 7(т)) <с(7(з). Но тогда ,у — си Е Р и в то же время ( (г)) — си (т)) < О. Следовательно, точка т), не принадлежащая з, не принадлежит н области, где Р(т))~0. Обратное следует из определения Р. Лемма 5.
)7усть Я вЂ” выпуклое ограниченное мнолсество из е., которое не пересекаепгся с определенным выше множеством Р. Тогда найдется такая т(цз и такое 6 > О, что (е(т))( — 6. Доказательство. Так как Я и Р замкнуты, выпуклы, а Я вЂ” ограничено, то по лемме 2 их можно строго разделить некоторой гиперплоскостью, т. е. выбрать Р ц Яе и 6> 0 так, что Р(Я)+6(Р(Р) здесь, как и ранее, Р(Я) — совокупность всех Р(7). при ~ Я). Это соотношение показывает, что множество Р(Р) ограничено снизу, ибо Я, а, значит, и Р Я) вообще ограничены.
Но тогда Р(Р) должно быть неотрицательным. Действительно, Р содержит 7е=О, Р(7,)=0, и если бы существовала 7Е Р, для которой Р()) < О, то для функций ~='я(( — (з) было бы Р((')=яР(7) и Р(() стремилось бы к — оо при й оо. Между тем й((" — 1е)(т))=Ц~(т() при т) Ез, ибо 7ЕР, и потому при любом )г>0 (г(~ — ЯЕР. Таким образом, отсюда следовала бы неограниченность снизу Р(Р). Итак, Р(Р) неотрицательно, н поскольку и — внутренняя точка Р, то неизбежно*) Р(и) > О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
