Неантагонистические дифференциальные игры со случайными моментами выхода игроков из игры тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

На правах рукописи

Костюнин Сергей Юрьевич

НЕАНТАГОНИСТИЧЕСКИЕ ДИФФЕРЕНЦИАЛЬНЫЕ ИГРЫ СО СЛУЧАЙНЫМИ МОМЕНТАМИ ВЫХОДА ИГРОКОВ ИЗ ИГРЫ

01.01.09 - Дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

005552581

1 8 СЕН 2014

Санкт-Петербург 2014

005552581

Работа выполнена в Санкт-Петербургском государственном университете.

Научный руководитель: доктор физико-математических наук,

профессор, Пстросян Леон Аганесович

Официальные оппоненты: Клейменов Анатолий Федорович,

доктор физико-математических наук, профессор, Институт математики и механики им. H.H. Красопского Уральского отделения РАН, ведущий научный сотрудник

Сандомирская Марина Сергеевна, кандидат физико-математических наук, Санкт-Петербургский экономико-математический институт РАН, младший научный сотрудник

Ведущая организация: Институт прикладных математических иссле-

дований Карельского научного центра РАН

Защита состоится «fiA^f^S^-ß 2014 г. в ^ часов на заседании диссертационного совета Д 212.232.29 на базе Санкт-Петербургского государственного университета по адресу: 199178, Санкт-Петербург, 10 линия В.О., д. 33/35, ауд. 74.

С диссертацией можно ознакомиться в Научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199304, Санкт-Петербург, Университетская наб., 7/9 и на сайте http://apbu.iu/8cience/ disser/dissertatsii-dopushchennye-k-zashchite-i-svedeiiiya-o-zashchite.

Автореферат разослан

. 2014 г.

Ученый секретарь диссертационного совета, доктор физ.-мат. наук, профессор

Нежинский В. М.

Общая характеристика работы

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

Теория дифференциальных игр сформировалась как отдельный раздел математической теории игр в пятидесятых годах двадцатого века. Одними из первых интересные результаты в этой области получили Р. Айзеке, Л. Берковитц,

B. Флеминг.

Долгое время исследования были посвящены в основном антагонистическим дифференциальным играм. Значительные успехи в данной области связаны с представителями отечественной научной школы Н. Н. Красовским, Л. А. Петросяном, Л. С. Понтрягиным.

Толчком для развития теории неантагонистических дифференциальных :игр послужили задачи конфликтного управления со многими участниками из различных практических областей. В качестве принципа оптимальности в неантагонистических дифференциальных играх чаще всего рассматривается равновесие по Нэшу в программных или позиционных стратегиях. Основные результаты, посвященные исследованию вопроса существования и проблемы построения равновесия по Нэшу, получены в работах А. Ф. Клейменова, А. Ф. Кононенко,

C. В. Чистякова. .

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

Впервые задача со случайной продолжительностью в игровой постановке была рассмотрена Л. А. Петросяном и Н. В. Мурзовым в работе «Теоретико-игровые задачи механики». В данной работе исследовалась дифференциальная игра преследования двух лиц, продолжительность которой задавалась некоторой случайной величиной с абсолютно непрерывной функцией распределения. Для заданной таким образом игры авторами было получено уравнение типа Айзекса-Беллмана.

Дифференциальные игры со случайной продолжительностью в общей постановке были введены в совместной работе Л. А. Петросяна и Е. В. Шевкопляс. В работах Е. В. Шевкопляс были продолжены исследования кооперативных дифференциальных игр со случайной продолжительностью, получены важные результаты, относящиеся к проблеме динамической устойчивости кооперативных принципов оптимальности.

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

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

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

Теоретическая и практическая значимость. Работа носит теоретиче-

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

Основные результаты, выносимые на защиту:

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

2. Для введенного класса дифференциальных игр двух лиц со случайной продолжительностью получена система уравнений Гамильтона-Якоби-Белл-мана и теорема, дающая достаточные условия существования состоятельного позиционного равновесия по Нэшу.

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

4. Исследована дифференциальная игра управления вредными выбросами. В условиях случайной продолжительности получены необходимые уело-

вия существования равновесия по Нэшу. Найдено в явном виде и исследовано решение, удовлетворяющее необходимым условиям.

