Смешанные стратегии. Теорема Неймана.

Смешанной стратегией первого игрока называется применение его чистых стратегий по случайному закону с частотами причем сумма частот (вероятностей) равна 1: . Смешанная стратегия первого игрока записывается в виде матрицы:

Аналогично смешанную стратегию второго игрока будем обозначать

где сумма частот его стратегий равна 1: .

Средняя цена игры V( , ) со стратегиями игроков и равна:

(1) V( , ) =

Любая чистая стратегия является частным случаем смешанной стратегии, в которой все стратегии, кроме одной, применяются с нулевыми частотами, а данная – с частотой 1.

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

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

В 1928 году американский математик Джон Нейман доказал теорему:

Теорема 2 (Неймана): Каждая конечная игра имеет по крайней мере одно решение, возможно, среди смешанных стратегий.

Для нахождения решения конечных игр без седловой точки требуется ввести еще одно понятие «активной» стратегии:

Активной стратегией называется стратегия игрока, входящая в его смешанную стратегию с отличной от нуля частотой.

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

Пример. Позднее мы докажем, что оптимальной стратегией Фионы в игре с пальцами является смешанная стратегия с частотами . Цена игры V = – . Так как игра без седловой точки, то обе стратегии Эдварда – активные. По теореме 3 при любых частотах стратегий Эдварда цена игры не изменится, если Фиона придерживается своей оптимальной стратегии. Пусть, например, частоты стратегий Эдварда таковы: . Средняя цена игры по формуле (1) равна: V.

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