в игре, попытавшись с самого начала отбрость те из них, которые заведомо не будут участвовать в формировании каких-либо оптимальных статегий.
17.2. Т е о р е м а. Пусть {X*, Y*) - приемлемая для игрока 1 ситуация в матричной игре Г, причем Z * = (?i, .. ., ). Тогда
1)из
AY* КХАУ""(17.1)
следует / = О, т.е. что чистая стратегия i не принадлежит спектру смешанной стратегии X *;
2)2сли
АУ* =Х*АУ* для / = zi,...,/fc,
то ХАУ* = Х*ЛУ* для любой смешанной стратегии Х игрока 1 со спектром {ix, , г.} (т.е. в этом случае ситуация (Х, У*) также оказывается приемлемой для игрока 1).
Дая ситуаций, приемлемых для игрока 2, имеет место двойственное утверждение.
Доказательство. 1)Из определения приемлемости ситуации (Х\ У*) для игрока 1 (см. п. 4.2) следует, что Л,. .У* <Х*ЛГ * ддя любого / = 1, ..., т. Умножив каждое из этих неравенств на , мы получим
AYiXy*,(17.2)
а просуммировав по всем i= 1,.. . ,т -
2 iAi,y* = X*AY*<( 2 i)X*Ay*=X*Ay*. 1=1/=1
В действительности здесь, очевидно, имеет место равенство. Так как оно бьшо получено суммированием нестрогих неравенств одного смысла, каждое из этих неравенств (17.2) должно быть точным равенством: Л/ .У * =
= Х*АУ*. В случае ?/>0 отсюда следовало бы=Х*ЛГ*, что
противоречило бы (16.1).
2) Получается непосредственным использованием леммы о переходе к смешанным стратегиям. □
17.3. Следующее свойство оптимальных стратегий игроков в матричной игре называется "дополняющей нежесткостью" по аналогии со сходным свойством решений пар двойственных задач линейного программирования (ср. далее в § 26). По своей формулировке и своему доказательству оно сходно с частью 1) теоремы предьщущего пункта и двойственным ей утверждением.
Теорема. Если У - оптимальная стратегия игрока 2 в игре и для стратегии /о игрока 1 имеет место
Л-.Г<1;л,(17.3)
то чистая стратегия Iq не может принадлежать спектру какой-либо оптимальной стратегии X = (?i,. .. , „) игрока 1,т.е. должно быть
=0.(17.4)
Доказательство подобно доказательству теоремы из п. 17.2. Согласно п. 15.6 для всех / = 1,., ., m должно быть
Ai.Yv..(17.5)
Почленное умножение каждого из таких неравенств на / дает нам
kiAi.Y.kiVA,(17.6) а после суммирования по / = 1,. . ., m -
i=l1=1
Из оптимальности стратегий X и Y следует, что в этом соотношении имеет место точное равенство. Но это может быть лишь в том случае, если равенствами являются все суммируемые неравенства (17.6), и в том
числе iiAi.Y = iv.
Если теперь > О, то обе части этого равенства можно разделить на ,
получив А( .Y = , что противоречит (17.3). Значит, должно выполняться (17.4).
17.4.Теоремы о дополняющей нежесткости часто применяют в следующей эквивалентной, так сказать, "контрапозитарной" форме: если чистая стратегия /о игрока 1 входит в спектр некоторой оптимальной его стратегии, то для любой оптимальной стратегии игрока 2 должно быть AY = = . Аналогичный вывод делается из вхождения в спектр какой-либо оптимальной стратегии игрока 2 некоторой его чистой стратегии.
17.5.Существенно более деликатным является доказательство утверждения, обратного теореме п. 17.3.
Предварительно мы докажем следующую лемму, которая известна под названием леммы Фаркаша.
Лемма. Пусть Z ,.. ., и Z - такие г -векторы, что для произвольного г-вектора W из условий WZO при /=1, ...,А: следует WZO.
Тогда Z принадлежит выпуклому конусу С, натянутому на векторы Z, . . . , Z .
Доказательство. Предположим, что Z ф С. Это значит, что найдутся такие вектор W и число с, что
WU>C длявсех UC(17.6)
и WZC.
Очевидно, Og С. Поэтому из (17.6) следует, что с < 0.
Если бы теперь нашлось такое 5 g С, что WS < О, то, умножая вектор S на достаточно болылой положительный скаляр г (произведение tS по-прежнему будет принад-
лежать конусу С), мы получили бы, что WitS) может стать меньше любого наперед заданного отрицательного числа и, в частности, стать меньше, чем с:
Witsf < с,
а это противоречит (17.6).
Значит, для всех 5 g С должно быть WS О и ъ том числе WZ О для всех
/ = 1,Но тогда по условию должно быть и WZ > О, а это противоречит тому,
что WZ=-C <0. О
17.6.Обратимся непосредственно к доказательству интересующего нас утверждения.
W(tsf<c,(17.7)
Теорема. Пусть - значение игры Г. Если для любой оптимальной стратегии Y* = (rji,... ,г}п) игрока 2будетrjj = О,то найдется такая оптимальная стратегия х* = (i, .. . , игрока 1, что
x*A.j>v.(17.8)
Доказательство сильно напоминает доказательство леммы о двух альтернативах (см. п. 13.1). Не нарушая общности, мы можем считать что =0.
Рассмотрим конус С, натянутый на « + w - 1 векторов: на орты Е и на столбцы матрицы А,- при о-
Предположим сначала, что -A.j- G С. Тогда вектор - Л .у можно представить в виде линейной комбинации векторов, порождающих конус:
-Л., = X eEU X oLjA.i,(17.9)
где 6/0 (i = I, .. ., т), ау 0 (j Ф]о).В покоординатной записи равенство (17.9) приобретает вид
-aij =€(+ 2 aj-ajj для i=l,...,m,
j /о
откуда
2 ajaij-\-aij=-€iQ для z = l,.,.,m. / /о
Деля почленно это неравенство на 1 + 2 ау > О и полагая
/ /о/ /о
мы получим Ai,Y 0 = 1? для всех г = 1, . .., т, так что стратегия У игрока 2 оптимальна, причем т? > D.
Значит, должно быть -A,j С Тогда по лемме предыдущего пункта найдется вектор Z = (f i,. . ., f„), для которого
Z>0,z=l,...,m,(17.10)
ZA, 0,/ = 1,...,«, 0,(17.11)
-ZA. <0.(17.12)
Неравенство (17.10) означает f/ О, а из (17.12) следует, что Z ФО. Значит, сумма компонент вектора Z положительна, и мы можем разделить на нее почленно неравенства (17.11) и (17.12) и, полагая
?, = ГД 2 = (?i,...,?m),
полздшть Х4.у 0 = 1?, XA.j >0=i;.
Таким образом, стратегия X является оптимальной стратегией игрока 1 и притом удовлетворяет требуемому условию (17.8). □