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

• Баранова, Елена Михайловна
• кандидат физико-математических наук
• 2006

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

Введение.

Глава 1. Кооперативная стохастическая игра со случайной продолжительностью.1G

§ 1.1 Определение стохастической игры со случайной продолжительностью.

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

§ 1.3 Построение кооперативной стохастической игры со случайной продолжительностью. Определение С-ядра, вектора

Шепли, iV-ядра.

§ 1.4 Кооперативная процедура распределения дележа.

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

§ 1.6 Регуляризация дележей.

§ 1.7 Регуляризация вектора Шепли и С-ядра.

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

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

§2.1 Определение стохастической игры с конечным числом игровых элементов.

§ 2.2 Основные функциональные уравнения для стохастической игры с конечным числом игровых элементов.

§2.3 Кооперативная стохастическая игра с конечным числом игровых элементов.

§ 2.4 Процедура распределения дележа и вектора Шепли.

§ 2.5 Позиционная состоятельность вектора Шепли.

§ 2.6 Условие сохранения кооперации в кооперативной стохастической игре с конечным числом игровых элементов.

§ 2.7 Примеры построения решений в кооперативных стохастических играх с конечным числом игровых элементов

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

Актуальность темы. Стохастические игры представляют собой бурно развивающийся раздел теории игр, поскольку с их помощью удастся создать адекватные реальности модели в области страхования, охраны окружающей среды и экономики. В частности, недавняя работа Р. Ами-ра [30] посвящена моделированию с помощью теории стохастических игр экономических задач, работа [63] — моделированию задач страхования, а работы [39, 47, 56] — моделированию задач охраны окружающей среды с использованием математического аппарата теории стохастических игр.

Впервые стохастические игры были рассмотрены Шепли (см. [61]). В этой работе Шепли описал антагонистическую стохастическую игру двух игроков, где использовал для решения классы стратегий поведения и стационарных стратегий. В этой же работе было доказано существование оптимальных стационарных стратегий поведения и выведено основное функциональное уравнение для значения стохастической игры. Это уравнение фактически явилось прямым обобщением уравнения Беллма-на (см. [6, 32]) для игровых динамических задач.

Стохастические игры представляют собой подкласс позиционных игр (игр в развернутой форме), определенных впервые в работах Г. Куна [48, 49]. На данный момент литература по стохастическим играм достаточно обширна, и в последнее время появилось множество работ, посвящепных неантагонистическим стохастическим играм (см. [33, 40, 44, 55]), а также нахождению равновесий по Нэшу в стохастических играх в различных классах стратегий (см. [41, 42]). Работы (см. [38, 43]) представляют исследование стохастических игр в классе стационарных стратегий, алгоритмы нахождения равновесия в классе стационарных стратегий. В работе [42] авторы исследуют стохастические игры в классе марковских стратегии, что "сближает" теорию стохастических игр с теорией цепей Маркова (см. [14, 29]).

Подавляющее большинство работ, касающихся кооперативных игр, относится к так называемым статическим или однократным играм. В этом случае при определении кооперативной игры изначально предполагается, что игроки перед началом игры договариваются о выборе набора стратегий, максимизирующих суммарный выигрыш игроков. Такой же подход может быть применен и при построении динамических и дифференциальных игр (см. [21, 26, 59]). Однако, при рассмотрении стохастических игр нельзя говорить о максимизации суммарного выигрыша, поскольку ситуация в чистых стратегиях в стохастической игре не определяет однозначно выигрыши игроков, а определяет однозначно лишь их математическое ожидание, так как ситуация в чистых стратегиях порождает вероятностную меру па партиях, вдоль которых происходит развитие игрового процесса. Именно поэтому при построении кооперативной стохастической игры мы изначально предполагаем, что игроки выбирают такой набор (ситуацию в чистых стратегиях поведения), который максимизирует математическое ожидание суммы выигрышей игроков. Указанный набор стратегий (кооперативное решение) порождает некоторое поддерево, которое в диссертации назвается кооперативным поддеревом.

Здесь так же, как и в детерминированных динамических и дифференциальных играх, возникает проблема, вполне аналогичная проблеме динамической устойчивости (см. [13, 20, 22, 57]) или состоятельности во времени рассматриваемых кооперативных принципов оптимальности.

