Введение в теорию игр (сторонняя методичка) (Введение в теорию игр (сторонняя методичка).PDF), страница 44

Ïóñòü C − ñóììà ìàòðèö A è B . Êàê îòìå÷àëîñü, C = (cij )m×n =(fj + gi )m×n . Ïîñêîëüêó f1 = 0, ðàçíîñòü j -ãî è 1-ãî ñòîëáöîâ ìàòðèöûC ìîæíî çàïèñàòü â âèäå fj e, ãäå e = (1, ..., 1) ∈ E m . Îòñþäà fj = c1j −c11 , j = 1, ..., n è a0ij = aij − fj = aij − a1j − b1j + a11 + b11 ∀ i, j.10.4. Çàìåòèì, ÷òî äëÿ ëþáîé ñìåøàííîé ñòðàòåãèè q âòîðîãî èãðîêà0A(i, q) = A (i, q) +nXfj qj , i = 1, ..., m.(22.4)j=1Ïîýòîìó íåðàâåíñòâà A(i, q 0 ) ≤ A(p0 , q 0 ) ðàâíîñèëüíû íåðàâåíñòâàìA0 (i, q 0 ) ≤ A0 (p0 , q 0 ), i = 1, ..., m. Àíàëîãè÷íî ïîêàçûâàåòñÿ, ÷òî äëÿ ëþáîé ñìåøàííîé ñòðàòåãèè p ïåðâîãî èãðîêà0B(p, j) = −A (p, j) +mXgi pi , j = 1, ..., n,(22.5)i=1è ÷òî íåðàâåíñòâà B(p0 , j) ≤ B(p0 , q 0 ) ðàâíîñèëüíû íåðàâåíñòâàìA0 (p0 , j) ≥ A0 (p0 , q 0 ), j = 1, ..., n. Îòñþäà âûòåêàåò, ÷òî äëÿ ñèòóàöèè(p0 , q 0 ) óñëîâèå (∗) â èãðå ñ ìàòðèöåé A0 (òåîðåìà 4.10 ) ýêâèâàëåíòíî óñëîâèþ (∗) â èãðå Γ (ëåììà 10.1).10.5.

Èç ôîðìóë (22.4) è (22.5) ñëåäóåò, ÷òîArg max A(i, q(k)) = Arg max A0 (i, q(k)),1≤i≤m1≤i≤mArg max B(p(k), j) = Arg min A0 (p(k), j).1≤j≤n1≤j≤nÏîýòîìó ïîñëåäîâàòåëüíîñòè ñòðàòåãèé èãðîêîâ {ik }, {jk } â ïðîöåññå Áðàóíà äëÿ èãðû ñ ìàòðèöåé A0 è â àíàëîãè÷íîì ïðîöåññå äëÿ èãðû Γ ìîæíîâçÿòü ñîâïàäàþùèìè. Ïî òåîðåìå 5.3 ëþáàÿ ïðåäåëüíàÿ òî÷êà (p0 , q 0 ) ïîñëåäîâàòåëüíîñòè {(p(k), q(k))} ÿâëÿåòñÿ ñåäëîâîé òî÷êîé â ñìåøàííûõñòðàòåãèÿõ è, ñëåäîâàòåëüíî, ñìåøàííûì ðàâíîâåñèåì ïî Íýøó èãðû Γ.247Ÿ 22.Ðåøåíèå óïðàæíåíèé11.1.