5. На основе игры управления вредными выбросами построена кооперативная дифференциальная игра, в которой найдены вектор Шепли, выбранный в качестве принципа оптимальности, и процедура распределения дележа, гарантирующая динамическую устойчивость вектора Шепли.

Научная новизна работы. Все основные результаты, представленные в диссертации, являются новыми.

Апробация работы. Основные результаты диссертационной работы были представлены на IV - VII Международных конференциях «Теория игр и менеджмент» (Санкт-Петербург, 2010 - 2013), на Всероссийской конференции «Устойчивость и процессы управления» (Санкт-Петербург, 2010), на международной научной конференции «Математика, экономика, менеджмент: 100 лет со дня рождения Л.В. Канторовича» (Санкт-Петербург 2012), на Международной конференции «Constructive Nonsmooth Analysis and Related Topics» (Санкт-Петербург, 2012), на XLI - XLIII международных научных конференциях аспирантов и студентов «Процессы управления и устойчивость» (Санкт-Петербург, 2010 - 2012), а также на семинарах кафедры математической теории игр и статистических решений и центра теории игр факультета Прикладной математики - процессов управления Санкт-Петербургского государственного университета.

Публикации. По материалам диссертации опубликованы работы [1-10]. Из них статьи [1, 2] опубликованы в журнале, входящем в список ведущих российских рецензируемых научных журналов ВАК РФ. Статьи [7,10] опубликованы в высокорейтинговых журналах, входящих в базу данных Scopus. Работы [3-6, 8, 9] опубликованы в материалах конференций.

Работы [1-4, 6-10] написаны в соавторстве. В работах [1,6, 7] диссертантом была предложена постановка задачи в виде дифференциальной игры со случайными моментами выхода игроков из игры, получен упрощенный вид функцио-

налов выигрыша, выведена система уравнений Гамильтона-Якоби-Беллмана. В работах [2, 3, 8] диссертанту принадлежат формулировки и доказательства теорем, построение контрпримера, а соавтору - постановка задачи и выбор методов решения. В статье [4] диссертантом получены основные результаты, а соавтором предложены для исследования различные функции полезности. В работах [9, 10] диссертантом предложена математическая модель управления вредными выбросами, получено решение кооперативной версии игры.

Структура и объем. Диссертация изложена на 101 странице, состоит из введения, четырех глав, заключения и списка литературы, включающего 64 наименования.

Содержание работы

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

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

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

ные условия представления выигрыша в упрощенном виде. В параграфе 1.3 приводится пример, когда достаточные условия, полученные в теореме 1.2, не выполняются. Показывается, что выигрыш в виде математического ожидания в этом случае не может быть упрощен.

Вторая глава посвящена исследованию дифференциальной игры управления вредными выбросами, обобщенной на случай случайной продолжительности игры.

В параграфе 2.1 строится теоретико-игровая модель управления вредными выбросами. Рассматриваются п игроков, каждый из которых имеет промышленное производство на своей территории. В каждый момент времени t управляющим параметром для каждого игрока является объём вредных выбросов ei(i) € [0; i € N, где N = {l,...,n}. Функции Cj(f) предполагаются кусочно-непрерывными функциями времени.

Динамика изменения общего уровня загрязнения P(t) задается дифференциальным уравнением

п

P(i) = 2>(t) 1=1

с начальными условиями

Р{ 0) = Р0 > 0.

Функция плотности выигрыша игрока i € N равна

hi(P(t),ei(t)) = ei(t)(bi - 1/2ei(t)) - ¿¡Р&), tfc > 0.

В качестве распределения момента окончания игры Т выбирается распределение Вейбулла. Функция распределения момента окончания имеет вид

F(t) = 1 - e~Xt', t > 0, Л > 0,5 > 0.

Определяется функционал выигрыша для игроков, задаваемый математи-

ческим ожиданием:

tfi(0,Polei,...,en) =Е

(е;(т)(Ь;-1/2е;(т))-4Р(т))сгт

, ieN.

В параграфе 2.2 к построенной модели применяются результаты параграфа 1.2. Строятся оценки функционала выигрыша, которые позволяют показать выполнение полученных в теореме 1.2 достаточных условий. Выводится упрощенный вид функционала выигрыша:

