Об оценке алгоритмов построения решений Штакельберга в линейной неантагонистической позиционной игре двух лиц А.А. Карасёв Д.Р. Кувшинов С.И. Осипов УрФУ (Екатеринбург) УрФУ (Екатеринбург) УрФУ (Екатеринбург) xxfist@gmail.com ИММ УрО РАН (Екатеринбург) sergei.osipov@urfu.ru kuvshinovdr@yandex.ru Аннотация Рассматривается вопрос корректности одного алгоритма построе- ния приближенных решений Штакельберга в линейной неантаго- нистической позиционной дифференциальной игре двух лиц с тер- минальными показателями качества и ограничениями на выбор управлений, заданными в виде выпуклых многогранников. Опре- деляются условия на показатели качества игроков, при наложении которых можно обеспечить сходимость алгоритма. 1 Введение В работах [1,2] был предложен алгоритм численного построения приближенных решений Штакельберга для случая позиционной дифференциальной игры двух лиц с линейной динамикой, фиксированным мо- ментом окончания, терминальными показателями качества и ограничениями на выбор управлений, задан- ными в виде выпуклых многогранников. Решение Штакельберга [3] основано на сведении игровой задачи к задаче оптимального управления. Рассматриваемый численный алгоритм базируется на формализации и результатах теории антагонистических позиционных дифференциальных игр [4] и неантагонистических по- зиционных дифференциальных игр [2]. Цель данной работы — заполнить пробел в области обоснованности сходимости данного алгоритма как процесса численной глобальной максимизации к истинному решению. Данный вопрос не рассматривался в работах [1,5]. Эффективная с практической точки зрения сходимость может быть обеспечена для липшицевых максимизируемых функций и ограничений на область поиска [6]. В разделе 2 вводится постановка задачи и используемое определение решения Штакельберга. В разделе 3 дается общее абстрактное описание численного алгоритма как задачи оптимизации. Раздел 4 посвящен критериям липшицевости максимизируемой алгоритмом функции. 2 Постановка исходной задачи 2.1 Линейная система В работах [1, 5] рассматривалась система, движение которой задается векторным обыкновенным диф- ференциальным уравнением вида ẋ = A(t)x + B(t)u + C(t)v, x(t0 ) = x0 , (1) Copyright © by the paper’s authors. Copying permitted for private and academic purposes. In: A.A. Makhnev, S.F. Pravdin (eds.): Proceedings of the International Youth School-conference «SoProMat-2017», Yekaterinburg, Russia, 06-Feb-2017, published at http://ceur-ws.org 42 где x(t) ∈ Rn — фазовый вектор системы, t ∈ T , [t0 , ϑ] ⊂ R, ϑ — фиксированный момент окончания игры (здесь и далее символ «,» означает «по определению равно»). Игроки 1 и 2 распоряжаются выбором управлений u(t) ∈ P ⊂ Rp и v(t) ∈ Q ⊂ Rq соответственно. Здесь множества P и Q — выпуклые много- гранники. Матрицы A(t), B(t) и C(t) — поэлементно-непрерывные на T матрицы-функции размеров n × n, n × p, n × q. Обозначим G ⊂ T ×R компактное множество такое, что (t0 , x0 ) ∈ G и всякая траектория (1), начавшаяся в G, остается в G. Игроки имеют полную информацию о текущей позиции (t, x(t)). Показатель качества игрока i имеет вид: Ii , σi (x(ϑ)) → max, i = 1, 2, (2) где σi : Rn → R — непрерывные функции такие, что множества уровня Mic , {x ∈ Rn | σi (x) > c}, i = 1, 2, (3) суть выпуклые множества для любого c ∈ R. Рассматривается игра в чистых позиционных стратегиях. Используемая в работе формализация стра- тегий и решений в неантагонистической позиционной дифференциальной игре взята из [2]. Определение 1. Чистая позиционная стратегия первого [второго] игрока [2] Пара функций U , (u(t, x, ε), β1 (ε)) [V , (v(t, x, ε), β2 (ε))], где u(·) [v(·)] — произвольная функция позиции (t, x) ∈ G и положительного параметра ε, принимающая значения из P [Q]. Функции βi (ε) : (0, ∞) → (0, ∞) — монотонные, удовлетворяющие условию lim βi (ε) = 0. ε→0 2.2 Рассматриваемые движения системы В теории позиционных дифференциальных игр [4] рассматриваются одновременно несколько типов дви- жений, отвечающих паре статегий. В частности, вводится понятие аппроксимационных движений или ло- маных Эйлера. Они наиболее удобны для практических построений. В теории неантагонистических игр вводятся аналогичные конструкции. Определение 2. Закон управления [2] Тройка (U, ε1 , ∆1 ) [(V, ε2 , ∆2 )] называется законом управления первого [второго] игрока, где U [V ] — чистая позиционная стратегия, εi — выбранные параметры точности, а ∆i , {tik }K k=1 — конечные разбиения i временно́го отрезка T такие, что k∆i k , max (tik+1 − tik ) 6 βi (εi ). 16k ci }, ci ∈ R, i = 1, 2. (6) Заметим, что Wici (ϑ) = Mici (3) (здесь и далее через Z(t), где Z — некоторое подмножество T × Rn , t ∈ T , обозначается множество { z ∈ Rn | (t, z) ∈ Z }). В [1, 2, 5] выписана структура S1 -решений, использующая стратегию u(2) (t, x, ε) и позволяющая свести задачу построения S1 -решений к задаче нахождения некоторых программных управлений u(t), v(t), t ∈ T . Итак, требуется найти измеримые управления u : T 7→ P и v : T 7→ Q такие, что порождаемое ими движение x(·) удовлетворяет неравенству γ2 (t, x(t)) 6 γ2 (ϑ, x(ϑ)) = σ2 (x(ϑ)), t ∈ T, (7) и доставляет максимум показателю σ1 (x(ϑ)). 44 2.5 Допустимые движения в неантагонистической игре Определение 6. Допустимое движение. Назовем решение x(·) системы (1), порожденное измеримыми управлениями u(·) и v(·), S1 -допустимым, если для него выполнено условие (7). Очевидно, что S1 -допустимые движения доставляют игроку 2 значение выигрыша, не меньшее γ2 (t0 , x0 ). Через D1 ⊂ G обозначим множество позиций, заметаемых S1 -допустимыми траекториями, т.е. множе- ство D1 = {(t, x(t)) | x(·) − S1 -допустимо, t ∈ T }. Через D1 (ϑ) обозначим сечение {(t, x(t)) ∈ D1 | t = ϑ}, то есть множество концов допустимых траекторий. Известно [2], что D1 (ϑ) компактно. 3 Численный метод Для численной аппроксимации решений Штакельберга предлагается следующая вычислительная схема. Пусть cmax 1 (c2 ) , max c σ1 (x), c2 ∈ R. (8) x∈D1 (ϑ)∩∂M2 2 В этом определении будем рассматривать те c2 , для которых D1 (ϑ) ∩ ∂M2c2 6= ∅. Из постановки задачи и определения множества D1 (ϑ) следует, что любая пара (c∗1 , c∗2 ), где c∗1 = cmax 1 (c∗2 ), c∗2 ∈ arg max cmax 1 (c) (9) c∈[c2 ,c2 ] есть пара выигрышей, доставляемых игрокам некоторым S1 -решением. Значения c2 и c2 должны быть выбраны так, чтобы выполнялись условия c2 6 γ2 (t0 , x0 ), maxx∈D1 (ϑ) σ2 (x) 6 c2 6 maxx∈Rn σ2 (x). Таким образом, задача нахождения решения Штакельберга может быть сведена к задаче (условной) максимиза- ции. Рассмотрим её более подробно. В [6] представлен ряд эффективных методов численной глобальной оптимизации. Для их применения требуется липшицевость максимизируемой функции и функций, задающих область поиска максимума (в виде системы неравенств). Таким образом, для эффективного решения задачи (9) требуется липшицевость функции cmax 1 (c2 ) на её области определения. Отрезок [c2 , c2 ] включает её область определения и может быть даже несколько больше, чем требуется. Истинные границы области определения (minx∈D1 (ϑ) σ2 (x) = γ2 (t0 , x0 ) и maxx∈D1 (ϑ) σ2 (x)) можно установить с заданной точностью в процессе вычислений. Рассмотрим задачу приближённого вычисления функции cmax 1 (c2 ) (8). Данная задача есть задача услов- ной максимизации. Условие x ∈ ∂M2c2 заменяется на два неравенства c2 − ζ 6 σ2 (x) 6 c2 + ζ, где ζ > 0 есть некоторый параметр точности. Главная сложность кроется в условии x ∈ D1 (ϑ). В [5] задача численной максимизации решалась через вычисление многоугольной аппроксимации мно- жества D1 (ϑ) перебором значений c2 с заданным шагом. Для задач с фазовым пространством размерности больше двух данный подход сталкивается со сложностью требуемых для этого процедур вычислительной геометрии (и в смысле вычислительной сложности, и в смысле сложности корректной программной реа- лизации). Поэтому представляется разумным оперировать не целыми множествами в Rn , как это делалось в [5] (для случая n = 2), а отдельными допустимыми траекториями [8] (сечения мостов аппроксимирова- лись выпуклыми многогранниками). Будем считать, что эффективно вычислима χ : Rn 7→ {0, 1} — индикаторная функция некоторой аппрок- симации множества D1 (ϑ). Для ускорения вычисления χ(x) можно также воспользоваться тем фактом, что γ (t ,x ) D1 (ϑ) ⊆ M1 1 0 0 ∩ G(ϑ). В [6] также рассматривается случай частичной вычислимости ограничений в задаче условной оптимизации, что позволяет использовать условие χ(x) = 1 в качестве ограничения поиска максимума. На практике, для определения факта попадания некоторой точки x в D1 (ϑ) выполняется попытка по- строить аппроксимацию S1 -допустимой траектории, ведущей в позицию (ϑ, x). Итак, если для некоторого x ∈ Rn окажется, что χ(x) = 1, то в процессе вычисления χ(x) будет получена аппроксимационная S1 - допустимая траектория, ведущая в позицию (ϑ, x), и порождающие её кусочно-непрерывные управления u(t), v(t). Таким образом, вычисление (9) влечёт вычисление численной аппроксимации S1 -решения. 45 4 Выполнение условий Липшица Рассмотрим S1 -допустимые траектории x(·), обеспечивающие выигрыш ведомого игрока σ2 (x(ϑ)) = c2 . Предположим, что c2 выбрано таким образом, что множество таких траекторий не пусто. Заметим, что из определения S1 -допустимой траектории следует, что такие траектории не заходят во внутренность W2c2 (6). Предположим также, что функция cmax1 (c2 ) (8) определена на отрезке [c2 , c2 ]. Исследуем липшицевость c1 (c2 ) в двух случаях. max 4.1 Условие Липшица в случае гладкости σi Условие Липшица для cmax 1 (c2 ) имеет вид: ∃L > 0 ∀c02 , c002 ∈ [c2 , c2 ] |cmax 1 (c02 ) − cmax 1 (c002 )| 6 L|c02 − c002 | (10) Поскольку из равенства c02 = c002 следует cmax 1 (c02 ) = cmax 1 (c002 ), то для этого случая (10) выполнено. Поэтому возьмем точки x , x ∈ R , такие что σ2 (x ) 6= σ2 (x ), и сформулируем условие следующего вида: 0 00 n 0 00 ∃L > 0 ∀x0 , x00 ∈ G(ϑ) : σ2 (x0 ) 6= σ2 (x00 ) |σ1 (x0 ) − σ1 (x00 )| 6 L|σ2 (x0 ) − σ2 (x00 )|. (11) c0 Пересечение ∂Mic ∩ G(ϑ) обозначим как Mci . Учитывая (3), мы можем выбирать x0 ∈ M22 , а x00 ∈ c00 c0 c00 M22 ∩ G(ϑ). При этом, если c02 6= c002 , то M22 ∩ M22 = ∅. Поскольку σ2 (x) — однозначная функция, то σ2 (x0 ) 6= σ2 (x00 ) ⇒ x0 6= x00 . Утверждение 1. При выполненных предположениях о показателях σi (x) и множествах Mic (3) из выполнения условия (11) следует выполнение условия Липшица (10). c0 c00 Выберем точки x0 ∈ M22 и x00 ∈ M22 . Для выбранных точек показатель второго игрока равен соот- ветственно σ2 (x0 ) = c02 и σ2 (x00 ) = c002 , а функция σ1 (x) для этих точек достигает максимума на данных множествах. То есть: max 0 σ1 (x0 ) = cmax 1 (c02 ), max 00 σ1 (x00 ) = cmax 1 (c002 ). c c x0 ∈M22 x00 ∈M22 0cmax (c0 ) 0c0 0cmax (c00 ) 0c00 Таким образом, можно взять точки x0 ∈ M1 1 2 ∩ M2 2 , и x00 ∈ M1 1 2 ∩ M2 2 . Подставив в выражение (11) соответствующие значения σ1 и σ2 , получаем условие (10). Утверждение доказано. Теорема 1. Условие (11) выполняется для σi (x), определенного на Rn , если выполнены следующие пред- положения: 1. Функции σi (x), i = 1, 2,— гладкие на G(θ) ⊂ Rn . 2. Все ∂σ∂x 2 (x) j , 1 6 j 6 n, не обращаются в нуль ни в какой точке x ∈ G(θ). Множество G(θ) компактно, а значит на нем σi (x) имеют непрерывные и ограниченные частные произ- водные: ∂σi (x) ∃Kij : ∀x ∈ G(θ) 6 Kij . (12) ∂xj Здесь xj — это координаты x = (x1 , x2 , ..., xn )> ∈ Rn . Из теоремы о среднем для функций многих переменных следует истинность n X ∂σi 0 00 0 ∃ ξ ∈ (x , x ) σi (x ) − σi (x ) = 00 (ξ)∆xj , (13) j=1 ∂xj ∆xj = x0j − x00j , Так как частные производные ограничены при любых x ∈ G(θ), то они ограничены и при ξ ∈ (x0 , x00 ) ⊂ G(θ), а значит, исходя из (13), выполняется следующее неравенство: n X |σ1 (x0 ) − σ1 (x00 )| 6 Kj1 |∆xj |. (14) j=1 46 Пусть σ2 (x) такова, что ∂σ2 kj2 = min (x) . x∈G(θ) ∂xj Минимум частных производных существует, так как это непрерывные функции, определенные на ком- пакте. При этом, в соответствии с предположением 2, имеем kj2 6= 0. Следовательно, справедливо следующее неравенство: n X |σ2 (x0 ) − σ2 (x00 )| > kj2 |∆xj |, (15) j=1 Пусть K 1 = maxj Kj1 , k 2 = minj kj2 , причем k 2 6= 0, так как ∀j kj2 6= 0. Тогда из (14) и (15) следует K1 |σ2 (x0 ) − σ2 (x00 )|, |σ1 (x0 ) − σ1 (x00 )| 6 k2 что доказывает исходное условие (11). Теорема доказана. Из условия (11) по утверждению 1 немедленно следует (10). К сожалению, данная теорема существенно ограничивает класс допустимых показателей качества. Тре- буется гладкость функций σi (x) на Rn , что неудобно уже в том простом случае, когда σi (x) задает рассто- яние от какой-либо точки, например: σi (x) = |x − ai |, x, ai ∈ R, i = 1, 2. Здесь показатель качества σi (x) не дифференцируем в точке ai . Поэтому далее рассмотрим более общий случай. 4.2 Случай липшицевости показателя первого игрока Предположим, что для функции σ2 (x) выполняется условие следующего вида: ∀x0 , x00 ∈ G(θ) : σ2 (x0 ) 6= σ2 (x00 ) ∃L2 (x0 , x00 ) > 0 : |σ2 (x0 ) − σ2 (x00 )| = L2 k∆xk. (16) Здесь и в дальнейшем ∆x = x − x . Вообще говоря, такое условие будет выполняться для ограниченной 0 00 функции на ограниченном множестве. Поскольку G(ϑ) — компакт в Rn , а функция σ2 (x) непрерывна на нем, то она ограничена на этом компакте. Так как функция σ2 (x) ограничена, то модуль разности можно записать |σ2 (x0 ) − σ2 (x00 )| = r1 > 0, поскольку выполняется σ2 (x0 ) 6= σ2 (x00 ). В то же время и x0 6= x00 , а значит на ограниченном множестве выполнено k∆xk = r2 > 0. Разделив два эти равенства друг на друга и приравняв rr21 = L2 , немедленно получаем условие (16). Теорема 2. Условие (11) выполняется для σi (x), определенного на Rn , если выполнены следующие пред- положения: 1. Функция σ1 (x) — липшицева в G(ϑ). 2. L2 (x0 , x00 ) из условия (16) имеет по всем x0 , x00 : σ2 (x0 ) 6= σ2 (x00 ) инфимум Linf 2 , не равный нулю. Допустим, для функции σ1 (x) выполняется условие Липшица вида: ∃L1 ∀x0 , x00 ∈ G(θ) |σ1 (x0 ) − σ1 (x00 )| 6 L1 k∆xk. (17) Учитывая выполнение равенства (16) и неравенства (17), можно записать: ∃L1 ∀x0 , x00 ∈ G(θ) : σ2 (x0 ) 6= σ2 (x00 ) ∃L2 (x0 , x00 ) : L1 |σ1 (x0 ) − σ1 (x00 )| 6 L1 k∆xk = |σ2 (x0 ) − σ2 (x00 )|. L2 Возьмем Linf 2 = inf L2 (x0 , x00 ) по всем x0 , x00 ∈ G(θ) таким, что выполнено σ2 (x0 ) 6= σ2 (x00 ). Тогда мы можем вынести Linf 2 вперед и записать: 0 00 0 00 0 00 L1 L1 ∃L1 , Linf 2 : ∀x , x ∈ G(θ) : σ2 (x ) 6= σ2 (x ) |σ1 (x ) − σ1 (x )| 6 |σ2 (x0 ) − σ2 (x00 )| 6 inf |σ2 (x0 ) − σ2 (x00 )|. L2 L2 Положим в (11) L = LLinf 1 . Теорема доказана. Из утверждения 1 следует истинность (10). 2 47 5 Обсуждение результатов Получены достаточные условия липшицевости функции cmax 1 (c2 ) (8). В первом случае (теорема 1) тре- буется гладкость показателей σi (x) (2) на компакте G(ϑ) ⊂ Rn и выполнение условия ∂σ∂x 2 (x) j 6= 0. Данные условия довольно жесткие и существенно ограничивают выбор показателей игроков. Во втором случае (теорема 2) уже не требуется гладкость функций. Вместо этого достаточно липшицевости σ1 (x). Условие неравенства нулю инфимума L2 (x0 , x00 ) (16) можно рассматривать как некоторый аналог условия, накла- дываемого на частные производные в первом случае. Если предположить, что σ2 (x) — гладкая и ни одна из частных производных ∂σ∂x2 (x) j не обращается в нуль, то inf L2 (x0 , x00 ) также будет ненулевым. Выполнение полученных в работе условий открывает возможность применения эффективных методов численной оптимизации к задаче построения решений Штакельберга в представленном классе позицион- ных дифференциальных игр с терминальными показателями качества. Список литературы [1] S. I. Osipov. On the implementation of the algorithm for constructing solutions for the class of hierarchical games. Avtom. i telemech. 11: 195-208, 2007 (in Russian). = С.И. Осипов. О реализации алгоритма построения решений для класса иерархических игр Штакельберга. Автом. и Телемех. 11: 195-208, 2007. [2] A. F. Kleimenov. Non-zero-sum positional differential games. Nauka, Ekaterinburg, 1993 (in Russian). = А.Ф. Клейменов. Неантагонистические позиционные дифференциальные игры. Наука, Екатеринбург, 1993. [3] V. H. Stakelberg. The theory of the market economy. Hodge, London, 1952. [4] N. N. Krasovskii, A. I. Subbotin. Game-Theoretical Control Problems. Springer-Verlag, New York, 1988. [5] A. F. Kleimenov, D. R. Kuvshinov, S. I. Osipov. Numerical construction of Nash and Stackelberg solutions in a two-player linear non-zero-sum positional differential game. Tr. Inst. Mat. i Mech. UrO RAN, 15(4):120- 133, 2009 (in Russian). = А.Ф. Клейменов, Д.Р. Кувшинов, С.И. Осипов. Оценки тригонометрических интегралов и неравенство Бернштейна для дробных производных. Тр. Инст. Мат. и Мех. УрО РАН, 15(4):120-133, 2009. [6] R. G. Strongin, V. P. Gergel, V. A. Grishagin, K. A. Barkalov. Parallel computations in global optimization problems. Moscow State University, Moscow, 2013 (in Russian). = Р.Г. Стронгин, В.П. Гергель, В.А. Гри- шагин, К.А. Баркалов. Параллельные вычисления в задачах глобальной оптимизации. Издательство Московского университета, Москва, 2013. [7] N. N. Krasovskii. Control of dynamic system. Nauka, Moscow, 1985 (in Russian). = Н.Н. Красовский. Управление динамической системой. Наука, Москва, 1985. [8] D. R. Kuvshinov. Numerical contruction of Nash solutions in a linear positional differential game of two persons with a phase space of more than two dimensions. Trudy IMM UrO RAN, 19(1):170-181, 2013 (in Russian). = Д.Р. Кувшинов. Численное построение решений по Нэшу в линейной позиционной дифференциальной игре двух лиц с фазовым пространством размерности больше двух. Труды ИММ УрО РАН, 19(1):170-181, 2013. 48 On the estimate of algorithms of constructing Stakelberg’s solutions in linear non-antogonistic positional two-person game Alexander A. Karasev1 , Dmitriy R. Kuvshinov1,2 , Sergey I. Osipov1 1 – Ural Federal University (Yekaterinburg, Russia) 2 – Krasovskii Institute of Mathematics and Mechanics (Yekaterinburg, Russia) Keywords: differential positional game, non-antagonistic, non-zero-sum game, Lipschitz condition, Stackelberg solution. The problem of justifying one algorithm for constructing approximate Stackelberg solutions in a linear non- antagonistic positional differential game of two persons with terminal quality indicators and restrictions on the choice of controls given in the form of convex polyhedra is considered. The conditions for the players’ quality indicators are determined, upon application of which it is possible to ensure the convergence of the algorithm. 49