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

Смешанная стратегия называется стационарной, если вероятности применения его чистых стратегий не зависят от шага игры . Стационарные смешанные стратегии записываются так:

,.

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

Обозначим через цену игры, если первым шагом игры был игровой элемент . Таким образом определяется вектор цены игры . Каждому значению соответствуют оптимальные смешанные стратегии игроков.

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

где означает цену игры с матрицей , а элементами будут

. (6)

Теперь возникают следующие вопросы:

Существует ли вектор ?

Единственный ли вектор ?

Как найти вектор и оптимальные стратегии?

На эти вопросы дает ответ следующая лемма и теорема.

Лемма 1. Пусть матрицы и порядка , удовлетворяющие условию

,

где - действительное число, тогда .

Доказательство. Пусть ,- оптимальная стратегия второго игрока в игре с матрицей . Тогда для всех

,

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

Теорема 1. Существует в точности один вектор цен игры , удовлетворяющий соотношениям

, (7)

где определена по формуле (6).