Новые ситуации равновесия в стохастических играх тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Грауэр, Лидия Вальтеровна

• Грауэр, Лидия Вальтеровна
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Грауэр, Лидия Вальтеровна

Введение

Глава 1. Стохастические игры п лиц с бесконечным числом шагов.

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

§ 1.2. Равновесие по Нэшу в стратегиях наказания

§ 1.3. Регуляризация игры G. Сильное трансферабельное равновесие.

Глава 2. Стохастические игры п лиц с конечным числом шагов

§ 2.1. Постановка задачи.

§ 2.2. Построение равновесий по Нэшу

Глава 3. Стохастические игры п лиц с постоянными вероятностями перехода

§ 3.1. Стохастические игры с постоянными вероятностями перехода с бесконечным числом шагов

3.1.1. Построение равновесий по Нэшу.

3.1.2. Сильное трансферабельное равновесие

§ 3.2. Стохастические игры с постоянными вероятностями перехода с конечным числом шагов

§ 3.3. Дилемма заключенного п лиц.

3.3.1. Случай одношаговой игры

3.3.2. Стохастическая игра дилемма заключенного.

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

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

Стохастические игры были введены JI.C. Шепли [48]. Шепли рассматривал останавливающиеся стохастические игры двух лиц с нулевой суммой, т.е. игры, для которых в каждом состоянии для каждой пары альтернатив игроков, игра останавливается с положительной вероятностью. Предполагалось, множество состояний конечно и множества альтернатив конечны. Шепли доказал, что такие игры имеют значение и оба игрока обладают оптимальными стационарными стратегиями.

Работы [21, 23, 24, 25, 37, 38, 47, 50, 51, 56] посвящены исследованию стационарных и марковских стратегий, стратегий поведения в стохастических играх. Особое место занимают алгоритмы построения стационарного равновесия в стохастических играх [22, 42, 36].

Основным принципом оптимальности в бескоалиционных играх является равновесие по Нэшу [39]. Вопросу построения равновесия в многошаговых и стохастических играх посвящены многочисленные исследования отечественных и зарубежных авторов [10, 11, 15, 18, 20, 21, 23, 24, 25, 35, 37, 38, 50, 51, 52, 56].

В литературе по теории многошаговых и повторяющихся игр особое место занимают так называемые народные теоремы, из которых следует возможность построения Парето оптимальных равновесий по Нэшу с использованием стратегий наказания. Поскольку авторство этих теорем не определено, они получили название народных теорем. Идеология народных теорем встречается в работах [19, 27, 28, 40, 46, 53, 54, 57].

В теории игр важным вопросом является построение сильных равновесий, то есть равновесий, устойчивых относительно отклонений коалиций игроков [13, 18, 27, 32, 40]. Для классического статического случая оно не имеет особого смысла, так как такие равновесия, как правило, не существуют. Однако, рассмотрение игр в динамике открывает новые возможности. JI.A. Петросян [14] предложил механизм регуляризации динамических и дифференциальных игр, в рамках которой сильное равновесие существует.

В работах [31, 33, 34, 49] предлагаются решения задач типа дилемма заключенного.

В данной работе рассматриваются стохастические игры п лиц с конечным и бесконечным числом шагов. В дискретные моменты времени игроку приходится выбирать одну из конечного множества альтернатив. Этот выбор определяет немедленный выигрыш, а также вероятностный вектор, согласно которому указывается новое состояние, в котором надо будет выбирать альтернативу на следующем шаге. В каждый момент времени для каждого набора альтернатив вероятность окончания игры положительна. Предполагается, что множества состояний и множества альтернатив конечны. Игрок стоит перед проблемой выбора стратегии, которая принесет ему наибольший выигрыш. В данной работе, используя идеологию народных теорем удалось конструктивно построить Парето оптимальные равновесия по Нэшу, а также, используя механизм регуляризации, предложенной JI.A. Петросяном [14], построены сильные равновесия в стохастических играх.

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

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

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

Основные положения, выносимые на защиту:

1. предлагается новый класс равновесий по Нэшу в стохастических играх п лиц;

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

3. предлагается новый класс равновесий по Нэшу в стохастических играх с постоянными вероятностями перехода;

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

Результаты работы докладывались на семинаре по теории игр (Санкт-Петербург), на 10-м международном симпозиуме по динамическим играм и приложениям (Санкт-Петербург), на XV конференции по теории игр и приложениям IMGTA (Урбино, Италия), на XXXII научной конференции "Процессы управления и устойчивость" (Санкт-Петербург).

Основные результаты диссертации опубликованы в работах [3, 4, 29, 30, 44, 45].

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

В первой главе рассматриваются стохастические игры п лиц с бесконечным числом шагов. В §1.1 формулируется теоретико-игровая модель стохастической игры с бесконечным числом шагов п лиц. Вводятся основные определения. Описывается стохастическая игра на бесконечном древовидном графе. Описывается структура графа.

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

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

