Исследование эволюционных игр в рамках теории обобщенных решений уравнений Гамильтона-Якоби

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

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

Становление теории дифференциальных игр относится к началу 60-х годов и связано с именами российских и зарубежных математиков H.H. Красовского, JI.C. Понтря-гина, Р. Айзекса, У. Флеминга. В качестве решения эволюционной игры в диссертации рассматривается совокупность позиционных управлений, ориентированных на гарантированную оптимизацию выигрышей -«- один из классических подходов теории дифференциальных игр. Равновесные управления конструируются на основе решений вспомогательных задач гарантированого управления. Базисным элементом решения этих задач является функция цены, для построения которой применяются сеточные схемы аппроксимации обобщенных решений уравнений Гамильто-на-Якоби. В этом аспекте материал диссертации опирается на результаты теории уравнений Гамильтона-Якоби, разработанных в работах А. И. Субботина для обобщенных минимаксных решений. Используются также конструкции вязкостных решений, предложенных в работах М.Дж. Крэндалла, П.-JI. Лионса. В частности, особое внимание уделяется конечно-разностным операторам. Аппро-ксимационные решения сеточных схем (аппроксимацион-ные функции цены) и информация об их обобщенных градиентах позволяют строить гарантированные управления методом экстремального сдвига, предложенным в работах H.H. Красовского. Равновесные решения (динамические равновесия по Нэшу) синтезируются на базе построенных гарантированных управлений в рамках конструкции, разработанной А. Ф. Клейменовым.

Основные целями работы являются.

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

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

3. Синтезирование равновесных траекторий и исследование их свойств.

Теоретическая и практическая ценность.

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

Диссертация состоит из введения и пяти глав. Нумерация параграфов сквозная.

Список литературы

включает 84 наименования. Объем работы составляет 116 страниц машинописного текста.

1. Адиатулина P.A., Тарасьев A.M. Дифференциальная игра неограниченной продолжительности // Прикл. математика и механика. 1987. Т. 51, Вып. 4. С. 531 537.

2. Адиатулина P.A., Тарасьев A.M. Функция цены в дифференциальной игре неограниченной продолжительности //В сб.?Позиционное управление с гарантированным результатом. УрО АН СССР. 1988. С. 4−13.

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

4. Акуленко Л. Д. Асимптотические методы оптимального управления. М.: Наука, 1987. 366 с.

5. Альбрехт Э. Г., Мухтаров М. О формировании программных оптимальных управлений в одной иерха-рической игре// Синтез оптимальных управлений в игровых системах. Свердловск. УНЦ АН СССР. 1985. С. 3−15.

6. Арнольд В. И. Математические методы классической механики. М.: Наука, 1979. 432 с.

7. Байдосов В. А. Отображения, сопряженные к многозначным отображениям, и их применение к обобщенным динамическим играм // Докл. АН СССР. 1987. Т. 297. No. 5 С. 1033−1036.

8. Батухтин В. Д. Об одном подходе к решению разрывных экстремальных задач // Изв. АН. Техн. кибернетика. 1994. No. 3. С. 37−46.

9. Батухтин В. Д., Майборода JI.A. Оптимизация разрывных Функций. М.: Наука, 1984. 208 с.

10. Беллман Р. Динамическое программирование. М.: ИЛ, 1960. 400 с.

11. Брайсон А., Хо Ю-Ши. Прикладная теория оптимального управления. М.: Мир, 1972. 544 с.

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

13. Сборник переводов под ред. Воробьева H.H. Матричные игры. М.: Государственное издательство физико-математической литературы, 1961. 280 с.

14. Григоренко Н. Л. К задаче группового иследования// Тр. МИАН СССР. 1988. Т 185. С. 66−73.

15. Жуковский В. И., Чикрий A.A. Линейно-квадратичньйдифференциальные игры. Киев: Нау-кова думка, 1994. 320 с.

16. Зеликин М. И. Об одной дифференциальной игре с неполной информацией // Докл. АН СССР. 1972. Т. 202. No. 5 С. 998−1000.

17. ГарнышеваГ.Г., Субботин А. И. Стратегии минимаксного прицеливания в направлении квазиградиента // Прикл. матем. и мех. 1994. Т. 58, Вып. 4. С. 5−11.