Çàìåòèì, ÷òî Y1∗ (f1ε ) = {g | g(xε ) = y ε }. Ñëåäîâàòåëüíî,W (f1ε ) =inf∗g∈Y1 (f1ε )F (f1ε (g), g) = F (xε , y ε ) ≥ K 0 − ε.11.2. Âîçüìåì ïðîèçâîëüíóþ ñòðàòåãèþ f1 ∈ {f1 } è äîêàæåì, ÷òîW (f1 ) ≤ max[K 0 , F1 ]. Ïóñòü {g ∗ } − ìíîæåñòâî âñåõ ôóíêöèé íàèëó÷øåãîîòâåòà âòîðîãî èãðîêà. Èìååìsup G(f1 (g), g) ≥ sup inf G(x, g) ≥g∈{g} x∈Xg∈{g}≥ sup inf G(x, g ∗ ) = min max G(x, y) = G3 .g ∗ ∈{g ∗ } x∈Xx∈X y∈YÐàññìîòðèì äâà ñëó÷àÿ.1) sup G(f1 (g), g) > G3 . Òîãäà íàéäåòñÿ òàêàÿ ôóíêöèÿg∈{g}g ε ∈ Y1∗ (f1 ), ÷òî ïàðà (x0 , y 0 ) = (f1 (g ε ), g ε (x0 )) ïðèíàäëåæèò ìíîæåñòâóD0 .  ýòîì ñëó÷àåW (f1 ) =inf∗g∈Y1 (f1 )F (f1 (g), g) ≤ F (f1 (g ε ), g ε ) = F (x0 , y 0 ) ≤ K 0 .2) sup G(f1 (g), g) = G3 .

Ïîêàæåì, ÷òî {g ∗ } ⊆ Y1∗ (f1 ).g∈{g}Äåéñòâèòåëüíî, äëÿ âñÿêîé ôóíêöèè íàèëó÷øåãî îòâåòà g ∗G3 = min max G(x, y) = min G(x, g ∗ ) ≤x∈X y∈Yx∈X≤ G(f1 (g ∗ ), g ∗ ) ≤ sup G(f1 (g), g) = G3 .g∈{g} ïîñëåäíèõ íåðàâåíñòâàõ êðàéíèå ÷ëåíû ñîâïàäàþò. Ñëåäîâàòåëüíî, âñåíåðàâåíñòâà âûïîëíåíû êàê ðàâåíñòâà è {g ∗ } ⊆ Y1∗ (f1 ).

Îïðåäåëèìg 0 ∈ {g ∗ } :g 0 (x) ∈ Arg min F (x, y) ∀x ∈ Xy∈Y (x)− ôóíêöèþ íàèëó÷øåãî îòâåòà âòîðîãî èãðîêà, íàèìåíåå áëàãîæåëàòåëüíîãî ïî îòíîøåíèþ ê ïåðâîìó. ÒîãäàW (f1 ) =infg∈Y1∗ (f1 )F (f1 (g), g) ≤ F (f1 (g 0 ), g 0 ) ≤≤ sup F (x, g 0 (x)) = sup min F (x, y) = F1 .x∈Xx∈X y∈Y (x)248Ÿ 22.Ðåøåíèå óïðàæíåíèé11.3. Çàäàäèì ñòðàòåãèþ g ∗ âòîðîãî èãðîêà óñëîâèåìg ∗ (x) ∈ Arg max F (x, y) ∀x ∈ X.y∈Y (x)Îíà àíàëîãè÷íà ñòðàòåãèè ïåðâîãî èãðîêà f ∗ , îïðåäåëåííîé ïåðåä ëåììîé 11.1. Èç ýòîé ëåììû ñëåäóåò, ÷òî ôóíêöèÿ F (x, g ∗ (x)) ïîëóíåïðåðûâíà ñâåðõó íà X.

Âîçüìåì x∗ ∈ Arg max F (x, g ∗ (x)). Òîãäà (x∗ , g ∗ ) −x∈Xñèòóàöèÿ ðàâíîâåñèÿ èãðû Γ1 .11.4. Åñëè ïåðâûé èãðîê â èãðå Γ3 èñïîëüçóåò ñòðàòåãèè-êîíñòàíòûf1 (g) ≡ x, òî îí ìîæåò îáåñïå÷èòü ñåáå òàêîé æå ðåçóëüòàò, êàê è â èãðåΓ1 . Ñëåäîâàòåëüíî, F1 ≤ F3 . Àíàëîãè÷íî ïîêàçûâàåòñÿ, ÷òî F1 ≤ F2 .Äàëåå, K 0 ≤ K, ïîñêîëüêó D0 ⊆ D. Ïîýòîìó F3 = max[K 0 , F1 ] ≤ F2 =max[K, M ].11.5.

