4.4. НЕКОТОРЫЕ ДОСТАТОЧНЫЕ УСЛОВИЯ ОПТИМАЛЬНОСТИ

Поскольку разнообразие особенностей, которое возникает даже в самых типичных задачах, столь велико, что исключается возможность установления теоремы существования, мы применим другой подход — разработаем сначала технику решения задач. Тогда вопрос будет состоять в том, является ли найденное формальное решение — цена игры и соответствующие ей оптимальные стратегии действительным решением задачи, и если то в каком смысле.

Оказывается, что оно является действительным решением в смысле К-стратегий. Это доказывается в теореме 4.4.1. Ее можно применять на различных стадиях процесса решения, каждая из которых состоит в нахождении интеграла основного уравнения, удовлетворяющего надлежащим граничным условиям, таким, как совпадение функций на

Мы сформулируем и докажем теорему 4.4.1 и продемонстрируем ее применение на нескольких примерах. Напоминаем основные допущения: каждая функция непрерывна по всем трем своим векторным аргументам; множества допустимых значений компактны и не зависят от х; будем называть эти множества и

Лемма 4.4.1. Если постоянны, а х принадлежит компактному множеству то равномерно непрерывна по х для всех допустимых постоянных значений

Доказательство. Нужно показать, что для каждого найдется такое что

для всех для которых и всех и Но непрерывна по всем трем своим векторным аргументам на компактном множестве следовательно, равномерно непрерывна на нем. Лемма утверждает частный случай такой непрерывности.

Теорема 4.4.1. Пусть подобласть области в игре степени с терминальной платой, имеющая своей границей область Пусть функция определенная на обладает следующими свойствами-.

1) удовлетворяет основному уравнению (4.3.1);

2) принадлежит классу ,

3) равна на

4) является единственной функцией, обладающей свойствами 1, 2, 3.

Если и -любые функции, доставляющие мини-макс в (4.3.1), то есть цена игры в смысле К-стратегий, а являются оптимальными тактиками, если только вектор х достигает множество из любой начальной точки в

Доказательство. В конце § 2.7 было показано, что изменением масштаба времени можно добиться (существенно не меняя игру), чтобы все модули скоростей в каждой полной вектограмме в были ограничены. Поэтому будем считать, что они не превосходят 1.

Выберем такую тактику для что для каждого х управление минимизирует сумму в уравнении (4.3.1). Пусть применяет некоторую -стратегию, и пусть — его тактика. Игра начинается в точке Зададим и дополним К-стратегию для построением последовательности Будем считать, что играет бесконечно; разумеется, когда достигается, нужно просто урезать предлагаемую схему.

Сначала разобьем время на единичные интервалы В течение интервала точка х не может переместиться относительно начальной точки более чем

на и поэтому х принадлежит некоторому компактному множеству. Поскольку непрерывны в силу второго свойства, из леммы 4.4.1 следует, что функция равномерно непрерывна на этом компактном множестве, когда постоянны, причем если рассматривать как параметры, то равномерно непрерывна также и по ним.

Возьмем такое целое число что если х изменяется меньше, чем на сумма изменится меньше, чем на Разобьем далее интервал на равных частей, присоединив точки деления последовательности На протяжении любого из этих подинтервалов изменяется, как и раньше, менее чем на Каждый подинтервал снова можно разбить на отрезки одной или несколькими точками из К-стратегии для Но поскольку использует управление минимизирующее сумму в (4.3.1) в начале каждого отрезка времени длиной мы имеем

Аргументы являются кусочно-постоянными тактиками К-стратегий игроков, и потому левая часть не достигает за время следовательно, за все время

Теперь рассмотрим траекторию точки х, соответствующую К-стратегиям. В каждом из полученных в конце концов подинтервалов, где обе функции постоянны, траектория является интегралом уравнений движения с этими постоянными аргументами. Таким образом, вся траектория представляет собой «многоугольную» последовательность гладких отрезков. Так как на всей траектории V непрерывна, то на каждом отрезке существует и равна с соответствующими константами Из предыдущего абзаца следует, что за время функция V возрастает меньше чем на следовательно, за все время меньше чем на