00

ЩО, Р0, еь ..., еп) = | (е^)(Ь{ - 1/2ф)) - ¿¡Р(«)) е-*'А. о

Параграф 2.3 посвящен построению равновесия по Нэшу в программных стратегиях. В качестве необходимого условия применяется принцип максимума Понтрягина, для нахождения максимума гамильтониана используются условия Куна-Таккера. Полученные решения анализируются при различных значениях параметров А, <5 распределения момента окончания игры.

В параграфе 2.4 на основе рассматриваемой неантагонистической дифференциальной игры строится кооперативная дифференциальная игра. Для определения характеристической функции У(5, Р),5 С N используется нестандартный подход: полагается, что игроки, объединившиеся в коалицию Б, максимизируют свой суммарный выигрыш, а игроки, не входящие в коалицию 5, придерживаются своих равновесных стратегий. При таком подходе следует дополнительно показать супераддитивность введенной характеристической функции.

Утверждение 2.1. Характеристическая функция V (5, Р) удовлетворяет свойству супераддитивности:

У(ЗиТ,т,Р)>У(8,т,Р) + У(Т,т,Р), т > 0; 5,Т с Ж,5ПТ = 0.

В качестве принципа оптимальности рассматривается вектор Шепли. Предполагается, что в игре принимают участие три игрока./V = {1,2,3}, а параметры = (I для всех i € N. В этом случае компоненты вектора Шепли можно получить в явном виде:

ЯМ*, = + + е где В(Ю = £

keN

Для обеспечения динамической устойчивости вектора Шепли вводится процедура распределения дележа (ПРД) /3(t) = {Pi(t)}ieN,t > 0. Для определения ПРД получено следующее соотношение

В явном виде ПРД имеет следующий вид

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

Рассматривается дифференциальная игра двух лицГ(£0, Динамика игры задаётся системой обыкновенных дифференциальных уравнений в векторной форме:

x(t) = 4>(t,x(t),ui,u2), x(t0) = Xq,

где x £ Rm, щ = Ui{t,x) eUiC compR\ ф(Ь,х,иии2) 6 Rm. Далее полагаются выполненными следующие условия: функцияф(1, х, щ,и2) непрерывна по своим агрументам и удовлетворяет условию Липшица по х:

\\ф(ь,х',щ,и2) - ф(г,х",иии2)\\ < к!\\х'-х"\\, ih = const),

для всех хх" € Rm, где ||-|| - евклидова норма; кроме того, для всех возможных значений t,x,u\,u2 выполнено

\\ф(1,х,иии2)\\ < к2{ 1 + М), (hi = const).

Каждый игрок имеет свой собственный случайный момент выхода из игры, 71 и Т2 соответственно. Предполагается, что Т\\\Т2 независимые абсолютно

непрерывные случайные величины, функции распределения и плот-

ности распределения /1(-), /г(') которых известны обоим игрокам.

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

Ь{(Ь,х,щ,и2)(1Щт.<т.]+

К{(г0,Х0,иии2) = Е

Ьо

+

^{Ь, X, иии2)с1Щт.>7}] + ф;(75> ХСТ]))1\Ъ>Ъ]

{1,2} [хфз), (1)

где ¡1^,х,щ,и2) - плотность выигрыша игрока г € {1,2}; 1[.] - индикаторная функция (равная единице при выполнении условия в скобках и нулю в противоположном случае), Е[-] - математическое ожидание.

Ъ

Вводятся следующие обозначения: Ф1(71, 7г) = / /^(¿)<М[7;<т-] +

(о

Ъ

+ / /ц(г)сМ[7;>7-], ФзСТъТг) = Далее предполагается, что

(о

моменты выхода игроков из игры распределены на отрезке [40, Лемма 3.1. Ожидаемый интегральный выигрыш игрока i может быть представлен в виде:

Е[%(ТиЪ)] =

при этом выражение в правой части равно ]

/ц(т)[1-Я(т)][1-ВД]А- = Е

Ы(т)[1 - Ъ(т)}[1 - Ъ(т)}с1т,

ат{ТиТ2}

Лемма 3.2. Ожидаемый терминальный выигрыш игрокаг может быть представлен в виде:

(о

Теорема 3.1. Ожидаемый выигрыш игрокаг (1) может быть представлен в виде:

где F(t) - функция распределения случайной величины Л1 = min{71,72}. Определение 3.1. Набор стратегий {7¡(t,x) € = 1,2} образует в игре r(io, яго) состоятельное позиционное равновесие по Нэшу, если существуют функции Vi(t,x) (аналоги функции Беллмапа), определенные на [io,w] х Rm и удовлетворяющие следующим условиям

ш

to

+Ф;(т,х(т)Шт)( 1 - Fi(T)))dr, i,j е {1,2} (г ф j), (2)

V1(w,x) = 0, V2{w,x)=0-,

W

J (/г!(т, a;*(r), -yj;x), x))[1 - F(r)} + Ф^т, х*(т))/2(т)(1 - ВД))

