Стохастическая игра

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

История[править | править вики-текст]

Стохастические игры были изобретены Л.Шепли в начале 1950-х годов [1]. Наиболее полным их описанием является сборник статей под редакцией А.Ноймана и С.Сорина [2]. Более элементарная книга Дж. Филар и К.Вриз содержит общее изложение теории марковских процессов принятия решений и стохастических игр двух лиц [3]. Ими был использован термин конкурентные марковские процессы принятия решений (англ. Competitive MDPs) для обозначения стохастических игр одного и двух лиц.

Этапы[править | править вики-текст]

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

При конечном числе игроков, конечных множествах действий и состояний игра с конечным числом повторений всегда имеет равновесие Нэша. Это справедливо также для игр с бесконечным числом повторений, если выигрыши участников представляют собой дисконтированную сумму.

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

Применение[править | править вики-текст]

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Shapley, L.S. Stochastic games // Proc. Nat. Acad. Science. — 1953. — vol. 39. — P. 1095—1100.
  2. Stochastic Games and Applications / A. Neyman, S. Sorin, eds. — Kluwer Academic Press, 2003.
  3. Filar, J., Vrieze, K. Competitive Markov Decision Processes. — Springer-Verlag, 1997.
  4. Vieille, N. Stochastic games: Recent results / In: Handbook of Game Theory. — Elsevier Science, 2002 — P. 1833—1850.

Ссылки[править | править вики-текст]