По определению и в силу третьего свойства плата будет равна когда х достигает Следовательно, плата меньше, чем Аналогично можно построить последовательность для обеспечивающую плату большую, чем Таким образом, V есть цена игры.

Применения теоремы 4.4.1 могут быть очень разнообразны Пусть, например, и удовлетворяют условиям теоремы Построим другую поверхность в Если использовать эту поверхность так же, как приняв за на значения

полученные в первом решении, то новое решение на стороне поверхности не смежной с будет совпадать со старым Этот принцип позволяет получать решение во всем последовательными этапами. Сингулярные поверхности различного типа можно рассматривать как поверхности относящиеся уже к новому этапу решения.

Каков же основной вывод теоремы? Произойдет ли окончание игры или нет — это вопрос некоторой игры качества, а трактовка таких игр также подпадает под эгиду К-стратегий. Эта тема подробно разбирается в гл. 8, но мы уже здесь должны изложить некоторые предварительные соображения.

Можно рассматривать игры, считая, что один из игроков, скажем желает окончания игры, а его противник не желает. В наиболее интересных случаях, а именно такие и рассматриваются в этой книге, наряду с точками, начинаясь в которых, игра оканчивается, существуют точки, начинаясь в которых, игра может и не окончиться. Множество точек первого типа, т. е. таких, где обладает стратегией, обеспечивающей окончание игры при любом поведении противника, назовем терминальным множеством. Множество точек второго типа, т. е. таких, где может помешать окончанию игры, назовем нетерминальным. Эти два множества разделены поверхностью, которая должна быть полупроницаемой; мы называем ее барьером. Представим себе, что барьер вложен в слой, состоящий из соседних «параллельных» полупроницаемых поверхностей, и определим (временно) гладкую функцию на этом слое, которая равна нулю на барьере, строго убывает в направлении окончания, или -на-правлении, и постоянна на каждой полупроницаемой поверхности. Тогда удовлетворяет тому же самому уравнению (4.3.1), что и V, и потому можно построить К-стратегию для как это было сделано в доказательстве теоремы 4.4.1. Для любой начальной точки расположенной на терминальной стороне и удовлетворяющей условию выберем Для всех х, расположенных на траектории, исходящей из этой точки, получим Тогда какую бы К-стратегию ни применял он не сможет заставить х пересечь барьер и переместиться на нетерминальное множество. Аналогично для начальных точек на другой стороне барьера будет иметь К-стратегию, удерживающую х от перехода в терминальную область.

Как только вопрос о том, происходит окончание или нет, тем или иным путем разрешен, можно применять теорему 4.4 1, приняв за область, состоящую только из терминальных точек. Тогда мы будем знать наверное, что окончание произойдет.

Мы решим здесь много примеров в том смысле, как это обсуждалось в § 4.1, т е. найдем функции В принципе мы должны каждый раз применять теорему 4.4.1, чтобы показать, что действительное решение совпадает с формальным. Но это приведет к монотонным повторениям, поэтому мы дадим здесь ряд простых, но типичных иллюстрации, являющихся вариациями одного и того же примера, которые пояснят многие стороны общего процесса. Цепь этих примеров обязательно нужна для понимания некоторых дальнейших идей. Читатель может бегло просмотреть эти примеры сейчас, возвращаясь к ним снова по мере прочтения следующих глав, а может сам проделать некоторые выкладки в соответствии с изложенными далее указаниями.

Напомним еще раз суть К-стратегий. Когда мы нашли, скажем, функцию и применяем ее как оптимальную тактику, она будет успешно противостоять любой стратегии допускаемой ограничениями. И мы уже можем не делать предположений функционального характера (таких, как кусочная непрерывность, дифференцируемость и т. д.) о стратегиях противника.