Содержательный смысл этой проблемы состоит в том, что, как оказалось, в подавляющем большинстве случаев оптимальное решение игры, выбранное в соответствии с некоторым кооперативным принципом оптимальности (ядро, JVM-рсшение, вектор Шепли и др.) в начале стохастической игры, может потерять свою оптимальность в некоторой подыг-ре, развивающейся из начального состояния па кооперативном поддереве. Последнее обстоятельство может привести к желанию пересмотра первоначально выбранного кооперативного решения и, в результате, к нарушению устойчивости всего процесса игры. Это и есть позиционная несостоятельность выбранного кооперативного принципа оптимальности. Здесь следует отмстить различие между термином временная несостоятельность (динамическая неустойчивость), введенного при исследовании детерминированных динамических и дифференциальных игр (см. [21, 25, 26, 58, 59]) и нового термина позиционной несостоятельности. В детерминированных многошаговых (см. [12]) и дифференциальных (см. [18, 59, 64, G5]) играх можно всегда ограничиться одной кооперативной траекторией (одним путем), вдоль которой происходит развитие игрового процесса, и суммарный выигрыш игроков достигает своего максимального значения. Поэтому нарушение оптимальности выбранного решения оказывается опасным лишь в точках данного единственным образом выбранного кооперативного пути, что требует проверки условий сохранения свойства оптимальности на временном интервале игры вдоль этого кооперативного пути, а поскольку кооперативный путь фиксирован, то па временном интервале игры. Отсюда и термин временная несостоятельность или динамическая неустойчивость.

Понятие динамической устойчивости было впервые введено и исследовано JI.A. Петросяиом в работах [16, 17]. Важность введенного JI.A. Петросяном понятия очевидна, поскольку невыполнение условия динамической устойчивости решения делает невозможным реальное применение его в динамической кооперативной игре. К сожалению, многие решения — дележи из классической кооперативной теории — оказываются динамически неустойчивыми или позиционно несостоятельными.

Актуальность выбранной темы подтверждает и вручение Нобелевской премии по экономике в 2004 году Эдварду Прескотту и Финну Кидланду за работу [50] о несостоятельности оптимальных планов и возможных проблем в области политической экономии, возникающих в связи с этим.

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

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

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

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

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

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

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

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

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

Апробация работы. Основные результаты были представлены на Международном семинаре "Теория управления и теория обощенных решений уравнений Гамильтопа-Якоби" (Екатеринбург, 2005), на Международном рабочем совещании "Задачи оптимальной остановки и стохастического управления" (Петрозаводск, 2005), на Международной конференции "Устойчивость и процессы управления" (Санкт-Петербург,

2005), на "Fifth International ISDG Workshop" (Segovia, Spain, 2005), на "Summer School on Game Theory in Computer Science" (Aarhus, Denmark,

2006), на семинаре российско-финской летней школы "Динамические игры и многокритериальная оптимизация" (Петрозаводск, 2006), на семинаре Воронежской весенней математической школы "Понтрягинские чтения-XV" (Воронеж, 2004), семинарах кафедры математической теории игр и статистических решений, семинарах Центра теории игр, XXXIV научной конференции "Процессы управления и устойчивость" (Санкт-Петербург, 2003).

По материалам диссертации опубликованы работы [1], [2], [3], [4], [5], [19], [31].

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

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

Заключение

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

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

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

Полученные результаты носят как теоретический, так и практический характер, продемонстрированы на примерах, где в качестве решений выбраны классические решения кооперативной теории игр, такие как вектор Шепли, С-ядро, JV-ядро.

Список литературы диссертационного исследования кандидат физико-математических наук Баранова, Елена Михайловна, 2006 год

1. Баранова Е. М., Петросян JI. А. Стохастические игры со случайной продолжительностью // Труды XXXIV научной конференции аспирантов и студентов "Процессы управления и устойчивость", СПб: Изд-во С.-Петербургского упив-та, 2003, с.456-462.

2. Баранова Е. М., Петросян J1.A. Кооперативные стохастические игры // Тезисы докладов международного семинара "Теория управления и теория обобщенных решений уравнений Гамильтопа-Якоби", Екатеринбург: Изд-во Уральского унив-та, 2005, с. 33-35.

