§ 10.3. Теорема о минимаксе

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

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

                                               (10.9)

Может оказаться, что это неравенство переходит в равенство

                                  (10.10)

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

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

                            (10.11)

Иными словами, существуют такие оптимальные смешанные стратегии и , что

                               (10.12)

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