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

• Шевкопляс, Екатерина Викторовна
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Шевкопляс, Екатерина Викторовна

Введение

1 Кооперативные дифференциальные игры со случайной продолжительностью.

§1.1 Определение кооперативной дифференциальной игры Гу(жо) в форме характеристической функции.

§ 1.2 Принцип динамической устойчивости в игре Гу(жо) • • • •

§ 1.3 Случай разрывной функции распределения момента окончания игры.

§ 1.4 Регуляризованные динамически устойчивые принципы оптимальности

§1.5 Уравнение Гамильтона-Якоби-Беллмана.

§ 1.6 Алгоритм регуляризации принципов оптимальности в игре

Г уЫ.

§ 1.7 Регуляризация С-ядра и вектора Шепли в игре Гу(ж0) • •

§ 1.8 Сильно динамически устойчивые принципы оптимальности.

§ 1.9 Сильная динамическая устойчивость регуляризованных принципов оптимальности

§ 1.10 Пример регуляризации вектора Шепли.

§1.11 Кооперативные игры с дисконтированными выигрышами

2 Многошаговые кооперативные игры со случайным числом шагов.

§2.1 Определение многошаговой кооперативной игры Gy{z$) в форме характеристической функции.

§ 2.2 Принцип динамической устойчивости в игре Gy (zo)

§ 2.3 Введение новой характеристической функции

§ 2.4 Регуляризованные динамически устойчивые принципы оптимальности

§ 2.5 Регуляризация вектора Шепли и С-ядра в игре Gy(zo)

§ 2.6 Алгоритм регуляризации вектора Шепли в игре Gy(zo)

§2.7 Сильно динамически устойчивые принципы оптимальности

§2.8 Регуляризованные сильно динамически устойчивые принципы оптимальности.

§2.9 Пример динамически устойчивого решения в кооперативной многошаговой игре двух лиц.

§2.10 Пример регуляризации вектора Шепли в кооперативной многошаговой игре двух лиц.

Введение диссертации (часть автореферата) на тему «Кооперативные дифференциальные игры со случайной продолжительностью»

Актуальность темы. Одной из основных задач современной теории игр является конструирование и анализ принципов оптимального поведения участников в различных задачах конфликтного управления. Естественным подходом к изучению кооперативных динамических игр, как игр дележей, является попытка переноса результатов классической кооперативной теории "однократных"игр Неймана-Моргенштерна [19]. Однако при использовании результатов классической теории необходимо дополнительно исследовать вопрос о динамической и сильно динамической устойчивости полученного решения. Попытки применения динамически неустойчивых принципов оптимальности при решении прикладных задач в области экономики, экологии, менеджмента приводят к нереализуемости таких принципов, поскольку в некоторый момент времени возникают условия, когда соглашение о кооперации могут быть пересмотрено.

Это обстоятельство впервые было замечено JI.A. Петросяном в 1977 году [25]. Позднее введенные им термины динамической и сильно динамической устойчивости в англоязычной литературе трансформировались в "состоятельность во времени "и "сильную состоятельность во времени "соответственно. Исследованиям проблемы динамической устойчивости посвящены работы [9], [23], [24], [29] и др.

В настоящее время одним из наиболее бурно развивающихся разделов теории игр являются кооперативные дифференциальные игры [4], [13], [15], [39]. Также следует отметить перспективное направление, связанное с развитием теории стохастических игр, введенных Шепли в 1953 году [56], а также дифференциальных игр при наличии неопределенности [11], [12] , [14], [33], [49], поскольку использование при моделировании фактора той или иной неопределенности позволяет наиболее адекватно описывать самые разнообразные процессы, происходящие в экономике, экологии, менеджменте, торговле, при принятии решений в области международных отношений, систем безопасности и пр!

