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

Среди конечных игр, имеющих практическое значение, сравнительно редко встречаются игры с седловой точкой; более типичным является случай, когда нижняя и верхняя цена игры различны. Если каждому игроку предоставлен выбор одной-единственной стратегии, то в расчете на разумно действующего противника этот выбор должен определяться принципом минимакса. Придерживаясь своей минимаксной стратегии, мы при любом поведении противника заведомо гарантируем себе выигрыш, равный нижней цене игры . Возникает вопрос: нельзя ли гарантировать себе средний выигрыш, больший , если применять не одну «чистую» стратегию, а чередовать случайным образом несколько стратегий.

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

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

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

Выигрыш, получаемый в результате решения, называется ценой игры. Очевидно, что цена игры всегда лежит между нижней ценой и верхней ценой : .

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

.

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

где - частоты, в которых смешиваются стратегии ; .

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

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

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