Автоматика и телемеханика, № 11, 2014
Системный анализ и исследование
операций
© 2014 г. М.А. ГОРЕЛОВ, канд. физ.-мат. наук (griefer@ccas.ru),
А.Ф. КОНОНЕНКО , д-р физ.-мат. наук
(Вычислительный центр РАН, Москва)
ДИНАМИЧЕСКИЕ МОДЕЛИ КОНФЛИКТОВ I. ЯЗЫК МОДЕЛИРОВАНИЯ
Содержится авторская концепция моделирования и анализа динамических игр и приведен обзор наиболее важных с точки зрения изложенной концепции результатов. Описаны основные качественные особенности решений динамических игр. Обзор адресован прежде всего математикам, использующим теорию игр в прикладных исследованиях. Обсуждаются принципы выбора языка описания динамических конфликтов.
1. Введение
В последние годы заметно повышается интерес прикладников к использованию в своих исследованиях теоретико-игровых моделей. Объясняется это как общей логикой развития науки, так и постепенным отходом от практики централизованного планирования в отечественной экономике.
К сожалению, часто приходится сталкиваться с ситуациями, когда авторы статей либо «ломятся в открытые двери», получая кустарными средствами давно известные результаты, либо «бьются головой о стенку», пытаясь решить задачи, заведомо решения не имеющие. Объясняться это может одной из двух причин: либо авторы этих статей не сочли нужным знакомиться с работами предшественников, либо им не удалось разобраться с тем, что было написано ранее.
В первом случае исправить ситуацию вряд ли возможно.
Во втором случае доля вины лежит и на авторах работ по этой тематике. В данном обзоре делается попытка исправить положение. Непонятность работ по теории динамических игр может быть обусловлена ставшим общепринятым слишком формальным стилем изложения. У этого есть свои объективные причины. С одной стороны, при обычном дефиците места авторы частенько опускают содержательные рассуждения, которые не являются необходимыми для формального обоснования полученных результатов, а с другой - многие рецензенты и редакторы неохотно принимают нестрогие формулировки и объяснения «на пальцах». В результате многие важные идеи остаются «между строк».
В данном обзоре делается попытка сосредоточить внимание именно на неформальных обсуждениях, пусть даже в ущерб строгости. Там, где полные доказательства отсутствуют, приводятся ссылки на работы, в которых соответствующие результаты аккуратно обоснованы.
Итак, цель настоящей работы - показать, во-первых, что несмотря на гиперсложность постановки и поиска решения динамической игры на стратегиях с обратной связью, ее решение, как правило, проще, чем решение на простых (исходных) управлениях. Во-вторых, задача все-таки сложна и имеет много «подводных камней». Поэтому неудачный выбор модели и/или небрежность в ее анализе могут привести к отрицательному результату - получению решения, далекого от описываемой ситуации.
В настоящее время число моделей динамических конфликтов, имеющих совершенно различную структуру, весьма велико. Причины этого будут указаны далее. Соответственно очень велико и число полученных результатов. Отразить в обзоре все классы изучавшихся моделей и все полученные результаты невозможно, да и не нужно. В то же время число успешно работающих идей относительно невелико, а полученные качественные выводы не слишком разнообразны. Именно об этих идеях и качественных особенностях пойдет речь далее.
Исходя из сформулированных целей, ссылки даются не на первоисточники, а на наиболее доступные работы, преимущественно на русском языке.
2. Логика игр
Большая часть прикладных работ пишется на так называемом «физическом» уровне строгости. Например, если при поиске решения задачи используются необходимые условия, то формально необходимо доказывать существование этого решения. Другой пример. Поскольку параметры модели чаще всего бывают известны неточно, то для получения надежных выводов необходимо исследовать зависимость решения от этих параметров. Такого рода «мелочи» в прикладных работах обычно опускаются.
И во многих случаях это оправдано. Но оправдано это не особым статусом прикладных работ (по мнению авторов, в таких случаях требования к надежности полученных выводов должны быть особенно жесткими), а опытом исследователя. Обычно математик может быть уверен, что, проделав определенный объем рутинной работы, он сможет получить недостающие выводы.
Когда речь заходит о теории игр, опыт, накопленный в других областях математики, нередко начинает подводить. Происходит это во многом из-за того, что задачи теории игр обычно сложнее задач из других разделов математики. Говоря это, не хочется обижать специалистов из этих областей, так как трудность, важность и красота задач меньше всего определяются разделом математики. Речь идет о вполне конкретных формальных признаках рассматриваемых задач.
В настоящее время уже достаточно широко распространена практика оценки сложности утверждения по числу входящих в него кванторов общности и существования (см., например, [1]). При этом несколько подряд идущих одноименных кванторов считаются за один. Например, большинство утвер-
ждений так называемой «элементарной» математики либо вовсе не содержат кванторов, либо содержат один квантор. Одно из первых утверждений «высшей» математики о непрерывности функции f на множестве X выглядит следующим образом:
Vx е XVe > 035Vy е X : \x - y\ <5 ^ \f (x) - f (y)\ < e.
Это уже достаточно сложное утверждение с тремя кванторами.
Понятно, что одноименные кванторы можно свободно менять местами. А вот изменение порядка разноименных кванторов приводит к новым утверждениям. Например, поменяв местами кванторы в предыдущей формуле, получим формулу
Ve > 035Vx е XVy е X : \х - у\ <5 ^ \ f (х) - f (у)\ < e,
означающую равномерную непрерывность функции f на множестве X.
Разницу между этими понятиями изучают лишь в продвинутых курсах анализа и только после достаточно долгой предварительной работы. В теории игр с такого рода сложными утверждениями приходится сталкиваться с самого начала.
Действительно, практически любой курс теории игр начинается с утверждения
sup inf g(u,v) ^ inf sup g(u,v).
ueuveV veV ueu
В логических символах оно может быть записано так:
Vu е U3v е VVy е VЭх е U : g(u, v) ^ g(x, y).
Уже здесь видно многократное чередование кванторов. А в теории динамических игр приходится постоянно работать с многократно повторяющимися минимаксами.
И дополнительные трудности, связанные со спецификой теоретико-игровых задач, начинаются практически сразу. Например, хорошо известно, что если X - компактное топологическое пространство, а f : X ^ R - непрерывная функция, то непременно достигается верхняя грань
sup f (x).
xex
Доказательство соответствующей теоремы совершенно элементарно и, например, в [2] занимает всего несколько строк. А попробуйте разобраться со следующим вопросом. Пусть U и V - компактные топологические пространства, а g : U х V ^ R - непрерывная функция. Верно ли, что достигается нижняя грань в формуле
inf max q(u, v)?
vev ueu v y
В более сложных динамических задачах проблемы оказываются еще более неожиданными. То вдруг в качестве решения нормально, казалось бы,
5 Автоматика и телемеханика, № 11
129
поставленной задачи возникает функция, взаимно однозначно отображающая отрезок на квадрат. То зависимость решения задачи от ее параметров оказывается всюду разрывной. Подобные примеры будут приведены в данном обзоре.
Впрочем, на определенной стадии развития подобные примеры возникают и в других областях математики. Видимо, сходную природу имеют нерекурсивные рекурсивно перечислймые множества в теории алгоритмов [3, 4], открытые М.Я. Суслиным аналитические множества, не являющиеся борелев-скими, в дескриптивной теории множеств [5], неизмеримые по Лебегу множества в теории меры [6] и т.д.
Довольно характерно, что, приближаясь к такого рода результатам, в некоторых областях математики переходят на язык теории игр. Например, на этом языке сформулирована аксиома детерминированности в теории множеств [7], являющаяся альтернативой знаменитой аксиоме выбора.
Раз уж зашла речь о такого рода результатах, стоит отметить, что не приходится рассчитывать на прикладную значимость результатов, которые напрямую зависят, например, от того, будет ли принята аксиома выбора или аксиома детерминированности. Поэтому следует внимательно следить за арсеналом средств, используемых при исследовании.
В этой связи приходится вспомнить давнюю дискуссию между А. Пуанкаре и А.М. Ляпуновым по поводу методологии математического исследования. Напомним, что Ляпунов считал, что «если в некоторых случаях и допустимо пользоваться неясными рассмотрениями, когда желают установить новый принцип, который логически не следует из того, что уже принято, ... однако же невозможно так поступать, когда надо решать определенную задачу (механики или физики), которая поставлена совершенно точно. Эта задача становится тогда проблемой чистого анализа и должна быть решаема как таковая.» (цитируется по [8]). При исследовании моделей игровой динамики так поступать вряд ли разумно. На сегодняшний день трудно сформулировать ясные критерии адекватности построенных моделей. Поэтому разумно постоянно обращаться к содержательным соображениям в процессе исследования задачи с целью проверки этой адекватности, следуя установке Пуанкаре.
Иногда приходится слышать мнения, что использование в прикладных исследованиях столь абстрактных понятий, как топологические пространства, не целесообразно, а можно ограничиться рассмотрением подмножеств обычных евклидовых пространств. Тогда все заумствования будут не нужны, а никаких патологий не встретится. Эти рассуждения не очень убеждают.
Во-первых, приведенные далее примеры показывают, что возникновение патологических конструкций связано не с использованием абстрактных объектов, а со сложной (в указанном выше смысле) логикой теоретико-игровых задач.
Во-вторых, если быть абсолютно честным, то следует обосновывать все гипотезы, лежащие в основе построенных моделей. А наличие евклидовой структуры - это более сильная гипотеза, чем наличие топологии. И ее, как правило, труднее обосновать. А ведь если
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.