2.4. Теорема о минимаксе

Теорема. Всякая конечная антагонистическая игра имеет хотя бы одну точку равновесия, может быть и в смешанных стратегиях.

v_I = v_II.

Эта важнейшая в теории игр теорема была доказана многими способами. Мы приведем здесь доказательство, принадлежащее фон Нейману и Моргенштерну. Для того, чтобы перейти к доказательству теоремы, начнем с двух лемм. [6]

Лемма 1 (теорема об опорной гиперплоскости). Пусть В — замкнутое выпуклое множество в п-мерном евклидовом про­странстве, а х = (х₁,..., х_n) – некоторая точка, не принадлежа­щая В. Тогда существуют такие числа р₁, ..., р_п, р_п+1, что

(2.32)

^и (2.33)

(Геометрически это означает, что через точку х можно провести гиперплоскость так, что В будет лежать целиком «выше» этой гиперплоскости.)

Доказательство. Пусть z – такая точка из В, расстояние которой от х минимально. (Такая точка существует, так как В замкнуто.) Положим

p_i = z_i – x_i, i=1, .... n,

Очевидно, равенство (2.32) выполняется. Нужно доказать, что имеет место (2.33). Мы имеем

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

Поэтому

Допустим, что существует , для которого

Так как В выпукло, отрезок, соединяющий у с z, должен целиком содержаться в В, т. е.

w_i=ry+(1-r)zВ

для всех 0 < r < 1. Квадрат расстояния от х до w_r имеет вид

Поэтому

Если r = 0 (в этом случае w_r =z), то имеем

Здесь первое слагаемое по предположению не превосходит 2р_n+1, а второе больше 2р_n+1. Поэтому

Отсюда следует, что для r, достаточно близких к нулю,

р(х, w_r ) < p(х, z).

Но это противоречит выбору z; следовательно, для всех у В условие (2.33) должно выполняться.

Таким образом, лемма жлказана.

Лемма 2 (теорема об альтернативах для матриц). Пусть H = (h_ij) есть (т X п) - матрица. Тогда справедливо либо утвер­ждение (*), либо утверждение (**):

(*): точка 0 (в т-мерном пространстве) содержится в выпуклой оболочке т + п точек

h₁ = (h₁₁,…, h_m1),

_{……………………………}

h_n = (h_1n,…, h_mn),

e₁ = (1, 0,…, 0),

e₂= (0, 1,…, 0),

_{……………………………}

e_m= (0, 0,…, 1);

(**): существуют числа х₁, ..., х_m, удовлетворяющие условиям

_{xi > 0, , j=1,…, n.}

Доказательство. Предположим, что утверждение (*) не­верно. На основании леммы 1 существуют такие числа р₁, .., р_m+1, что

(отсюда следует, конечно, что р_т+1 = 0) и

для всех у в указанном выпуклом множестве. В частности, это выполняется, если у является любым из т + п векторов h_j, е_i. По­этому

для всех j,

p_i > 0 для всех i.

Так как р_i > 0, получаем, и можно положить

.

Следовательно,

_{xi > 0,} .

Лемма доказана.

На основании двух этих лемм можно доказать теорему.

Доказательство теоремы о минимаксе. Пусть Г – некоторая матричная игра с матрицей H. По лемме 2 имеет место либо утверждение (*), либо (**).

Если верно (*), то 0 является выпуклой линейной комбинацией т + п векторов. Поэтому существуют такие s₁, ..., s_n, что

i =1,…, m,

s_j > 0, j =1, …, m+n

Если бы все числа s₁, ..., s_n были равны нулю, то 0 оказывался бы выпуклой линейной комбинацией т единичных векторов е₁, ..., е_m , что, очевидно, невозможно, так как они линейно независимы. Следовательно, по крайней мере одно из чисел s₁, …, s_n положительно и . Тогда можно положить

и мы получаем

для всех i.

Значит, v(у) < 0 и v_II < 0.

Предположим теперь, что верно утверждение (**). Тогда v(х) > 0, так что v_I > 0.

Следовательно, неравенство v₁<0<v_II не может иметь места. Предположим теперь, что мы изменили игру H, заменив ее на игру В = (b_ij), где

b_ij = h_ij + k.

Ясно, что для любых х, у

хВу^T = хHу^T + k.

Поэтому

v_I (В)=v_I (H)+ k,

v_II (В)=v_II (H)+ k.

Так как неравенство

v_I (В)<0< v_II (В)

не может иметь места, то неравенство

v_I (H)<-k< v_II (H)

также не выполняется. Но H произвольно. Значит, неравенство v₁< v_II невозможно. Так как v₁< v_II, то

v₁ = v_II

что и требовалось доказать.

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

_{j =1,…,n, (2.34)}

является оптимальной для игрока I в том смысле, что не существует стратегии, которая дала бы ему больший ожидаемый выигрыш, чем v, против каждой стратегии игрока II. Обратно, если у удовлетворяет условию

_{i =1,…,m, (2.35)}

то у является оптимальной стратегией для игрока II в том же смысле. Далее, очевидно, что

хHу^T = v,

так как если бы правая часть этого равенства была меньше левой, то это противоречило бы (2.35), а если бы она была больше ле­вой, это противоречило бы (2.34). Следовательно, оптимальные стратегии х и у являются также оптимальными одна против другой, а также против любой иной оптимальной стратегии. Будем на­зывать любую пару оптимальных стратегий (х, у) решением игры.

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

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

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