В данной работе вводится новый класс дифференциальных игр — кооперативные дифференциальные игры п лиц со случайной продолжительностью Т — to. Случайность времени существования любого организма, системы, процесса заложена в окружающую человека реальность, поэтому спектр приложений кооперативных дифференциальных игр со случайной продолжительностью может быть велик. Отметим, что в работе J1.A. Петросяна и Н.В. Мурзова "Теоретико-игровые задачи механики" в 1966 г. [30] впервые были исследованы дифференциальные игры преследования двух лиц со случайной продолжительностью. В рассматриваемой авторами задаче продолжительность игры Т являлась случайной величиной с абсолютно непрерывной функцией распределения F(t) и множеством возможных значений в отрезке [0,То]. В этой же работе впервые было выведено уравнение типа Айзекса-Беллмана для заданной таким образом игры преследования.

В кооперативных дифференциальных играх супераддитивность характеристической функции не обеспечивает сохранение кооперации между игроками во время всей игры.Предположим, что перед началом игры игроки договариваются об использовании ими некоторого принципа оптимальности С{хо) и по окончанию игры рассчитывают получить некоторый соответствующий ему дележ £ Е С{хо). Развитию игры во времени соответствует движение вдоль оптимальной траектории #*(£), на которой по определению игроки получают наибольший ожидаемый дележ. Однако движение вдоль оптимальной траектории еще не обеспечивает, сохранение кооперации. Действительно, при движении вдоль x*(t) игроки попадают в подыгры с текущими начальными состояниями, в которых один и тот же игрок имеет различные возможности. Следовательно, в некоторый момент -д может возникнуть ситуация, когда решение текущей игры будет неоптимальным в смысле первоначально выбранного принципа оптимальности С{х$). В таком случае перед игроками встанет вопрос о целесообразности придерживаться далее намеченного перед началом игры соглашения действовать "совместно оптимально". Последнее будет означать динамическую неустойчивость принципа оптимальности С{хо) и, соответственно, самого движения по траектории x*(t). Следовательно, проблема динамической устойчивости является очень важной для кооперативных дифференциальных игр со случайной продолжительностью. Разрешить данную проблему предлагается путем введения специальных выплат (процедуры распределения дележа), которые будут регулировать распределение общего выигрыша во времени так, чтобы ни в какой момент времени t G [£0, сю) ни у кого из игроков не возникло желание уклониться от первоначального соглашения.

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

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

Научная новизна работы заключается в том, что в ней:

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

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

3. получено и обосновано уравнение Гамильтона-Якоби-Беллмана для кооперативных дифференциальных игр со случайной продолжительностью.

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

Основные положения, выносимые на защиту:

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

2. Получено аналитическое выражение для процедуры распределения дележа при динамической устойчивости принципа оптимальности.

3. Проведена регуляризация классических принципов оптимальности, приводящая к динамической и сильно динамической устойчивости. Регуляризация задана в форме алгоритма.

4. Получено уравнение Беллмана-Гамильтона-Якоби для нахождения значения кооперативной дифференциальной игры со случайной продолжительности .

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

Апробация работы. Основные результаты были представлены на семинарах кафедры математической теории игр и статистических решений, на семинарах Центра теории игр, на XXX и XXXI научных конференциях "Процессы управления и устойчивость" (Санкт-Петербург, 1999, 2000 гг.), на 3 международной конференции "Logic, Game Theory and Social Choices" (Италия, University of Sciena, 2003), на семинаре Механико-математического факультета Саратовского государственного университета имени Н.Г. Чернышевского (Саратов, 2004). 1

По материалам диссертации опубликованы работы [28], [36], [37], [32], [53], [54], [55].

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

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Шевкопляс, Екатерина Викторовна

Заключение

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

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

3. Получено уравнение Беллмана-Гамильтона-Якоби для функционала, являющегося математическим ожиданием совместного выигрыша игроков.

4. Рассмотрены кооперативные многошаговые игры со случайным числом шагов. Введены понятия процедуры распределения дележа, динамической и сильно динамической устойчивости принципа оптиv мальности. Приведен алгоритм регуляризации принципов оптимальности для данного класса игр.

Список литературы диссертационного исследования кандидат физико-математических наук Шевкопляс, Екатерина Викторовна, 2004 год

1. Айзеке Р. Дифференциальные игры. М., 1967.

2. Беллман Р. Динамическое программирование. М., 1960.

3. Болтянский В. Г. Математические методы оптимального управления. Москва, "Наука", 1969.

