[учебник] Введение в теорию игр (с приложениями к экономике). Васин, Морозов (2003) (1186146), страница 42
Текст из файла (страница 42)
Ïîñëåâû÷åðêèâàíèÿ ñëàáî äîìèíèðóåìûõ ñòðîê, çàìå÷àåì, ÷òî ñòîëáåö 2 ðàâåíïîëóñóììå ñòîëáöîâ 1 è 3 è ïîýòîìó åãî ìîæíî âû÷åðêíóòü.  ðåçóëüòàòå(2, 0) (0, 2)(3, 0)13ïîëó÷àåòñÿ ìàòðèöà B =. Îòñþäà íàõîäèì ðåøå(0, 3)31íèå èñõîäíîé èãðû: p0 = (1/2, 0, 0, 1/2), q 0 = (1/2, 0, 1/2), v = 2. Îòìåòèì,÷òî ÷èñòàÿ ñòðàòåãèÿ 2 âòîðîãî èãðîêà òàêæå îïòèìàëüíà.5.3. Çäåñü l1 (p1 ) = 3p1 , l2 (p1 ) ≡ 1 è l3 (p1 ) = 3(1 − p1 ).
Ôóíêöèÿmin lj (p1 ) äîñòèãàåò ìàêñèìóìà â òî÷êàõ îòðåçêà [1/3,2/3]. Ïîýòîìó ìíî1≤j≤3æåñòâî âñåõ îïòèìàëüíûõ ñìåøàííûõ ñòðàòåãèé ïåðâîãî èãðîêà èìååòâèä P 0 = {p0 ∈ P | 1/3 ≤ p01 ≤ 2/3}. Âòîðîé èãðîê èìååò åäèíñòâåííóþîïòèìàëüíóþ ÷èñòóþ ñòðàòåãèþ 2.240 22.Ðåøåíèå óïðàæíåíèé5.4. Ïðåäïîëîæèì, ÷òî òî÷êà z 0 íå ÿâëÿåòñÿ êðàéíåé òî÷êîé ìíîæåñòâà Z è ïðåäñòàâèìà â âèäå z 0 = λz 0 + (1 − λ)z 00 , z 0 6= z 00 ∈ Z, 0 < λ < 1.Ïîñêîëüêó ôóíêöèÿ |z|2 ñòðîãî âûïóêëà íà ìíîæåñòâå Z (ñì. óïðàæíåíèå 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 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