3. Баранова Е. М., Петросян JI.A. Кооперативные стохастические игры в стационарных стратегиях // Сборник трудов международной конференции "Устойчивость и процессы управления", СПб: СПбГУ, НИИ ВМ и ПУ, 2005, Т.1, с. 495-503.

4. Беллмап Р. Динамическое программирование. М.: Изд-во иностр. лит-ры, 1960, 400 с.

5. Берж К. Теория графов и её применения. М.: Изд-во иностр. лит-ры, 1962, 320 с.

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

7. Воробьев Н. Н. Устойчивые ситуации в коалиционных играх // Доклады АН СССР, 1960, Т. 131, с. 493-495.

8. Воробьев Н.Н. Коалиционные игры // "Теория вероятности и её применение", 1967, Т. 12, вып. 2, с. 289-306.

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

10. Грауэр Л.В., Петросян Л. А. Многошаговые игры // Прикладная математика и механика, 2004, Т. 68, вып. 4, с. 667-677.

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

12. Кемени Дж., Снелл Дж. Конечные цепи Маркова. М.: Наука, 1970, 272 с.

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

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

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

16. Петросян Л.А., Данилов Н.Н. Устойчивость решений в неантагонистических дифференциальных играх с трапсферабельными выигрышами // Вестник Ленинград, упив-та, Л.: Изд-во ЛГУ, 1979, № 1, с. 46-54.

17. Петросян JI. А., Данилов Н. Н. Кооперативные дифференциальные игры и их приложения. Томск: Изд. Томского ГУ, 1985, 276 с.

18. Петросян Л.А., Захаров В.В. Введение в математическую экологию. Л.: Изд. ЛГУ, 1986, 224 с.

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

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

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

22. Петросян Л. А., Шевкопляс Е. В. Кооперативные дифференциальные игры со случайной продолжительностью // Вестник С.-П. гос. университета, СПб.: Изд-во С.-П. гос. университета, 2000, сер. 1, вып. 4, с. 18-23.

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

24. Соболев А., И. Кооперативные игры // Проблемы кибернетики, М.: Наука, 1982, вып. 39, с. 201-222.

25. Чжун К. Л. Однородные цепи Маркова. М.: Мир, 1964, 426 с.

26. Amir R. Stochastic games in economics: The latter-theoretic approach // Stochastic Games and Applications in A. Neyrnan and S. Sorin (eds.)

27. NATO Science Series C, Mathematical and Physical Sciences, 2003, Vol. 570, Kluwer Academic Publishers, Dordrecht, Chapter 29, pp. 443-453.

28. Baranova E. M., Petrosjan L.A. Cooperative Stochastic Games in Stationary Strategies // Game theory and Applications, Nova Science Publishers, 200G, vol. 11, pp. 7-17.

29. Bellman R. Dynamic programming. Princeton: Princeton University Press, New Jersey, 1957.

30. Breton M. Algorithms for Stochastic Games in I.E.S. Raghavan, T.S. Ferguson, T. Parthasarathy and O.T. Vrieze (eds.) Stochastic Games and Related Topics, Series C: Game Theory, Mathematical Programming and Operation Research, 1991, pp. 45-57.

31. Driessen T., Muto S. ,Nakayama M. A cooperative Game of Information Trading: the Core, the Nucleolus and the Kernel // ZOR Methods and Models of Operations Research, Section "Theory", 1992, vol. 36, no 1, pp 55-72.

32. Dutta P. A Folk Theorem for Stochastic Games // Journal of Economic Theory, 1995, vol. 66, pp 1-32.

33. Ferguson T.S. Game Theory // http://www.math.ucla.edu/ torn / GameTheory/Contents.html.

34. Fink A.M. Equilibrium in a Stochastic n-person Game. // Journal of Science in Hiroshima University, Series AI, 1964, vol. 28, pp. 89-93.

35. Fisher R., Mirman L. The complete fish wars: biological and dynamic interactions // Journal of Environmental Economics and Management, 1996, vol. 30(1), pp. 34-42.

36. Flesch J., Thuijsman F., Vrieze 0. J. Optimality in different strategy classes of zero-sum stochastic games // Mathematical Methods of Operations Research, 2002, vol. 56, no 2, pp. 315-322.

