автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Условия существования устойчивых исходов в теоретико-игровых моделях

Введение

1. Общая постановка проблемы

2. Основные определения и обозначения

3. Обзор содержания

Глава 1. Структурированные функции выигрыша: свертка «минимум»

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

1. 2. Теоремы существования равновесий

1.3. Условия регулярности

Глава 2. Структурированные функции выигрыша: свертка «максимум»

2. 1. Основные определения

2. 2. Теоремы для общего случая

2.3. Регулярные игры

Глава 3. Игры с личными и общественными интересами

3. 1. Общая формулировка

3.2. Основная теорема

3.3. Проблема манипулирования

3. 4. О характеризации списков функций свертки

Глава 4. Структурированные функции выигрыша: аддитивная свертка

4. 1. Сепарабельные предпорядки и существование равновесия по Нэшу

4. 2. Характеризация аддитивной свертки

4.3. Существование коалиционно-устойчивых равновесий

Глава 5. Убывающие оптимальные ответы при аддитивном агрегировании

5. 1. Основная теорема

5.2. Дальнейшие результаты и контрпримеры

5. 3. Применения к другим правилам агрегирования

5. 4. О необходимости аддитивного агрегирования

Глава 6. Убывающие оптимальные ответы без аддитивного агрегирования

6. 1. Ограничения на взаимозависимость

6.2. Агрегирование по максимуму

6.3. Примеры с лексикографией

Глава 7. Двойственная стратегическая заменимость в квазисимметричных играх с аддитивным агрегированием

7. 1. Основные определения

7.2. Непрерывные множества стратегий

7.3. Дискретные множества стратегий

7.4. Некоторые приложения

Глава 8. Устойчивость по отношению к борьбе за первый или второй ход в игровых формах с двумя игроками

8. 1. Основные определения и классификация по Мулену

8. 2. ЭБР и ЭРГ игровые формы

8.3. Проблема манипулирования

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

Дж. фон Нейман, по-видимому, впервые явно поставил вопрос о том, каким должен быть математический аппарат, чтобы быть, хотя бы в принципе, работоспособным в этих специфических условиях. В монографии [33] под названием «теория игр» был предложен вариант математической теории рационального поведения. Хотя с тех пор даже общий облик теории претерпел значительные изменения (например, центральное в [33] понятие решения «по фон Нейману -Моргенштерну» занимает в современной теории игр вполне периферийное положение), указанная монография оказала сильнейшее влияние на все дальнейшее развитие математического моделирования в этой области. В настоящий момент многие разделы, например, экономической теории немыслимы без теоретико-игровых моделей, а в других они, во всяком случае, играют заметную роль [1, 3, 11, 34, 37, 61, 74, 86, 110, 112].

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

1 О ности, не требуется особенных эмпирических знаний, а требуется ¡ / t лишь настойчивое применение базовых логико-математических / ' средств. Результаты такого анализа способствуют лучшему пониманию проблем, возникающих при исследовании совершенно разных, в содержательном смысле, ситуаций. Этим объясняется существование и сравнительно автономное развитие общей теории рационального поведения (неважно, как ее называть: «теория -игр», «теория принятия решений» или как-нибудь еще), см. [2, 5, 6, 7, 9, 12, 25, 27, 29, 30, 32, 36, 38, 40, 62, 66, 75, 100, 105, 108, 109]. Сюда относится и направление исследований, ^ изложенное в настоящей работе. —

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

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

С формальной точки зрения равновесия по Нэшу являются неподвижными точками отображения оптимальных ответов. В принципе, любая теорема о существовании неподвижной точки у (многозначного) отображения может быть трансформирована в условие существования равновесия по Нэшу - вопрос лишь в том, насколько естественным и широко применимым окажется это условие. Наиболее' популярны в теории игр ссылки на теорему Какутани (или эквивалентные ей утверждения, также основанные на выпуклости), см., например, [34, 35]. В последнее время заметное внимание уделяется теореме о неподвижной точке Тарского [113], гарантирующей существование равновесия, когда множества стратегий являются полными решетками, а оптимальные ответы монотонны. (Интересно отметить, что для этой цели, по-видимому, еще ни разу не применялся принцип сжимающих отображений.)

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

1. Ашманов С. А. Введение в математическую экономику. М. : Наука, 1984.

2. Бондарева О. Н. О теоретико-игровых моделях в экономике. Л. : ИЗД-ВО ЛГУ, 1974.

3. Васильев В. А. Модели экономического обмена и кооперативные игры. Новосибирск: Изд-во НсбГУ, 1984.

4. Ватель И. А. Ядро в игре многих лиц с личными и общественными критериями. // Автоматика и телемеханика, 1980, N. 1, С. 9196.

5. Воробьев H.H. Теория игр: Лекции для экономистов-кибернетиков. Л. : Изд-во ЛГУ, 1974.

