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

, (12)

. (13)

Из (12) и леммы 1 следует, что для всех

,

а это вместе с (13) означает, что для всех

.

Поскольку произвольно, то , что и требовалось доказать.

Используя конструктивный способ доказательства теоремы 1, можно построить аппроксимацию цен игровых элементов следующим образом: предположим, что игра будет продолжаться как стохастическая, пока не будет разыграна раз, а затем её необходимо заканчивать (если она не закончилась естественно раньше), тогда получим усеченную игру на разорение, а не стохастическую игру. Решив её известными методами, получим вектор цен и оптимальные стратегии в матричных играх с матрицами . Число , определенное формулой (11), обладает тем свойством, что вероятность продолжения игры более шагов, какие бы стратегии не использовались, не превосходит (здесь в степени ). Поэтому, если достаточно велико, то мало, и мы можем аппроксимировать стохастическую игру игрой, усеченной после шагов. Оптимальные стратегии и усеченных игр сходятся к оптимальным стационарным стратегиям стохастической игры.

2. Задача « Герб - Решетка»

Игроки 1 и 2 имеют вместе пять единиц. На каждом шаге игры игрок 1 выбирает либо «герб», либо «решетку»; игрок 2, не зная выбора игрока 1, делает аналогичный выбор. Если выборы совпадают, игрок 2 платит игроку 1 либо три, либо одну единицу в зависимости от того, что было выбрано, «герб» или «решетка». Если выборы не совпадают, игрок 1 платит игроку 2 две единицы. После каждого шага бросается монета для того чтобы определить, продолжать игру или закончить ее; кроме того, игра заканчивается, как только один из игроков разорится. Мы накладываем еще дополнительное условие, состоящее в том, что ни один игрок не может платить больше, чем он имеет.

Рассмотренная игра может быть представлена четырьмя игровыми элементами , где - величина капитала, которую имеет первый игрок в начале данного шага: