В работе обсуждаются асимптотические свойства цен в динамических играх и соответствующие им тауберовы теоремы. Рассматриваются предел функций цены в играх с усредненным по большому промежутку платежом при стремлении длины промежутка к бесконечности и предел функций цены в играх с дисконтированным платежом, если ставка дисконта стремится к нулю. Вся динамика игры интерпретируется как отображение, сопоставляющее каждой платежной функции цену соответствующей игры. Анонсируется равномерная тауберова теорема для таких функций цены: при слабых предположениях на отображение, из равномерной сходимости функций цены для одного из семейств (усредненные по промежутку или усредненные с дисконтом) следует равномерная сходимость функций цены для другого семейства, и к тому же пределу. Соответствующее доказательство основано на принципе оптимальности Беллмана. В работе также имеется обширный обзор результатов, полученных для таких пределов.
Тауберовы теоремы возникли в математическом анализе, и изначально под ними понимались теоремы, устанавливающие условия сходимости одного метода суммирования из сходимости другого метода. Первые результаты такого рода были показаны Абелем и Таубером: для сходящихся рядов суммирование по Абелю дает ту же сумму [1], при выполнении некоторых асимптотик если ряд суммируем по Абелю, то этот ряд обязан сходиться и к тому же числу [2]. Само название "Тауберова теорема" было впервые использовано Харди (см., например, [3]), установившего следующее соответствие между суммированием по Абелю и суммированием по Чезаро: для ограниченной последовательности из a i , если один из пределов
существует, то существует и другой, и они равны. Теоремы такого типа позволяют, в частности, получать хорошие приближения для суммы ряда, используя более быстрые методы суммирования. О дальнейшем исследовании методов суммирования, как в функциональных, так и в топологических пространствах, см. [4,7,16,36].
Чуть более общий взгляд позволяет посмотреть на тауберовы теоремы как на теоремы, связывающие асимптотики образа интегрального преобразования с асимптотиками прообраза [37], [21,Ch.8]. Такая интерпретация позволила тауберовым теоремам стать базовым инструментом при доказательстве предельных теорем в теории вероятности и в теории случайных процессов (см. [6,Ch 13], [21,Ch.8], [41]); в частности, с помощью таких теорем был показан асимптотический закон распределения простых чисел [37,78]. На этом пути удалось обобщить такие теоремы на локально компактные группы [10]. Еще одна область применения эргодическая теория [8]. Указанная выше тауберова теорема для последовательностей может быть обобщена на функции (см., например, [5,Sect. 6.8]): для ограниченной функции h имеет место равенство пределов среднего по промежутку и среднего с дисконтом (среднее по Абелю, Abel mean, и среднее по Чезаро, Cesaro mean)
если хотя бы один из этих пределов существует. Нас будут интересовать аналоги этих двух тауберовых теорем уже для игровых постановок, равно как и асимптотики цен (оптимальных средних), если усреднение ведется по одной из указанных выше формул. Интерес именно к этим асимптотикам объясняется следующими соображениями. В случае когда горизонт планирования потенциально неограничен, оптимизировать нужно некоторую асимптотику функционала качества, при этом лучше, если эта асимптотика будет числовой характеристикой, в частности окажется конечной. Уже в случае ограниченноcти функции g (фукнции мгновенной полезности), нельзя гарантировать для всех допустимых траекторий z конечность интеграла от h(t) = g(z(t)) при интегрировании по всей положительной оси, то есть нельзя обеспечить и конечность соответствующих цен. С другой стороны, хотя бы верхние и нижние частичные пределы указанных выше выражений для h(t) = g(z(t)) заведомо существуют и конечны. Но тогда именно их и следует оптимизировать.
Эти пределы как объект оптимизации впервые были рассмотрены для марковских управляемых процессов в [11]. В случае конечного числа состояний было показано как существование предела цен (для дисконтированных средних), так и существование стратегии, близкой к оптимальной (Blackwell optimality) сразу при всех достаточно малых дисконтах. Отсюда автоматически, в силу указанной выше тауберовой теоремы, следовало, что такие стратегии близки к оптимальным и для усредненных по промежутку платежей, оптимальные средние по промежутку (цены для усредненных по промежутку платежей) сходятся к тому же пределу. Показать, что предел существует пытались неоднократно, в том числе с помощью уже имеющихся на тот момент тауберовых теорем (см. [9,13]). Для дисконтированных платежей в стохастических играх с конечным числом состояний и действий существование было показано [14] с использованием весьма нетривиального математического аппарата (разложение в ряд Пюизё при помощи принципа Тарского о неподвижной точке). В 1981 наконец была доказана [15] тауберова теорема для стохастической игры двух лиц с конечным числом состояний и действий: оптимальные средние по промежутку и оптимальные средние с дисконтом имеют общий предел. Тем самым для стохастических игр с конечным числом состояний и действий было доказано существование предела оптимальных средних по промежутку.
На этом интерес к тауберовой теореме со стороны игр не затих. В частности, показанные еще во времена Харди утверждения и (контр)примеры были найдены, подробно изучены и опубликованы снова [24,66] вместе с доказательствами в той форме, что была удобна для исследования стохастических игр. Тауберова теорема оказалась для стохастических игр удобным инструментом при доказательстве существования почти оптимальных стратегий, алгоритмов их построения, ограничимся здесь лишь обзорами [23,33,45,67,88]. Последние результаты в этой области см. в [65,71,87].
Еще один смежный для таких постановок вопрос: асимптотические свойства оптимальных и близких к оптимальным стратегий при усредненных по большому промежутку и/или с малым дисконтированием платежах, в частности, возникающие при этом теоремы о магистрали (turnpike phenomenon). Ограничимся в этой связи лишь ссылками на [56,68,74].
При исследовании процессов с непрерывным временем, в теории управления и смежных с ней областях, вопрос существования пределов оптимальных средних (по большому промежутку и/или с малым дисконтированием) возникал неоднократно: стохастические уравнения [12], управление с малым параметром [18], асимптотики уравнений Гамильтона-Якоби [17], теория возмущений [19], задачи управления на бесконечном промежутке [20,22].
С конца 1990-х гг. условия существования пределов оптимальных средних стали исследоваться особенно активно. Несколькими группами, независимо, они были показаны методами слабой КАМ теории (weak KAM-theory) [30,32]; методами теории управления [35]; через условия нерезонансности [29]. Примерно тогда же была доказана первая тауберова теорема для управляемых процессов с непрерывным временем: цены при усреднении с малым дисконтом сходятся равномерно на инвариантном компактном множестве к некоторой константе тогда и только тогда, когда цены при усреднении по большому промежутку сходятся к той же константе равномерно на том же множестве [28].
В эргодическом случае такие пределы существуют и действительно равны константе, сама константа называется при этом критическим значением (additive eigenvalue, или Mane critical value) соответствующего гамильтониана, подробнее см. в [47,58,62,83]. Условие эргодичности можно ослабить, при этом накладываются условия типа коэрцитивности (или равномерной эллиптичности) гамильтониана, управляемости и/или диссипативности самой системы (nonexpansive-like case); не претендуя на полноту, ограничимся лишь [29,34,44,46,47,48]. В эргодическом случае тауберова теорема была показана также и для дифференциальных игр [42].
Отметим, что цены могут не сходиться к константе даже в задачах управления уже в самых простых случаях [31,52]. Последние результаты о существовании таких пределов цен (прежде всего в случае неэргодичности, но в рамках nonexpansive-like case) см. также в [52,61], [65,Sect. 3.4], [77].
В случае дифференциальных игр пока существование пределов показано или при очень сильных требованиях на систему [39,40,42,47,53,77] или для систем конкретного вида [49].
Как было отмечено в обзоре [50] пятилетней давности, The existence of a limit for large time differential games is certainly one of the main challenges in differential games theory . Любопытно, что в то же самое время, уже в обзоре [51], посвященном дифференциальным играм как методу построения оптимальных решений в повторяющихся играх (идея не нова, смотрите, например, в [26]), в отдельный параграф были выделены найденные на тот момент условия для существования (у различных модификаций стохастических игр, у управляемых процессов с дискретным временем) равномерных пределов оптимальных средних. Более свежие результаты о существовании оптимальных средних, о тауберовых теоремах для процессов с дискретным временем см. в [75].
Хотя тауберова теорема для управляемых процессов с дискретным временем -достаточно старый результат [25], на задачи управления с непрерывным временем она была перенесена существенно позже [60]. Полученный в [60] результат примечателен тем, что он показан в максимально общей абстрактной постановке. Фактически [85,86], доказано следующее: пусть для некоторого фазового пространства Ω есть некоторое множество процессов z, замкнутое относительно конкатенации, причем каждое сужение процесса (на бесконечный вправо интервал) также является процессом; пусть также для ограниченной функции g (функции мгновенной полезности), для всякого процесса z можно гарантировать, что реализующийся вдоль него платеж g(z(•)) измерим; если, в этих условиях, хотя бы один предел оптимальных средних (по большому промежутку или при малом дисконтировании) существует при всяком начальном (для z) условии из Ω и равномерен по Ω, то существует и другой предел и эти пределы равны.
Впрочем, как отмечено в [60] для игр, в том числе и дифференциальных: When the dynamic is controlled by two players with opposite goals, a Tauberian theorem is given in the ergodic case by Theorem 2.1 in [42]. However, the general, non ergodic case is still an open problem in both the discrete and the continuous settings .
За прошедшие со времен публикации [60] три года ситуация существенно изменилась, были доказаны тауберовы теоремы:
• для абстрактных динамических игр с нулевой суммой [69],
• для стохастических игр с нулевой суммой [71],
• для антагонистических дифференциальных игр [73],
• для рекурсивных игр (с нулевой суммой) со счетным числом состояний и конечным числом действий для каждого состояния [75] (следует из результата [71]).
В [69] для заданной в духе [60] абстрактной динамической игры был введен ряд аксиом, гарантирующих, в частности, выполнение принципа оптимальности Беллмана и существование близких к оптимальным стратегий. Далее, в явном виде, по близким к оптимальным стратегиям в играх одного семейства (при усреднении по большому промежутку или усреднении с малым дисконтом), строились стратегии для игр другого семейства, гарантирующие там (в случае существования соответствующего равномерного предела) тот же результат. Поскольку существование седловой точки также предполагалось, отсюда автоматически следовала тауберова теорема для таких игр. В [73] тауберова теорема для дифференциальных игр была показана также прямым конструированием соответствующих стратегий (в классе однозначных неупреждающих операторов [38]), соответствующие гарантии также были показаны прямыми оценками.
В [71] рассматривался более любопытный подход. В стохастических играх цена является неподвижной точкой оператора Шепли соответствующей игры (фактически, это пошаговый вариант принципа оптимальности Беллмана). Параметризованные (дисконтом или длиной промежутка) семейства соответствующих операторов Шепли были погружены в некоторые липшицевые семейства нерасширяющихся операторов, для неподвижных точек которых и была показана соответствующая тауберова теорема.
Все указанные выше тауберовы теоремы требовали от игр существования седловой точки. Анонсируемый ниже результат не требует этого.
• непустое множество Ω состояний,
• функция мгновенной полезности g : Ω → [0, 1],
• непустое множество K функций-процессов из R 0 в Ω.
Пусть также отображение t → g(z(t)) измеримо по Борелю для всякого z ∈ K.
Определим средний по промежутку платеж v T : K → R и средний с дисконтом платеж w λ : K → R правилами:
Будем говорить, что отображение V удовлетворяет принципу динамического программирования для платежей v T (T > 0), если для всех положительных T, h значение V для платежа
Будем говорить, что отображение V удовлетворяет принципу динамического программирования для платежей w λ (λ > 0), если для всех положительных λ, h значение V для платежа
Доказательство следующей теоремы смотрите в [89].
Теорема. Предположим, что как для платежей v T (T > 0), так и для платежей w λ (λ > 0), отображение V удовлетворяет принципу динамического программирования.
Тогда, если по крайней мере один из пределов цен
Анонсируемая выше теорема и ее модификации влекут с V = V 1 , V = V 2 тауберовы теоремы для абстрактной задачи управления [60], для дифференциальных игр [73], для абстрактной динамической игры [69], для стохастических игр [64].
На текущий момент можно сформулировать несколько достаточно масштабных целей при исследовании тауберовых теорем для игр.
• Получение общих теорем, связывающих сходимость цен для одного семейства плотностей, со сходимостью к тому же пределу цен с другим семейством вероятностных распределений.
Пока все упомянутые выше результаты касались случая, когда усреднение велось для семейств плотностей 1 T 1 [0,T ] (усреднение по большому промежутку), λe −λt (усреднение с дисконтом). Однако, вообще говоря, можно рассматривать произвольные направленные семейства вероятностных распределений, лишь бы платеж за любой фиксированный промежуток времени в пределе был пренебрежимо мал. Особенно полезны в этом отношении самоподобные семейства плотностей (см. [21,Ch 8.5]). Для дискретного случая в [63] получены некоторые условия существования равномерного предела, не зависящего от выбора вероятностных распределений. В [27] было замечено, что если плотность не возрастает, то для случая одного игрока функция платы может быть выражена как выпуклая комбинация средних по Чезаро. Следовательно, что и было там доказано для управляемых процессов с дискретным временем, существует равномерный предел цен, соответствующим этим распределениям, и он совпадает с равномерным пределом цен при усреднении по большому промежутку, лишь бы последний предел существовал и был равномерен. Подобный подход использовался в [55,64] для повторяющихся игр. В [72,76] было показана общая тауберова теорема из существования равномерного предела цен для самоподобного семейства плотностей следует существование такого же предела для цен по любому направленному семейству плотностей из достаточно широкого класса. О последних результатах для задач управления в non-expansive case смотрите [79,82,84]. В стохастических играх с конечным числом состояний и действий вопрос решен совсем недавно, см. [87].
Для теории суммирования соответствующая общая теория была построена в статье [7]. Для задач управления, для игровых постановок, подобные результаты пока несут частный характер.
• Получение для игровых постановок условий, при которых существует стратегия, гарантирующая ту же асимптотику, что и предел оптимальных цен.
Такая стратегия была бы нечувствительна к выбору достаточно малого параметра дисконтирования и/или достаточно большого промежутка времени. В случае задач управления в non-expansive case имеется стратегия, нечувствительная также и к выбору вероятностного распределения [84]. В стохастических играх такая постановка известна, текущее состояние вопроса хорошо разобрано в [67,87,88].
• Подбор в формулировке игровых вариантов тауберовых теорем слабейшей топологии для предела цен.
На текущий момент имеется масса примеров, в которых из существования поточечного предела для одного из оптимальных средних не следует существование предела для другого оптимального среднего [54,71]. При этом, в отличие от некоторых стохастических постановок, в детерминированных задачах существующие примеры позволяют надеяться на тауберову теорему для поточечной сходимости почти всюду [27,60]. С другой стороны, например в эргодическом случае, принципиальное значение (ср. [43,58]) имела бы тауберова теорема для равномерной сходимости на каждом компакте.
• Тауберовы теоремы для игр с ненулевой суммой (кооперативные игры, равновесие по Штакельбергу, равновесие по Нэшу).
На данный момент максимальное продвижение для стохастических игр с конечным числом состояний и действий рассмотрены равновесие по Нэшу для двух лиц [57] и кооперативные игры [80].
• Распространие тауберовых теорем на задачи, описываемые различными обобщениями уравнения Гамильтона-Якоби, например на игры среднего поля.
Пока полученные результаты требуют эргодичность (см. [58,59,70,81,83]).
On value functions and Tauberian theorems Dmitry V. Khlopin Krasovskii Institute of Mathematics and Mechanics (Yekaterinburg, Russia) Ural Federal University (Yekaterinburg, Russia)
Keywords: game theory, Tauberian theorems, dynamic games, Bellman's principle.
The paper deals with dynamic games and Tauberian theorems for their value function. We study the limit of value functions of games with long run average costs as the time horizon tends to infinity, and the limit of value functions of discounted games as the discount tends to zero. We treat a dynamics as a map from payoffs to value functions. Under weak assumptions on this map, we announced Uniform Tauberian Theorem for value functions: the uniform convergence of value functions for one of these families (either long-run, or discounted averages) implies the uniform convergence for the other family to the same limit. Its proof is based on Bellman's principle. Also, this paper contains an extensive survey of results obtained for these limits.