Промышленный лизинг
Методички
слишком очевидных утверждений, которые позволяют свести поиск оптимального решения к разумному перебору. Здесь мы их сформулируем и докажем. Первое из утверждений повышает роль чистых стратегий (выводит их вперед) в непосредственном поиске оптимального решения. Второе утверждение вместе со следствием из него показывает, что для поиска значения игры существуют достаточно простые формулы. Третье устанавливает еще более жесткую связь между искомым решением и чистыми стратегиями игроков. ТЕОРЕМА 1. Для того чтобы набор (Р*, Q*, v) был решением матричной игры в смешанных стратегиях, необходимо и достаточно, чтобы выполнялось условие Доказательство начнем с необходимости. Пусть (Р*, Q*, v) - решение матричной игры в смешанных стратегиях. Тогда для любых наборов Р = {ри рт) и Q = {qb q } выполнены неравенства справедливые, в частности, и для любых чистых стратегий игроков (здесь Р = {рь рт} - произвольная стратегия игрока А), которое доказывается совсем просто: #(! (} )£v£#(P\l,), / = 1,...,/и; * = !,...,л. (*) Я(Р, (Г)£Я(Р\ Q>v<#(P\ Q), Я(1 СГ)<#(Р\1,). Достаточность. Предположим выполненным условие #(l Q.)<v£#(P\l,), / = 1,...,/я; * = 1,...,л, и воспользуемся равенством т п т I п > / 1 Ы\ / 1 \к=\ I Домножим неравенства #(l Q.)<v, / = 1,...,/и, на Pi и, сложив их, получим, что 2>,tf(l Q)Sv5>,=v. /=1 /=1 Откуда в силу того, что 2>,яо,.Р> %{%*А= \%лрлк = #(p,q), получаем, что Я(Р, Q)<v. Взяв произвольную стратегию Q = {qh qn} игрока В и действуя подобным же образом, домножим неравенства v<H(P\lk), * = 1,...,и, на qk, сложим их и получим, что v = v%k<H<r, Q). Тем самым Я(Р, Q-)*v<H(P\ Q). Положив здесь Р = Р*, Q = Q*, получим, что Я(Р\ Q>v и значит (Р*, Q*, v) - решение в смешанных стратегиях. ТЕОРЕМА 2. Для любой матричной игры справедливы следующие два соотношения: штЯ(Р, Q) = mjn#(P,l4), max Я(Р, Q) = max Я(1 Q). Докажем первую серию равенств. То, что выражение в левой части не превосходит правой, ramЯ(Р, Q) < min Я(Р, 1к) легко следует из того, что минимум функции Я(Р, Q) слева ищется на большем множестве (всех стратегий игрока В), а справа на меньшем множестве (только его чистых стратегий). Введем обозначение и оценим функцию Я(Р, Q) снизу. Имеем т I я \ т 1 = 1 \ АГ= 1 / 1 = 1 /Я Л Л * 2Х, Л = 5Х. А 1 = Я(Р, 110) min Я(Р, 1, ) /=1 Аг= 1 /=1 Отсюда пипЯ(Р, Р)>1ШпЯ(Р, 1.). Сопоставив первое из доказанных неравенств с последним, убеждаемся в справедливости утверждения. Справедливость второй серии соотношений доказывается аналогично. Следствие. I v = maxmin Я(Р, 1) = пиптахЯ(1/,Р). ТЕОРЕМА 3. Пусть набор (Р*, Q*, v) является решением матричной игры в смешанных стратегиях. Тогда из того, что /*,*>(), вытекает равенство HQ.i9Q*) = v9 из того, что q*k>09 вытекает равенство Я(Р\ lk)=v. Доказательство первого из сформулированных утверждений будем вести от противного. Вследствие того что набор (Р*, Q*, v) - решение матричной игры в смешанных стратегиях, для любого / выполняются неравенства H(\i9Q)<v, / = 1,...,/и. Предположим, что существует номер /., для которого Pt. >о и соответствующее неравенство является строгим Ж1,.,(Г)< Умножим обе части каждого из неравенств H(lnQ*)<v на р\ и, сложив (в силу сделанного предположения о том, что одно из них является строгим), получим, что #(Р\ (Г)=Я(Р\ Q*). 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 91 92 |