dr >

1

t

+Ф1(г,г'1'(г))/2(г)(1 - Fi(r)))dr, Vi 6

(Ji2(t,x*(t), 7J(t, x), 72(т, x))[1 - F(r)] + Ф2(т, x*(r))/i(r)(l - F2(r)))

dr >

>

(h2 (т, ж'2' (т), 7i (т, т), 72(т, х)) [1 - F(r)]+

(1 - Fx(t))(l - Fa(t)), t

+Ф2(г,х-[21(т))/1(г)(1 - F2(r)))dr, Vi 6 [io.w), для всех 7i(r, x), i = 1,2. Дри этом на промежутке [¿о,ы]:

х*(т) = ф(т,х*(т),-у1 (г, х), 72 (т, х)), х*(£) = х;

¿14(7-) = 0(T,*%),7i(T,X),72V,*)), *|Ч(*) =

±Й(т) = 0(т, хИ(т), 7Г(г, х), ts(t, х)), ^(t) = х.

Теорема 3.3. Набор стратегий {7*(£,х) € Ui,i = 1,2} является состоятельным позиционным равновесием по Нэшу в игре Г(£о,хо), если существуют непрерывно-дифференцируемые фу>1кцииУ^,х) : [¿о, ш] х Rm R, i £ {1, 2}, удовлетворяющие системе дифференциальных уравнений в частных производных (3)-(4) с граничными условиями (5)

W)

= шах «i6t/i

ML

Fi(t) ' 1 -F2(t) dVi(t, x)

)-

dVi(t,x)

at

dx

+/ii(i,x,ui,72*(i,x)) + Ф1 (£, x)

Mt)

v2

■ + ■

Mt)

max

U2&U2

Сt) 1 -W)

dV2{t ,x)

1 - F2(t)

dV2(t,x) dt

(3)

dx

<t>(t,x,Yi(t,x),u2)+

ЛС0

1 - Fi(i)

(4)

И(ы,х) = 0, V2(w,x)=0.

(5)

Отдельно рассматривается случай, когда игра Г(£о, xq) после выхода одно-

го из игроков сводится к задаче оптимального управления для другого игрока:

д{(т,х,щ)йт

,t

max < Е

I

х = <j>i(T,x,Ui), г €{1,2}.

Теорема 3.4. Набор стратегий {7¡(t,x) £Ui,i = 1,2} является состоятельным позиционным равновесием по Нэшу в игре r(io, хд), если существуют непрерывно-дифференцируемые функции Vi(t,x) : [io,w] х Rm i 6 {1,2J-,

удовлетворяющие системе дифференциальных уравнений в частных производных (3)-(4) с граничными условиями (5), где Ф{((, х), г € {1,2} - функции, удовлетворяющие уравнениям

дФ i{r,x)

--i-- + Ф<(т, х)Х ¡(т) = шах

ОТ UiiUi

Фг(ш,х) = О, ОФ i(T,x)

дх

Ф^т,х,щ)'+ gi(t,x,ui)

,ie {1,2},

где - функция интенсивности отказов для момента окончания управляемого процесса для игрока г € {1,2}.

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

В параграфе 4.1 строится модель дифференциальной игры. В игре принимают участие два игрока - фирмы, ведущие совместную разработку невозобновляемого ресурса. Для каждой фирмы момент окончания разработки является случайной величиной. После окончания добычи ресурса одной из фирм, другая продолжает разработку до своего момента окончания.

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

В параграфе 4.3 с учетом функции значения игрока в задаче оптимального управления определяется его функционал выигрыша в дифференциальной игре. Состоятельное позиционное равновесие по Нэшу в игре разработки невоз-ебновляемого ресурса строится путем решения системы уравнений Гамильтона-Якоби-Беллмана.

В параграфе 4.4 полученные равновесные стратегии анализируются для случая усеченного экспоненциального распределения. Исследуется зависимость оптимального поведения игроков от параметров распределения их моментов окончания разработки невозобнозляемого ресурса. Проводится сравнение равновесия в игре в новой постановке и равновесия в дифференциальной игре со случайным моментом окончания в общепринятой постановке.

В Заключении приведены основные результаты, полученные в работе.

Публикации автора по теме диссертации

1. Костюнин С. Ю., Палестини А., Шевкопляс Е. В. Об одной дифференциальной игре, моделирующей разработку невозобновляе-мого ресурса // Вестник С.-Петерб. ун-та. Сер 10: Прикладная математика, информатика, процессы управления. 2013. Вып. 3. С. 73-82.

2. Костюнин С. Ю., Шевкопляс Е. В. Об упрощении интегрального выигрыша в дифференциальных играх со случайной продолжительностью // Вестник С.-Петерб. ун-та. Сер 10: Прикладная математика, информатика, процессы управления. 2011. Вып. 4. С. 47-56.

3. Костюнин С. Ю., Шевкопляс Е. В. Одна модифицированная теоретико- игровая модель регулирования вредных выбросов // Процессы управления и устойчивость: Труды 41-й международной научной конференции аспирантов и студентов / под ред. Н. В. Смирнова, Г. Ш. Тамасяна. СПб.: Издат. Дом С.-Петерб. гос. ун-та, 2010. С. 647-653.

4. Костюншг С. Ю., Шепкопляс Е. В. О выборе функции полезности в задачи разработки невозобновляемого ресурса // Процессы управления и устойчивость: Труды 43-й международной научной конференции аспирантов и студентов / под ред. А. С. Еремина, Н. В. Смирнова. СПб.: Издат. Дом С.-Петерб. гос. ун-та, 2012. С. 527-531.

5. Kostyunin S. Differential games with random terminal instants // Contributions to game theory and management, vol. VI. SPb.: Graduate School of Management SPbU. 2013. P. 222-230.

6. Kostyunin S., Palestini A., Shevkoplyas E. Differential game of resource extraction with random time horizon and different hazard functions // Процессы управления и устойчивость: Труды 42-й международной научной конференции аспирантов и студентов / Под ред. А. С. Еремина, Н. В. Смирнова. СПб.: Издат. Дом С.-Петерб. гос. ун-та, 2011. С. 571-576.

7. Kostyunin S, Palestini A, Shevkoplyas E. On a nonrenewable resource extraction game played by asymmetric firms // Journal of Optimization Theory and Applications. 2013. P. 1-14. Available online: http://dx.doi.org/10.1007/sl0957-013-0462-x.

8. Shevkoplyas E., Kostyunin S. Modelling of Environmental Projects under Condition of a Random Time Horizon // Contributions to game theory and management, vol. IV. SPb.: Graduate School of Management, SPbU. 2011. P. 447-459.

9. Wrzaczek S, Shevkoplyas E, Kostyunin S. Differential Game of Pollution Control with overlapping generations // Contributions to game theory and management, vol. V. SPb.: Graduate School of Management SPbU. 2012. P. 310-320.

10. Wrzaczek S, Shevkoplyas E, Kostyunin S. A differential game of pollution control with overlapping generations // International Game Theory Review. 2014. Vol. 16, no. 3. P. 1450005.

Подписано к печати 30.06.14. Формат 60x84 Vi& .

Бумага офсетная. Гарнитура Тайме. Печать цифровая. 11еч. л. 1,00.

_Тираж 100 экз. Заказ 6045._

Отпечатано в Отделе оперативной полиграфии химического факультета СПбГУ 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 26 Тел.: (812)428-4043,428-6919