Многошаговые игры с коалиционной структурой

Актуальность темы

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

Статические коалиционные игры рассматривались в работах Ауман-на и Дрезе [31], Оуэна [50], Майерсона [46], Ауманна и Майерсона [32],.

Курца [44], позднее у Бильбао, ван ден Бринка и ван дер Лаана. Однако динамические игры выбора коалиционного разбиеиия самими игроками до сих пор не рассматривались.

Известно, что в позиционных играх с полной информацией всегда существует ситуация абсолютного равновесия по Нэшу в чистых стратегиях. Взяв за основу данный факт и решения из теории динамических кооперативных игр, был опубликован ряд работ, в которых строились решения многошаговых игр с коалиционной структурой, отвечающие тем или иным требованиям. В частности, в совместной работе Л. А. Петро-сяна и Д. А. Аешина [15] изначально «сверху» задавалась кооперативная функция игроков, которая предписывала каждому игроку в какой момент он действует в интересах коалиции, а в какой индивидуально, и, соответственно, однозначно определялась коалиционная структура. Иной способ задания коалиционного разбиения рассматривался в работах Л. А. Петросяна и С. И. Мамкиной [19, 51], где предполагалось, что коалиционное разбиение в определенных вершинах может изменяться случайным образом. В качестве решения многошаговой игры с коалиционной структурой был предложен РМБ-вектор.

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

В работе также рассматриваются динамические игры с сетевой структурой. В теории сетевых игр в основном рассматривались статические игры [38, 40, 41, 62], а теоретико-игровые аспекты создания сетевой структуры в динамике до сих пор не исследовались. Предполагается, что сетевая структура также формируется самими игроками — каждый игрок решает в какой момент установить новую связь и с каким игроком, а в какой, наоборот, ликвидировать уже существующую связь. В рассматриваемых моделях исследуется вопрос нахождения оптимального поведения игроков, а при некоторых предположениях и единственного оптимального поведения.

Таким образом, рассматриваемая тема является актуальной и ее исследование вносит определенный вклад в развитие теории игр. I.

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

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

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

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

1. Построение принципов оптимальности в многошаговой игре с простой коалиционной структурой и полной информацией.

2. Формулировка теоремы о существовании единственного решения для многошаговой игры с простой коалиционной структурой и ее конструктивное доказательство.

3. Построение принципов оптимальности в многошаговой игре с простой коалиционной структурой и неполной информацией, применение их к динамической модели рыночной дуополии Курно.

4. Построение принципов оптимальности в многошаговой сетевой игре с полной информацией.

5. Формулировка теоремы о существовании единственного решения для многошаговой сетевой игры с полной информацией и ее конструктивное доказательство.

Апробация работы. Основные результаты были представлены на Международном семинаре «Теория управления и теория обобщенных решений уравнений Гамильтона-Якоби» (Екатеринбург, 2005), на Международной конференции «Устойчивость и процессы управления» (Санкт-Петербург, 2005), на семинаре российско-финской летней школы «Динамические игры и многокритериальная оптимизация» (Петрозаводск, 2006), на Международной конференции Game Theory and Management GTM07 (Санкт-Петербург, 2007), на Международной конференции The Second International Conference on Game Theory and Applications (Qingdao, China, 2007), на Международной конференции The Fourth Spain Italy Netherlands Meeting on Game Theory SING4 (Wroclaw, Poland, 2008), а также на семинарах кафедры математической теории игр и статистических решений факультета прикладной математики — процессов' управления и семинарах Центра теории игр Санкт-Петербургского государственного университета.

По материалам диссертации опубликованы работы [20], [21], [22], [25], [26], [28], [52], [53], [54], [55], [56].

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

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

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

3. Берж К. Общая теория игр нескольких лиц. М.: Физматгиз, 1961.

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

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

6. Воробьев Н. Н. Коалиционные игры // «Теория вероятности и ее применение», 1967, Т. 12, вып. 2, с. 289−306.

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

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

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

10. Кун Г. У. Позиционные игры и проблемы информации // Позиционные игры под ред. Н. Н. Воробьева, И. Н. Врублевская. М.: Наука, 1967, с. 13−40.

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

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

13. Оуэн Г. Теория игр, М., 1971.

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

15. Петросян J1.A., Аешин Д. А. Значение динамических игр с частичной кооперацией // Труды Ин-та математики и механики УрО РАН, 2000, Т. 6, № 1, с. 160−172.

16. Петросян JI. А., Захаров В. В.

Введение

в математическую экологию. Л.: Изд. ЛГУ, 1986, 224 с.

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

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

19. Петросян JI.A., Мамкина С. И. Игры с переменным коалиционным разбиением // Вестн. С.-Петерб. ун-та. Сер. 1: Математика, механика, астрономия, 2003, Вып. 3, с. 60−69.

20. Петросян J1. А., Седаков A.A. Оптимизация простых коалиционных структур в играх с полной информацией // Устойчивость и процессы управления под редакцией Д. А. Овсянникова, J1. А. Петросяна. Санкт-Петербург, СПбГУ, 2005, том 1, сс. 586−595.