Пример В качестве возьмем верхнюю полуплоскость, в качестве — ось х. Вектограмма для изображена на рис. 4.4.1, а. Расположенный в середине ее вертикальный вектор направлен вниз и имеет единичную длину; геометрическое место концов векторов есть горизонтальный отрезок, полудлина его является гладкой положительной функцией. Вектограмма для представляет собой окружность радиуса причем также гладкая положительная функция и всегда меньше и. Кроме того, где с — некоторая константа. Полная скорость точки х есть сумма двух векторов, один из которых принадлежит а другой -вектограмме. Аналитически это означает, что уравнения движения имеют вид

Плата терминальная, на (где Тогда целью будет достичь в точке, наиболее удаленной вправо, а соответственно стремится влево.

Ясно, что всегда будет применять свой крайний правый вектор. (Это значит, что в уравнениях движения.) На рис. 4.4.1,6 этот вектор обозначен Пунктирная линия есть касательная, проведенная из точки X к окружности радиуса

с центром в А Тогда это надлежащим образом ориентированное полупроницаемое направление Если такие направления являются касательными в каждой точке к кривым некоторого семейства (решениям обыкновенного дифференциального уравнения), то эти кривые будут полупроницаемыми

Рис. 4.4.1 (см. скан)

Если теперь каждую из этих кривых мы отметим числом, равным значению в точке встречи кривой с то тем самым получим функцию

Эти заключения, следующие из наших аналитических методов, можно также получить из геометрических соображений Так, лемма 10 2 2, где ситуация очень похожа, помогает усмотреть тот факт, что есть полупроницаемое направление

Кривые постоянных значений V, которые являются также и оптимальными траекториями, могут выглядеть, скажем, как на рис в Функция полученная таким способом,

удовлетворяет четырем условиям теоремы Далее, так как скорость точки х вниз всегда не меньше, чем 1 — с, мы можем быть уверены, что каждая партия окончится Таким образом, здесь не возникает трудностей при использовании теоремы

Пример 4.4.2. Задача та же самая, однако функция здесь другая, она возрастает всюду, кроме некоторого интервала, где она постоянна и равна график ее представтен на рис Это приводит к появлению области в где V постоянна, эта область на рис запирихована, здесь

Рис. 4.4.2

Поскольку для этой области все равны 0, основное уравнение здесь, разумеется, удовлетворяется Любые дают мини-макс и являются оптимальными Вникая в природу этой игры, мы видим, что в заштрихованной области это действительно так Теорема справедлива

Дело здесь просто в том, что, несмотря на то что V единственна, вовсе не обязаны определяться однозначно

Пример 4.4.3. Снова рассматривается та же самая задача, но теперь Тогда будет стремиться пересечь возможно дальше от точки, где возможно ближе к этой точке Очевидно, что для точек лежащих далеко справа, сохраняется предыдущее построение, а для точек, удаленных влево, имеет место симметричное построение, так как здесь использует крайний левый вектор своей вектограммы

Итак, мы построили два семейства траекторий, они изображены на рис Подобные случаи рассматриваются в гл 6, где показывается, что куски траекторий после их пересечения нужно отбросить (считая, что движение по ним начинается от

. Траектории пересекаются по кривой , в каждой точке которой значения для обоих игроков равны (позднее кривая 3) будет названа рассеивающей поверхностью)

Мы можем применить теорему для точек х, расположенных по шобую сторону от кривой , но при этом мы должны за принять часть пространства, расположенную на той же стороне, а за — часть поверхности лежащую с той же стороны от , и саму

Рис. 4.4.3

В качестве берем прежние значения И на оставшейся части поверхности и общее для обеих сторон значение V на кривой 3). Таким образом, выполняются все условия теоремы, и можно пользоваться ее заключениями Заметим, что никакая другая разделяющая кривая, кроме , не дает этого результата

Итак, мы видим, что в начальных точках, лежащих на , у каждого игрока есть два равноценных значения управления Он может выбрать любое из них, применить смешанную стратегию, делая свой выбор с вероятностями Этот вопрос обсуждается в гл 6

Сделаем здесь еще два замечания Мы урезали часть решения основного уравнения; следовательно, не все формальное решение обязано быть ценой игры Более тонкие моменты, связанные с так называемыми экивокальными поверхностями, будут разъяснены в гл. 10

