C-ядро в кооперативных играх группового преследования тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Панкратова, Ярославна Борисовна

• Панкратова, Ярославна Борисовна
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Панкратова, Ярославна Борисовна

Введение.

Глава 1. Игра преследования с одним убегающим и т преследователями.

§1.1 Неантагонистческая игра преследования с одним убегающим и т преследователями.

§ 1.2 Вывод аналитических формул для нахождения координат точек пересечения окружностей Аполлония.

§ 1.3 Множество ситуаций равновесия по Нэшу в неантагонистической игре простого преследования.

§ 1.4 Кооперативная форма игры ,.,

§ 1.5 Существование непустого С-ядра в кооперативной игре преследования ГД^,., 2°).

§ 1.6 Динамическая устойчивость С-ядра игры ад,.,^0).

§ 1.7 Примеры.

Глава 2. Игра преследования с одним преследователем и т убегающими.

§2.1 Неантагонистическая игра преследования с одним преследователем и т убегающими.

§ 2.2 Типы поведения и стратегии игроков в неантагонистической игре преследования г®,., г^)

§ 2.3 Основные неравенства, обеспечивающие существование равновесия по Нэшу.

§ 2.4 Построение областей эффективности стратегии наказания преследователя.

§ 2.5 Кооперативная форма игры ^,., г^).

§ 2.6 Существование непустого С-ядра в кооперативной игре преследования ГД^р, X®,.,

Введение диссертации (часть автореферата) на тему «C-ядро в кооперативных играх группового преследования»

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

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

Антагонистические дифференциальные игры преследования впервые были подробно описаны в монографии Р. Айзекса, изданной в 1965 году и переведенной на русский язык в 1967 году. Среди работ этого периода следует также отметить работы В. Флеминга и JI. Берковича.

Основополагающий вклад в развитие теории дифференциальных игр внесли H.H. Красовский и JI.C. Понтрягин. Также фундаментальные результаты в области теории дифференциальных игр преследования получены в работах Э.Г. Альбрехта, М. Барди, Т. Башара, Р. Беллма-на, А. Брайсона, H.JI. Григоренко, Р.В. Гамкрелидзе, В.И. Жуковского, М.И. Зеликина, А.Ф. Клейменова, А.Н. Красовского, A.B. Кряжим-ского, В.Н. Лагунова, O.A. Малафеева, A.A. Меликяна, Е.Ф. Мищенко, М.С. Никольского, Г. Ольсдера, Ю.С. Осипова, H.H. Петрова, JI.A. Пет-росяна, Б.Н. Пшеничного, А.Н. Субботина, Г.В. Томского, А. Фридмана, Ф.Л. Черноусько, A.A. Чикрия, C.B. Чистякова и многих других.

Неантагонистические дифференциальные игры преследования являются в настоящее время недостаточно изученными. Здесь следует отметить работу Л.А. Петросяна и В.Д. Ширяева [32], в которой впервые задача преследования формализована как неантагонистическая дифференциальная игра преследования с одним преследователем и двумя убегающими на плоскости, получившая свое развитие в работах С.И. Та-рашниной.

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

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

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

Основа теории кооперативных дифференциальных игр была построена J1.A. Петросяном, в развитие которой в различное время свой вклад внесли H.H. Данилов, Дж. Заккур, В.В. Захаров, H.A. Зенкевич, В.И. Жуковский, С. Йоргенсен, А.Ф. Клейменов, А.Ф. Кононенко, Дж.А. Филлар, С.В Чистяков, Д.В.К. Янг и многие другие.

В работе рассматриваются два класса неантагонистических дифференциальных игр группового преследования:

• между одним убегающим и несколькими преследователями, действующими как самостоятельные игроки;

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

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

Некооперативный подход состоит в формализации процесса преследования как неантагонистической некооперативной игры и описание в ней множества равновесных по Нэшу ситуаций. Важнейшим результатом в теории неантагонистических некооперативных дифференциальных игр является доказательство существования равновесия по Нэшу для общего случая игры п лиц. Оно было получено с использованием различных подходов в работах O.A. Малафеева [14] и C.B. Чистякова [42]. В работе С.И. Тарашниной [60] доказано, что в игре преследования с одним преследователем и m убегающими существует бесконечное множество равновесных по Нэшу ситуаций: от крайне неблагоприятных для убегающих до благоприятных, а также всевозможные промежуточные равновесия (при определенных условиях накладываемые на скорости и местоположения игроков).

Кооперативный подход состоит в объединении всех игроков (преследователей и убегающих) в единую коалицию с целью получения максимального суммарного выигрыша. Такой подход к решению игр группового преследования является новым и впервые был предложен в работах автора [19, 52].

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

