Решения кооперативных динамических игр

Актуальность проблемы определяется необходимостью построения математических моделей кооперативного поведения в условиях наличия угроз, затрагивающих интересы большого числа участников конфликта. При этом особо актуальны динамические модели, поскольку реальные конфликты развиваются во времени. Важное значение имеет вопрос об условиях, при которых игроки будут вступать в соглашение, а также сохранение условий кооперации на всем протяжении многошаговой игры. Различным аспектам динамических кооперативных игр посвящены работы [4, 7, 19, 21, 25, 33, 38, 46, 55].

Теория динамических кооперативных игр отличается множественностью принципов оптимальности, привнесенных из классической кооперативной теории [3, 11, 23, 29, 33, 34, 50, 51]. Однако, попытка переноса, статических" принципов оптимальности в динамические модели требует разработки особого механизма, учитывающего особенности динамического процесса принятия решений. Таким механизмом является концепция динамической устойчивости принципов оптимальности. Динамическая устойчивость решения означает, что любой отрезок оптимальной траектории от данного состояния до конечного определяет оптимальное движение относительно соответствующих начальных состояний. Отсутствие динамической устойчивости приводит к возможности отказа от ранее принятого плана действий в некоторый текущий момент. В связи со сказанным, при исследовании динамических кооперативных игр важное значение имеет построение динамически устойчивых решений. В разное время исследованиям динамической устойчивости решений были посвящены работы [13, 14, 33, 46, 52].

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

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

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

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

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

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

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

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

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

4. Определение оптимальной доли отчислений на эволюцию системы с целью достижения максимального выигрыша за определенное число шагов.

Апробация работы. Научные и практические результаты докладывались на конференциях «Процессы управления и устойчивость» в Санкт-Петербургском Государственном университете в 1999, 2000, 2003 гг, на 10 Международном симпозиуме по динамическим играм и приложениям (Санкт-Петербург, 2002 г), на семинарах Центра теории игр при факультете ПМ-ПУ СПбГУ, на семинаре в Институте прикладных математических исследований Карельского научного центра РАН (г. Петрозаводск).

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

В § 1.1 рассматривается многошаговая игра G на каждом шаге которой разыгрывается одношаговая иерархическая древовидная игра (п + 1)-го игрока. Описывается процесс построения многошаговой кооперативной игры, выводятся уравнения эволюции характеристической функции в процессе игры. В данном параграфе приводятся определения процедуры распределения дележа, динамически устойчивого и внутренне динамически устойчивого принципа оптимальности.

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

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

Во второй главе рассматривается бесконечношаговая игра G с кооперативной иерархической игрой Г на каждом шаге. Для этой игры строится сильное равновесие по Нэшу с использованием механизма регуляризации [47, 48]. Определяется «кооперативная траектория», предыстория и функция выигрыша игроков для игры G и подыгр Gk, начинающихся с шага к = 0,1,2,. этой игры. Вводится процедура распределения дележа и на этой основе проводится регуляризация игры вдоль кооперативной траектории. Вводятся стратегии, которые включают возможность наказания игроков, отклоняющихся от заранее оговоренной траектории. Формулируются достаточные условия, при выполнении которых эти стратегии образуют сильное равновесие по Нэшу для случаев, когда мгновенная игра, разыгрываемая на каждом шаге имеет древовидную или ромбовидную структуру.

В § 2.1 приводится постановка задачи, определение сильного равновесия по Нэшу, определение выигрыша в бесконечношаговой игре. Рассматривается бесконечношаговая повторяющаяся иерархическая игра G, выводятся условия существования сильного равновесия по Нэшу в повторяющейся иерархической древовидной игре.

В § 2.2 рассмотрен частный случай бесконечношаговой повторяющейся игры G с иерархической древовидной игрой (п + 1)-го игрока на каждом шаге. Выводятся условия существования сильного равновесия в явной аналитической форме.

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

