[учебник] Введение в теорию игр (с приложениями к экономике). Васин, Морозов (2003) (1186146), страница 43
Текст из файла (страница 43)
Ïîýòîìóðàññóæäåíèÿ ìîæíî ïîâòîðèòü äëÿ ðåäóöèðîâàííîé èãðû è ïîëó÷èòü,÷òî p0i = 0 ∀ i ∈ X2 \X3 , qj0 = 0 ∀ j ∈ Y2 \Y3 è ò.ä.2) Ïóñòü ìíîæåñòâàZ = Zk ⊂ Zk−1 ⊂ · · · ⊂ Z1 = Z, Zl = Xl × Yl , l = 1, ..., k,îòâå÷àþò îïðåäåëåíèþ ñëàáîãî äîìèíèðîâàíèÿ Z Z.Ïóñòü Ak−1 è B k−1 − ïîäìàòðèöû ìàòðèö A è B ñ íîìåðàìè ñòðîê èçX k−1 è íîìåðàìè ñòîëáöîâ èç Y k−1 . Ðàññìîòðèì âåêòîð pk−1 , ïîëó÷åííûéèç âåêòîðà p äîáàâëåíèåì íóëåâûõ êîìïîíåíò ñ íîìåðàìè èç X k−1 \X.Àíàëîãè÷íî, âåêòîð q k−1 ïîëó÷àåòñÿ èç âåêòîðà q äîáàâëåíèåì íóëåâûõêîìïîíåíò ñ íîìåðàìè èç Y k−1 \Y . Äîêàæåì, ÷òî (pk−1 , q k−1 ) − ñèòóàöèÿðàâíîâåñèÿ â èãðå ñ ìàòðèöàìè Ak−1 è B k−1 .
Äëÿ ýòîãî ïðîâåðèì óñëîâèå(∗) äëÿ ñèòóàöèè (pk−1 , q k−1 ). ÈìååìAk−1 (i, q k−1 ) = A(i, q) ≤ A(p, q) = Ak−1 (pk−1 , q k−1 ) ∀ i ∈ X.Ïóñòü i ∈ X k−1 \X. Òîãäà íàéäåòñÿ òàêàÿ ñòðàòåãèÿ p, ÷òî p i íà Y k−1è pi1 = 0 ∀ i1 ∈/ X. Îïðåäåëèì âåêòîð Pp0 = (pi1 , i1 ∈ X). Òîãäàk−1k−1A (i, q ) =aij qjk−1 ≤j∈Y k−1P P0≤(ai1 j pi1 )q j = A(p , q) ≤ A(p, q) = Ak−1 (pk−1 , q k−1 ).j∈Y i1 ∈X ðåçóëüòàòå äîêàçàëè íåðàâåíñòâà246 22.Ðåøåíèå óïðàæíåíèéAk−1 (i, q k−1 ) ≤ Ak−1 (pk−1 , q k−1 ) ∀ i ∈ X k−1 .Àíàëîãè÷íî äîêàçûâàåòñÿ âòîðàÿ ãðóïïà íåðàâåíñòâ èç óñëîâèÿ (∗)B k−1 (pk−1 , j) ≤ B k−1 (pk−1 , q k−1 ) ∀ j ∈ Y k−1 .k−1 k−1Èòàê, (p , q ) − ñèòóàöèÿ ðàâíîâåñèÿ èãðû ñ ìàòðèöàìè Ak−1 è B k−1 .Ðàññóæäåíèÿ ìîæíî ïðîäîëæèòü, àíàëîãè÷íûì îáðàçîì ââåñòè ñèòóàöèþ (pk−2 , q k−2 ) è äîêàçàòü, ÷òî îíà ÿâëÿåòñÿ ðàâíîâåñèåì ïî Íýøóèãðû ñ ìàòðèöàìè Ak−2 è B k−2 è ò.ä.10.3.
Ïóñòü 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/41/2 −11 −1/27/4 −11/42 , B = −2A=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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
