Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 47
Текст из файла (страница 47)
! <;<и!=! ' О !=11=! Впрочем, это неравенство нам известно — оно выражает отсутствие необходимости в смеси стратегий для противника, если стратегия Р= (р;» ему известна. Отсюда и гпах ш(п,Е ацр1< шах ш(п~~~' а1/р11!/=о. .» 1<!<т1=! '1 ' Р Е Но из-за (275) максимум в левой части последнего неравенства не может быть и меньше о. Тем самым л л таХ т!П ~ ацр;= т(П ,'~акр!1=О, Р ! л-1~ л1=! ! ="!< Совершенно также показываются и остальные равенства (276). Равенства (276) иногда носят наименование двойного описания игры и позволяют определять о и р'„на 294 теОРемы О Решении АнтАГОнистических иГР [Гл.
Гя определяя д«„и наоборот. С нашей общей точки зрения (276) выражают тот уже нам известный факт, что понятие оптимальной гарантирующей смешанной стратегии Р' = = (рр) оперирующей стороны определяется без предположения о том, что противник будет применять смешанные стратегии. Более того, они противнику и не нужны, если он имеет информацию о выборе Р'=(рД (но, конечно, не о выборе конкретных 1). Новым по сравнению с прежними нашими представлениями об оптимальных гарантирующих смешанных стратегиях является только утверждение, что эти стратегии и максимальный гарантированный результат совпадают с аналогичными понятиями для игры в смешанных стратегиях обоих противников и что этот гарантированный результат совпадает с ценой игры.
Однако это «только» весьма важно и полностью выясняет смысл применения смешанных стратегий, если, конечно, противники не обладают информацией о выборе конкретных чистых стратегий при реализации смешанных. Иногда матричные игры при решении их в смешанных стратегиях могут несколько упрощаться путем использования теорем о доминировании стратегий.
Введем для четкости определение. Вектор а= (и„..., а„) строго доминирует*) вектор р= (р„..., [3„), если а; ) р, для всех « = 1, 2, ..., и. Ймеют место следующие теоремы. Теорема ХЬ. Если в матричной игре [[а;Д 4-я строка строго доминируется выпуклой комбинацией других строк, то [,-я чиспюя стратегия оперирующей стороны не входит ни в одну ее оптимальную смешанную стратегию и, следовательно, может быть вычеркнута из матрицы (при решении игры в смешанных сптратегиях). Теорема Х1.'.
Если в той лге игре 1;й столбец доминирует некоторую выпуклую комбинацию других столбцов, то [,-й столбец может быть вычеркнут из матрицы. Поскольку вторая теорема есть не что иное, как повторение первой для случая, когда оперирующей стороной является противник в антагонистической игре (его ') Легко заметить, что это понятие связано с понятием абсолютного превосходства стратегий, ф 221 гвояствк оптимальных стгктггий 295 матрица противоположна заданной), то достаточно доказать первую. Пусть по условию этой теоремы существует совокупл ность чисел р!)О; Др!=1; р!,=0 такая, что л .(ъ чц для всех 1'(т. Тогда если (дЯ вЂ” оптимальная смешанная стратегия, то имеет место ь! ь Да!„о!ч < ,'»" ~а! р!а!4(шахД'Ца! р;р4=о.
Но тогда в силу теоремы ХХХ1Х чистая стратегия », не входит ни в какую оптимальную смешанную стратегию оперирующей стороны Р', т. е. всегда Р,=О, и, значит, без ущерба для оперирующей стороны эта стратегия может быть выброшена. Следует еще раз подчеркнуть, что при поиске оптимальных гарантирующих чистых стратегий такие стратегии выбрасывать, вообще говоря, нельзя. Так, например, в матрице 1 0 0 1 ! 1 4 4 полусумма первых двух строк доминирует над последней, и при решении в смешанных стратегиях последнюю строку можно выбросить. Однако именно она реализует максимин в чистых стратегиях, т.
е. выбор третьей строки есть оптимальное поведение в чистых стратегиях. При решении игр в чистых стратегиях можно, однако, выбрасывать строку, доминируемую другой строкой 4а не выпуклой комбинацией), ибо такая доминируемая строка никак не может реализовать максимин. Аналогично, конечно, обстоит дело и со столбцами. Все указанные теоремы доказаны для строгого выполнения условий доминирования. Как же обстоит дело со случаем, когда доминирование нестрогое, т.
е. когда доминирование определяется как выполнение условий а,. ° )),? 296 тгоевны о ггшгнни лнткгоннстичгсннх нгг (гл. пс Ясно, что выбрасывание доминируемых строк при этом может привести к уменьшению количества оптимальных стратегий, к потере некоторых из них. Простейший пример доставляют две совершенно равноценные стратегии. Однако цена игры при этом не меняется, и поэтому, если задача состоит в поиске хоть одной оптимальной стратегии, вполне можно выбрасывать и не строго доминируемые строки. Что касается не строго доминирующих столбцов, то в исследовании операций их всегда можно выбрасьмать, поскольку стратегии противника сами по себе нас вообще не интересуют.
Убедимся, что выбрасывание не строго доминируемых строк не меняет цены игры. л Пусть ас„(,~ ~Л,аы для всех ) при Лс)~0; ~ Лс=с. слос ° с ~со Пусть, далее, Р' — оптимальная стратегия. Стратегия Р, дЛЯ котоРой Р,=Р,'+ЛРсо, пРи с~с,; Рс,— — О, дает, очевидно, для любых ) ~ч~ (ро+ ~ о) ~ч~~ ~ро, + о 'я с лс. с~со соос ° о ) ~ рса,~+рс,ас„= Ясрса;гРо. с, с, с=с Но отсюда и о) ппп (,'~~ рсас~) = пип У р,аы)о. сыск~~ ~с~со с ск!к"'' — с Следовательно, вычеркивание со-й стратегии не меняет цены игры, сохраняя хотя бы одну из оптимальных стратегий Р. ф 23. Основная теорема для непрерывных игр Пусть х(и„..., и„) и у(г„..., г„) пробегают множества М и су любой природы, когда и (и„..., и„) и г=(г„..., г ) пробегают соответственно прямые произведения Е, и Е„заданных на прямой множеств Е,,(с(п) и Его (((т). з 231 осноенля ткоккнл для нкпкккывных нгк 297 Пусть, далее, дана игра Р(х, у) такая, что функция Р [х(и;), у(г~)] непрерывна относительно точек [и, г] на прамом пРойзведении Е,ХЕ, всех Енн и Екп котоРые пРимем ограниченными и замкнутыми.
Тогда Р [х(и;), у(гг)] равномерно непрерывна на этом же прямом произведении, и, следовательно, для любого е найдется такое 6, что [Р [х(и;), у(г )] — Р [х(и)), у(г])][(е, как только [ и; — и,'[ < 6; [г — г~[ =" 6 для всех ~ и ]. Возьмем теперь в каждом Е„, и Ео конечное число точек и;, и П, занумерованных в порядке роста так, что для каждого и; найдется хоть одно из и;, (а для каждого г. — П ), удаленное не больше чем на 6. Пусть для каждого е' Енн есть множество точек из Ечн расположенных ближе к и;„, чем к и;...
и не дальше, чем к и~,,, Аналогично определяется Е... Определим теперь функцию Р,(х, у)=Р, [х(и;), у(гг)], положив ее равной Р[х(иц), у(г; )], когда и;ЕЕ,, и г7йЕ,; . Согласно построению очевидно, что [ Р(х, у) — Р,(х, у)[(е, и, следовательно, Р,(х, у) аппроксимирует Р(х, у), так что выполнены все утверждения теоремы ХХ!Х. Но функция Р,(х, у) принимает, очевидно, лишь конечное число значений вслед за конечностью числа множеств Есн и Ео . Более того, очевидно, что в игре с 5 ок' платежом Р,(х, у) все стратегии х, соответствующие векторам и = [иД из прямого произведения множеств Е„, для фиксированных зь эквивалентны между собой и эквивалентны стратегии х...„, соответствующей вектору [и~ ч Точно так же эквивалентны все стратегии у, соответствующие векторам прямого произведения множеств Е,, 'л; для фиксированных Й,, т.
е. эквивалентны стратегии ул„..., ул, соответствующей вектору [г; ). Поэтому без ущерба для обеих сторон в игре с платежом Р,(х, у) могут быть выброшены все стратегии, кроме хн .„и ул,...,л„, для всевозможных з; и йт из ранее определенного конечного числа их значений. 298 тиогимы о гишении антлгонистичкскпх ига [гл. пг Таким образом, игра с платежом Р,(х, у) эквивалентна по своим результатам матричной игре Р, (х.. уе, . а )=-Р(х(игм)у(г! )).
Следовательно, для любого е 5. любая игра Р(х, у), удовлетворяющая указанным выше свойствам, приближенно может быть заменена матричной игрой. Смешанной стратегии Р= р(и) *) при такой замене отвечает, очевидно, смешанная стратегия (р,„...,„~ пря всевозможных в„..., в„, так что р,, ...,,„есть вероят- ность попадания всех и; в соответствующие Еиг придан- ном распределении р(и); это легко проверить, если выпи- сать выражение осреднеиного по закону распределения р(и) платежа Р,(х, у) и учесть кусочную постоянность Р,(х, у).
Точно так же обстоит дело и с соответствием смешан- ных стратегий противника, которые будем обозначать через Я=Я(г). Но для матричных игр доказана основная теорема, т. е. наличие равенства (273). В силу эквивалентности Р,(х, у) и матричной игры доказано, следовательно, и равенство впр [п1Р,(Р, Я) = ш1впрР,(Р, Я). Р о о Р Тогда в силу близости игр с Р(х, у) и Р,(х, у) по тео- реме ХХ1Х имеет место ! впр [п1Р(Р, [е) — впр [и[Р,(Р, Я)~ (е, е е а Г [п1 ви р Р (Р, Я) — [п[ впр Р, (Р, ф~ ( е. и о и Отсюда, очевидно, !. впр гп[Р(Р, [е) — [п[ впр Р (Р, [е)~ ( 2е, у я а и а в силу произвольности е имеем окончательно впрш1Р(Р, ®=[п[впрР(Р, 9)=о.
(279) е о Этим по существу и доказана основная теорема не- прерывньис игр. *) Таким образом, смешанная стратегия над чистыми стратегиями х задается здесь законом распределения и. 5 23! основная ткогкмл длн нвпгззывных нгг 299 Остается лишь убедиться в возможности замены верхней и нижней границы в (279) на максимум и минимум при принятых условиях непрерывности Р[х(иг), у(гу)]. Для доказательства необходимы две леммы из теории законов распределения и интегралов Стилтьеса, которые здесь доказываться не будут, но могут быть по существу найдены в курсах теории вероятностей или в книге Г.
Е. Шилова и Б. Л. Гуревича «Интеграл, мера и производная» *). Ограничимсяихформулировкой для случайных величин. Л е м м а 1. Всякая последовательность функций распределения случайных величин содержит подпоследовательность, сходяищюся к некоторой функции распределения во всякой точке непрерывноспш последней. Лемма 2. Если 6(х) непрерывна на [а, Ь] и Р„..., Є— последовательность функций распределения, сходящаяся к функции распределения Р во всех точках непрерывности Р, пго ь ь 1цп ~ 6(х) йР„(х) = ~ 6(х)НР(х).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