В третьей главе рассматривается кооперативная многошаговая динамическая игра G. На каждом шаге многошаговой игры разыгрывается одношаговая иерархическая кооперативная игра Г. Рассматриваются две модели одношаговых иерархических игр с древовидной и ромбовидной структурами. Многошаговая кооперативная игра с древовидной игрой на каждом шаге подробно описана в первой главе. Описание иерархической ромбовидной игры дано во второй главе. Многошаговая игра строится следующим образом. На каждом шаге игроки отчисляют какую-то долю от заработанного дохода на развитие системы, а другую часть оставляют на собственные нужды. Под развитием системы понимаем закупку ресурсов, улучшение производства. На каждом следующем шаге параметры нашей задачи строятся с использованием отчислений от выигрышей игроков, заработанных на предыдущем шаге. Отличие этой главы от главы 1 состоит в том, что нас интересует, какую именно долю от собственного выигрыша игроки должны отчислять на развитие системы, для получения максимального дохода, тогда как в первой главе доля отчислений от выигрыша игроков использовались только для построения многошаговой игры.

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

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

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

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

1. Вилкас, Э. Й. (1972). Формализация проблемы выбора теоретико-игрового критерия оптимальности. Математические методы в социальных науках. Вып.2. Вильнюс, 1972.

2. Вилкас, Э. Й. (1976). Понятие оптимальности в теории игр. Современные направления теории игр. Вильнюс: Минтис, 1976.

3. Вилкас, Э. Й. (1990). Оптимальность в играх и решениях. М.: Наука, 1990.

4. Данилов, Н. Н. (1986). Связь между методом динамического программирования и принципом динамической устойчивости в кооперативных играх. Многошаговые, иерархические, дифференциальные и кооперативные игры: Сб. научн. тр. Калинин, 1986.

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

6. Клейменов А.Ф.(1985). К теории иерархических дифференциальных игр двух лиц: Прпринт. Свердловск: Ин-т мат. и мех. УНЦ АН СССР, 67 с.

7. Клейменов А. Ф. (1990). К кооперативной теории бескоалиционных позиционных дифференциальных игр. Доклады АН СССР, 1990, Т.32, N 1.

8. Корниенко Е. А. (1999). Эволюция характеристической функции в ромбовидной иерархической игре. Процессы управления и устойчивость. НИИ Химии СПбГУ, с.461−465.

9. Корниенко Е. А. (2000) Эволюция вектора Шепли в динамической иерархической ромбовидной игре. Процессы управления и устойчивость. НИИ Химии СПбГУ, с.447−450.

10. Корниенко Е. А. (2003). Построение сильного равновесия в повторяющихся иерархических играх. Процессы управления и устойчивость. СПб.: Изд-во С.-Петерб. ун-та, с.537−541.

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

12. Петренко, И. В. (1999). Древовидные кооперативные иерархические игры. Процессы управления и устойчивость, pp. 488−495.

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

14. Петросян Л. А. (1977). Дифференциальные игры преследования. Л., 1977.

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

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

17. Петросян JI.A., Захаров В. В. (1996). Математические модели в экологии. СПб: Изд. СПбГУ, 1996, 253 с.

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

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

20. Петросян Л. А., Зенкевич Н. А. Семина Е. А., (1998). Теория игр. М.: Высш. шк., Книжный дом «Университет», 1998. 304 с.:ил.

21. Петросян Л. А., Кузютин Д. В., (2000). Игры в развернутой форме. Издательство Санкт-Петербургского государственного университета, 2000 г.

22. Печерский С. Л., Соболев А. И., (1983). Проблема оптимального распределения в социально-экономических задачах и кооперативные игры. Л.: Наука, 1983.

23. Розенмюллер И., (1974). Кооперативные игры и рынки. М.: Мир, 1974.

24. Соболев А. И., (1975). Характеризация принципов оптимальности кооперативных игр посредством функциональных уравнений. Математические методы в социальных науках, N 6, под ред. Н. Н. Воробьева. Вильнюс, 1975.

25. Чистяков С. В., (1993). Динамический аспект решения классических кооперативных игр. Докл. РАН. Т. ЗЗО, N6.

26. Яновская Е. Б., (1972). Бесконечные антагонистический игры. В кн.: Теория вероятностей. Математическая статистика. Математическая кибернетика. Т.10. М., 1972, с. 75−106.

27. Яновская Е. В., (1999). Аксиоматическая характеризация редуцированных игр. Вопросы механики и процессов управления, Сер." Управление в социальноэкономических системах", 7V20. Издательство Санкт-Петербургского государственного университета, 1999.

28. Aumann R., Maschler М., Е., Streams., Repeated Games with Incomplete Information. Games and Economical Behavior, 16, 1996, pp. 347 -352.

29. Banzhaf J. F. (1965). Weighted voting does not work: A mathematical analysis. Rutgers Law Review, 19.

