назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [ 20 ] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90]


20

в игре, попытавшись с самого начала отбрость те из них, которые заведомо не будут участвовать в формировании каких-либо оптимальных статегий.

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). □

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [ 20 ] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90]