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

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

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

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

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

Высказанное утверждение составляет содержание так называемой основной теоремы теории игр. Эта теорема была впервые доказана фон Нейманом в 1928г. Приведем ее формулировку.

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

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

a£n£b.

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

n³a.

Аналогично, рассматривая возможности противника, покажем, что

n£b,

откуда следует доказываемое неравенство.

Введем специальное обозначение для смешанных стратегий. Если, например, наша смешанная стратегия состоит в применении стратегий А₁, А₂, А₃ с частотами р_1, р₂, р₃, причем р₁ + р₂ + р₃ = 1, будем обозначать, эту стратегию:

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

где q₁, q₂, q₃ — частоты, в которых смешиваются стратегии В₁, В₂, В₃; q₁ +q₂ + q₃=1.

Предположим, что нами найдено решение игры, состоящее из двух оптимальных смешанных стратегий S_A^*, S_B^*. В общем случае не все чистые стратегии, доступные данному игроку, входят в его оптимальную смешанную стратегию, а только некоторые. Будем называть стратегии, входящие в оптимальную смешанную стратегию игрока, его "полезными" стратегиями.

Оказывается, что решение игры обладает еще одним замечательным свойством: если один из игроков придерживается своей оптимальной смешанной стратегии S_A^* (S_B^*), то выигрыш остается неизменным и равным цене игры n, независимо от того, что делает другой игрок, если он только не выходит за пределы своих "полезных" стратегий. Он, например, может пользоваться любой из своих "полезных" стратегий в чистом виде, а также может смешивать их в любых пропорциях.