Наиболее распространенной концепцией решения в рамках классической кооперативной теории игр с трансферабельными полезностями является С-ядро, введенное Н.Е. Scarf [58]. В работе осуществляется построение С-ядра и исследуется его непустота в рассматриваемых классах игр.

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

Таким образом, динамическая устойчивость, введенная Л.А. Петро-сяном [24], является важным свойством решения и означает, что игроки в каждый текущий момент игры не имеют причин отклоняться от первоначально выбранного оптимального поведения. В работе для игры с одним убегающим и т преследователями доказывается динамическая устойчивость С-ядра.

Основной целью работы является исследование двух классов неантагонистических игр группового преследования: с одним убегающим и т преследователями и с одним преследователем и т убегающими; построение кооперативных версий этих игр; нахождение некооперативных (в форме равновесия по Нэшу) и кооперативных (в форме С-ядра) решений рассматриваемых игр.

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

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

2. определен класс кооперативных игр преследования с одним убегающим и т преследователями и дано аналитическое описание С-ядра для случая максимального числа крайних точек, доказана его непустота и динамическая устойчивость;

3. определен класс кооперативных игр преследования с одним преследователем и т убегающими и построено непустое С-ядро;

4. для неантагонистической игры преследования с одним убегающим и т преследователями построено равновесие по Нэшу и доказано его существование для любых начальных местоположений игроков;

5. для неантагонистической игры преследования с одним преследователем и т убегающими введено понятие области эффективности стратегии наказания преследователя.

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

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

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

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

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

4. Получено аналитическое описание С-ядра для случая максимального числа крайних точек в кооперативной игре группового преследования с одним убегающим и т преследователями.

5. Доказана динамическая устойчивость С-ядра в кооперативной игре группового преследования с одним убегающим и т преследователями.

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

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

Апробация работы. Основные результаты работы представлены на семинарах кафедры математической теории игр и статистических решений Санкт-Петербургского государственного университета, на семинарах Центра теории игр, на 3-й международной конференции "Spain Italy Netherlands Meeting on Game Theory" (Мадрид, 2007), на 2-й, 3-й и 4-й Международных конференциях "Game Theory and Management" (Санкт-Петербург, 2008, 2009, 2010), на Всероссийской конференции "Устойчивость и процессы управления", посвященной 80-летию со дня рождения В.И. Зубова (Санкт-Петербург, 2010), на 24-й Европейской конференции по исследованию операций (Лиссабон, 2010), на 25-й Европейской конференции по исследованию операций (Вильнюс, 2012), на семинаре института прикладных математических исследований Карельского научного центра РАН (г. Петрозаводск).

По материалам диссертации опубликованы работы [18], [19], [50]-[57].

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

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

Заключение

На основе полученных результатов диссертационной работы можно сделать следующие выводы.

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Панкратова, Ярославна Борисовна, 2012 год

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

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

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

4. Бондарева О.Н. Некоторые применения методов линейного программирования к теории кооперативных игр // Проблемы кибернетики. Вып. 10, М.: Физматгиз. с. 119-140.

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

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

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

8. Григоренко Н. Л. Дифференциальные игры преследования несколькими объектами. М.: Изд-во МГУ, 1983. 77 с.

9. Жуковский В. И., Тынянский Т. Н. Оптимальность в бескоалиционных дифференциальных играх. — Неантагонистические дифференциальные игры и их приложения: Сб. научн. тр. М., 1986. с. 3-7.

10. Зенкевич Н. А., Зятчин А. В. Построение сильного равновесия в дифференциальной игре многих лиц. МТИП, 2010. 2: 2, с. 42-65.

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

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

13. Мазалов В.В. Математическая теория игр и приложения: учебное пособие. СПб.: Из-во: "Лань", 2010. 448 с.

14. Малафеев О. А. Существование ситуаций равновесия в дифференциальных бескоалиционных играх со многими участниками. — Вестн. Ленигр. ун-та, 1982. № 13, с. 40-45.

15. Меликян А. А., Овакимян Н. В. Дифференциальная игра простого сближения на многообразиях. — Прикл. мат. и мех., 1993. 57, № 1, с. 41-51.

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

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

18. Никольский М.С. Линейные дифференциальные игры преследования с интегральными ограничениями. — Дифференциальные уравнения, 1992. т. 28, № 2, с. 219-223.

19. Панкратова Я. Б. Решение кооперативной дифференциальной игры группового преследования. Дискретный анализ и исследование операций. 2010. т. 17, № 2, с. 57-78.

20. Панкратова Я. Б. Кооперация в одной игре группового преследования // Всероссийская конференция по-священная 80-летию со дня рожде-ния В.И. Зубова "Устойчивость и процессы управления", СПб, 2010. с. 168-169.

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

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

23. Петросян Л. А. Об одном семействе дифференциальных игр на выживание в пространстве К1. ДАН СССР, 1965. Том 161, № 1, с. 52-54.

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