4. Вайсборд Э. М.,Жуковский В. И. Введение в дифференциальные игры нескольких лиц и их приложения. М.: "Советское радио", 1980.

5. Вентцелъ Е. С.,Овчаров Л. А. Теория вероятностей М.: "Наука", 1969.

6. Воробьев Н. Н. Основы теории игр. Бескоалиционные игры. М: Наука, 1984.

7. Воробьев Н. Н. Теория игр для экономистов-кибернетиков. М.: На• ука, 1985.

8. Горелик В. А., Кононенко А. Ф. Теоретико-игровые модели принятия решений в эколого-экономических системах. М., 1982.

9. Данилов Н.Н. Кооперативные многошаговые игры с побочными платежами // Изв. Вузов. Мат. 1991. №2. С.33-42.

10. Данилов В.И. Лекции по теории игр. М: РЭШ, 2002.

11. Жуковский В. И. Кооперативные игры при неопределенности и их приложения. М.: Эдиториал УРСС. 1999, 334 с.

12. Жуковский В. И., Молоствов В. С. Многокритериальная оптимизация систем в условиях неполной информации. М.: Международный научно-исследовательский институт проблем управления, 1990, 112 с.

13. Клейменов А.Ф. Неантагонистические дифференциальные игры. Екатеринбург: Наука, 1993, 184 с.

14. Кононенко А. Ф., Халезов А. Д., Чумаков В. В. Принятие решений в условиях неопределенности. М.: ВЦ АН СССР, 1991. 197 с.

15. Красовский Н. Н., Субботин А. И. Позиционные дифференциальные игры. М., 1974.

16. Куммер Вернд. Игры на графах. М: Мир, 1982.

17. Лагунов В. Н., Сушкин В. В. Многошаговые позиционные игры N лиц. Тверь, 1993.

18. Мулен Э. Теория игр с примерами из математической экономики. М: Мир, 1985.

19. Нейман В. фон, Моргенштерн О. Теория игр и экономическое поведение. М: Наука, 1970.

20. Петросян Л. А., Данилов Н. Н. Устойчивость решений в неантагонистических дифференциальных играх с трансферабельными выигрышами // Вестник Ленинградского университета. 1979. №1

21. Петросян Л. А., Захаров В. В. Математические модели в экологии. СПб: Изд. СПбГУ, 1996.

22. Петросян Л. А., Зенкевич П. А., Семина Е. А. Теория игр. М: Высш. шк., 1998.

23. Петросян Л. А., Кузютин Д. В. Игры в развернутой форме: оптимальность и устойчивость. СПб: Изд. СПбГУ, 2000.

24. Петросян Л. А., Томский Г. В. Динамические игры и их приложения. Л: Изд. ЛГУ, 1982.

25. Петросян Л. А. Устойчивость решений в дифференциальных играх со многими участниками. Вестник Ленинградского университета, 1977, N 19, Вып. 4.

26. Петросян Л. А.Неантагонистические дифференциальные игры. В кн.: Вопросы механики процессов управления, управление динамическими системами. Л., 1978.

27. Петросян Л. А. Решение неантагонистических дифференциальных игр п лиц. В кн.: Динамическое управление. Тезисы докладов Всесоюзной конференции. Свердловск, 1979.

28. Петросян Л. А., Баранова Е. М., Шевкопляс Е. В. Многошаговые кооперативные игры со случайной продолжительностью. Труды Института Математики и Механики уральского отделения РАН, т.10, в.2, 2004, стр. 116 130.

29. Петросян Л. А., Данилов Н. Н. Кооперативные дифференциальные игры и их приложения. Томск, 1985.

30. Петросяп JI. А., Мурзов Н. В. Теоретико-игровые задачи механики. Литовский математический сборник, вып.VI, 1966.

31. Петросян Л. А., Савищенко Н. И. Теоретико-игровая модель загрязнения воздушного бассейна. СПбГУ, 1997.

32. Петросян Л .А., Шевкопляс Е. В. Кооперативные дифференциальные игры со случайной продолжительностью. "Вестник СПбГУ", издание СПбГУ, 2001, серия 4, выпуск 1, стр. 21-28.