18. Кларк Ф. Оптимизация и негладкий анализ. М.: Наука, 1988. 280 с.

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

20. Красовский А. Н. Дифференциальная игра для позиционного функционала // Докл. АН СССР. 1980. Т. 253. No. 6. С. 1303−1307.

21. Красовский А. Н. Построение смешанных стратегий на основе стохастических программ // Прикл. матем. и мех. 1981. Т. 45, Вып 4. С. 579−586.

22. Красовский H.H. Теория управления движением. М.: Наука, 1968. 475 с.

23. Красовский H.H. Игровые задачи о встрече движений. М.: Наука, 1970. 420 с.

24. Красовский H.H. Управление динамической системой. М.: Наука, 1985. 518 с.

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

26. Красовский H.H. Об одной задаче преследования // Прикл. матем. и мех. 1963. Т. 27, Вып. 2. С. 244−254.

27. Красовский H.H. К задаче о преследовании в случае линейных однотипных объектов // Прикл. матем. и мех. 1966. Т. 30, Вып. 2. С. 209−225.

28. Красовский H.H. Минимаксное поглощение в игре сближения // Прикл. матем. и мех. 1971. Т. 3, Вып. 6. С. 945−951.

29. Красовский H.H. Дифференциальные игры. Аппрок-симационные и формальные модели // Мат. сб. 1978. Т. 107. No. 4. С. 795−822.

30. Красовский H.H., Решетова Т. Н. О программном синтезе гарантирующего управления // Проблемы управления и теории информации. 1988. Т. 17. No. 6. С.1−11.

31. Красовский H.H., Третьяков В. Е. Стохастический программный синтез для позиционной дифференциальной игры // Докл. АН СССР. 1981. т. 259 N. 1. С. 24−27.

32. Кряжимский A.B., Осипов Ю. С. О эволюционно-дифференциальных играх // Труды МИР АН им. В. А. Стеклова. 1995. Т. 211. С. 257−287.

33. Кряжимский A.B., Осипов Ю. С. О моделировании управления в линейной динамической системе // Изв. АН СССР. Техн. кибернетика. 1983. No. 2. С. 51−60.

34. Куржанский A.B., Никонов О. И. К задаче синтеза стратегий управления. Эволюционные уравнения и многозначное интегрирование // Докл. АН СССР. 1990. Т. 311 No. 4. С. 788−793.

35. Куржанский A.B., Филиппова Т. Ф. Об описании множества выживающих траекторий дифференциального включения // Докл. АН СССР. 1986. Т. 289 No. 1. С. 38−41.

36. Лейтман Дж.

Введение

в теорию оптимального управления. М: Наука, 1968. 190 с.

37. Логинов М. И. Об одном способе экстремального управления// Прикл. матем. и мех. 1982. Т. 46, Вып. 6. С. 893−899.

38. Меликян A.A. Необходимые условия оптимальности на поверхности разрыва одного типа в дифференциальной игре // Изв. АН СССР. Техн. кибернетика. 1981. No. 4. С. 10−18.

39. Мищенко Е. Ф. Задачи преследования и уклонения от встречи в теории дифференциальных игр // Изв. АН СССР. Техн. кибернетика. 1971. No. 5. С. 3−9.

40. Мельникова Н. В., Тарасьев А. М. Градиенты локальных линейных оболочек в конечно-разностных операторах для уравнений Гамильтона-Лкоби // Прикл. математика и механика. 1997. Т.61, Вып. 3. С. 422 431.

41. Мельникова Н. В., Тарасьев А. М. Синтез оптимального гарантированного управления в сеточных аппроксимационных схемах // Прикл. математика и механика. 1997. Т.61, Вып. 4. С. 570−583.

42. Никольский М. С. О гарантированных оценках в дифференциальных играх с векторным критерием качества и фиксированным временем// Изв. АН СССР. Техн. кибернетика. 1980. N0. 2. С. 37−43.

43. Понтрягин Л. С. О линейных дифференциальных играх // Докл. АН СССР. 1967. Т. 174. N0.6. С. 12 781 280. // Докл. АН СССР. 1967. Т. 175. N. 4. С. 764 766.

