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

В этом параграфе мы докажем для прямоугольных игр основную теорему, которая иногда называется «теоремой о минимаксе». Мы покажем, что если функция Е определена так, как в разделе 1, то для любой прямоугольной игры величины

существуют и равны между собой.

Докажем предварительно лемму о матрицах.

Лемма 2.5. Пусть дана матрица

Тогда 1) либо существует элемент множества , такой, что

2) либо существует элемент множества , такой, что

Доказательство. В этом доказательстве мы будем использовать дельта-символы Кронекера, которые определяются следующим образом:

Положим

Тогда , где есть точка пространства , координата которой равна 1, а все другие координаты равны нулю.

Положим также

Таким образом, где есть точка, координаты которой — элементы столбца матрицы А Пусть С — выпуклая оболочка множества точек

Пусть — начало координат пространства . Разберем два случая, когда и . Если , то z есть выпуклая линейная комбинация точек . Следовательно, существует элемент множества такой, что

Из уравнения (4) следует

или, как это следует из определения дельта-символов,

    (5)

Так как , то неотрицательно, следовательно, из равенства (5) получим

Заметим теперь, что

так как иначе, поскольку для , мы должны иметь

то есть на основании равенства (5)

что противоречит тому, что . Поэтому мы можем положить

Из неравенств (6) и (7) мы заключаем, что

Так как из равенств (8) очевидно, что , мы заключаем, что условие (2) леммы 2.5 выполняется, так что лемма в случае, когда , справедлива.

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

Так как z лежит на гиперплоскости, то мы имеем

и следовательно, .

Таким образом, уравнение гиперплоскости имеет вид

Можно предположить, что любая точка множества С удовлетворяет неравенству

ибо если точки множества С удовлетворяют неравенству

то, умножая его на —1, получим

и можно получить неравенство (10), заменив — на . Неравенство (10) должно быть справедливо, в частности, для точек множества С; таким образом,

а это означает (согласно определению дельта-символов), что

Кроме того, (10) должно быть справедливо для точек ; таким образом,

    (12)

Из неравенства (11) ясно, что , и следовательно, мы можем написать

Из выражений (12) и (13) мы заключаем, что

и тем более

    (14)

Поскольку из выражений (11) и (13) следует, что , то неравенство (14) означает, что условие (1) леммы выполняется. Это завершает доказательство.

Докажем основную теорему теории прямоугольных игр.

Теорема 2.6. Пусть

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

Тогда величины

и

существуют и равны между собой.

Доказательство. Для каждого функция есть непрерывная линейная функция от определенная на замкнутом подмножестве пространства ; отсюда

существует для любого Y из . Далее, легко убедиться в том, что

есть непрерывная кусочно-линейная функция . Поскольку есть замкнутое подмножество пространства мы заключаем отсюда, что

существует. Аналогично можно показать, что

существует.

Если первое условие леммы 2.5 выполняется, то существует элемент множества такой, что

и, следовательно, такой, что для любого

    (15)

Так как (15) справедливо для любого , то

и, следовательно,

Аналогично заключаем, что если условие (2) леммы 2.5 выполнено, то

Но поскольку выполняется либо условие (1), либо условие (2) леммы 2.5, то по крайней мере одно из двух неравенств, (16) или (17), должно выполняться, и, следовательно, неравенство

не может быть справедливо.

Пусть — матрица, которая получается из А при вычитании к из каждого элемента матрицы А, то есть

и пусть — математическое ожидание выигрыша для , так что для любого X и любого Y, являющихся соответственно элементами множеств , мы имеем

Тогда, точно так же, как мы показали, что неравенство (18) неверно для А, мы можем показать, что неравенство

неверно для . Но из равенства (19) легко увидеть, что

а из условий (20) и (21) мы заключаем, что. неравенство

неверно. Следовательно, неверно неравенство

Поскольку (23) неверно для любого , мы заключаем, что неравенство

неверно, отсюда справедливо неравенство

С другой стороны, согласно теореме 1.1, мы имеем

из неравенств (24) и (25) следует, что

что завершает доказательство теоремы.

В терминах теории игр теорема 2.6 может быть сформулирована следующим образом.

Теорема 2.7. Всякая прямоугольная игра имеет цену, игрок в прямоугольной игре всегда имеет оптимальную стратегию.

Доказательство теоремы легко вытекает из теорем 2.6 и 1.5.