Введение в теорию игр (сторонняя методичка) (1184510), страница 43
Текст из файла (страница 43)
óïðàæíåíèå 2.4),|z 0 |2 = |λz 0 + (1 − λ)z 00 |2 < λ|z 0 |2 + (1 − λ)|z 00 |2 ≤ max |z|2 ,z∈Z÷òî ïðîòèâîðå÷èò îïðåäåëåíèþ òî÷êè z 0 .5.5. Ìíîæåñòâî Z ∗ = Arg max h(z) − âûïóêëûé êîìïàêò. Ïóñòü z 0z∈Z− åãî êðàéíÿÿ òî÷êà. Ïîêàæåì, ÷òî z 0 − êðàéíÿÿ òî÷êà ìíîæåñòâà Z.Ïóñòü, íàïðîòèâ, íàéäóòñÿ òàêèå òî÷êè z 0 6= z 00 ìíîæåñòâà Z è òàêîå÷èñëî 0 < λ < 1, ÷òî z 0 = λz 0 + (1 − λ)z 00 .
Òîãäà ïî êðàéíåé ìåðå îäíà èçòî÷åê z 0 èëè z 00 íå ïðèíàäëåæàò ìíîæåñòâó Z ∗ . Ïîýòîìó h(z 0 ) =λh(z 0 ) + (1 − λ)h(z 00 ) < max h(z) (ïðîòèâîðå÷èå ñ îïðåäåëåíèåì z 0 ).z∈Z5.6. Ïóñòü îïòèìàëüíàÿ ñòðàòåãèÿ p0 ïåðâîãî èãðîêà óäîâëåòâîðÿåòñèñòåìå óðàâíåíèé (5.3), ãäå v − çíà÷åíèå èãðû, à ìàòðèöà B = (ail jt )k×k− íåâûðîæäåííàÿ. Ïîêàæåì, ÷òî p0 − êðàéíÿÿ îïòèìàëüíàÿ ñìåøàííàÿñòðàòåãèÿ. Ïðåäïîëîæèì ïðîòèâíîå, ò.å. p0 ïðåäñòàâèìî â âèäå p0 = λp0 +(1 − λ)p00 , ãäå p0 6= p00 ∈ P 0 , 0 < λ < 1. Èç ðàâåíñòâp0i = 0 = λp0i + (1 − λ)p00i ∀i 6= il , l = 1, ..., k,ñëåäóåò, ÷òî p0i = p00i = 0 ∀i 6= il , l = 1, ..., k.
Ïîñêîëüêó p0 , p00 − îïòèìàëüíûå ñìåøàííûå ñòðàòåãèè,A(p0 , jt ) ≥ v, A(p00 , jt ) ≥ v, t = 1, ..., k.(22.3)Ïîêàæåì, ÷òî íåðàâåíñòâà (22.3) ìîãóò âûïîëíÿòüñÿ òîëüêî êàê ðàâåíñòâà. Ïðåäïîëîæèì, ÷òî íàéäåòñÿ òàêîé íîìåð t1 ,÷òî A(p0 , jt1 ) > v, A(p00 , jt1 ) ≥ v. Óìíîæàÿ ïåðâîå íåðàâåíñòâî íà λ, àâòîðîå íà 1 − λ è ñêëàäûâàÿ èõ, ïîëó÷èì A(p0 , jt1 ) > v (ïðîòèâîðå÷èå).Èòàê,A(p0 , jt ) = A(p00 , jt ) ⇒kX(p0il − p00il )ail jt = 0, t = 1, ..., k.l=1Èç íåâûðîæäåííîñòè ìàòðèöû B ïîëó÷èì, ÷òîp0il = p00il , l = 1, ..., k ⇒ p0 = p00 (ïðîòèâîðå÷èå).241 22.5.7. Ïóñòü B =ðåííàÿ ìàòðèöàÐåøåíèå óïðàæíåíèé−1 0.
Òîãäà ìàòðèöà ñèñòåìû (5.3) è åå ðàñøè0 1−1 0 −1 | 0 0 1 −1 | 01 10 |1èìåþò ðàíãè 2 è 3 ñîîòâåòñòâåííî. Ñëåäîâàòåëüíî, ïî òåîðåìå ÊðîíåêåðàÊàïåëëè ñèñòåìà (5.3) íå èìååò ðåøåíèÿ.5.8. Ïðîäåëàåì 8 øàãîâ ïî àëãîðèòìó Áðàóíà.Ïðîäîëæåíèå òàáëèöû 5.1.k1112131415161718ik33322222c1 ()1010101010101010c2 ()811141720232629c3 ()171411852-1-4v1 ()17/117/614/1317/144/323/1626/1729/18jk23333333d1 ()1312111315171921d2 ()1114171717171717d3 ()96369121518v2 ()9/111/23/133/73/53/415/1717/18Îòñþäà v1∗ (18) = 1, v2∗ (18) = 17/18 ⇒ ε = 1/18. Äàëåå,t1 = 8, t2 = 18, p(18) = (1/9, 11/18, 5/18), q(8) = (1/8, 5/8, 1/4).6.1.
Ïóñòü Dα = [aα , bα ], α ∈ L − ñåìåéñòâî îòðåçêîâ, ëþáûå äâàèç êîòîðûõ èìåþò íåïóñòîå ïåðåñå÷åíèå. Äîêàæåì, ÷òî íàéäåòñÿ òî÷êàx0 ∈ Dα ∀ α ∈ L. Çàìåòèì, ÷òî èç óñëîâèÿ òåîðåìû aα ≤ bβ ∀ α, β ∈ L.defdefÑëåäîâàòåëüíî, a = sup aα ≤ b = inf bβ . Ëþáàÿ òî÷êà x0 ∈ [a, b] ÿâëÿåòñÿβ∈Lα∈Lèñêîìîé.6.2. Ïîëîæèì y 1 = (0, 0), y 2 = (0, 1), y 3 = (1, 0), y 4 = (1, 1). Ïî àíàëîãèè ñ ïðèìåðîì 6.1 ïîêàæåì, ÷òî4P(x0 , ψ 0 , v) = ((1/2, 1/2),Iyj /4, 1/2) − ðåøåíèå â ñìåøàííûõ ñòðàòåãèj=1ÿõ. Ïðîâåðèì óñëîâèå (∗). ÔóíêöèÿF (x, ψ 0 ) =4X1j=14[1 − (x1 − y1j )2 − (x2 − y2j )2 ]242 22.Ðåøåíèå óïðàæíåíèéñòðîãî âîãíóòà ïî x = (x1 , x2 ).
ÈìååìFx0 1=−4X(x1 −y1j )= 0,Fx0 2=−j=14X(x2 − y2j ) = 0.j=1Îòñþäà ñëåäóåò, ÷òî max F (x, ψ 0 ) äîñòèãàåòñÿ â òî÷êå x0 = (1/2, 1/2) èx∈Xðàâåí 1/2. Äàëåå,min F (x0 , y) = F (x0 , y 1 ) = 1/2 = max F (x, ψ 0 )y∈Yx∈Xè óñëîâèå (∗) âûïîëíåíî.6.3. Äëÿ íîðìàëüíîãî ðàñïðåäåëåíèÿF (x, c) = σ 2 c21 /n + (c1 − 1)2 x2 + 2c2 (c1 − 1)x + c22 .Ñòðàòåãèÿ ñòàòèñòèêà y 0 (z) = c01 z +c02 áóäåò âûðàâíèâàþùåé, åñëè c01 = 1.Ïðè ýòîì çíà÷åíèå ôóíêöèè ðèñêà áóäåò ìèíèìàëüíûì, åñëè c02 = 0.Åñëè c1 6= 1, òî sup F (x, c) = +∞.
Ñëåäîâàòåëüíî, íàéäåííàÿ ðåøàþùàÿx≥0ôóíêöèÿ y (z) = z − ìèíèìàêñíàÿ ñòðàòåãèÿ ñòàòèñòèêà.7.1. Çàìåòèì, ÷òî sup F (x, d0 ) = sup p1 (x) = 1 è ñòðàòåãèÿ y = d000≤x≤d00≤x≤d0íå ìîæåò áûòü ìèíèìàêñíîé. Ïóñòü 0 ≤ y < d0 . Òîãäàsup F (x, y) =0≤x≤d0= max[ sup (1 − p2 (y))p1 (x), sup p1 (x)] = max[1 − p2 (y), p1 (y)].0≤x≤yy<x≤d0Ôóíêöèÿ 1 − p2 (y) âîçðàñòàåò, à ôóíêöèÿ p1 (y) óáûâàåò ïî y. Ñëåäîâàòåëüíî, ôóíêöèÿ max[1−p2 (y), p1 (y)] äîñòèãàåò ìèíèìóìà â òî÷êå y = d∗ .Èòàê, v = p1 (d∗ ).8.1. Ïîëîæèìw = max minmax···minx1 ∈U1 y1 ∈V1 x2 ∈U2 (x1 ,y1 ) y2 ∈V2 (x1 ,y1 )maxminxT ∈UT (αT ) yT ∈VT (βT )F (xT , y T ).Îïðåäåëèì ñòðàòåãèþ x̃0 = (x̃0t , t = 1, ..., T ) ïåðâîãî èãðîêà: ïðè ëþáûõt = 1, ..., T è αt = (xt−1 , y t−1 )x̃0t (αt ) ∈ Arg maxmin · · ·xt ∈Ut (αt ) yt ∈Vt (βt )maxminxT ∈UT (αT ) yT ∈VT (βT )243F (xT , y T ). 22.Ðåøåíèå óïðàæíåíèéÒîãäà äëÿ ëþáîé ñòðàòåãèè ỹ âòîðîãî èãðîêàF (x̃0 , ỹ) ≥=maxminxT ∈UT (αT ) ỹT ∈VT (βT )mindef x̃ 0yT ∈VT (βT )TF (x̃0 , y T −1 , yT ) =F (x̃01 , ..., x̃0T −1 , xT , ỹ1 , ..., ỹT −1 , yT ) ≥ · · · ≥ w.Ñëåäîâàòåëüíî,min F (x̃0 , ỹ) ≥ w.ỹ∈ỸÑ äðóãîé ñòîðîíû äëÿ ñòðàòåãèè ỹ ∗ = (ỹt∗ , t = 1, ..., T ) âòîðîãî èãðîêà,îïðåäåëÿåìîé óñëîâèÿìè: ïðè ëþáûõ t = 1, ..., T èβt = (xt−1 , y t−1 ) ỹt∗ (βt ) ∈∈ Arg minmaxyt ∈Vt (βt ) xt+1 ∈Ut+1 (αt+1 )···minyT ∈VT (βT )F (x̃01 , ..., x̃0t , xt+1 , ..xT , y T ),âûïîëíåíî ðàâåíñòâî F (x̃0 , ỹ ∗ ) = w.
Îòñþäà w = v.Ôîðìóëà äëÿ v âûâîäèòñÿ àíàëîãè÷íî.8.2. ÏîëîæèìF11 (α, β) = max min aij , F12 (α, β) = min max aij , α, β = 1, 2.i∈Mα j∈Nβj∈Nβ i∈MαÏðè ýòîì(F11 (α, β))2×2è=3 05 22, (F1 (α, β))2×2 =2 32 3v = max min F11 (α, β)) = 2, v = min max F12 (α, β)) = 3.α=1,2 β=1,2β=1,2 α=1,29.1. Îïðåäåëåíèå ñåäëîâîé òî÷êè (x0 , y 0 ) ôóíêöèè F (x, y) íà X × Yìîæíî çàïèñàòü ñëåäóþùèì îáðàçîì:F (x0 , y 0 ) = max F (x, y 0 ), −F (x0 , y 0 ) = max(−F (x0 , y)),x∈Xy∈Y÷òî ñîâïàäàåò ñ îïðåäåëåíèåì ñèòóàöèè ðàâíîâåñèÿ.9.2.
Ïóñòü â èãðå âîçíèêëà ñèòóàöèÿ (1,1). Òîãäà âûãîäíî îòêëîíèòüñÿïåðâîìó èãðîêó è âîçíèêíåò ñèòóàöèÿ (2,1). Òåïåðü âûãîäíî îòêëîíèòüñÿâòîðîìó èãðîêó, âîçíèêíåò ñèòóàöèÿ (2,1) è ò.ä. ïî ñõåìå (1, 1) → (2, 1) →(2, 2) → (1, 2) → (1, 1).244 22.Ðåøåíèå óïðàæíåíèé9.3. Åñëè èãðîêè îäíîâðåìåííî ïðèìåíÿþò ïðàâèëî ïðàâîé ðóêè (ëåâîé ðóêè), òî ïåðâûé (âòîðîé) èãðîê ïðîåäåò è "ïîëó÷èò"1, à âòîðîé(ïåðâûé) åãî ïðîïóñòèò è ïîëó÷èò 0.
Åñëè ïåðâûé ïðèìåíÿåò ïðàâèëîïðàâîé ðóêè, à âòîðîé − ëåâîé, òî ïðîèçîéäåò ñòîëêíîâåíèÿ è îáà ïðîèãðàþò ïî 10. Åñëè − íàîáîðîò, òî îáà áóäóò ñòîÿòü è ïðîèãðàþò ïî1.9.4.  èãðå Γ äâà ðàâíîâåñèÿ ïî Íýøó: (1,1) è (2,2).9.5.  èãðå Γ åäèíñòâåííîå ðàâíîâåñèå ïî Íýøó: (1,1).9.6. Ïóñòü (x0 , y 0 ) − ïðîèçâîëüíàÿ ñèòóàöèÿ â àíòàãîíèñòè÷åñêîé èãðå. Ïðåäïîëîæèì, ÷òî ñèòóàöèÿ (x0 , y 0 ) íå ÿâëÿåòñÿ îïòèìàëüíîé ïî Ïàðåòî. Òîãäà íàéäåòñÿ ñèòóàöèÿ (x0 , y 0 ), äëÿ êîòîðîé âûïîëíåíû íåðàâåíñòâà F (x0 , y 0 ) ≥ F (x0 , y 0 ), −F (x0 , y 0 ) ≥ −F (x0 , y 0 ) è ïðè ýòîì õîòÿ áûîäíî èç íèõ âûïîëíåíî êàê ñòðîãîå.
Ñêëàäûâàÿ ýòè íåðàâåíñòâà, ïîëó÷èì 0 > 0 (ïðîòèâîðå÷èå).9.7. Ïóñòü ôóíêöèÿ f : [0, 1] → [0, 1] íåïðåðûâíà. Òîãäà äëÿ ôóíêöèèg(x) = f (x)−x g(0) ≥ 0 è g(1) ≤ 0. Ïî òåîðåìå ìàòåìàòè÷åñêîãî àíàëèçàî ïðîìåæóòî÷íûõ çíà÷åíèÿõ íàéäåòñÿ òî÷êà x0 , äëÿ êîòîðîé g(x0 ) = 0.9.8. 1) f (x) = x + 1, x ∈ [0, +∞);2) f (x) = x/2,( x ∈ (0, 1];x + 1/2, x ∈ [0, 1/2),3) f (x) =x − 1/2, x ∈ [1/2, 1].0 010.1.
Ïóñòü (p , q ) − ñèòóàöèÿ ðàâíîâåñèÿ è ñòðàòåãèÿ q 0 ïðè íåêîòîðîì v1 óäîâëåòâîðÿåò ñèñòåìå (ñì. (10.1))2q10 + q30 = q10 + 2q20 = q20 + 2q30 = v1 , q10 + q20 + q30 = 1.Îòñþäà q 0 = (1/3, 1/3, 1/3).Ïðåäïîëîæèì, ÷òî q 0 óäîâëåòâîðÿåò ñèñòåìå2q10 + q30 < q10 + 2q20 = q20 + 2q30 = v1 , q10 + q20 + q30 = 1.Òîãäà q30 = 1/3, à q20 > 1/3. Ïî ñâîéñòâó äîïîëíÿþùåé íåæåñòêîñòèp01 = 0, p02 + 2p03 = p03 = v2 . Îòñþäà p01 = p02 = p03 = 0 (ïðîòèâîðå÷èå).Íàêîíåö, ðàçáåðåì ñëó÷àé, êîãäà2q10 + q30 , q10 + 2q20 < q20 + 2q30 = v1 , q10 + q20 + q30 = 1.Òîãäà q30 > 1/3, à ïî ñâîéñòâó äîïîëíÿþùåé íåæåñòêîñòè p01 = p02 = 0 ⇒p03 = 1.
Èç ñèñòåìû (10.2) ñëåäóåò, ÷òî v2 = B(p0 , 3) ≥ B(p0 , 2) èëè 1 ≥ 2(ïðîòèâîðå÷èå).245 22.Ðåøåíèå óïðàæíåíèéÄðóãèå ñëó÷àè ðåàëèçàöèè ñèñòåìû (10.1) ïîëó÷àþòñÿ èç ðàçîáðàííûõ ïåðåñòàíîâêîé êîîðäèíàò, ïîñêîëüêó ìàòðèöû A è B − öèêëè÷åñêèå.Àíàëîãè÷íî äîêàçûâàåòñÿ, ÷òî p0 = (1/3, 1/3, 1/3).10.2. Äîêàçàòåëüñòâî òåîðåìû 10.4. 1) Ïóñòü ìíîæåñòâàZ = Zk ⊂ Zk−1 ⊂ · · · ⊂ Z1 = Z, Zl = Xl × Yl , l = 1, ..., k,îòâå÷àþò îïðåäåëåíèþ ñòðîãîãî äîìèíèðîâàíèÿ Z Z.Âîçüìåì i ∈ X1 \X2 .
Òîãäà íàéäåòñÿ òàêàÿ ñòðàòåãèÿ p ∈ P, ÷òîp i íà Y1 = Y. Îòñþäà A(p, j) > aij , j = 1, ..., n. Óìíîæàÿ j -å íåðàâåíñòâî íà qj0 è ñêëàäûâàÿ âñå íåðàâåíñòâà, ïîëó÷èì A(p, q 0 ) > A(i, q 0 ).Åñëè p0i > 0, òî èç ñèñòåìû (10.1) âûòåêàþò íåðàâåíñòâà A(i, q 0 ) = v1 ≥A(i1 , q 0 ), i1 = 1, ..., m. Óìíîæàÿ ýòè íåðàâåíñòâà íà âåëè÷èíû pi1 è ñêëàäûâàÿ èõ, ïîëó÷èì A(i, q 0 ) ≥ A(p, q 0 ) (ïðîòèâîðå÷èå). Îòñþäà p0i = 0 ∀ i ∈X1 \X2 . Àíàëîãè÷íî äîêàçûâàåòñÿ, ÷òî qj0 = 0 ∀ j ∈ Y1 \Y2 .Ïóñòü âåêòîðû p2 è q 2 ïîëó÷åíû èç p0 è q 0 îòáðàñûâàíèåì íóëåâûõ êîìïîíåíò ñ íîìåðàìè èç ìíîæåñòâ X1 \X2 è Y1 \Y2 ñîîòâåòñòâåííî.Íåòðóäíî ïîêàçàòü, ÷òî (p2 , q 2 ) − ñèòóàöèÿ ðàâíîâåñèÿ â ðåäóöèðîâàííîéèãðå ñ ìàòðèöàìè A2 è B 2 , ïîëó÷åííûìè èç ìàòðèö A è B âû÷åðêèâàíèåì ñòðîê ñ íîìåðàìè èç X1 \X2 è ñòîëáöîâ ñ íîìåðàìè èç Y1 \Y2 .
Ïîýòîìóðàññóæäåíèÿ ìîæíî ïîâòîðèòü äëÿ ðåäóöèðîâàííîé èãðû è ïîëó÷èòü,÷òî 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