44. Понтрягин Л. С. Математическая теория оптимальных процессов и дифференциальные игры // Тр. МИАН СССР. 1985. Т. 169. С. 119−157.

45. Понтрягин Л. С., Болтянский В. Г., Гамкрелидзе Р. В., Мищенко Е. Ф. Математическая теория оптимальных процессов. М: Наука, 1976. 392 с.

46. Пшеничный Б. Н. Выпуклый анализ и экстремальные задачи. М: Наука, 1980. 319 с.

47. Пшеничный Б. Н. Структура дифференциальных игр // Докл. АН СССР. 1969. Т. 184. N0. 2. С. 285−287.

48. Рокафеллар Р. Выпуклый анализ. М.: Мир, 1973. 469 с.

49. Субботин А. И. Обобщение оснозного уравнения теории дифференциальных игр // Докл. АН СССР. 1980. Т. 254. No. 2. С. 293−297.

50. Субботин А. И. Об одном свойстве субдифференциала // Мат. сб. 1991. Т. 182. No. 9. С. 1315−1330.

51. Субботин А. И. Минимаксные неравенства и уравнения Гамильтона-Лкоби. М.:Наука, 1991. 215 с.

52. Субботин А. И. Ченцов А.Г. Оптимизации гарантии в задачах управления. М.:Наука, 1981. 288 с.

53. Субботин А. И. Обобщение основного уравнения теории дифференциальных игр // Докл. АН СССР. 1980. Т. 254. No. 2. С. 293−297.

54. Субботин А. И. Об одном свойстве субдифференциала // Мат. сб. 1991. Т. 182. No. 9. С. 1315−1330.

55. Субботин А. И., Субботина H.H. Необходимые и достаточные условия для кусочно-гладкой цены дифференциальной игры // Докл. АН СССР. 1978. Т. 243. No. 4. С. 829−865.

56. Субботин А. И., Субботина H.H. Свойства потенциала дифференциальной игры // Прикл. матем. и мех. 1982. Т. 46, Вып. 2. С. 204−211.

57. Субботин А. И., Субботина H.H. Кусочно-гладкие решения уравнений с частными производными первого порядка // Докл. АН. 1993. Т. 333. No. 6. С. 705−707.

58. Субботин А. И., Тарасьев A.M. Сопряженные производные функции цены дифференциальной игры // Докл. АН СССР. 1985. Т. 283. No. 3. С. 559−564.

59. Субботин А. И., Тарасьев A.M., Ушаков В. Н. Обобщенные характеристики уравнений Гамильтона-Яко-би // Изв. АН. Техн. кибернетика. 1993. No. 1. С. 190−197.

60. Субботин А. И., Шагалова Л. Г. Кусочно-линейное решение задачи Коши для уравнений Гамильтона-Яко-би // Докл. АН. 1992. Т. 325. No. 5. С. 932−936.

61. Субботин H.H. Метод характеристик Коши и обобщенные решения уравнений Гамильтон а-Якоби-Беллмана // Докл. АН. СССР. 1991. Т. 320. No. 3. С. 556−561.

62. Тарасьев A.M. Аппроксимационные схемы построения минимаксных решений уравнений Гамильтона-Якоби // Прикл. математика и механика. 1994. Т.58, Вып.2. С. 22−36.

63. Тарасьев A.M. Неравенства для сопряженных производных кусочно-гладкой функции цены //В сб.: Управление с гарантированным результатом. Свердловск. УНЦ АН СССР. 1987. С. 86−91.

64. Тарасьев A.M. Решение эволюционных игр в рамках теории уравнений Гамильтона-Якоби // Прикл. математика и механика. 1995. Т.59, Вып. 6. С. 965−978.

65. Тарасьев А. М., Ушаков В. Н. Об одном вычислительном алгоритме решения игровых задач управления // Прикл. математика и механика. 1987. Т.51, Вып. 2. С. 219−222.

66. Тарасьев А. М., Успенский A.A., Ушаков В. Н. Конечно-разностный метод построения функции оптимального гарантированного результата // Сборник избранных докладов. Гагаринские научные чтения. Москва. 1991. С. 166−172.