25. Петросян Л. А. Дифференциальные игры преследования. Л.: Изд-во Ленингр. ун-та. 1977. 224 с.

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

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

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

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

30. Петросян Л. А., Томский Г. В. Геометрия простого преследования. Наука, Новосибирск. 1983.

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

32. Петросян Л. А., Ширяев В. Д. Простое преследование одним преследователем двух преследуемых. — В кн.: Некоторые вопросы дифференциальных и интегральных уравнений и их приложения. Вып. 3, Якутск, ун-т. 1978. с. 103-108.

33. Петросян Л. А., Рихсиев Б. Б. Преследование на плоскости. М: Наука. Гл. ред. физ.-мат. лит., 1991. Вып. 61.

34. Печерский С. Л., Яновская Е. Б. Кооперативные игры: решения и аксиомы. СПб.: Изд-во Европейского университета, 2004. 459 с.

35. Понтрягин Л. С. О некоторых дифференциальных играх. — Докл. АН СССР, 1964. т. 156, № 4.

36. Понтрягин Л. С. О линейных дифференциальных играх. 1. — Докл. АН СССР, 1967. т. 174, № 6, с. 1278-1280.

37. Понтрягин Л. С. О линейных дифференциальных играх. 2. — Докл. АН СССР, 1967. т. 175, № 4, с. 764-766.

38. Пшеничный В. Н. Игра с простым движением и выпуклым терминальным множеством. — Теория оптимальных решений, Киев, 1969. вып. 3, с. 3-16.

39. Пшеничный Б. Н. Простое преследование несколькими объектами. — Кибернетика, 1976. № 3, с. 145-146.

40. Тарашнина С. И. Равновесные по Нэшу ситуации в игре простого преследования. — Выпросы механики и процессов управления, Санкт-Петербург, 2001. вып. 20, с. 188-201.

41. Чикрий А. А., Калашникова С. Ф. Преследование управляемым объектом группы убегающих. — Кибернетика, 1987. К2 4, с. 1-8.

42. Чистяков С. В. О бескоалиционных дифференциальных играх. Докл. АН СССР, 1981. т. 259, № 5.

43. Чистяков С. В. О существовании решения бескоалиционных дифференциальных игр. — Управление в динамических системах, Ле-нингрд, 1979. с. 128-145.

44. Basar T., Olsder G. Dynamic Noncooperative Game Theory. N.Y. Ac, Press. 1998.

45. Bercovitz L. D., Fleming W. H. On diffirential games with integral payoff. Contributions to the theory of Games. Ann of Math Studies. 1957. № 3, p. 413-435.

46. Filar G. A., L. A. Petrosjan. Dynamic Cooperative Games. International Game Theory Review. 2000. Vol. 2, № 1, p. 47-66.

47. Owen G. Game Theory. W. B. Saunders Company. PhiladelphiaLondon-Toronto. 1986.

48. Nash J. F. Equilibrium points in n-person games // Proc. Nat. Acad. Sci. USA. 1950. Vol. 36. p. 48-49.

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

50. Pankratova Ya., Tarashnina S. How many people can be controlled in a group pursuit game. Theory and Decision. Kluwer Academic Publishers. 2004. 56, p. 165-181.

51. Pankratova Y. On cooperative differential game of pursuit // SING3. Spain Italy Netherlands Meeting on Game Theory. Madrid, 2007. p. 127.

52. Pankratova Ya., Tarashnina S. Time-consistency of the Core in group pursuit games // The Second International Conference Game Theory and Management, St.Petersburg, 2008. p. 216.

53. Pankratova Ya., Tarashnina S. The importance of cooperation in a group pursuit game between a pursuer and m evaders // The Third International Conference Game Theory and Management, St.Petersburg,2009. p. 198-199.

54. Pankratova Y., Tarashnina S., Marchenko I. Cooperative solutions for a group pursuit game between a pursuer and m evaders // The 4-th International Conference Game Theory and Management, St.Petersburg,2010. p. 123-124.

55. Pankratova Y. Cooperation in a group pursuit game //24 European Conference on Operational Reseach, Lisbon, 2010. p. 295.

56. Pankratova Y. A cooperative version of one group pursuit game //25 European Conference on Operational Reseach, Vilnuis, 2012. p. 221.

57. Scarf H. E. The core of an n-person game. Econometrica. 1967. 35, p. 50-69.

58. Shapley L. S. On balanced sets and cores. Naval Research Logistic Quarterly. 1967. 14, p. 453-460.

59. Tarashnina S. Nash equilibria in a differential pursuit game with one pursuer and m evaders. Game Theory and Applications. N.Y. Nova Science Publ. 1998. Vol. Ill, p. 115-123.

60. Tarashnina S. Time-consistent solution of a cooperative group pursuit game. International Game Theory Review. 2002. Vol. 4, p. 301-317.