21. Петросян J1.A., Седаков A.A., Сюрин А. Н. Многошаговые игры с коалиционной структурой // Вестник С-Петерб. ун-та., сер. 10, 2006, вып. 4, сс. 97−110.

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

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

24. Седаков А. А. Стратегическое поведение в динамическом конфликте с частичной кооперацией // Тезисы докладов Международного конгресса «Нелинейный динамический анализ», Санкт-Петербург, 2007, с. 342.

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

26. Adjeroh D., Kandaswamy U. Game-Theoretic Analysis of Network Community Structure, International Journal of Computational Intelligence Res. 2007, Vol.3, No.4, pp. 313−325.

27. Arnold Т., Wooders M. Dynamic club formation with coordination // II Congress of Game Theory Society, Marceille, 2004.

28. Aumann R., Dreze A. Cooperative Games with Coalition Structure. Int J. Game theory, 1974, Vol. 4, pp. 217−237.

29. Aumann R., Myerson R. Endogenous formation of links between players and of coalitions: An application of the Shapley value // Essays in honor of Llyoyd Shapley, Cambridge university press, 1988, pp. 175−191.

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

31. Dai Y., Gao H. PGN-vector of One Kind of Partial-cooperative Game in Extensive Form //in Proceedings of The Second International Conference on Game Theory and Applications, Qingdao, P.R.China, 2007, pp. 30−34.

32. Ferguson T. S. Game Theory // http://www.math.ucla.edu/~tom/ GameTheory/Contents.html.

33. Fudenberg D., Tirole J. Game Theory. Mass: MIT Press, 1991.

34. Fukuda. E., Muto S. Dynamic Coalition Formation in the Apex Game. Preprint version, 2004.

35. Goyal S. Vega-Redondo F., Network formation and social coordination // Games and Economic Behavior, 2005, vol. 50, pp. 178−207.

36. Hart S., Kurz M. Endogenous formation of coalitions // Econometrica, 51, 1983, pp. 1047−1064.

37. Jackson M. 0., Watts A. On the formation of interaction networks in social coordination game // Games and Economic Behavior, 1999, vol. 41, pp. 265−291.

38. Jackson M.O. Allocation rules for network games // Games and Economic Behavior, 2005, vol. 51, pp. 128−154.

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

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

41. Kurz M. Coalition value, in the Shapley value // Essays in honor of Llyoyd Shapley, Cambridge university press, 1988, pp. 155−173.

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

43. Myerson R. Graphs and cooperation in games // Math, of Oper. Res. 2:225−229.

44. Nash J. Non-cooperative Games // Ann. of Math, 1951, Vol. 54, pp. 286 295.

45. Nash J. Equilibrium Points in n-Person Games // Proc. Nat. Acad. Sei. USA, 1950, vol. 36, pp. 48−49.

46. Owen G. Game Theory. Third edition, Academic Press, 1995.

47. Owen G. Political games // Naval Research Logistics Quarterly, 1989, Vol. 18, pp. 345−355.

48. Petrosjan L.A., Mamkina S.I. New Value for Dynamic Games with Perfect Information and Changing Coalitional Structure / / Proceedings of the XI International Symposium on Dynamic Games and Applications, pp. 799−813.

49. Petrosyan L.A., Sedakov A.A. Multistage Network Games // Spain Italy Netherlands Meeting on Game Theory, Abstracts, Poland, 2008.

50. Petrosyan L.A., Sedakov A.A., Syurin A.N. Multistage Games with Coalitional Structure // in Proceedings of the 12th International Symposium on Dynamic Games and Applications, France, 2006, p. 172.

51. Sedakov A. A. An Approach for Formation of Coalitional Partitions // Collected abstracts of papers presented on the International Conference Game Theory and Management, St Peterburg, Russia, 2007, p. 117.

52. Sedakov A. A. On a Coalitional Dynamic Cournot Duopoly Model //in Proceedings of The Second International Conference on Game Theory and Applications, Qingdao, P.R.China, 2007, pp. 9−12.

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

54. Tirole J. The Theory of Industrial Organization, The MIT Press, Cambridge, 1988.

55. Van den Brink R., van der Laan G. Axiomatization of the Normalized Banzhaf Value and the Shapley Value. Social Choice and Welfare, 15. Springer-Verlag, 1998.

56. Vives X. Nash equilibrium with strategic complementarities, Journal of Mathematical Economics, 1990, Vol. 19(3), pp. 305−321.

57. Vives X. Strategic Complementarities in Multi-Stage Games, CEPRDiscussion Papers 5583, C.E.P.R. Discussion Papers, 2006.

58. Watts A. A dynamic model network formation // Games and Economic Behavior, 2001, vol. 34, pp. 331−341.

59. Zhang L., Gao H., Qiao H. The PMS Value of Games in Repeatedly Extensive Form with Changing Coalitional Structures //in Proceedings of The Second International Conference on Game Theory and Applications, Qingdao, P.R.China, 2007, pp. 282−286.