Ïðè α = 1 ôóíêöèÿ íàèëó÷øèõ îòâåòîâ âòîðîãî èãðîêà èìååòâèä(pKx/c2 − x, 0 ≤ x ≤ K/c2 ,y(x) =0,K/c2 ≤ x ≤ K/c1 .Îöåíêà ýôôåêòèâíîñòè W (x) ñòðàòåãèè x ðàâíà(√Kc2 x − c1 x, 0 ≤ x ≤ K/c2 ,W (x) = F (x, y(x)) =K − c1 x,K/c2 ≤ x ≤ K/c1 ,îïòèìàëüíàÿ ñòðàòåãèÿ(Kc2 /(4Kc21 )), c2 ≤ 2c1 ,x∗ =K/c2 ,c2 > 2c1è íàèëó÷øèé ãàðàíòèðîâàííûé ðåçóëüòàò äëÿ ïåðâîãî èãðîêà(Kc2 /(4c1 ),c2 ≤ 2c1 ,F1 = max W (x) = W (x∗ ) =0≤x≤K/c1(c2 − c1 )K/c2 , c2 > 2c1 .Âî âòîðîì ñëó÷àå y(x∗ ) = 0 è ïåðâàÿ ôèðìà âûòåñíÿåò âòîðóþ ñ ðûíêà.

Âîáîèõ ñëó÷àÿõ F1 ≥ F (x0 , y 0 ) = Kc1 c2 /(c1 + c2 )−2 , ãäå (x0 , y 0 ) = (Kc2 (c1 +c2 )−2 , Kc1 (c1 + c2 )−2 ) − ñèòóàöèÿ ðàâíîâåñèÿ â èãðå Γ ïðè k = 1.11.6. Ðàâíîâåñèå ïî Øòàêåëüáåðãó â ïðèìåðå 11.1 (i0 , j 0 ) = (2, 1), à âïðèìåðå 11.2 (x0 , y 0 ) = (1/2, 1).249Ÿ 22.Ðåøåíèå óïðàæíåíèé12.1. Íåîáõîäèìîñòü.

Ïóñòü ôóíêöèÿ h(z) êâàçèâîãíóòà. Äîêàæåì,÷òî ìíîæåñòâî Ëåáåãà Z + (z 0 ) âûïóêëî äëÿ ïðîèçâîëüíîãî z 0 ∈ Z. Âîçüìåì ëþáûå äâå òî÷êè z 0 , z 00 ∈ Z + (z 0 ) è ëþáîå ÷èñëî 0 < λ < 1. Òîãäàh(λz 0 + (1 − λ)z 00 ) ≥ min[h(z 0 ), h(z 00 )] ≥ h(z 0 ).Äîñòàòî÷íîñòü. Ïóñòü ìíîæåñòâà Ëåáåãà Z + (z 0 ) âûïóêëû ïðè âñåõ0z ∈ Z. Âîçüìåì ëþáûå äâå òî÷êè z 0 , z 00 ∈ Z è ëþáîå ÷èñëî 0 < λ < 1.Áåç ïîòåðè îáùíîñòè ìîæíî ñ÷èòàòü, ÷òî h(z 0 ) ≤ h(z 00 ). Òîãäà z 0 , z 00 ∈Z + (z 0 ) è â ñèëó âûïóêëîñòè ìíîæåñòâà Z + (z 0 ) òî÷êà λz 0 + (1 − λ)z 00 òàêæåïðèíàäëåæèò Z + (z 0 ), ò.å. h(λz 0 + (1 − λ)z 00 ) ≥ h(z 0 ) = min[h(z 0 ), h(z 00 )].Ñëåäîâàòåëüíî, ôóíêöèÿ h(z) êâàçèâîãíóòà íà Z.13.1.

p(i, µ) = 0, i = 1, 2, 4, 6, p(3, µ) = 1/4, p(5, µ) = 3/4.13.2. Èãðîê 1 èìååò ñòðàòåãèè µ1 = (k, l) ∈ {(1, 1), (1, 2), (2, 1), (2, 2)},ãäå k è l − íîìåðà àëüòåðíàòèâ åãî ëåâîé è ïðàâîé ëè÷íîé ïîçèöèè (ñì.ðèñ. 13.4). Àíàëîãè÷íûé âèä èìåþò ñòðàòåãèè âòîðîãî èãðîêà.

Íîðìàëüíàÿ ôîðìà èãðû G çàäàåòñÿ ìàòðèöàìè1/2215/2−2 −1/2 −11/4 −1/41/2 −11 −1/27/4 −11/42  , B =  −2A=1/4−7/4 −1/4 −7/4 −1/4 ,7/4 1/47/4 1/4 −5/4 1/4 −5/4−7/42−7/42à íîðìàëüíàÿ ôîðìà ïîäèãðû Gz − ìàòðèöàìè1 3−3 −1Az =, Bz =.1 −1−3213.3. µ = ((1, 1), (1, 2)).14.1. Ïóñòü x ∈ Poss µa . Åñëè â íåêîòîðîé ïîçèöèè0x ∈ [x0 , x] ∩ X a , x0 6= x ñòðàòåãèÿ µa âûáèðàåò àëüòåðíàòèâó, íå ïðèíàäëåæàùóþ ïóòè [x0 , x], òî âåðîÿòíîñòü ïîïàñòü â âåðøèíó x ðàâíà íóëþ(ïðîòèâîðå÷èå).Îáðàòíî, ïóñòü â êàæäîé âåðøèíå x0 ∈ [x0 , x] ∩ X a , x0 6= x, ñòðàòåãèÿµa âûáèðàåò àëüòåðíàòèâó, ïðèíàäëåæàùóþ ïóòè [x0 , x]. Ïîêàæåì, ÷òî âýòîì ñëó÷àå x ∈ Poss µa .

Äåéñòâèòåëüíî, îïðåäåëèì ñòðàòåãèèµb , b ∈ A\{a}, äðóãèõ èãðîêîâ òàêèì îáðàçîì, ÷òîáû ýòè ñòðàòåãèè âûáèðàëè â êàæäîé âåðøèíå x0 ∈ [x0 , x] ∩ X b , x0 6= x,, àëüòåðíàòèâû ïðèíàäëåæàùèå ïóòè [x0 , x]. Åñëè x0 ∈ [x0 , x] ∩ X 0 , x0 6= x, òî âåðîÿòíîñòüâûáîðà òàêîé àëüòåðíàòèâû ïîëîæèòåëüíà. Ñëåäîâàòåëüíî, p(x|µ) > 0.14.2.

Íà ðèñ. 22.1 èçîáðàæåíî äåðåâî èãðû. Èãðîê 1 èìååò ïîëíóþïàìÿòü, ïîñêîëüêó Ïàðòíåð íàáëþäàåò çà äåéñòâèÿìè Èãðàþùåãî. Èãðîê250Ÿ 22.Ðåøåíèå óïðàæíåíèé2 õîäèò òîëüêî îäèí ðàç è ïîýòîìó òàêæå èìååò ïîëíóþ ïàìÿòü. Çàïèøåìñòðàòåãèþ ïîâåäåíèÿ èãðîêà 1 â âèäå β 1 = (h, r, t), ãäå 0 ≤ h, r, t ≤ 1 −âåðîÿòíîñòè âûáîðà ïåðâîé àëüòåðíàòèâû â ìíîæåñòâàõ Z 11 , Z 12 è Z 13ñîîòâåòñòâåííî. Èãðîê 2 èìååò äâå ÷èñòûå ñòðàòåãèè: (1) è (2).21•HZHHHH• Z 11•hh•Z 12 •B Br •1•C C CBt BBB• •−2−213C Z C•B CC B CCBCrtCBCCBCC• •B• •C•4 −13 3−3Ðèñ. 22.1Îæèäàåìûéâûèãðûø èãðîêà 1 ðàâåí(hr − 2h(1 − r) − 2(1 − h)t + 4(1 − h)(1 − t),åñëè µ2 = (1),−hr + 3h(1 − r) + 3(1 − h)t − 3(1 − h)(1 − t), åñëè µ2 = (2),èëè(h(3r − 2) + (1 − h)(2 − 6t), åñëè µ2 = (1),h(3 − 4r) + (1 − h)(6t − 3), åñëè µ2 = (2).Ïîýòîìó ìàêñèìàëüíûé ãàðàíòèðîâàííûé âûèãðûø èãðîêà 1 ðàâåív = max min[h(3r − 2) + (1 − h)(2 − 6t), h(3 − 4r) + (1 − h)(6t − 3)].0≤h,r,t≤1Åãî ìîæíî çàïèñàòü êàê max v(r, t), ãäå v(r, t) − çíà÷åíèå èãðû Γrt ñìàòðèöåé0≤r,t≤13r − 2 3 − 4r.4 − 6t 6t − 3Èãðîê 2, ïðèìåíÿÿ ñìåøàííóþ ñòðàòåãèþ 1/2(1)+1/2(2) íå ïîçâîëèò èãðîêó 1 âûèãðàòü â èãðå Γrt áîëüøå, ÷åì 1/2 ïðè ëþáûõ r, t.

Íî èãðîê 1, èñïîëüçóÿ ñòðàòåãèþ β = (7/12, 0, 0), îáåñïå÷èâàåò ñåáå âûèãðûø 1/2. Ñëåäîâàòåëüíî, óêàçàííûå ñòðàòåãèè îïòèìàëüíû è çíà÷åíèå èãðû v = 1/2.14.3.  ïðîöåññå Áðàóíà ht = ((ik , jk ), k = 1, ..., t) è p1 (j|ht ) =|{k|jk = j, 1 ≤ k ≤ t}|/t → 0 ïðè t → ∞, åñëè ñòðàòåãèÿ j èãðîêà 2 âòðàåêòîðèè ((it , jt ), t = 1, 2, ...) ïðèìåíÿëàñü êîíå÷íîå ÷èñëî ðàç.251Ÿ 22.Ðåøåíèå óïðàæíåíèé15.1. Âîçüìåì äâå íåïåðåñåêàþùèåñÿ êîàëèöèè K è T . Ïóñòü P K −ìíîæåñòâî ñìåøàííûõ ñòðàòåãèé pK êîàëèöèè K.

Íåòðóäíî âèäåòü, ÷òîP K∪T ⊃ P K × P T . Îòñþäàv(K ∪ T ) =minmaxpK∪T ∈P K∪T sA\(K∪T ) ∈S A\(K∪T )≥ max maxminpK ∈P K pT ∈P T sA\(K∪T ) ∈S A\(K∪T )[uK (pK , pT , sA\(K∪T ) )++uT (pT , pK , sA\(K∪T ) )] ≥ max maxpK ∈P K pT ∈P T+uK∪T (pK∪T , sA\(K∪T ) ) ≥uK (pK , sA\K )+minsA\K ∈S A\KuT (pT , sA\T ) = v(K) + v(T ).minsA\T ∈S A\TÄîêàæåì ðàâåíñòâî (15.1).v(K) = maxminpK ∈P K sA\K ∈S A\K= maxminpK ∈P K sA\K ∈S A\K= v(A) − min[v(A) − uA\K (pK , sA\K )] =maxpK ∈P K sA\K ∈S A\K= v(A) −maxpA\K ∈P A\KuK (pK , sA\K ) =uA\K (pK , sA\K ) =min uA\K (pA\K , sK ) = v(A) − v(A\K).sK ∈S K15.2. v(2) = 1, v(13) = 9, v(3) = 4, v(12) = 6.15.3.

c = 1/500, b1 = −2/5, b2 = −3/5, b3 = 0, v 0 (12) = v 0 (13) =3/5, v 0 (23) = 7/10.P a15.4. Çàìåòèì, ÷òî ìíîæåñòâî C 0 íå ïóñòî, à ôóíêöèÿy îãðàíè÷åa∈APíà íà íåì ñíèçó âåëè÷èíîév(a). Îòñþäà ñëåäóåò, ÷òî çàäà÷à ëèíåéa∈Aíîãîz. ÏóñòüP aïðîãðàììèðîâàíèÿ â (15.2) èìååò îïòèìàëüíîåP ðåøåíèå0az ≤ v(A). Âîçüìåì òàêîé âåêòîð h ∈ C , ÷òîh > v(A). Òîãäàa∈Aa∈Aâûïóêëàÿ êîìáèíàöèÿ λz + (1 − λ)h, ãäå λ ∈ (0, 1] îïðåäåëÿåòñÿ èç óðàâíåíèÿXXλz a + (1 − λ)ha = v(A),a∈Aa∈Aïðèíàäëåæèò ÿäðó C.

Îáðàòíî, äîïóñòèì, ÷òî ÿäðî C íå ïóñòî. Òîãäà(15.2) ñëåäóåò èç âêëþ÷åíèÿ ìíîæåñòâ C ⊂ C 0 .252Ÿ 22.Ðåøåíèå óïðàæíåíèé15.5. Ïóñòü λ − çàäàííîå â óñëîâèè ïðèâåäåííîå ñáàëàíñèðîâàííîå ïîêðûòèå. Òîãäà λT ∪L = 0, ïîñêîëüêó â ïðîòèâíîì ñëó÷àå âåêòîðû χ(T ), χ(L)è χ(T ∪ L) áûëè áû ëèíåéíî çàâèñèìûìè. ÈìååìλT χ(T ) + λL χ(L) = (λT − λL )χ(T ) + λL (χ(T ) + χ(L)) == µT χ(T ) + µT ∪L χ(T ∪ L).ÏîýòîìóXµK χ(K) =K6=AXλK χ(K) = χ(A),K6=Aà ñèñòåìà âåêòîðîâ{χ(K) | µK > 0} = {χ(K) | λK > 0} ∪ {χ(T ∪ L)}\{χ(L)}ëèíåéíî íåçàâèñèìà.

Òàêèì îáðàçîì, âåêòîð µ − ïðèâåäåííîå ñáàëàíñèðîâàííîå ïîêðûòèå. Äàëåå,λT v(T ) + λL v(L) = (λT − λL )v(T ) + λL (v(T ) + v(L)) ≤≤ (λT − λL )v(T ) + λL v(T ∪ L) = µT v(T ) + µT ∪L v(T ∪ L).Îòñþäà âûòåêàåò íåðàâåíñòâî (15.4).15.6. Ïðîåêöèÿ ÿäðà C íà ïëîñêîñòü (y 1 , y 2 ) èìååò âèä{(y 1 , y 2 ) | v(12) ≤ y 1 + y 2 ≤ v(123) − v(3),v(1) ≤ y 1 ≤ v(123) − v(23), v(2) ≤ y 2 ≤ v(123) − v(13)} == {(y 1 , y 2 ) | 800 ≤ y 1 + y 2 ≤ 1000, 200 ≤ y 1 ≤ 350, 300 ≤ y 2 ≤ 500}.Âåðøèíû ìíîæåñòâà C :y(1) = (300, 500, 200), y(2) = (350, 450, 200), y(3) = (350, 500, 150).15.7. Íåîáõîäèìîñòü. Âîçüìåì äåëåæ y(0) èç ÿäðà C.