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

Введение

1 Селекторы С-ядра в классических кооперативных играх

1.1 Основные понятия и определения

1.2 Свойства основания 5С-ядра и большого

БС-ядра.

1.3 Свойства селекторов из БС-ядра.

1.4 Согласованность ЗС-ядра.

1.5 МДМ-редукция (ЛГ \ Я,^).

1.6 Задача о минимальной редукции

2 5С-ядро в динамических кооперативных играх

2.1 Динамическая устойчивость дележей из 5С-ядра.

2.2 Процедуры распределения дележей в многошаговой кооперативной игре

2.3 Обобщенная процедура распределения платежей.

2.4 Динамическая согласованность дележей из БС-ядра.

2.0 Динамически неустойчивые решения из С-ядра и редукция.

3 Теоретико-игровой подход к реализации механизмов

Киотского протокола

3.1 Парниковый эффект и механизмы Киотского протокола

3.2 Теоретико-игровая модель для двух игроков.

3.3 Модель «торговли квотами» для п игроков.

3.4 Распределение выигрыша в модели трех игроков.

Актуальность проблемы. Основным предметом изучения в диссертационной работе являются динамические кооперативные игры, впервые рассмотренные Л.А.Петросяном [10, 13, 14]. Различным аспектам теории динамических кооперативных игр посвящены работы [6, 9, 15, 16, 18, 21, 22, 41, 33, 42, 53].

Теория динамических кооперативных игр отличается множественностью принципов оптимальности, привнесенных из классической теории игр с трансферабельной полезностью [5, 19, 24, 26, 30, 46, 47, 49]. Так же, как и в теории неантагонистических дифференциальных игр, использование принципов оптимальности из статической теории приводит к противоречиям, возникающим из-за потери динамической устойчивости выбранного решения. Впервые это было замечено в [10, 11]. Динамическая устойчивость решения означает, что любой отрезок оптимальной траектории определяет оптимальное движение относительно соответствующих начальных состояний. Отсутствие динамической устойчивости приводит к возможности отказа от ранее принятого плана действий в некоторый текущий момент. В связи со сказанным при исследовании динамических кооперативных игр важное значение имеет построение динамически устойчивых решений. В работе [50] был представлен принцип оптимальности, предлагающий динамически устойчивое решение из С-ядра для дифференциальных кооперативных игр и построена процедура распределения дележа (ПРД) [41], обеспечивающая неотрицательные выплаты агентам вдоль оптимальной траектории. Однако, при использовании аналогичных процедур в многошаговых ТП-играх мы можем столкнуться с отрицательными платежами на некотором шаге. Это, фактически, означает, что игроки вынуждены возвращать часть заработанных сумм для сохранения динамической устойчивости решения. Последнее приводит к необходимости построения ПРД, учитывающих дискретный характер выплат выигрышей игрокам, специально для многошаговых игр.

Основой изучения свойств решений динамических кооперативных игр являются аналогичные свойства этих решений в статической теории. В разное время этой теме были посвящены работы [4, 17, 25, 26, 34, 38, 40, 43] и многие другие.

Одним из важных свойств решений кооперативных игр является свойство редуцированной игры [20, 23, 26, 28, 29, 31, 35, 36, 39, 45, 48, 51, 52, 54], или согласованность. Согласованность решения означает, что при выходе из исходной игры некоторой коалиции игроков оставшиеся могут придерживаться в редуцированной игре того же решения, что и в начальной, при этом значения индивидуальных выигрышей останется прежним. В данной работе вводится подобное понятие для динамических кооперативных игр, устанавливаются условия динамической согласованности для дележей из 5С-ядра, предлагается процедура регуляризации динамически неустойчивого решения с помощью редукции исходной игры.

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