37. Grauer L. V., Petrosjan L.A. Strong Nash Equilibrium in Multistage Games // International Game Theory Review, 2002, vol. 4(3), pp. 255264.

38. Haller H., Lagunoff R. Genericity and Markovian Behavior in Stochastic Games. // Econometrica, 2000, vol. 68, no. 5, pp. 1231-1248.

39. Herings P. J.-J., Peeters R.J. A. P. Stationary Equlibria in Stochastic Games: Structure, Selection, and Computation // Journal of Economic Theory, 2004, vol. 118, No. 1, pp. 32-60.

40. Jas'kiewicz A., Nowak A. On the optimality equation for zero-sum ergodic stochastic games // Mathematical Methods of Operations Research, 2001, vol. 54, no. 2, pp. 291-301.

41. Kohlberg E. On the Nucleolus of a Characteristic Function Game // SI AM Journal of Applied Mathematics, 1971, vol. 20 , pp. 62-66.

42. Kohlberg E. The Nucleolus as a Solution to a Minimization Problem // SIAM Journal of Applied Mathematics, 1972, vol. 23, no. 1, pp. 34-39.

43. Kronbak L. G. A coalition Game of the Baltic Sea Cod Fishery // http://www.sam.sdu.dk/ime/PDF/kronbak55.pdf.

44. Kuhn H. W. Extensive Games // Proceedings of National Academy of Sciences of the USA, 1950, vol. 36, pp. 570-576.

45. Kuhn H. W. Extensive Games and the Problem of Information // Annals of Mathematics Studies, 1953, no. 28, pp. 193-216.

46. Kydland F., Prescott E. Rules Rather than Discretion: The Inconsistency of Optimal Plans // Journal of Political Economy, 1977, vol. 85, pp. 473-491.

47. Maschler M., Peleg B., Shapley L. Geometrical Properties of the Kernel, Nucleolus and Related Solution Concepts // Mathematics of Operation Research, 1979, vol. 4, pp. 303-338.

48. Mathworks, 2005, http://www.mathworks.com.

49. Meinhardt H.I. Graphical Extensions of the Mathematica Package TU Games // http://library.wolfram.com/ infocenter/MathSource/5709/TuGames View3D.pdf.

50. Montero M. On the nucleolus as a Power Index // Homo Oeconomicus, 2005, vol. 22(4), pp. 551-567.

51. Najim K., Poznyak A. S., Gomez E. Adaptive policy for two finite Markov chains zero-sum stochastic game with unknown transition matrices and average payoffs // Automatica, 2001, vol. 37, no. 7, pp. 1007-1018.

52. Petrosjan L. A. Strongly time consistent optimality principles for the game with discount payoffs // System modelling and optimization, Lecture Notes in Control and Inform. Sci., Springer, London, 1994, no. 197, pp. 513-520.

53. Petrosjan L.A., Shevkoplyas E.V. Cooperative solutions for games with random duration // Game Theory and Applications, Nova Science Publishers, 2003, vol. 9, pp. 125-139.

54. Schmeidler D. The Nucleolus of a Characteristic Function game // SIAM Journal of Applied Mathematics, 1969, vol. 17, pp. 1163-1170.

55. Shapley L. S. Stochastic Games // Proceedings of National Academy of Sciences of the USA, 1953, vol. 39, pp. 1095-1100.

56. Shapley L.S. A Value for n-person Games // In H.W. Kuhn, A.W. Tucker, eds. Contributions to the theory of games II, Princeton: Princeton Univ. Press, pp. 307-317.

57. Suijs J., Waegenaere A., Borm P. Stochastic Cooperative Games in Insurance and Reinsurance // Insurance: Mathematics к Economics, 1998, vol. 22, no. 3, pp. 209-228.

58. Yeung D. W. K., Petrosyan L. A. Subgame consistent cooperative solutions in stochastic differential games // Journal of Optimization Theory and Applications, 2004, vol. 120, no. 3, pp. 651-666.

59. Yeung D.W. K., Petrosyan L.A. Cooperative Stochastic Differential Games. Springer Series in Operations Research and Financial Engineering, 2005.