6. Гермейер Ю. Б. Введение в теорию исследования операций. М. : Наука, 1971.

7. Гермейер Ю. Б. Игры с непротивоположными интересами. М. : Наука, 1976.

8. Гермейер Ю.Б. , Ватель И. А. Игры с иерархическим вектором интересов. // Изв. АН СССР. Техн. кибернетика, 1974, N. 3, С. 5469.

9. Горелик В.А., Кононенко А. Ф. Теоретико-игровые модели принятия решений в эколого-экономических системах. М. : Радио и связь, 1982.

10. Гурвич В. А. Равновесие в чистых стратегиях. // ДАН СССР, 1988, Т. 303, N. 4, С. 789-793.

11. Иванов Ю. Н. , Токарев В. В. , Уздемир А. П. Математическое описание элементов экономики. М. : Наука, 1994.

12. Кирута А. Я. , Рубинов A.M., Яновская Е. Б. Оптимальный выбор распределений в сложных социально-экономических задачах. JI. : Наука, 1980.

13. Кукушкин Н. С. Устойчивость N-ядра в играх со структурированными функциями выигрыша. // ДАН СССР, 1986, Т.290, N. 5, С. 1045-1047.

14. Кукушкин Н. С. Об одном классе игр, обладающих устойчивыыми исходами. // ДАН СССР, 1989, Т. 307, N. 4, С. 799-802.

15. Кукушкин Н. С. Существование устойчивых исходов в конфликтных ситуациях с групповой структурой целевых функций. М.: ВЦ АН СССР, 1989.

16. Кукушкин Н. С. О существовании устойчивых исходов в теоретико-игровой модели экономики с общественными благами. // ДАН СССР, 1991, Т. 320, N. 1, С. 25-28.

17. Кукушкин Н. С. Новое достаточное условие существования равновесия в модели Курно. // ДАН, 1993, Т. 331, N. 6, С. 674-676.

18. Кукушкин Н. С. Теоремы о неподвижной точке для систем убывающих функций при аддитивном агрегировании. // ДАН, 1998, Т. 362, N. 2, С. 158-160.

19. Kukushkin N. S. Fixed point theorems for decreasing mappings. // Тезисы докладов 2-й Московской международной конференции по исследованию операций. М. : ВЦ РАН, 1998, С. 19-20.

20. Кукушкин Н. С. , Меньшиков И.С., Меньшикова 0.Р., Моисеев Н. Н. Устойчивые компромиссы в играх со структурированными функциями выигрыша. // ЖВМИМФ, 1985, Т. 25, N.12, С. 1761-1776.

21. Кукушкин Н.С. , Меньшиков И.С., Меньшикова О.Р., Моисеев H.H. Об одном классе теоретико-игровых конструкций, представляющих интерес для экологии. // ДАН СССР, 1986, Т. 287, N. 5, С. 1044-1046.

22. Кукушкин Н.С. , Меньшиков И.С., Меньшикова О.Р., Морозов В. В. Исследование игр с распределением ресурсов. // В кн. : Программное обеспечение и модели исследования операций. М. : Изд-во МГУ, 1986, С. 126-144.

23. Кукушкин Н.С., Морозов В. В. Теория неантагонистических игр. М. : Изд-во МГУ, 1984.

24. Куратовский К. Топология. Т. 1. М. : Мир, 1966.

25. Льюс Р. Д. , Райфа X. , Игры и решения. М. : ИЛ, 1961.

26. Меньшиков И.С., Меньшикова 0. Р. , Сильные ситуации равновесия и W-ядро в играх с иерархическим вектором интересов. // ЖВМиМФ, 1985, Т. 25, № 9, С. 1304-1313.

27. Миркин Б. Г. Проблема группового выбора. М. : Наука, 1974.

28. Моисеев H.H. Элементы теории оптимальных систем. М. Наука, 1975.

29. Моисеев Н. Н. , Александров В. В. , Тарко А. М. Человек и биосфера. М. : Наука, 1985.

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

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

32. Никайдо X. Выпуклые структуры и математическая экономика. М. : Мир, 1972.

33. Обен Ж.-П. Нелинейный анализ и его экономические приложения. М. : Мир, 1988.

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

35. Петров А.А., Поспелов И.Г., Шананин А. А. Опыт математического моделирования экономики. М. : Энергоатомиздат, 1996.

36. Подиновский В.В., Ногин В. Д. Парето-оптимальные решения многокритериальных задач. М. : Наука, 1982.

37. Розен В. В. Смешанные расширения игр с упорядоченными исходами. // ЖВМиМФ, 1976, Т. 16, N. 6, С. 1436-1450.

38. Юдин Д. Б. Вычислительные методы теории принятия решений. М- : Наука, 1989.