Научная новизна. В диссертационной работе впервые были установлены необходимые и достаточные условия динамической устойчивости решений из 5(7-ядра для многошаговых кооперативных игр, предложены процедуры перераспределения доходов для многошаговых кооперативных игр, введено понятие динамической согласованности принципа оптимальности, исследованы процедуры регуляризации динамически неустойчивого решения из С-ядра с использованием редукции исходной игры, построена кооперативная модель реализации механизмов Киотского протокола, направленного на снижение выбросов парниковых газов. Основные результаты работы опубликованы в [7, 8, 27, 56, 55].

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

Апробация работы. Результаты диссертационной работы докладывались на семинарах кафедры Математического моделирования энергетических систем факультета Прикладной математики — процессов управления Санкт-Петербургского государственного университета (далее — ПМ-ПУ СПбГУ), семинарах Центра теории игр при факультете ПМ-ПУ СПбГУ, научных конференциях факультета ПМ-ПУ СПбГУ «Процессы управления и устойчивость» (2001, 2002 гг.), Международном симпозиуме по динамическим играм и приложениям «1800-2002» (Санкт-Петербург, 2002 г.), Международной конференции «Теория игр и приложения» «ЮМ-СТА 2002» (Китай, 2002 г.).

Заключение

Сформулируем основные результаты работы:

1. Исследованы свойства селекторов С-ядра классической кооперативной игры, в частности, Б С-ядра, сепарабельного вектора Шепли, сепарабельного вектора Банзафа и других сепарабель-ных решений;

2. Установлены необходимые и достаточные условия динамической устойчивости дележей из 5С-ядра в многошаговых кооперативных играх;

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

4. Введено понятие динамической согласованности решения динамической кооперативной игры, установлены условия динамической согласованности дележей из 5С-ядра относительно модифицированной редукции по Дэвису-Машлеру и рассмотрена задача о минимальной редукции.

1. А.Н. Акимова (2000). N-ядро и SC-ядро в кооперативной игре трех лиц. Труды XXX1.научной конференции «Процессы управления и устойчивость». СПб, 2000.

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

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

4. Э.Й. Вилкас (1979). Аксиоматическое определение обобщенного п-ядра. Математические методы в социальных науках. Вып.12. Вильнюс, 1979.

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

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

7. М.Б. Дементьева (2001). Некоторые свойства БС-ядра. Труды XXXII научной конференции «Процессы управления и устойчивость». СПб, 2001 г.

8. М.Б. Дементьева (2002). Свойство согласованности БС-ядра. Труды XXXIII научной конференции «Процессы управления и устойчивость». СПб, 2002 г.

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

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

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

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

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

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

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

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

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

18. В.А. Прокопьев (1986). О существовании устойчивых решений в одном классе кооперативных дифференциальных игр. Неантагонистические дифференциальные игры и их приложение: Сб. научн. тр. М.: 1986.

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

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

21. C.B. Чистяков (1992). О построении сильно динамически устойчивых решений кооперативных дифференциальных игр. Вестник Санкт-Петербургского университета. Сер.1, 1992, N1.

22. C.B. Чистяков (1993). Динамический аспект решения классических кооперативных игр. Докл. РАН. Т.330, N6.

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

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

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

26. M. Davis, M. Maschler (1965). The kernel of a cooperative game. Naval Res. Logist. Quart., 12.

27. M. Dementieva (2002). Some Properties of the Subcore in Dynamic TU-Game. Abstracts of International Congress of Mathematicians (Beijing, 2002).

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

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

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

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

32. D. Kuzutin (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.

33. M. Maschler, B. Peleg (1966). A characterization, existance proof and dimention bounds for the kernel of game. Pacific Journal of Mathematics, Vol. 18.

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

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

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

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

38. B. Peleg (1986). On the reduced game property and its convers. International Journal of Game Theory, 15.

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

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

41. L. Petrosjan (2000). Dynamic cooperative game. Proceedings of the 9th ISDG symposium on Dynamic Game and Applications, South Australia.

42. J.A.M. Potters (1990). An axiomatization of the nucleolus. International Journal of Game Theory, 19.

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

44. L. Ruiz, F. Valenciano, J. Zarzuello (1996). The Least Square Prenucleolus and the Least Square Nucleolus, two Values for TU-games based on the Excess Vector. International Journal of Game Theory, 25, N1.

45. L.S. Shapley (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.e.

46. D. Schm^idler (1969). The nucleolus of a characteristic function game. SIAM Journal of Applied Mathematics, Vol.17.

47. W. Thomson (1996). Consistent Allocation Rules. Economics Department, Unoversity of Rochester.

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

49. R. Villiger 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.

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

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

52. V. Zakharov (1997). Selectors of the core and consistency properties. Book of abstracts. International Conference on Game Theory. Stony Brook, USA.

53. V. Zakharov, M. Dementieva (2002). Time-Consistent Impiutations in Subcore of Dynamic Cooperative Games. Proceedings of the 10th1.ternational Symposium on Dynamic Games and Applications, 2002 (St.Petersburg, Russia).

54. V. Zakharov, M. Dementieva (2002). Time-consistent imputation distribution procedure for multistage game. Proceedings of the International Conference ICM-GTA 2002 (Qingdao, China).

55. V. Zakharov, O-Hun Kwon (1999). Selectors of the core and consistency properties . Game Theory and Applications, 4.58. http://www.wwf.ru/climate/kyotoinfo2.html.59. http://www.wwf.ru/climate/kyotoprotocol.html.