§ 13. ТЕОРЕМА О МИНИМАКСАХ
Теорема. Какова бы ни была матрица А, max min ХА = min maxX4 Y.
X YY X
Доказательство. Применим к матрице А лемму о двух альтернативах.
Предположим, что осуществляется первая альтернатива, т.е. существует такой вектор Xq , что
ХоЛ.уО, /=(13.1)
Переходя на основании леммы п. 9.4 к смешанным стратегиям, мы ползшм XqA Y О (FG Y). Так как это неравенство справедливо для любого вектора У Е У, в силу следствия п. 3.3 должно быть
minXor О(13.2)
и тем более
max min ХА Y > 0.
X Y
Пусть теперь осуществляется вторая альтернатива, т.е. существует такой вектор Уо, что
Ai.Y О, /= 1,...,т.(13.3)
Переход к смешанным стратегиям дает нам ХА Yq О для всех XGX, Поэтому должно быть и max ХА yI 0,и тем более
minmaxX4r 0.(13.4)
у X
Мы видим, что в зависимости от осуществления той или иной альтернативы вьшолняется неравенство (13.2) или неравенство (13.4). Следовательно, хотя бы одно из этих неравенств должно соблюдаться. Поэтому не может быть так, чтобы оба эти неравенства не выполнялись. Иными словами, не может выполняться двойное неравенство
max min XAY<0< min max ХА Г.(13.5)
X YY X
Возьмем теперь произвольное вещественное число t и рассмотрим матрицу
ац - t ai2 - tахп - t
A{t) =
-t a22-t ... a2n-t
Напишем для матрицы A{t) неравенство (13.5) :
max min XA{t)Y < 0 < min max XA{t)Y.(13.6)
X YY X
Но в нашем случае
т п
XA(t)Y= Г 2 1/(,7= / = 1 / = 1
т пт п
= 22 м Г?/-Г 2 2 ?,-г?у = ХЛГ-Г.(13.7)
Z = 1 / = 1I = 1 / = 1
Поэтому (13.6) равносильно
max min(X4 - о < О < min max(X4 Y- t\
X YY X
или, что то же самое,
max min XAY <t< min maxX4 Y.
X YY X
По-прежнему обе стороны написанного неравенства не могут быть верными одновременно, каково бы ни бьшо число t. Но это значит, что между мини-максами max minX Y и min maxX4 У- нельзя вставить ни одного чис-
X YY X
ла, которое бьшо бы строго больше первого из них и строго меньше второго. Такое может оказаться только тогда, когда второй минимакс не превосходит первого:
min max ХА У < max min ХА У.(13.8)
Y XX Y
Вместе с тем на основании неравенства минимаксов (теорема п. 3.4) должно быть
maxminX4y maxminX4y.(13.9)
X YX Y
Неравенства (13.8) и (13.9) вместе дают нам maxminX4y = т1птахХ4У,
X YY X
что и требовалось. □
О смысле выражения "полная определенность игры" см. приложение 1.
§ 14. ЗАДАЧА РЕШЕНИЯ МАТРИЧНЫХ ИГР
14.1.Доказанная в предыдущем параграфе теорема о минимаксах утверждает, что во всякой матрично1 игре игроки имеют смешанные оптимальные стратегии. Однако никаких явных путей для вычисления таких стратегий эта теорема не указывает. В этом смысле она оказьшается типичной "теоремой существования". Проанализируем складьшающееся в связи с этим положение дел.
14.2.Установление существования в матричных играх оптимальных стратегий игроков означает, прежде всего, реализуемость принципа максимина. По существу это выражает тот "метаматематический" факт, что принцип максимина не противоречит конструкции матричной игры и ее смешанного расширения. Этот факт может стать побудительным мотивом к поискам опти-
мальных стратегий игроков в той или иной матричной игре и даже алгорифма описания множеств всех оптимальных стратегий в любой матричной игре.
Если точное нахождение оптимальной стратегии игры не удается, то уверенность в их объективном существовании увеличивает ценность и их приближенного определения.
14.3. Вместе с тем неэффективная теорема существования сама по себе представляет лишь весьма ограниченную практическ)ао ценность и нуждается в более эффективном "восполнении" (каковым может служить, например, фактическое определение объекта, существование которого доказано). Более того, с некоторой, достаточно последовательной "конструктивистской точки зрения, такое неэффективное доказательство может даже оспариваться.
Впрочем, для матричных игр все эти проблемы получают достаточно удовлетворительное и притом сравнительно простое решение.
§ 15. СВОЙСТВА ЗНАЧЕНИЯ ИГРЫ И ОПТИМАЛЬНЫХ СТРАТЕГИЙ ИГРОКОВ
15.1.Теорема. Для матричной игры Та имеет место соотношение
=тахшшХЛ./ = min шах Л/. У",*(15.1)
X jY i
причем внешние экстремумы достигаются на оптимальных стратегиях игроков.
Для доказательства достаточно заметить, что по определению значения игры (см. пп. 4.5 и 6.4)
Va =maxminX4F = minmaxX4F-,(15.2)
X уу X
а внутренние экстремумы можно по лемме п. 10.2 заменить на экстремумы, распространенные по множествам чистых стратегий.
После этого остается вспомнить (см. п. 6.2), что внепшие экстремумы в (15.2) достигаются именно на оптимальных стратегиях игроков. □
Из этой теоремы получается много полезных свойств значения игры и оптимальных стратегий игроков.
15.2.Т е о р е м а. Для любой матрицы Л
maxminfl,y minmaxfl/y.(15.3)
Доказательство. Из (15.1) и леммы п. 3.7 следует, что
Va = max min ХЛ./тах min ац. X i i J
Правая половина соотношения (15.3) доказьшается аналогично. □
15.3.Теорема. Если игрок 1 имеет чистую оптимальную стратегию /о, то
Va = max min aij = min у.(15.4)
i
Если игрок 2 имеет чистую оптимальную стратегию /о, то
i; =min maxfl/ =тахл,у .(15.5)