30. R. van den Brink, G. van der Laan (1998). Axiomatization of the normalized Banzhaf value and the Shapley value. Social Choice and Welfare, 15. Springer-Verlag, 1998.

31. Driessen T.S.H. Radzik T. R.G. Wanink (1996). Potential and consistency: a uniform approach to values for TV-games. Memorandum No. 1323, Department of Applied Mathematics, University of Twent, Enschede, The Netherlands.

32. Funaki Y., Yamato T. (2001) The Core and Consistency Properties: A General Characterization. International Game Theory Review Vol. 3 No. 2 & 3, June & September.

33. Filar, G. A. and L. A. Petrosjan (2000). Dynamic Cooperative Games. International Game Theory Review. Vol. 2, No. 1, pp. 47−66.

34. Gillies D. B. (1953). Some theorems on n-person games. Ph.D. thesis, Princeton University Press, Princeton, NJ.

35. Hart S. Mas-Colell'A. (1989). Potential, Value and Consistency. Econometrica, 57.

36. Kalai E., Smorodinsky M. (1975). Other solutions to the Nash’s bargaining problem. Econometrica, 43.

37. Korniyenko E. A. Cooperative Multistage Hierarchycal Game on a Tree. Proceedings of the Tenth International Symposium on Dynamic Games and Applications, Vol.1, 2002, pp. 440−445, St.Petersburg.

38. Kuzutin D. (1996). One approach to the construction of time consistent optimality principles in n-person differential games. Game Theory and Applications (eds. L. Petrosjan and V. Mazalov). NY: Nova Science Publishers, 1996.

39. Maschler M. Peleg B. L.S. Shapley (1972). The kernel and bargaining set for convex games. International Journal of Game Theory, 1.

40. Nagahisa R. Yamato T. (1992). A simple Axiomatization of the Core of Cooperative Games with a Variable Number of Agents. Toyota University.

41. Nash, J. (1950). Equilibrium points in n-person games. Nat. Acad. Sci. U. S. 36, 48 49.

42. J. Von Neumann, O. Morgenstern (1944). Theory of games and economic behavior. Princeton University Press, Princeton, NJ.

43. Owen, G. (1986). Game Theory. W. B. Saunders Company. Philadelphia London — Toronto.

44. Pechersky S.L. (1998). Note on the Core and Quasicore of Cooperative Games. Game Theory and Applications, Vol.4. NY, Nova Science Publishers, 1998.

45. Peleg B. (1989). An axiomatization of the core of market games. Math. Oper. Research, 14.

46. Petrosjan L. A. (1995). The Shapley Value in Differential Games. Annals of the International Society of Dynamic Games, Greet van Olsder editor, vol. 3.

47. Petrosjan L.A., Grauer L.V. (2002). Strong Nash Equilibrium In Multistage Games. International Game Theory Review, Vol. 4, No. 3, pp. 255−264.

48. Petrosjan, L.A., Egorova, A.A. (2000). New class of solutions for repeated bimatrix games. Proceedings of the 11th IFAC Workshop on Control Applications of Optimization 2000. Pergamon, 2, 617 622.

49. Raiffa H. (1953). Arbitration schemes for generalized two-person games. Contributions to the Theory of Games. Ann. Math. Studies, Vol.1, N 28.

50. Shapley L.S. (1953). A value for n-person games. In Contributions to the Theory of Games II (Eds. H. Kuhn and A.W. Tucker). Ann. Math. Stud. 28, Princeton University Press. Prinecton, NJ.

51. Tijs S.H. (1981). Bounds for the Core and the т-Value. Game Theory and Mathematical Economics (eds. O. Moeschlin and D. Pallasche). North-Holland Publishing Company, Amsterdam.

52. Villiger R. and L.A. Petrosjan (2001). Construction of time-consistent imputations in differential games. Proceedings of the 2nd International Conference «Logic, Game Theory and Social Choice», St. Petersburg, Russia.

53. Yanovskaya E. (1999). Strongly consistent solutions to balanced TU games. International Game Theory Review, 1999, Vol.1, N 1.

54. Zakharov V. (1996). About selectors of the core in dynamic games. Proceedings of the 7th ISDG symposium on Dynamic Game and Applications, Kanagawa, Japan.

55. Zakharov V., O-Hun Kwon. (1997). Linear programming approach in cooperative games J. Korean Math. Soc. 1997. Vol.34, no.2. P.423−435.

56. 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.