Приложение. Стохастические игры

Понятие стохастической игры было впервые введено Шэпли [105]. Стохастическая игра представляет собой случайный процесс с дискретным временем и дискретным пространством состояний, у которого случайные переходы из одного состояния в другое зависят от поведения обоих игроков. Число состояний предполагается конечным. На каждом шаге игра может находиться в одном из возможных состояний. Игроков, участвующих в игре, будем называть игрок I и игрок И. Если игра находится в состоянии и игрок I выбирает чистую стратегию а игрок II — чистую стратегию то с вероятностью следующим состоянием игры будет состояние и игрок I получит выигрыш Игрок I стремится выбрать стратегию, максимизирующую его суммарный средний выигрыш, накопленный к моменту остановки игры, в то время как игрок II выбирает стратегию, минимизирующую этот выигрыш. Фиксируя состояние игры, приходим к классической прямоугольной игре Таким образом, «стохастическая игра» состоит из набора прямоугольных игр

Для стохастических игр Шэпли ввел понятие остановки, заключающееся в том, что для каждого состояния существует положительная вероятность

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

выигрыш игрока I, приходящийся на одну партию. Такая игра изучалась Джилетти [601. Проиллюстрируем результаты, полученные Шэпли [105], на примере стохастических игр с остановкой.

В случае, когда один из игроков не имеет возможности выбора стратегии (такой игрок называется пассивным), стохастическая игра сводится к марковскому процессу принятия решений. Таким образом, стохастические игры представляют особый интерес с точки зрения марковских процессов принятия решений. С этой позиции стохастические игры без остановки изучали Гоффман и Карп [62]. Дальнейшее развитие стохастические игры получили в работах Эверетта [55], Закриссона [121], Чарнза и Шройдера [22] и др.

Стохастическая игра с остановкой задается начальным состоянием и набором из матриц:

элементы которых удовлетворяют условиям

Так как произвольная стратегия в общем случае зависит от всей предыстории игры, то весьма трудно придумать для нее удобное обозначение. Однако мы ограничимся стратегиями, не зависящими от предыстории и времени, т. е. стационарными рандомизированными (смешанными) марковскими стратегиями, задаваемыми наборами из вероятностных распределений. Например, для игрока I такой набор имеет вид

где при каждом

является распределением вероятностей. Аналогично можно записать стационарную стратегию у игрока И. Если равно 1 при некотором и при остальных то чистая стратегия.

Рассмотрим сначала матричную игру (см. [112]). Для данной матричной игры В обозначим верхнюю цену этой игры, т. е. минимаксное значение выигрыша игрока I, а [5] и обозначим множества оптимальных стратегий игроков I и II соответственно. Если две матрицы одинаковой размерности, то легко показать, что

Возвращаясь к стохастической игре определим матрицу -элемент которой равен

где -мерный вектор, элемент которого равен а. Выберем произвольный вектор Определим последовательность векторов

где Покажем, что у при существует предел, не зависящий от причем элемент предельного вектора равен цене игры

Определим преобразование по формуле

где

В качестве нормы вектора а выберем

Тогда из получим

В частности, Следовательно, последовательность сходится,

причем предельный вектор обладает тем Свойством, что неподвижная точка преобразования Пусть некоторый другой вектор удовлетворяет уравнению тогда из получаем

Следовательно, Значит, единственная неподвижная точка отображения причем не зависит от

Чтобы показать, что цена игры 1 заметим, что если игрок I в течение первых шагов будет придерживаться в игре оптимальной стратегии, а затем будет играть произвольно, то его выигрыш будет отличаться от цены игры не более чем на то же самое верно и для игрока II. Так как а цена игры стремится к то отсюда следует, что является ценой игры Таким образом, доказана следующая теорема.

Теорема Цена стохастической игры является единственным решением системы уравнений

Теорема Оптимальными стационарными стратегиями игроков I и II в стохастической игре являются соответственно стратегии х и у такие, у которых суть оптимальные стратегии игроков I и II в каждой игре принадлежащей

Доказательство. Пусть игра заканчивается на ходу, и игрок I вместо получает выигрыш . Ясно, что в этом случае применение игроком I стационарной стратегии гарантирует ему выигрыш

В исходной же игре средний выигрыш за ходов игрока I, использующего стратегию , будет не меньше, чем

и, следовательно, этот выигрыш не меньше, чем

Поэтому суммарный выигрыш игрока I больше или равен

Так как все сказанное справедливо при любых достаточно больших то отсюда следует, что — оптимальная стратегия для игрока I в игре Аналогично, стратегия оптимальна для игрока

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

Эта система имеет единственное решение. В самом деле, для линейного преобразования

справедливо соотношение

что соответствует неравенству

Следовательно, применяя правило Крамера, находим

Теорема П.3. Каждая игра имеет седловую точку:

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

Доказательство довольно просто следует из теоремы Отметим, что стратегия оптимальная для одной игры может быть неоптимальной для других игр, принадлежащих (или

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

Литература

(см. скан)