39. Aumann R.J., 1962, Utility theory without the completeness axiom. Econometrica 30, 445-462.

40. Aumann R.J., 1964, Utility theory without the completeness axiom: A correction. Econometrica 32, 210-212.

41. Ba§ar T., 1973, On the relative leadership property of Stackelberg strategies. J. of Optimization Theory and Applications 11, 655-661.

42. BergstromT., L. Blume, H. Varian, 1986, On the private provision of public goods. J. of Public Economics 29, 23-49.

43. Bernheim B.D., B. Peleg, M.D. Whinston, 1987, Coalition-proof Nash equilibria. I. Concepts, J. of Economic Theory 42, 1-12.

44. Bernheim B.D. and M.D. Whinston, 1987, Coalition-proof Nash equilibria. II. Applications, J. of Economic Theory 42, 13-29.

45. Birkhoff G., 1967, Lattice Theory. Providence: American Mathematical Society.

46. Bliss C. and B. Nalebuff, 1984, Dragon-slaying and ballroom dancing: The private supply of a public good. J. of Public Economics 25, 1-12.

47. Bulow J.I., J.D. Geanakoplos, P.D. Klemperer, 1985, Multi-market oligopoly: Strategic substitutes and complements. J. of Political Economy- 93, 488-511.

48. CorchonL., 1996, Theories of Imperfectly Competitive Markets. Berlin: Springer-Verlag.

49. DanilovV., 1992, Implementation via Nash equilibrium. Econometrica 60, 43-56.

50. Dasgupta P., P. Hammond, E. Maskin, 1979, The implementation of social choice rules: Some general results on incentive compatibility. Review of Economic Studies 46, 185-216.

51. Davey B.A. and H.A. Priestly, 1990, Introduction to Lattices and Order. Cambridge: Cambridge University Press.

52. Debreu G., 1960, Topological methods in cardinal utility. In: Mathematical Methods in Social Sciences. Stanford: Stanford University Press. P.16-26.

53. Deschamps R. and L. Gevers, 1978, Leximin and utilitarian rules: A joint characterization. J. of Economic Theory 17, 143-163.

54. Dubins L.E., 1977, Group decision devices. American Mathematical Monthly 84, 350-356.

55. Feldman A.M., 1980, Welfare Economics and Social Choice Theory. Boston The Hague - London: Martinus Nijhoff Publ.

56. Fishburn P.C., 1970, Utility Theory for Decision Making. New York: J. Wiley & Sons.

57. Fleming M., 1952, A cardinal concept of welfare. Quarterly J. of Economics 46, 366-384.

58. Frank C.R., 1965, Entry in a Cournot market. Review of Economic Studies 32, 245-250.

59. Fudenberg D. and J. Tirole, 1984, The fat-cat effect, the puppy-dog ploy and the lean and hungry look. American Economic Review 74, 361-366.

60. Fudenberg D. and J. Tirole, 1992, Game Theory. Cambridge, Mass.: MIT Press.

61. Gal-Or E., 1985, First mover and second mover advantages. International Economic Review 26, 649-653.

62. GibbardA., 1973, Manipulation of voting schemes: A general result. Econometrica 41, 587-601.

63. Gorman W.M., 1968, The structure of utility functions. Review of Economic Studies 35, 367-390.

64. Hahn F., 1962, The stability of Cournot oligopoly solution. Review of Economic Studies 29, 329-333.

65. Hammond P.J., 1976, Equity, Arrow's conditions, and Rawls' difference principle. Econometrica 44, 793-804.

66. Hirshleifer J., 1983, From weakest-link to best-shot: The voluntary provision of public goods. Public Choice 41, 371-386.

67. Hurwicz L., 1972, On informationally decentralized systems. In: Decision and Organization. Amsterdam London: North-Holland Publ. P.297-336.

68. Kreps D.M., 1990, A Course in Microeconomic Theory. Princeton: Princeton University Press.

69. Kreps D.M., 1990, Game Theory and Economic Modelling. Oxford: Clarendon Press.

70. Kukushkin N.S., 1992, On existence of stable and efficient outcomes in games with public and private objectives. International J. of Game Theory, 20, 295-303.

71. Kukushkin N.S., 1993, Cournot oligopoly with "almost" identical convex costs. Instituto Valenciano de Investigaciones Económicas, Discussion Paper WP-AD 93-07.

72. Kukushkin N.S., 1994, A fixed-point theorem for decreasing mappings. Economics Letters, 46, 23-26.1.

73. Kukushkin N.S., 1994, A condition for the existence of a Nash equilibrium in games with public and private objectives. Games and Economic Behavior, 7, 177-192.

74. Kukushkin N. S., 1995, Two-person game forms guaranteeing the stability against commitment and delaying tactics. International J. of Game Theory 24, 37-48.

