Помощь в написании студенческих работ
Антистрессовый сервис

Новые ситуации равновесия в стохастических играх

Диссертация: Новые ситуации равновесия в стохастических играх
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

В теории игр важным вопросом является построение сильных равновесий, то есть равновесий, устойчивых относительно отклонений коалиций игроков. Для классического статического случая оно не имеет особого смысла, так как такие равновесия, как правило, не существуют. Однако, рассмотрение игр в динамике открывает новые возможности. JI.A. Петросян предложил механизм регуляризации динамических… Читать ещё >

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

Содержание

  • Глава 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) построены сильное трансферабельное и сильное равновесия в стохастических играх п лиц с бесконечным числом шаговполучены необходимые и достаточные условия существования регуляризации стохастической игры п лиц с постоянными вероятностями перехода, в которой существует сильное трансферабельное равновесие.

Показать весь текст

Список литературы

  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. 255 264.
  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.
Заполнить форму текущей работой

Сессия? Спокойно!