Во второй главе рассматриваются стохастические игры п лиц с конечным числом шагов. В § 2.1 приводится постановка задачи. Описывается стохастическая игра на конечном древовидном графе. Описывается структура графа.

В § 2.2 предлагается способ построения равновесия по Нэшу в стохастической игре с конечным числом шагов п лиц, основанного на комбинировании наказания игрока, отклонившегося от соглашения, и использования абсолютного равновесия по Нэшу. Впервые данный подход построения такого равновесия был предложен в работе [43] для случая биматричных повторяющихся игр. Результаты иллюстрируются на примере.

В третьей главе рассматриваются стохастические игры п лиц с постоянными вероятностями перехода.

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

В §3.2 рассматриваются стохастические игры п лиц с постоянными вероятностями перехода с конечным числом шагов. Строится новое комбинированное равновесие по Нэшу

В § 3.3 рассматривается случай стохастической игры с конечным числом шагов на каждом шаге, которой разыгрывается игра вида дилемма заключенного п лиц. Для такого вида игр проводится регуляризация. Формулируются достаточные условия существования нового равновесия по Нэшу в регуляризованной игре. Результаты иллюстрируются на примере.

В заключении подытоживаются полученные результаты.

В приложении 1 приводятся необходимые расчетные выкладки к примеру из § 1.3.

В приложении 2 приводятся необходимые расчетные выкладки к примеру из §2.2.

В диссертационной работе использована двойная нумерация формул, теорем, определений, следствий, замечаний. Первая цифра означает номер главы, вторая — номер в главе. Параграфы пронумерованы для каждой главы отдельно. Литература приведена в алфавитном порядке. Для рисунков и таблиц используется сквозная для всей работы нумерация.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Грауэр, Лидия Вальтеровна

Заключение

Подведем основные итоги диссертационной работы. В работе

1) предложен новый класс равновесий по Нэшу в стохастических играх п лиц с бесконечным числом шагов;

2) предложен новый класс равновесий по Нэшу в стохастических играх п лиц с конечным числом шагов;

3) построены сильное трансферабельное и сильное равновесия в стохастических играх п лиц с бесконечным числом шагов; получены необходимые условия существования регуляризации стохастической игры п лиц, в которой существует сильное трансферабельное равновесие;

4) предложен новый класс равновесий по Нэшу в стохастических играх п лиц с постоянными вероятностями перехода;

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

Список литературы диссертационного исследования кандидат физико-математических наук Грауэр, Лидия Вальтеровна, 2004 год

1. Беллман Р. Динамическое программирование. М., 1960.

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

3. Грауэр Л. В. Повторяющаяся игра "Дилемма заключенного"п лиц // Труды XXXII научной конференции "Процессы управления и устойчивость". 2001. С. 357-361.

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

5. Данилов Н.Н. Кооперативные многошаговые игры с побочными платежами // Изв. Вузов. Мат. 1991. №2. С. 33-42.

6. Данилов В.И. Лекции по теории игр. М: РЭШ, 2002.

7. Кемени Дж., Снелл Дж., Кнепп А. Счетные цепи Маркова. М: Наука, 1987.

8. Кузютин В., Зенкевич Н., Еремеев В. Геометрия. СПб, 2003.

9. Куммер Бернд Игры на графах. М: Мир, 1982.

10. Лагунов В.Н., Сушкин В.В. Многошаговые позиционные игры N лиц. Тверь, 1993.

11. Многошаговые, иерархические, дифференциальные и бескоалиционные игры: межвузовский тематический сб. науч. тр. Калинин КГУ, 1987.

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

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

14. Петросян Л.А. Полукооперативные игры // Вестник СПбГУ. 1998. Сер. I. Вып. 2(8). С. 62-69.

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

16. Петросян Л.А., Захаров В.В. Математические модели в экологии. СПб: Изд. СПбГУ, 1996.

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

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

19. Abreu D., Dutta Р.К., Smith L. The folk theorem for repeated games: a NEU condition // Econometrica. 1985. V. 62. P. 939-948.

20. Aumann R.J. Mixed and behavior strategies in infinite extensive games // Ann. Math. Studies. 1964. V. 52. P. 627-650.

21. Duffie D., Geanakoplos J., Mas-Colell A., McLennan A. Stationary Markov Equilibria // Econometrica. 1994. V. 62. P. 745-781

22. Filar J.A., Schultz Т.A., Thuijsman F., Vrieze O.J. Nonlinear programming and stationary equilibria in stochastic games // Mathematical Programming. 1991. V. 50. P. 227-237.

23. Flesch J., Thuijsman F., Vrieze O.J. Markov strategies are better than stationary strategies // International Game Theory Review. 1997. V. 1. P. 9-31

24. Flesch J., Thuijsman F., Vrieze O.J. Optimality in different strategy classes in zero-sum stochastic games // Math. Meth. Oper. Res. 2002. V. 56. P. 315-322.