67. Тарасьев А. М., Успенский A.A., Ушаков В. Н. Аппро-ксимационные схемы и конечно-разностные операторы для построения обобщенных решений уравнений Гамильтона-Якоби // Изв. РАН. Техн. Кибернетика. 1994. No. 3. С. 173−185.

68. Третьяков В. Е. К теории стохастических дифференциальных игр// Докл. АН. СССР. 1983. Т. 269. No. 3. С. 1049−1053.

69. Ченцов А. Г. Об условиях стабильности дифференциальной игры// Докл. АН. СССР. 1974. Т. 215. No. 4. С. 800−803.

70. Ченцов А. Г. Цена дифференциальной игры с обобщенной платой// Докл. АН. СССР. 1977. Т. 237. No. 1. С. 41−43.

71. Ченоусько Ф. Л. Меликян A.A. Игровые задачи управления и поиска. М.:Наука, 1978. 270 с.

72. Ушаков В. Н. К задаче построения стабильных мостов в дифференциальной игре сближения-уклонения // Изв. АН СССР. Техн. Кибернетика. 1980, No 4. С. 29−36.

73. Шориков А. Ф. Минимаксные фильтры для оценивания состояний нелинейных дискретных систем / / Автоматика и телемеханика. 1991, No 4. С. 112−122.

74. Bardi М., Falcone М. An Approximation Scheme for the Minimax Time Function // SIAM J. Control Optimiz. 1990. Vol. 28. No. 4. P. 950−965.

75. Bardi M., Osher S. The nonconvex multi-dimensional Riemann problem for Hamilton-Jacobi equations // SIAM J. Math. Anal. 1991. V. 22. No. 2. P. 344−351.

76. Crandall M.G., Lions P.-L. Viscosity solutions of Hamilton-Jacobi equations // Trans. Amer. Math. Soc.1983. Vol. 277. No. 1. P. 1−42.

77. Crandall M.G., Lions P.-L. Two approximations of solutions of Hamilton-Jacobi equations // Math. Com put.1984. Vol. 43. No. 167. P. 1−19.

78. Dolcheta I.C. On a discrete approximation of Hamilton-Jacobi equation of dynamic programming // Appl. Math. Optimiz. 1983. V. 10. No. 4. P. 367−377.

79. Fleming W.H. The convergence problem for differential games // Math. Anal. Appl. 1961. Vol. 3. No. 1. P. 102 116.

80. Hofbauer J. and Sigmund K., The Theory of Evolution and Dynamic Systems, Cambrige: Cambrige University Press, 1988.

81. Krasovskii A.N., Krasovskii N.N. Control under Lack of «Information, Birkhauser, Boston, 1995.

82. Kryazhimskii A.V. Behavioral equilibria for a 2×2-" Seller-Buyer" game evolutionary model // Working paper. WP-94−131. IIASA. Laxenburg. 1994. 25 p.

83. Lax P.D. Weak solutions of nonlinear hyperbolic equations and their numerical computation // Comm. Pure Appl. Math. 1954. V. 7. No. 1. P. 159−193.

84. Souganidis P.E. Approximation schemes for viscosity solutions of Hamilton-Jacobi equations // J. Different. Equat. 1985. Vol. 59. No. 1. P. 1−43.

85. Tarasyev A.M. A differential model for a 2 X 2-evolutionary games dynamics // Working paper. WP-94−63. IIASA. Laxenburg. 1994. 32 p.

86. III111IIIIIIIIIIII111. 11IIIIIIII0 О. ЙО 1.00 1.20фиг. 19Траектория ТЯ. сгенерированная позитивным управлением v [Э]-линии переключения и2° 1 т Матрицы А=С1, В=СЗ. 1Р=(0.2Д1)1,00 -Е0,80 -Е.

87. ГГТГГТ ГГ1ТГГ^Г'ГГ>" | | ГГГГГТГТ177 Г|^ГГ)" ?У7 ГГ1) Г1ТГГ |1| 111 111 111о. бо 0.20 0.4−0 оАо О. ЙО 1.00 1.20Хд хвфиг. 20ЛвПозитивное управлениефиг. 21Траектория Т (*. сгенерированная позитивным управлениемфиг. 22.