Решение игр в смешанных стратегиях

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

К примеру, в задаче игры «поиск» , т.е. седловая точка отсутствует. В данном случае можно получить оптимальное решение, случайным образом чередуя чистые стратегии.

Смешанной стратегией S_A игрока A будем называть применение чистых стратегий A₁, A₂, …, A_m с вероятностями p₁, p₂, …, p_m, причем:

. (7.9)

Смешанные стратегии можно записывать в матричной форме:

, (7.10)

или в векторной:

. (7.11)

Чистые стратегии можно считать частным случаем смешанных и задавать строкой, в которой 1 соответствует чистой стратегии.

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

Выигрыш, соответствующий оптимальному решению – цена игры, удовлетворяет следующему неравенству:

, (7.12)

где – соответственно нижняя и верхняя цена игры.

Справедлива следующая теорема (основная теорема теории игр – теорема Неймана): каждая конечная игра имеет, по крайней мере, одно оптимальное решение, возможно, среди смешанных стратегий.

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

Теорема об активных стратегиях: если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры ν, если второй игрок не выходит за пределы своих активных стратегий.

Рассмотрим игру 2×2. Если такая игра имеет седловую точку, то оптимальное решение – это пара чистых стратегий, соответствующих этой точке.

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

Для их определения воспользуемся теоремой об активных стратегиях.

Если игрок А придерживается своей оптимальной стратегии , то его средний выигрыш будет равен цене игры ν, какой бы активной стратегией ни пользовался игрок В. Для игры 2×2 любая чистая стратегия противника является активной, если отсутствует седловая точка.

Выигрыш игрока А (проигрыш игрока В) – случайная величина, математическое ожидание которой является ценой игры. Поэтому средний выигрыш игрока А при использовании оптимальной смешанной стратегии будет равен ν и для первой, и для второй стратегии противника.

Пусть игра задана следующей платежной матрицей: