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

• Богданов, Андрей Владимирович
• кандидат физико-математических наук
• 2000

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

Введение.

Глава I. Условия сходимости итерационного метода Брауна-Робинсон для биматричных игр.

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

2. Определение игрового процесса.

3. Игра двух лиц с нулевой суммой.

4. Теорема сходимости.

5. Построение игрового процесса для биматричных игр.

6. Условия сходимости игровых процессов для биматричных игр.

7. Условия сходимости для биматричных игр, получаемые за счет эквивалентного преобразования биматричной игры.

8. Результаты.

Глава II. Модели адаптивно-подражательного поведения.

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

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

2.1. Популяционная игра и статические принципы оптимальности.

2.2. Устойчивость решений модели динамики.

2.3. Модель динамики репликаторов.

2.4. Модель адаптивно-подражательного поведения.

3. Связь статических принципов оптимальности с устойчивостью решений динамики МАПП. лава III. Устойчивость смешанных равновесий модели адаптивно-одражательного поведения.

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

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

3. Связь статических принципов оптимальности с устойчивостью решений МАПП.

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

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

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

3. Верхняя оценка необходимой величины залога. аключение.

Введение диссертации (часть автореферата) на тему «Условия сходимости итеративных процессов в повторяющихся играх»

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

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

Данная проблема рассматривалась рядом исследователей, начиная с работ Брауна я Робинсон [41], которые исследовали процесс так называемого фиктивного разыгрывания и доказали его сходимость к седловой точке антагонистической игры. Обобщения этого результата получены в работах Беленького, Волконского и др. [4] и Антипина [1,2]. В них указаны достаточные условия на функции выигрыша, при выполнении которых указанный процесс, а также некоторые процессы градиентного гипа, сходятся к равновесию Нэша игры п лиц. Известен, однако, пример довольно простой игры двух лиц, для которой процесс фиктивного разыгрывания не сходится [Jordan 25].

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

Рассматриваемые в Главе 1 процессы соответствуют случаю, когда игра овторяется с одним и тем же составом участников, каждый из которых оптимизирует вою стратегию, исходя из предыдущих стратегий партнеров. Другое направление сследований в данной области связано с моделями, в которых множество игроков дновременно участвует в одинаковых конфликтных ситуациях. В каждый период артнеры выбираются случайным образом. Изменение распределения по стратегиям осит коллективный характер и основано на механизмах адаптации и подражания, [роцессы такого рода изучаются в рамках математической теории коллективного оведения, известной также как эволюционная теория игр (см. [Опойцев 35], Засин 50,51,54], р^ейпШ 57], [Краснощекое 29]). В упомянутых работах исследованы тдельные адаптивно-подражательные механизмы. В ряде случаев выяснена связь их симптотического поведения с равновесиями Нэша и решениями по доминированию. В о же время вопрос об условиях сходимости для моделей адаптивно-подражательного оведения общего вида не был изучен. Во второй главе настоящей работы ассматриваются различные способы выбора игроками альтернативных стратегий и их равнения с текущими стратегиями и найдены условия, при выполнении которых ходимость к указанным решениям имеет место.

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

Приложение посвящено повторяющимся играм с полной информацией и аддитивными функциями выигрыша. Состав игроков является постоянным и в отличие от предыдущих моделей каждый игрок стремится максимизировать свой суммарный выигрыш за данное число повторений. Для таких игр известен ряд результатов, получивших название «народных теорем». (См. работы [Ашпапп 3], [Васин 52,56] и др.). Их общее содержание состоит в том, что всякий индивидуально-рациональный исход однократной игры может быть реализован как решение повторяющейся игры. При этом рассматриваются различные понятия решения: от равновесия по Нэшу до наиболее сильного понятия - решения по доминированию. Последний вариант получен в работе [Васин 56] для повторяющейся игры с конечным временем и возмущенными функциями выигрыша. Показано, что за счет возмущения, не превышающего выигрыша в одном повторении, можно обеспечить превращение любого исхода, доминирующего некоторое равновесие Нэша, в исход, соответствующий решению по доминированию повторяющейся игры.

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

Таким образом, в Главах 1,2,3 дано обоснование сходимости широкого круга теративных процессов к точкам равновесия и решениям по доминированию, [риложение показывает, как за счет малого возмущения функций выигрыша можно беспечить соответствие решения по доминированию желательному исходу овторяющейся игры. В Заключении сформулированы основные результаты работы.

Основные результаты диссертации были опубликованы в статьях: [Богданов 8,9].

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

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

3) Для повторяющейся игры с полной информацией, в которой каждый игрок стремиться максимизировать выигрыш за Т повторений, исследована проблема устойчивой реализации исходов, доминирующих некоторое равновесие Нэша и соответствующих чередованию ситуаций, выгодных разным участникам игры. Доказано, что для реализации такого исхода в виде решения по доминированию достаточно модифицировать повторяющуюся игру следующим образом. До ее начала каждый участник вносит залог, который возвращается в случае, если игрок следует заранее согласованной стратегии. Установлено, что при оптимальном выборе последовательности реализуемых ситуаций необходимая величина залога не превышает М[п/2 + 1]/Т, где М - максимальное изменение выигрыша в одном повторении, а п - число игроков.

Заключение.

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

1. Antipin A.S. (1997) Calculation of Fixed Points of Extremal Mappings by Gradient-Type Methods //Сотр. Maths. Math. Phys., Vol. 37. №1. p.40-50

2. Aumann R.J. (1961) The Core of a Cooperative Game Without Side Payments. //Transactions of American Mathematical Society, Vol.98, P.535-552.

3. Беленький В. 3., Волконский В. А., Иванков С. А., Поманский А. Б., Шапиро А. Д., Итеративные методы в теории игр и программировании, Москва, "Наука", 1974.

4. Benaim М., Hirsch M.W., Learning Processes, Mixed Equilibria and Dynamical Systems arising from Repeated Games, preprint, University of California at Berkely, 1994.

5. Benoit G-P., Krishna V. (1985) Finitely Repeated Games. //Econometrica, Vol.53, P.905-922, 1985.

6. Bjornerstedt J., WeibullJ. (1996), "Nash equilibrium and evolution by imitation" //"The Rational Foundations of Economic Behaviour", Macmillan, London.

7. Богданов A.B. (1999) «Об условиях сходимости итерационного метода Брауна-Робинсон для биматричных игр», сборник «Прикладная математика и информатика» № 2, стр. 69-83

8. Богданов А.В. (2000) «Об устойчивости эффективных исходов в повторяющихся играх», сборник «Прикладная математика и информатика» № 4, стр. 102-110

9. Bomzel. М. (1986) "Non-cooperative two person games in biology: a classification" //International Journal of Game Theory 15: 31-57.

10. Боненбласт X. Ф., Шепли JI.C., Игры с непрерывной выпуклой функцией выигрыша, Сборник "Бесконечные антагонистические игры", Физматгиз, Москва, 1963.

11. Борисова Э.П., Магарик И.В., О двух модификациях метода Брауна решения матричных игр, Физматгиз, Москва, 1962.

12. Buhler Н. (1973) Zur Theorie Dynamisher Nichtcooperative Zwie-Personspile. //C.Oper.Res., A-17, N3, P. 143-156.14. van Damme E. "Evolutionary game theory" /European Economic Review 38: 847-858, 1994.

13. Данскин Дж. M., Итеративный метод решения непрерывных игр, Сборник "Бесконечные антагонистические игры", Физматгиз, Москва, 1963.

14. DekelE., Scotchmer S. "On the evolution of optimizing behavior" //Journal of Economic Theory 57: 392-406, 1992

15. Friedman D. "Evolutionary games in economics" //Econometrica 59: 637-666,1991.

16. Friedman D. Noncooperative Equilibrium for Supergames. //Review of Economical Studies, Vol.38, P.l-12,1971.

17. Fudenberg D., KrepsK., "Learning Mixed Equilibria", Games and economic behavior 5, pp.320-367,1993.

18. Fudenberg D., Maskin, E. The Folk Theorem in Repeated Games with Discounting and with Incomplete Information. //Econometrica, Vol.54, P.533-554,1986.

19. Fudenberg D., Tirole J. (1991) "Game Theory" /Cambridge: MIT Press.

20. Gaunersdorfer A., Hofbauer J. (1995) Fictitious play, Shapley polygons, and the Replicator Equation, Games and economic behavior 11, pp.279-303.

21. Hofbauer J., Sigmund K. (1988) "Dynamical Systems and the Theory of Evolution" /Cambridge: Cambridge University Press.

