§ 10.3. Теорема о минимаксе
Рассмотрим игру с платежной матрицей (10.1). Естественное стремление первого игрока увеличить свой выигрыш приводит к тому, что он выбирает из всех стратегий
такую, которая гарантировала бы ему наибольший из всех минимальных выигрышей,
.
Второй игрок стремится выбрать такую стратегию
, которая обеспечила бы ему наименьший из всех максимальных проигрышей,
. При этом всегда
(10.9)
Может оказаться, что это неравенство переходит в равенство
(10.10)
Тогда говорят, что игра в чистых стратегиях имеет седловую точку
. При этом стратегии
,
оптимальны. Отклонение любого игрока от оптимальной стратегии приводит к тому, что противник только увеличивает свой выигрыш. Мало того, за счет соответствующего выбора стратегий он может выиграть еще больше.
Если бы равенство (10.10) выполнялось для любой платежной матрицы
, то на этом поиски оптимальных способов игры закончились. Но часто платежная матрица может не иметь седловой точки. В этих случаях игрок вынужден в каждой партии выбирать сметанные стратегии, при этом противник уже не может точно определить результат этого выбора. Таким образом, мы приходим к игре со смешанными стратегиями
и
. Фундаментом теории игр является теорема фон Неймана о минимаксе, состоящая в том, что платежная функция (10.3) удовлетворяет соотношению
(10.11)
Иными словами, существуют такие оптимальные смешанные стратегии
и
, что
(10.12)
Величина
называется ценой игры. Эта теорема утверждает, что матричная игра со сметанными стратегиями всегда имеет седловую точку
. Любопытно то, что как первый, так и второй игрок не получают никакого преимущества от знания распределения вероятностей ходов противника.