33. Петросян Л. А., Янг В. К. Кооперативные дифференциальные игры с неопределенными выигрышами. "Ветник СпбГУ", выпуск 3, 2000.

34. Феллер В. Введение в теорию вероятностей и ее приложения, т.1, 2. М.: "Мир", 1967.

35. Розен В. В. Математические модели принятия решений в экономике. М.: Книжный дом "Университет", 2002.

36. Шевкопляс Е .В. Кооперативные дифференциальные игры со случайной продолжительностью.//Труды XXX научной конференции "Процессы управления и устойчивость". СПбГУ, 1999, стр. 547-551.

37. Шевкопляс Е .В. Кооперативные многошаговые игры со случайным числом шагов". //Труды XXXI научной конференции "Процессы управления и устойчивость". СПбГУ, 2000, стр. 501-504.

38. Янг Л. Лекции по вариационному исчислению и теории оптимального управления. Москва, "Мир", 1974.

39. E.J. Dockner, S. Jorgensen, N. van Long, G. Sorger. Differential Games in Economics and Management Science. Cambridge University Press, 2000.

40. Dolchetta I. C. Hamilton-Jacobi-Bellman Equation and Optimal Control. International Series of Numerical Mathematics. Vol. 124. 1998, Birkhauser Verlag, Bazel. pp. 121-128.

41. Fudenberg D., Tirole J. Game theory. Cambridge: MIT press, 1991.

42. Germain, M., Toint, P., Tulkens, H., de Zeeuw, A.J. Transfers to Sustain Core-theoretic Cooperation in International Stock Pollutant Control. CLIMNEG, Working Paper No. 6, 1998.

43. Haurie, A., Zaccour, G. Differential Game Models of Global Environment Management. Annals of the International Society of Dynamic Games 2, 3-24, 1995.

44. Kaitala, V., Pohjola, M. Sustainable International Agreements on Green House Warming: a Game Theory Study. Annals of the International Society of Dynamic Games 2, 67-88, 1995.

45. Filar, G. A. and L. A. Petrosjan. Dynamic Cooperative Games. International Game Theory Review. 2000, Vol. 2, No. 1, pp. 47-66.

46. Owen G. Game Theory. W. B. Saunders Company. Philadelphia-London-Toronto. 1986.

47. Straffin P. D. Game Theory and Strategy. Washington. Washington: The Math. Associat. America, 1993.

48. Villiger R., Petrosjan L.A. Construction of Time-Consistent Imputations in Differential Games // Proc. 2nd International Conference "Logic, Game Theory and Social Choice". 2001.

49. Zhukovsky V.I., Molostvov V.S., and K.S.Vaisman. Non-Cooperative Games under Uncertainity. Game Theory and Applications. Eds. by L.A.Petrosjan and V.V.Mazalov, Vol. III.

50. Kleimenov A. F., Kryazhimskii A. V. Normal Behavior, Altruism and Aggression in Cooperative Game Dynamics, IIASA, IR-98-076, Laxenburg, 1998, 48 p.

51. Petrosjan L. A., Zaccour G. Time-consistent Shapley Value Allocation of Pollution Cost Reduction, Journal of Economic Dynamics and Control, Vol. 27, 381-398, 2003.

52. Petrosjan L. A. The Shapley Value for Differential Games, New Trends in Dynamic Games and Applications, Geert Olsder eds., Birkhauser, 409-417, 1995.

53. Petrosjan L. A., Shevkoplyas E. V. Cooperation under condition on random duration. Proc. 4 ISDG Workshop.Germany, Hannover University, 2003. pp.1-10.

54. Petrosjan L. A., Shevkoplyas E. V. Cooperative Solutions for Games with Random Duration. Game Theory and Applications, Volume IX. Nova Science Publishers, 2003. pp. 125-139. 1.

55. Shapley L.S. Stochastic games // Proc. Nat. Acad. Sci. U.S.A. 1953. V. 39, pp. 1095-1100.

56. Shapley L.S. A Value for n-person Games. // Contributions to the Theory of Games II. Princeton: Princeton University Press, 1953, pp.307-317.