75. Kukushkin N. S. , 1995, On the existence of Cournot equilibrium with indivisibilities. In: Abstracts for the Symposium on Operations Research. Passau, P.130.

76. Kukushkin N. S. , 1995, Separable aggregation and the existence of Nash equilibrium. Universität Bielefeld, Institute of Mathematical Economics, Working Paper No. 248.

77. Kukushkin N. S. , 1996, Reasons for the existence of Cournot equilibrium. Game Theory and Economics; N.N.Vorob'ev Memorial Conference. Abstracts. St.Petersburg, P.33.

78. Kukushkin N.S. , 1997, An existence result for coalition-proof equilibrium. Economics Letters 57, 269-273.

79. Kukushkin N. S. , 1998, Systems of decreasing reactions and their fixed points. Universität Bielefeld, Institute of Mathematical Economics, Working Paper No. 294.

80. Laffont J.-J., 1989, Fundamentals of Public Economics. Cambridge Mass. London: MIT Press.

81. Markowski G., 1976, Chain-complete posets and directed sets with applications. Algebra Universalis 6, 53-68.

82. McManus M., 1962, Numbers and size in Cournot oligopoly. Yorkshire Bulletin of Economic and Social Research 14, 14r-22.

83. McManus M., 1964, Equilibrium, number and size in'Cournot oligopoly. Yorkshire Bulletin of Economic and Social Research 16, 68-75.

84. Milgrom P. and J. Roberts, 1990, Rationalizability, learning, and equilibrium in games with strategic complementarities.Econometrica 58, 1255-1277.

85. Milgrom P. and J. Roberts, 1994, Comparing eguilibria. American Economic Review 84, 441-459.

86. Milgrom P. and J. Roberts, 1996, Coalition-proofness and correlation with arbitrary communication possibilities, Games and Economic Behavior 17, 113-128.

87. Milgrom P. and C. Shannon, 1994, Monotone comparative statics. Econometrica 62, 157-180.

88. Monderer D. and L.S. Shapley, 1996, Potential games. Games and Economic Behavior 14, 124-143.

89. Moreno D. and J. Wooders, 1996, Coalition-proof equilibrium, Games and Economic Behavior 17, 80-112.

90. Moulin H., 1976, Prolongements des jeux à deux joueurs de somme nulle. Bulletin de la Société Mathématique de France, Supplémentaire Mémoire N°45.

91. Moulin H., 1981, Deterrence and cooperation. European Economic Review 15, 179-193.

92. Moulin H. and B. Peleg, 1982, Cores of effectivity functions and implementation theory. J. of Mathematical Economics 10, 115-145.

93. Myerson R.B., 1979, Incentive compatibility and the bargaining problem. Econometrica 47, 61-73.

94. Myerson R.B., 1991, Game Theory." Cambridge, Mass.: Harvard University Press.

95. Nash J., 1950, The bargaining problem. Econometrica 18, 155-162.

96. Nash J., 1951, Non-cooperative games. Annals of Mathematics 54, 286-295.

97. Rasmusen E., 1989, Games and Information. Oxford: Basil Blackwell.

98. Ray I., 1996, Coalition-proof correlated equilibrium: A definition. Games and Economic Behavior 17, 56-79.

99. Roddy M.S., 1994, Fixed points and products. Order 11, 11-14.

100. Schelling T.C., 1960, The Strategy of Conflict. Cambridge, Mass.: Harvard University Press.

101. Schelling T.C., 1978, Micromotives and Macrobehavior. New York: W.W. Norton and Company.

102. SeltenR., 1970, Preispolitik der Mehrproduktenunternehmung in der statischen Theorie. Berlin: Springer-Verlag.

103. Sen A.K., 1977, On weights and measures: Informational constraints in social welfare analysis. Econometrica 45, 15391572.

104. Sen A.K., 1984, Collective Choice and Social Welfare. Amsterdam: North-Holland Publ.

105. Tarski A., 1955, A lattice-theoretical fixpoint theorem and its applications. Pacific J. of Mathematics 5, 285-309.

106. Topkis D.M., 1978, Minimizing a Submodular Function on a Lattice. Operations Research 26, 305-321.

107. Topkis D.M., 1979, Equilibrium points in nonzero-sum n-person submodular games. SIAM J. of Control and Optimization17, 773-787.

108. VickreyW., 1960, Utility, strategy, and social decision rules. Quarterly J. of Economics 74, 507-535.

109. VindK., 1991, Independent preferences. J. of Mathematical Economics 20, 119-135.

110. Vives X., 1990, Nash eguilibrium with strategic complementarities. J. of Mathematical Economics 19, 305-321.

111. Voorneveld M. and H. Norde, 1996, A characterization of ordinal potential games. Games and Economic Behavior 19, 235242.