Второе замечание состоит в том, что здесь 3) является сингулярной поверхностью, и хогя непрерывна, ее частные производные на 3, конечно, не существуют. Но оказалось, что при разумном подходе теорему можно применить и к таким задачам, в которых появляются сингулярные поверхности

Пример 4.4.4. Пусть теперь вся плоскость, - положительная часть оси х. Положим как в примере 4.4.1

Новое здесь то, что если начальные точки находятся далеко влево, то х может не попасть на и игра никогда не окончится Интереснее, конечно, чтобы стремился окончить игру, избежать окончания, если возможно, а в противном случае заставить х достичь как можно правее

Мы могли бы охарактеризовать эту ситуацию численно, приписав бесконечную положительную плату случаю, когда игра не оканчивается, но это оказывается скорее пустой формальностью.

Рис. 4.4.4

В этом параграфе мы уже коротко объясняли природу сингулярных поверхностей, названных барьерами, и отсылаем читателя к гл 8, где этот вопрос изложен подробно В данном случае барьером служит «левая» полупроницаемая поверхность (в смысле примера проходящая через О и обозначенная на рис. 4.4.4.

Как было выяснено раньше, если х лежит слева от то имеет К-стратегию, гарантирующую, что х не пересечет следовательно, окончание не произойдет Если х лежит справа от то обладает К-стратегией, которая удерживает х от пересечения и таким образом обеспечивает окончание игры (Относительно начальных точек, лежащих на мы пока ничего не утверждаем

Что касается начальных точек, расположенных правее и выше то, поскольку оба игрока знают о неизбежности окончания, игра здесь становится игрой степени Дальнейшие рассуждения аналогичны рассуждениям в примере только здесь за нужно принять область в ограниченную барьером и поверхностью

Тот факт, то оптимальная стратегия для которая обеспечивает окончание игры, отличается от оптимальной стратегии,

которая минимизирует значение платы, не имеет существенного значения. Он может не заботиться об окончании, пока х не окажется достаточно близко от . (Поскольку нельзя точно определить, что значит «достаточно близко», мы можем считать, что последняя стратегия оптимальна лишь внутри Но если окажется столь неразумным, что попытается избежать окончания, находясь внутри то может не спешить расстраивать его замыслы, пока х не подойдет очень близко к (если это вообще случится), применяя тем временем оптимальную стратегию игры степени. Тогда не только не сможет избежать окончания, но еще будет наказан уменьшением платы.

Снова мы выяснили, что часть формального решения (слева от не имеет отношения к оптимальной стратегии Основным здесь является нахождение терминальной области Рассмотрим еще один подобный пример

Пример 4.4.5. Та же самая задача, что и в 4.4.1, но условия, наложенные на другие В точках пространства У, достаточно удаленных вправо, радиус удовлетворяет старым условиям, а с уменьшением х он возрастает, так что в точках, достаточно удаленных влево, В таких начальных точках уже может распоряжаться перемещением х; если, в частности, он хочет избежать окончания, он всегда может это сделать.

Пусть теперь хочет избежать окончания, а стремится к нему, когда это возможно. Так может быть в точках, достаточно удаленных вправо.

Снова можно отделить терминальные точки от нетерминальных полупроницаемой поверхностью того типа, которая в гл. 8 названа естественным барьером; читатель может непосредственно обратиться к этой главе. Мы не станем здесь приводить какие-либо предварительные подробности, так как это заняло бы слишком много места.

Как только этот барьер известен, дальнейший анализ становится точно таким же, как в предыдущем примере, поэтому не будем повторять его здесь.

Единственное, что мы хотим здесь подчеркнуть, по-видимому, не так уж важно. Во всех предыдущих примерах основную роль играла неизбежность окончания; только в примере 4.4.4 допускалась другая возможность. Не кажутся ли наши примеры искусственными? В первом случае было неизбежным движение вниз; во втором была исключена из отрицательная часть оси х. Мы хотели показать, что наши идеи можно применять и в более «естественных» обстоятельствах.