25. Flesch J., Thuijsman F., Vrieze O.J. N-person switching control stochastic games // Proc. 10th International Symposium on Dynamic Games and Applications. 2002. V. 1 P. 315-321.

26. Fudenberg D., Maskin E. The folk theorem for repeated games with discounting or with incomplete information // Econometrica. 1986. V. 54. P. 533-554.

27. Fudenberg D., Tirole J. Game theory. Cambridge: MIT press, 1991.

28. Gossner O. The folk theorem for finitely repeated games with mixed strategies // Int. J. Game Theory. 1995. V. 24. P. 95-107."

29. Grauer L.V. Folk Theorems for Stochastic Games // Proc. 10th International Symposium on Dynamic Games and Applications. 2002. V. 1 P. 345-348.

30. Grauer L. Strong Nash equilibrium in stochastic games // Conference Book of the XV Italian Meeting on Game Theory and Applications, 2003. P. 38.

31. Hamburger H. N-person prisoner's dilemma // J. Mathematical Sociology. 1973. V. 3. P. 27-48.

32. Holzman R., Law-Yone N. Strong Equilibrium in Congestion Games // Games and Economic Behavior. 1997. V. 21. P. 85-101.

33. Jones M. The effect of punishment duration of trigger strategies and quasifinite continuation probabilities for prisoner's dilemma // Int. J. Game Theory. 1999. V. 28. P. 533-546.

34. Kreps D., Milgrom P., Roberts J., Wilsson R. Rational cooperation in the finitely repeated prisoner's dilemma // J. Economic Theory. 1982. V. 27. P. 245-252.

35. Kuhn, H. W. Extensive games and the problem of information // Anals of Mathematics Studies. 1953. V. 28 P. 193-216.

36. Liapounov A.N. Asymptotic optimality in Markov processes and stochastic games // In: Int. Conf. "Logic, Game theory and Social Choice", Ext Abstracts. 2001. P.155-157.

37. Mertens J.F., Parthasarathy T. Non Zero Sum Stochastic Games //In Stochastic Games and Related Topics, Raghavan T.E.S. et al. (eds.), Kluwer Academic Publishers, 1991. P. 145-148.

38. Mertens J.F., Neyman A. Stochastic games j j Int. J. Game Theory. 1981. V. 10. P. 53-66.

39. Nash J. Equilibrium points in n-person games // Proc. Nat. Acad. Sci. U.S.A. 1950. Vol. 36. P. 48-49

40. Osborne M. J., Rubinstein A. A course in game theory. Oxford: Univ. Press, 1996.

41. Owen G. Game Theory. W. B. Saunders Company. Philade-lphia-London-Toronto. 1986.

42. Peeters R.J.A.P., Herings P.J.-J. Stationary equilibria in Stochastic games: structure, selection and computation // Proc. 10 ISDG. 2002. V. 2. P.669-685

43. Petrosjan L.A., Egorova A. A. New class of solutions for repeated bimatrix games. // Proc. 11th IFAC Workshop Game "Control Applications of Optimization". 2000. V. 2. P. 617-622.

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

45. Petrosjan L.A., Grauer L.V. New Class of Solutions in Multistage Games with Applications to "Prisoner's Dilemma" // Game Theory and Applications. 2002. V. 8. P. 125-134.

46. Smith L. Necessary and sufficient conditions for the perfect finite horizon folk theorem // Econometrica. 1995. V. 63. P.425-430.

47. Sobel M.J. Non-cooperative stochastic games // Ann. Math. Studies. 1971. V. 42. P. 1930-1935.

48. Shapley L.S. Stochastic games // Proc. Nat. Acad. Sci. U.S.A. 1953. V. 39. P. 1095-1100.

49. Straffin P. D. Game Theory and Strategy. Washington. Washington: The Math. Associat. America, 1993.

50. Thuijsman F. Optimality and equilibria in stochastic games. CWI tract. Amsterdam: Centrum voor wiskunde en informatica, 1992.

51. Thuijsman F., Raghavan T.E.S. Perfect information stochastic games and related classes // Int. J. Game Theory. 1997. V.26. P. 403-408.

52. Van Damme E.E.C. Stability and perfection of Nash Equilibria. Berlin: Springer-Verlag, 1991.

53. Vasin A.A. The folk theorem for dominance solutions // Int. J. Game Theory. 1999. V. 28. P. 15-24.

54. Vasin A. The folk theorems in the framework of evolution and cooperation // Proc. 10th International Symposium on Dynamic Games and Applications. 2002. V. 2 P. 852-857.

55. Villiger R., Petrosjan L.A. Construction of time-consistent imputations in differential games // Proc. 2nd International Conference "Logic, Game Theory and Social Choice". 2001.

56. Vrieze O. Stochastic games with finite state and action spaces. CWI tract. Amsterdam: Centrum voor wiskunde en informatica, 1987.

57. Wen Q. The folk theorem for repeated games with complete information // Econometrica. 1994. V. 62. P. 949-954.