История исследований стохастических игр

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

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

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

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