22. Jackson M, Kalai E., Social learning in recuring games, Discussion Paper Noll38, Northwestern University, Department of Managerial Economics and Decision Sciences, 1995.

23. Jordan J.S., Tree problems in learning mixed-strategy Nash equilibria, Games and economic behavior 5, pp.368-386, 1993.

24. Jordan J.S., Bayessian learning in normal form games, Games and economic behavior 3, pp.60-81, 1991.

25. Jordan J.S., The exponential convergence of Beyesian learning in normal form games, Games and economic behavior 4, pp.202-217, 1992.

26. Ильин В. A., Поздняк Э. Г., Основы математического анализа, Москва, "Наука", 1975.

27. Краснощеков П.С., Об одной простейшей модели колективного поведения. Приложения и их интерпретация, Материалы учредительной конференции Российского Научного Общества Исследования Операций, ВЦ РАН, Москва 1997

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

29. Maynard Smith J. 1982. "Evolution and the Theory of Games" /Cambridge: Cambridge University Press.

30. Moulin H. Theorie des jeus pour l'Economie et la Politique. //Hhermann, Paris Collection Methodes, 1981.

31. Nachbar J. (1990) "Evolutionary selection dynamics in games: Convergence and limit properties" //International Journal of Game Theory 19: 59-89.

32. Nash J. 1951. "Non-cooperative games" /Annals of Mathematics 54: 286-295.

33. Опойцев В.И. 1977. Равновесие и устойчивость в моделях коллективного поведения// Изд-во «Наука», Москва.

34. Пасеков В.П. 1988. "Математические модели эколого-генетических взаимодействий" /В сб. "Итоги науки и техники", сер. Математическая биология и медицина, т.2, 3-80.

35. Понтрягин Л.С. (1980) "Обыкновенные дифференциальные уравнения" //Москва: Наука.

36. Ritzberger К., The theory of normal form games from the differable viewpoint, preprint, Institute for Advanced Studies, Vienna, 1992.

37. SamuelsonL., Zhang J. (1992). "Evolutionary stability in asymmetric games" //Journal of Economic Theory 57: 363-391.

38. Schuster P., Sigmund K., Hofbauer J., Wolff R. (1981) "Self-regulation of behaviour in animal societies I" /Biological Cybernetics 40: 1-15.

39. Schuster P., Sigmund K. 1983. "Replicator dynamics" /Journal of Theoretical Biology 100: 533-538.

40. Selten R. 1980. "A note on evolutionary stable strategies in asymmetric animal conflicts." /Journal of Theoretical Biology 84: 93-101.

41. Selten R. 1983. "Evolutionary stability in extensive-form two-person games." /Mathematical Social Sciences 5: 269-363.4.7. Семевский Ф.И., Семенов C.M. 1982. "Математическое моделирование экологических процессов" /Ленинград: Гидрометеоииздат.

42. Taylor P., Jonker L. (1978) "Evolutionary stable strategies and game dynamics"//Mathematical Biosciences 40: 145-156.

43. Vasin A. 1999. "On stability of mixed equilibria" /Nonlinear Analysis 38: 793-802.

44. Васин A.A. 1989a. "Методы теории игр и исследования динамики коллективного поведения" //Вестник Московского Университета, сер. Вычислительная математика и кибернетика, №2, 55-60.

45. Васин A.A. 1989b. "Модели динамики коллективного поведения" //Москва: Изд-во Московского Университета.

46. Васин А.А. 1990. Эволюционная модель поведения в сверхигре. //Вестн. Моск. ун-та, сер. 15, Вычисл. матем. и киберн., №3.

47. Васин А.А., Самойлова И. А., Устойчивость точек равновесия эволюционных игровых моделей, 1996.

48. Васин А.А., "О некоторых проблемах теории коллективного поведения" //Обозрение прикладной и промышленной математики, т. 2, вып. 4, научное издательство "ТВП", 1995.

49. Vasin А.А., 1994. Stability of mixed equilibria in interactions between two populations, Instituto Valenciano de Investigatciones Económicas.

50. Vasin A.A. 1999. The Folk theorem for dominance solutions. //Int J Game Theory, Vol.28, P. 15-24.

51. Weibull J. (1996) "Evolutionary Game Theory" //Cambridge: MIT Press.