Настоящий обзор представляет собой попытку дать описание основных направлений и результатов игр среднего поля первого порядка для русскоязычного читателя. В настоящей работе отражены основные теоретические результаты игр среднего поля первого порядка (т.е. игр среднего поля с динамикой, задаваемой обыкновенным дифференциальным уравнением). Кроме того, рассмотрена модель энергетических сетей, формализуемая в рамках теории игр среднего поля первого порядка.
Также стратегии, которые строятся в рамках этого подхода, основаны на угрозах, которые стоит признать неправдоподобными.
Идея теории игр среднего поля состоит в том, чтобы рассмотреть систему бесконечного числа игроков. При этом влияние каждого игрока становится пренебрежимо малым, а значение имеет только масса игроков. В получившейся системе каждый игрок оптимизирует свое поведение в соответствие с движением всей массы игроков, при этом поведение массы игроков задается суммой поведения игроков. Отметим основные задачи, которые рассматриваются в теории игр среднего поля: исследование существования и единственности решения игры среднего поля; при этом игра среднего поля формализуется в виде системы двух уравнений в частных производных или задачи управления для некоторой динамической системы; построение приближенного равновесия в игре конечного числа лиц по заданному решению игры среднего поля; исследование сходимости равновесий в играх конечного числа лиц к решению игры среднего поля при стремлении числа игроков к бесконечности; анализ конкретных прикладных задач при помощи методологии игр среднего поля.
В настоящее время существует несколько подходов к определению и построению решения игры среднего поля. Исторически первый подход основан на прямом анализе системы двух уравнений: первое уравнение – уравнение Беллмана, описывающее выигрыш игроков (игроки предполагаются однотипными), второе уравнение – уравнение Колмогорова, описывающее распределение игроков. Отметим, что краевое условие для уравнения Беллмана задается в последний момент времени, а для уравнения Колмогорова – в начальный. Этот подход был развит в работах J.-M. Lasry и P.-L. Lions [49]–[51], M. Huang, R.P. Malham´e и P. Caines (см. [31]–[34]). В этих работах преимущественно рассматривались системы, заданные стохастическими дифференциальными уравнениями. В работах [51, 52] был рассмотрен случай динамики, задаваемой обыкновенным дифференциальным уравнением. Также здесь отметим работу [25], где рассмотрены игры среднего поля с динамикой каждого игрока, задаваемой марковской цепью с непрерывным временем и конечным числом состояний. Отметим также, что в рамках подхода, основанного на анализе системы дифференциальных уравнений, были изучены игры среднего поля с динамикой, задаваемой марковским процессом достаточно общего вида (см. [42, 39, 43]). К этому же подходу примыкает идея слабых решений для детерминированных игр среднего поля, предложенная в [13] (см. также [15, 29, 52]). В этом случае оба уравнения заменяются на специально построенные задачи оптимизации.
Альтернативный подход к играм среднего поля называется вероятностным и связан с исследованием задачи управления для динамической системы, описываемой нелинейным марковским процессом. В этом случае динамика и интегральная часть выигрыша зависят от распределения игроков в текущий момент времени. Распределение игроков определяется по решению задачи оптимизации. Этот подход был развит для стохастических игр среднего поля в серии работ [16]–[19]. В частности, в рамках этого подхода были получены аналоги принципа максимума Понтрягина для игр среднего поля. Для детерминированных игр среднего поля вероятностный подход был развит в [28] (см. также [27]). Некоторым недостатком вероятностного подходя является зависимость определения решения от выбора сопутствующего вероятностного пространства. Этот недостаток пытается преодолеть минимаксный подход, в рамках которого задача поиска решения игры среднего поля сводится к решению игры бесконечного числа лиц; при этом этом динамика определяется распределением оптимальных траекторий.
Игра среднего поля является предельным (“искусственным”) объектом. Поэтому необходимо исследовать вопрос о связи равновесия в игре конечного (но большого) числа игроков и решения игры среднего поля. Построение приближенных решений в играх конечного числа игроков рассматривалось для стохастических игр в работах [52, 43]. В этом случае строятся позиционные стратегии. Для детерминированных игр среднего поля приближенное равновесие по Нэшу рассматривалось в классе программных стратегий [4, 13].
Предел решений игр многих лиц при стремлении числа игроков к бесконечности как решение игры среднего поля исследовался в работах [22, 46]. Было показано, что если в игре N лиц с однотипными игроками и динамикой каждого игрока, определяемой положением игрока, его управлением и симметричной функцией от положения всех игроков, существует универсальное равновесие по Нэшу (т.е. набор стратегий, не зависящий от выбора начальных положений игроков), то все предельные точки эмпирических распределений игроков соответствуют решениям игры среднего поля в вероятностном смысле. Отметим, что в настоящее время разработаны численные методы для игр среднего поля. Они преимущественно охватывают стохастические игры среднего поля [1]–[3].
Еще одно направление игр среднего поля связано с так называемым “основным уравнением” (master equation). В рамках этого подхода игра среднего поля описывается одним уравнением, записанным в терминах производных в функциональных пространствах или пространствах вероятностей. Исследование основного уравнения было инициировано P.-L. Lions [52]. Этой тематике посвящены работы [11, 14, 28, 41]. Для детерминированных игр среднего поля было введено понятие вязкостного решения и доказана теорема существования этого решения [24].
Многие задачи включают в себя модели взаимодействия множества “слабых” агентов с одним или несколькими могущественными игроками. Такие задачи формализованы в рамках игр среднего поля с ведущим игроком [10, 20, 30, 53].
Отметим, что теория игр среднего поля находит многочисленные применения в финансовом анализе [51], в экономических задачах [47, 26], в моделировании движения [48] и в моделировании социальноэкономических задач, в частности вопросов коррупции и преступности [40, 44]. Также многочисленны технические приложения, в частности к задачам моделирования электрических и энергетических сетей [35]–[37], [8].
Настоящий обзор представляет собой попытку дать описание основных направлений и результатов игр среднего поля первого порядка, т.е. игр среднего поля, которые описываются системой дифференциальных уравнений первого порядка, что соответствует детерминированным динамическим системам, в рамках “вероятностного подхода”. Кроме того, рассмотрена модель энергетических сетей, формализуемая в рамках теории игр среднего поля первого порядка. Обзор основных результатов, касающихся игр среднего поля второго порядка, дан в [10, 27]. 2
Эмпирический вывод системы уравнений для игры среднего поля В большинстве работ, посвящённых играм среднего поля, задача ставится аксиоматически. Однако, представляется полезным получить постановки теории игр среднего поля, исходя из теории игр конечного числа лиц. Данный вывод является математически нестрогим. В целом вывод следует работам [39, 51].
Прежде всего напомним определение равновесия по Нэшу. Рассмотрим игру N лиц, пусть Zi, i = 1; : : : ; N , – множество стратегий i-го игрока. Выигрыш каждого игрока определяется функцией полезности Ji(z1; : : : ; zN ). Если z = (z1; : : : ; zk; : : : ; zN ) 2 Z1 : : : ZN – профиль стратегий, wi 2 Zk – стратегия игрока i, то обозначим через zjwi профиль стратегий, полученный из профиля z путём замены стратегии zi игрока i на стратегию wi, т.е.
Профиль стратегий z называется равновесием по Нэшу, если для всех i 2 1; N и wi 2 Zi zjwi = (z1; : : : ; zi 1; wi; zi+1 : : : ; zN ):
Ji(z jwi) 6 Ji(z ): Далее мы рассмотрим дифференциальные игры многих лиц с разделённой динамикой, т.е. будем предполагать, что i-й игрок непосредственно воздействует только на динамику вектора xi 2 Rd: x_ i = fi(t; x1; : : : ; xN ; ui); t 2 [0; T ]; u 2 U: Более того, мы будем предполагать симметричную зависимость уравнений динамики от xj, j 6= i. Для того чтобы упростить дальнейшее изложение, мы предполагаем, что правая часть динамики вектора xi зависит от времени, текущего состояния, эмпирического распределения игроков и управления самого i-го игрока. Под эмпирическим распределением игроков мы понимаем вероятность
N 1 x(t) , N
x1(t) + : : : + xN (t) : Таким образом, мы рассматриваем управляемую систему x_ i = f (t; xi; xN(t); ui); i = 1; N : (1) Предполагается, что каждый игрок стремится максимизировать свой выигрыш, состоящий из терминальной и интегральной частей. Мы будем предполагать, что выигрыш также зависит от эмпирического распределения игроков:
В качестве примера зависимости от эмпирического распределения можно рассматривать зависимость от среднего. В этом случае
Ji(u1; : : : ; uN ) , xi(T ); xN(T ) + g t; xi(t); xN(t); ui(t) dt:
(2) 1 1
Z T
0 0 0
N f (t; xi; xN ; u) = f^@t; xi; X xj; uiA = f^ t; xi; j=1
Z
Rd
y xN (dy); ui ; 0
1
N (xi; xN ) = ^ @xi; X xjA = ^ xi; j=1
Z
Rd
y xN (dy) ;
N g(t; xi; xN ; u) = g^ @t; xi; X xj; uiA = g^ t; xi; j=1
Z
Rd y xN (dy); ui : Отметим, что множество взвешенных сумм мер Дирака плотно во множестве P1(Rd), состоящем из вероятностных мер m таких, что конечен первый абсолютный момент, т.е.
Z
Rd
kykm(dy) < 1: Поэтому можно считать, что функции f , g определены для всех t, x, вероятностных мер с конечным первым абсолютным моментом m и управлений u. Аналогично, функция определена для состояний x и вероятностей с конечным первым абсолютным моментом m.
Мы будем рассматривать концепцию равновесия по Нэшу для игры с динамикой (1) и показателем качества (2). Кроме того, мы предполагаем существование универсального равновесия в классе чистых позиционных стратегий. Замечание 1. Вообще говоря, нельзя говорить о существовании универсального равновесия по Нэшу для дифференциальной игры общего вида в классе чистых позиционных стратегий. Для игр двух лиц построен пример, показывающий, что в чистых стратегиях нельзя построить универсальную (т.е. не зависящую от начальной позиции) оптимальную позиционную стратегию [57]. Из этого следует и невозможность построить универсальную равновесную стратегию уже в игре двух лиц. В настоящий момент доказано существование равновесия по Нэшу в классе позиционных стратегий, зависящих от параметра " [38]. В этом случае движения строятся пошагово, на основе конструкций, предложенных в теории антагонистических дифференциальных игр Н.Н. Красовским и А.И. Субботиным [55] (см. также конструкцию универсальных стратегий в [55]). Отметим, что равновесие достигается лишь в предельном случае, когда длина шага и параметр " стремятся к нулю. Необходимым условием является и согласованность параметров мелкости у стратегий игроков. Также универсальные в заданном компакте стратегии могут быть построены в классе управлений с поводырем [6, 7].
Поскольку динамика и функции выигрыша зависят от эмпирической меры, то логично считать, что стратегии игроков зависят от позиции и вероятности, описывающей распределение игроков. Пусть ui : [0; T ] Rd P1(Rd) ! U – стратегия i-го игрока. Через u обозначим профиль стратегий. Пусть также x0 = (x0;1; : : : ; x0;N ) – набор начальных позиций игроков. Обозначим через x[ ; t0; x0; u] решение задачи Коши: x_i(t) = f (t; xi(t); xN(t); ui(t; xi(t); xN(t))); xi(t0) = x0;i; i = 1; N : (3) Напомним, что xN(t) = N1 ( x1(t) + : : : + xN (t)):
Z T
t0
Ji[t0; x0; u] =
g t; xi(t); xN(t); ui(t; xi(t); xN(t)) dt:
(
Ji[t0; x0; u jvi] 6 Ji[t0; x0; u ]: Рассмотрим лишь симметричные равновесия по Нэшу. В этом случае ui не зависит от номера i и равна некоторой стратегии u^. В дальнейшем будем и набор из N стратегий u^ обозначать через u^. Также можно считать, что u^ есть функция из [0; T ] Rd P1(Rd) со значениями в U .
Также выпишем уравнение на изменение вероятности N [t] , xN(t). Пусть '(x) – функция класса C1, быстро убывающая на бесконечности вместе со своими частными производными. В силу динамики системы имеем, что d dt Отсюда,
'(xi[t; t0; x0; u^]) = hr'(xi[t; t0; x0; u~]); x_i[t; t0; x0; u^]i = d Z dt Rd '(x) N [t](dx) = d " 1 XN '(xi[t; t0; x0; u^]) =
# dt N i=1 N Xhr'(xi[t; t0; x0; u]); f (t; xi; xN(t); u^(t; xi(t); xN(t))) =
Z i=1 = hr'(xi[t; t0; x0; u^]); f (t; xi; xN(t); u^(t; xi(t); xN(t))): Rdhr'(x); f (t; x; N [t]; u^(t; x; N [t]))i N [t](dx): (5) Отметим, что задача поиска равновесия в игре большого числа лиц чрезвычайно сложна. Ключевая идея теории игр среднего поля – перейти к пределу и исследовать систему бесконечного числа лиц. Прежде всего, отметим, что при больших N вклад каждого игрока в эмпирическое распределение игроков невелик (порядка 1=N ). В первом приближении им можно пренебречь. Тогда для каждого игрока распределение игроков становится внешним параметром. Обозначим распределение игроков в момент времени t через [t]. Заметим, что в предельной игре каждый игрок решает задачу максимизации при условии того, что динамика задаётся уравнением
Z T
t0 (x(T ); [T ]) +
g(t; x(t); [t]; u(t))dt x_ = f (t; x; [t]; u(t)); x(t0) = y: При этом динамика распределения игроков в момент t – вероятности [t] – определяется по оптимальному управлению всех игроков. Необходимо отметить, что при фиксированном распределении игроков задача поиска равновесной по Нэшу стратегии сводится к задаче оптимального управления.
Одним из способов решения задач оптимального управления является метод динамического программирования. В этом случае необходимо рассмотреть уравнение Беллмана + H(t; x; [t]; rV ) = 0; V (T; x) = (x; [T ]); (6) где H – гамильтониан, вычисляемый по формуле Здесь m – вероятность, p 2 Rd – сопряжённая переменная.
H(t; x; m; p) = mu2aUx[hp; f (t; x; m; u)i + g(t; x; m; u)]: Решение уравнения (6) надо понимать в минимаксном/вязкостном смысле [56, 9]. Однако, для наших целей эмпирического вывода мы будем понимать решение этого уравнения в классическом смысле. Более того, мы считаем, что с классическим решением данного уравнения ассоциирована оптимальная стратегия u^(t; x; m), которая удовлетворяет условию
mu2aUx[hrV (t; x); f (t; x; m; u)i + g(t; x; m; u)] = hrV (t; x); f (t; x; m; u^(t; x; m))i + g(t; x; m; u^(t; x; m)): Заметим, что если гамильтониан H является дифференцируемым по сопряженной переменной, то f (t; x; m; u^(t; x; m))i = @H(t; x; m; rV (t; x)) @p : В этих предположениях динамика распределения игроков (5) может быть переписана в виде d Z dt Rd
Z '(x) [t](dx) = Rdhr'(x); f (t; x; [t]; u^(t; x; [t]))i [t](dx) = =
Z
Rd r'(x); @H(t; x; [t]; rV (t; x)) @p [t](dx): В дальнейшем мы будем записывать последнее уравнение в формальном виде d dt + H(t; x; [t]; rV ) = 0; V (T; x) = (x; [T ]); ; r [t]; [0] = m0: Здесь (x; m) – некоторая функция со значениями в R, m0 – некоторое начальное распределение игроков. Отметим, что в данном случае гамильтониан H, а также терминальное условие зависят от вероятности в целом.
Чтобы упростить запись, обозначим
Hp(t; x; m; rV (t; x)) =
@H(t; x; m; rV (t; x))
@p
:
(8)
(9)
Принципиально важным является случай, когда мера [t] при каждом t абсолютно непрерывна
относительно меры Лебега. Обозначим через плотность меры [t], т.е. – это функция класса L1([0; T ] Rd)
такая, что
Отметим, что представление вероятности через ее плотность задает отображение функций
L1(Rd) таких, что
(
A dx = d Z dt Rd (x) [t]dt =
Z
Rd
hHp(t; x; (t; ); rV (t; x)); r (x)i [t](dx) = Оставляя лишь правую и левую части этого равенства, получаем систему уравнений в частных производных для игр среднего поля в предположении того, что распределение вероятностей имеет плотность: = hHp(t; x; (t; ); rV (t; x)); r (x)i (t; x)dx =
div(Hp(t; x; (t; ); rV (t; x)) (t; x)) (x)dx: Z
Rd + div(Hp(t; x; (t; ); rV (t; x)) (t; x)) = 0; (0; x) = 0(x): + H(t; x; (t; x); rV ) = 0; V (T; x) = (x; (T; x));
+ div(Hp(t; x; ; rV ) ) = 0; (0; x) = 0(x): Отметим, что обе системы – (8), (9) и (11), (12) – описывают игры среднего поля с нелокальной связью, т.е. гамильтониан зависит от функции из класса L1 “в целом”. Теми же методами, что и в предыдущем разделе, можно вывести систему уравнений среднего поля с локальной связью, в этом случае гамильтониан зависит от текущего значения плотности. В этом случае система уравнений для игры среднего поля имеет вид 4 4.1 Игры среднего поля с нелокальной связью
Вязкостный подход Вязкостный подход является исторически первым в теории игр среднего поля, он развит Lasry и Lions в работах [49]–[51]. Кратко опишем основные идеи этого подхода, следуя работе [51]. Мы предполагаем, что распределение игроков имеет плотность, Тогда система (8), (9) принимает вид
H(t; x; ; p) = kpk2=2 + F (x; ):
1 + 2 krV k2 + F (x; (t; )) = 0; V (T; x) = (x; (T; ); + div(rV (t; x)) (t; x)) = 0; (0; x) = 0(x): (11) (12) (13) (14) (15) (16) (17) Первое уравнение соответствует задаче максимизации функционала если
удовлетворяет краевому условию и на множестве всех траекторий Отметим, что оптимальное управление задается равенством u^(t; x) = rV (t; x).
Накладываются условия непрерывности функций F и , их дважды непрерывной дифференцируемости по x. Предполагаем, что сами функции F и , их первые и вторые производные по x равномерно ограничены. Также считаем, что 0 финитна.
Решение уравнения (16) понимается в вязкостном смысле [56, 9]. Напомним, что функция (t; x) является вязкостным решением уравнения (x(T )) +
+ F (x(t); (t; )) dt Z T 0 u2(t)
2 x_ = u; u 2 Rd: + h(t; x; r ) = 0;
(T; x) = T (x) a + h(t; x; b ) 6 0; 8(a ; b ) 2 D
(t; x); a+ + h(t; x; b+) > 0; 8(a+; b+) 2 D+ (t; x): Здесь
D (t; x) = (a; b) 2 R
Rd : 8( ; ) ( D+ (t; x) = (a; b) 2 R
Rd : 8( ; )
lim inf !0; 0! ; 0!
lim sup !0; 0! ; 0! (t +
0; x + (t + 0; x + 0) 0) (t; x) (t; x) a a hb; i > 0 ;
) hb; i 6 0 : Решение уравнения (17) понимается в смысле распределений, т.е. мы считаем, что 2 L1([0; T ] Rd) – решение уравнения (17), если для всех гладких финитных функций 2 C1([0; T ] Rd), обращающихся в ноль при t = 0 и t = T , выполнено равенство
Z [0;T ] Rd (t; x)dt dx: Теорема существования для такого решения имеет два доказательства. Первое доказательство основано на следующих идеях.
1. Оператор , который ставит в соответствие функции решение уравнения
1
+ 2 kr k + F (t; (t; )) = 0;
(
Как видно, конструкция решения в рамках вязкостного подхода существенно опирается на структуру гамильтониана H(t; x; p; ) = kpk2 + F (x; ). Прежде всего используется явная формула вычисления потока вероятности по заданной почти всюду дифференцируемой функции, эта формула является следствием уравнения (17). Перенос ее на более общий случай невозможен. Это требует других подходов к определению решения. 4.2
Вероятностный подход В настоящем разделе мы рассматриваем полную систему (8), (9). Вероятностный подход основан на исследовании игры бесконечного числа игроков. А именно, пусть – множество игроков. На этом множестве необходимо ввести некоторую вероятность (измеримую структуру также предполагаем заданной) %. Предположим, что каждый игрок в начальный момент находится в позиции X0(!). От функции X0 необходимо потребовать согласованности с распределением m0, т.е. чтобы для каждого измеримого множества A Rd %(X0 1(A)) = m0(A). Движение каждого игрока описывается уравнением d dt
X(t; !) = f (t; X(t; !); [t]; u(t; !)); X(0; !) = X0(!); u(t; !) 2 P:
(19)
(
Rd
(
Z
Rd Каждый игрок стремится к максимизации своего выигрыша, который задается величиной + H(t; x; X(t; ); rV ) = 0; V (T; x) = (x; X(t; )):
Z T
0 (X(t; !); [T ]) +
g(t; X(t; !); [t]; u(t; !))dt: [t](A) = %(X 1(t; A)): m(A) = %(Y 1(A)): При этом [t] является законом распределения X(t; !) т.е. для любого измеримого множества A выполнено равенство Далее в рамках этого раздела (несколько нестрого) будем считать, что функции f , g, и H зависят не от вероятности m, а от функции Y : ! Rd, которая определяет вероятность m по правилу Данные предположения позволяют переписать уравнение (8) в виде Изменение X(t; !) описывается уравнением d dt
X(t; !) =
; X(0; !) = X0(!):
Последнее уравнение получено из (19) и (
Z и при Y 0 6= Y 00
[F (Y 0(!); Y 0( )) F (Y 0(!); Y 00( )) + F (Y 00(!); Y 00( )) F (Y 00(!); Y 0( ))]%(d!) 6= 0: В рамках второго подхода условие накладывается на H . А именно, единственность имеет место, когда [H (t; Y 0(!); Y 0( ); Z0(!)) H (t; Y 00(!); Y 0( ); Z00(!))+ + H (t; Y 00(!); Y 00( ); Z00(!)) H (t; Y 0(!); Y 00( ); Z00(!))]%(d!)
Z [ (Y 0(!); Y 0( )) (Y 0(!); Z( )) + (Z(!); Z( ))
(Z(!); Y 0( ))]%(d!) 6 0; [H (t; Y 0(!); Y 0( ); Z0(!)) H (t; Y 00(!); Y 0( ); Z00(!))+
+ H (t; Y 00(!); Y 00( ); Z00(!)) H (t; Y 0(!); Y 00( ); Z00(!))]%(d!) 6= 0: Отметим, что решение в рамках вероятностного подхода определяется выбором множества игроков , вероятностью % и функцией, определяющей начальное положение игрока X0 : ! Rd. Вообще говоря, доказанная в рамках этого подхода единственность – это единственность при заданном выборе вероятностного пространства. тогда и только тогда, когда график слабо инвариантен относительно дифференциального включения (x_ (t); z_(t)) 2 f( ; ) : 2 domh (t; x; ); > h (t; x; )g: (23) Здесь h (t; x; ) , sup [h ; pi h(t; x; p)];
p2Rd domh (t; x; ) = f : h (t; x; ) < 1g: При достаточно широких предположениях решения дифференциального включения (23) продолжимы.
В рамках минимаксного подхода решение системы (8), (9) определяется следующим образом. Прежде всего, напомним, что носитель вероятности (supp( )), определенной на некотором банаховом пространстве A, есть наименьшее замкнутое множество B такое, что для всех измеримых C A n B выполнено (C) = 0.
Далее, если V – некоторая функция, определенная на [0; T ] Rd, со значениями в R, – поток вероятностей (т.е. [t] – вероятность на Rd), то обозначим через S[V; ] множество кривых (x( ); z( )) : [0; T ] ! Rd+1, удовлетворяющих дифференциальному включению (x_ (t); z_(t)) 2 f( ; ) : 2 dom H (t; x; [t]; ); > h (t; x; )g; таких, что для всех t; s 2 [0; T ] Здесь
V (x(t)) z(t) = V (x(s)) z(s): H (t; x; m; ) = sup [h ; pi p2Rd
H(t; x; m; p)]; domH (t; x; m; ) = f : H (t; x; m; ) < 1g: Определение 1. Будем говорить, что пара (V; ), где V : [0; T ] является решением системы (8), (9), если
V – минимаксное/вязскостное решение уравнения (8); Rd ! R,
– поток вероятностей, существует вероятность , определенная на C([0; T ]; Rd+1), такая, что ее носитель лежит в множестве S[V; ], и для всех измеримых множеств A R
[t](A) = f(x( ); z( )) : x(t) 2 Ag: Теорема существования решения в рамках минимаксного подхода может быть получена при следующих предположениях:
H представим в виде
H(t; x; m; p) = mu2aUx[hp; f (t; x; m; u)i + g(t; x; m; u)]; функции f , g и
непрерывны (при этом по m предполагается топология слабой сходимости); функция f локально липшицева по x; начальное распределение m0 имеет первый абсолютный момент, т.е.
Z
Rd
kykm0(dy) < 1: Доказательство теоремы существования такого решения основано на доказательстве существования равновесия по Нэшу в игре бесконечного числа лиц и в этой части смыкается с вероятностным подходом. Предполагается, что задано множество игроков и неатомическая мера % на . Также предполагается выбранной функция X0 : ! Rd, физический смысл которой состоит в том, что она назначает каждому игроку его положение в начальный момент. Естественным условием является условие согласованности вероятности % и функции X0 с вероятностью m0: для всех измеримых множеств A Rd m0(A) = %(X0 1(A)): (24) Отметим, что всегда можно подобрать множество , вероятность % на нем и функцию X0 так, чтобы условие (24) выполнялось. Далее рассматривается игра бесконечного числа лиц, в которой положение каждого игрока X(t; !) задается системой
X(t; !) = f (t; X(t; !); [t]; u(t)); u(t) 2 P; X(0; !) = X0(!);
Z T 0
g(t; X(t; !); [t]; u(t))dt + (X(T; !); [T ]): Здесь – поток вероятностей, связанный с динамикой игроков правилом:
[t](A) = %f! : X(t; !) 2 Ag: В данной игре существует равновесие по Нэшу в классе обобщенных программных управлений (меруправлений). Полученное равновесие по Нэшу определяет вероятность и соответствующую функцию цены для пробного игрока, начавшего движение в некоторой позиции (t ; x ).
Вопрос о единственности в рамках минимаксного подхода пока не рассматривался. Однако было построено приближенное равновесие по Нэшу в игре конечного числа игроков в классе рандомизированных программных стратегий. 5
Игры среднего поля с локальной связью Для игр среднего поля с локальной связью (т.е. для системы (13), (14)) можно построить вязкостный подход, это сделано, в частности в [51]. Однако этот подход имеет те же ограничения, что и в случае нелокальной связи. В этом случае обобщенные решения строятся на основе концепции слабых решений [13] (см. также [15, 29]). Она развита в предположении, что
H(t; x; ; p) = h1(x; )
h2(x; p); 1. h1 непрерывна, возрастает по (напомним, что показатель q > 1 такой, что
2 R), также выполнено условие роста по : существует
h2(x; rV ) = 0; V (T; x) = (x); div(h2;p(x; rV ) ) = 0; (0; x) = 0(x): h2;p(x; p) = 1 C1 j j q 1
C1 6 h1(x; ) 6 C1j jq 1 + C1; 1 r rC2 j j
C2 6 h1(x; ) 6 Cr2 j jr + C2; Z
Td 0(x)dx = 1: Далее рассматривается задача минимизации функционала 2. h1 непрерывна, а также выпукла и дифференцируема по p; @h1=@p непрерывна; сама же функция h1 имеет суперлинейный рост по p, т.е. существуют показатель r > maxfd(q 1); 1g и константа C2 такие, что
непрерывно дифференцируема, 0 непрерывна, неотрицательна и Вводится функция F (x; ) по правилу
F (x; ) =
R0 h1(x; )d ;
+1;
> 0
< 0:
(
Понятие слабого решения основано на двух (дуальных) задачах оптимизации. Прежде всего, введем множество
K0 = f 2 C1([0; T ]
Td) : (T; x) = (x)g: Пусть
A0( ) =
F (x;
t(t; x) + h2(t; r (t; x)))dx dt
С исходным уравнением (
Z T Z 0
Td Z T Z 0
Td inf A0( ): 2K0 (t; x) =
Td Вторая оптимизационная задача связана с уравнением (26). Рассмотрим множество K1, состоящее из пар ( ; w) 2 L1([0; T ] Td) L1([0; T ] Td; Rd) таких, что > 0,
Z
Td
(t; x)dx = 1 t + div(w) = 0; (0; x) = 0(x): для почти всех t 2 [0; T ] и пара ( ; w) удовлетворяет в смысле распределений уравнению неразрывности Рассматривается функционал Отметим, что величина
B( ; w) =
Z T Z 0 Td (t; x)h2 t; w(t; x) (t; x) w(t; x)
(t; x) может рассматриваться как скорость потока в момент времени t в позиции x. Вторая оптимизационная задача состоит в минимизации величины B( ; w) при ( ; w) 2 K1.
Имеет место следующее свойство (дуальность оптимизационных задач): + F (x; (t; x)) dxdt +
(x) (T; x)dx: Z
Td inf A0( ) = 2K0
min B( ; w): ( ;w)2K1 (29) Доказательство этого факта основано на теореме Фенхеля–Рокафеллара [21]. Кроме того, минимум во второй оптимизационной задаче достигается на единственном элементе таком, что 2 Lq([0; T ] Td).
Для того чтобы найти минимизирующий элемент в первой оптимизационной задаче, проведем ее релаксацию. Для этого рассмотрим множество K, состоящее из пар ( ; ) 2 BV ([0; T ] Td) L1([0; T ] Td) таких, что (t; x) > Принципиальная польза введенного расширения состоит в том, что минимум в левой части достигается. Более того, если ( ; ) – минимизирующий элемент, то
удовлетворяет в вязкостном смысле неравенству т.е. для всех (a; b) 2 D (t; x) выполнено неравенство = maxf tac + h2(t; r ); 0g.
t h1(t; r ) 6 0;
a h1(t; b) 6 0;
Слабым решением системы (
div(h2;p(x; rV ) ) = 0; (0; x) = 0(x) выполнено в смысле распределений;
Z T Z 0 Td( tac(t; x) hr (t; x); h2(t; r (t; x))i) (t; x)dxdt = Z
Td ( (T; x) (x) 0(x) (0; x))dx: Отметим, что данное определение согласуется с классическим решением, т.е. классическое решение – слабое, а гладкое слабое решение является классическим.
Также единственность минизирующего элемента во второй задаче влечет единственность слабого решения.
Отметим, что по слабому решению может быть построено приближенное решение в игровой вариационной задаче N лиц с показателем качества i-го игрока
JiN ( 1; : : : ; N ) =
X j=1;N;j6=i
11 j(t)AA dt + ( (T )): Здесь L(x; ) – функция, сопряженная к функции p 7! h2(t; p), h10; 00 – результат двойного сглаживания функции h1 (вначале сглаживаем второй аргумент путем свертки с некоторой гладкой функцией при параметре, равном 0, потом саму функцию свертываем с тем же ядром при параметре 00).
Одна модель энергетических сетей x_ = (x (x xon); xoff ); устройство выключено; устройство включено: Если считать, что устройство управляется включением/выключением, то динамика температуры может быть переписана в виде где ; и – некоторые константы, > 0, u 2 [0; 1] – управляющее воздействие.
Если m – некоторая вероятность на R, то через E[m] обозначим среднюю по вероятности m: x_ = x + u + ; Z
R E[m] , xm(dx): Далее обозначим через E+[m] , maxfE[m] E ; 0g, E [m] = maxf (E[m] E ); 0g. Здесь E – номинальная температура сети.
Пусть [t] – распределение устройств по температуре в момент времени t. Интегральная часть функции платы каждого игрока определяется функцией g = u(t)(r + qx2(t) + hE + [ [t]] + (1
u(t))(qx2(t) + kE [ [t]]) = = ru(t) + qx2(t) + hE+[ [t]]u(t) + kE [ [t]](1 u(t)): Предполагается, что r; q; h и k – положительные константы. Смысл этой функции платы следующий: каждый игрок стремится к минимизации времени включения устройства, температуры устройства, также каждый игрок наказывается за включение устройства, когда температура сети выше номинала, и за невключение устройства, если температура ниже номинала.
Как видно, мы имеем ситуацию, когда поведение каждого игрока определяется средним состоянием системы. При этом гамильтониан равен
H(t; x; m; u) = um2[a0;x1]f x + u + + ru + ru(t) + qx2 + hE+[m]u + kE [m](1 u)g: Данная задача может быть исследована в рамках описанных выше подходов для игр среднего поля с нелокальной связью или с использованием специальных методов, предложенных в [8]. Благодарности Список литературы
Работа частично поддержана в рамках Программы Президиума РАН “Математические задачи современной теории управления” и гранта РФФИ 15-01-07909. [1] Y. Achdou. Finite difference methods for mean field games. In Hamilton-Jacobi Equations: Approximations,
Numerical Analysis and Applications:1-47. Springer, 2013. [2] Y. Achdou, F. Camilli, I. Capuzzo-Dolcetta. Mean field games: numerical methods for the planning problem.
SIAM J. Control Optim., 50(1):77-109, 2012. [3] Y. Achdou and I. Capuzzo-Dolcetta. Mean field games: numerical methods. SIAM J. Numer. Anal., 48(3):1136-1162, 2010. [4] Yu. V.Averboukh. A minimax approach to mean field games. Sbornik: Mathematics, 206(7):893–920, 2015 (in Russian). = Ю. В. Авербух. Минимаксный подход к играм среднего поля. Матем. сб., 206(7):3-32, 2015.
Deterministic limit of mean field games associated with nonlinear markov processes. [46] D. Lacker. A general characterization of the mean field limit for stochastic differential games.
arXiv:1408.2708, 2014. [57] N.N. Subbotina. Universal optimal strategies in positional differential games. Differential Equations 19:1377– 1382, 1983. Yurii Averboukh Krasovskii Institute of Mathematics and Mechanics (Yekaterinburg, Russia), Ural Federal University (Yekaterinburg, Russia) Keywords: mean field games, differential games, N -person games, Nash equilibrium.
This survey attempts to describe the main directions of the first order mean field games theory. We present the general theoretical results concerning first-order MFG. Additionally, the model of power-grid is discussed which is studied within MFG point of view.