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

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

История

Стохастические игры были изобретены Л.Шепли в начале 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.

Ссылки