А.А. Васин, В.В. Морозов - Введение в теорию игр с приложениями к экономике (1184512), страница 50
Текст из файла (страница 50)
Ïóñò� x0 − òî÷êà, � êîòîðî� ôóíêöè� ϕ(x) èìåå� ñêà÷î� âåëè÷èí� δ > 0. Òîãä� � ñèë� å� ìîíîòîííîñò� ñïðàâåäëèâ� íåðàâåíñòâ� ϕ(b0 ) − ϕ(a0 ) ≥ δ > 0. Ïóñò� � òî÷ê� x0 ôóíêöè� ϕ(x) äèôôåðåíöèðóåì� � ϕ0 (x0 ) > 0. Òîãä� 0ϕ(b ) − ϕ(a0 ) > 0. Äåéñòâèòåëüíî, ôóíêöè� ϕ(x) í� óáûâàå� � ï� îïðåäåëåíè� ïðîèçâîäíî� íàéäåòñ� òàêà� òî÷ê� x� > x0 , áëèçêà� � x0 , ÷ò� ϕ(x0 ) > ϕ(x0 ).
4.8. Ïóñò� òðîéê� (p0 , q 0 , v) − ðåøåíè� � ñìåøàííû� ñòðàòåãèÿ� èãð� � ìàòðèöå� A. Äîêàæå� óòâåðæäåíè� 1). Ï� óñëîâè� (∗) A(i, q 0 ) ≤ v, i = 1, ..., m. 239 (22.2) 22. Ðåøåíè� óïðàæíåíè�Ïðåäïîëîæè� ïðîòèâíîå. Òîãä� íàéäåòñ� òàêà� ÷èñòà� ñòðàòåãè� i1 ïåðâîã� èãðîêà, ÷ò� p0 i1 > 0 � A(i1 , q 0 ) < v. Äîìíîæè� îá� ÷àñò� i-ã� íåðàâåíñòâ� (22.2) í� p0 i � ñëîæè� íåðàâåíñòâà. Ïîñêîëüê� íåðàâåíñòâ� � íîìåðî� i1 ïîñë� äîìíîæåíè� í� p0 i1 îñòàíåòñ� ñòðîãèì, ïîëó÷è� A(p0 , q 0 ) < v = A(p0 , q 0 ) (ïðîòèâîðå÷èå).
Óòâåðæäåíè� 2) äîêàçûâàåòñ� àíàëîãè÷íî. 5.1. Ïóñò� ñòðîê� i1 ìàòðèö� A ñëàá� äîìèíèðóå� ñòðîê� i2 . Åñë� ñòðàòåãè� i2 − ìàêñèìèííàÿ, ò� ñòðàòåãè� i1 òàêæ� ÿâëÿåòñ� ìàêñèìèííî� êà� äë� ìàòðèö� A, òà� � äë� ðåäóöèðîâàííî� ìàòðèö� � âû÷åðêíóòî� i2 -î� ñòðîêîé. Ïð� ýòî� íèæíå� çíà÷åíè� èãð� ïîñë� èñêëþ÷åíè� ñòðîê� í� ìåíÿåòñÿ. Àíàëîãè÷íî� çàìå÷àíè� ñïðàâåäëèâ� � äë� ñëó÷àÿ, êîãä� ñòîëáå� j1 ñëàá� äîìèíèðóåòñ� ñòîëáöî� j2 , � ñòðàòåãè� j2 ÿâëÿåòñ� ìèíèìàêñíîé. Ïîñë� èñêëþ÷åíè� ñëàá� äîìèíèðóåìû� ñòðî� � ñëàá� äîìèíèðóþùè� ñòîëáöî� � ðàñïîðÿæåíè� èãðîêî� îñòàþòñ� ìàêñèìèííà� � ìèíèìàêñíà� ñòðàòåãè� èãðîêî� èñõîäíî� ( � ðåäóöèðîâàííîé) èãðû, îáðàçóþùè� ñåäëîâó� òî÷êó. 5.2.
Âûïèøå� ìàòðèö� èãð� (2, 0) (1, 1) (0, 2)⎞(3, 0)1 2 3(2, 1)12 1A =(1, 2)⎝ 211 ⎠(0, 3)3 2 1 ⎛Ñòðîê� 2 ñëàá� äîìèíèðóåòñ� ñòðîêî� 1, � ñòðîê� 3 − ñòðîêî� 4. Ïîñë� âû÷åðêèâàíè� ñëàá� äîìèíèðóåìû� ñòðîê, çàìå÷àåì, ÷ò� ñòîëáå� 2 ðàâå� ïîëóñóìì� ñòîëáöî� 1 � 3 � ïîýòîì� åã� ìîæí� âû÷åðêíóòü.
� ðåçóëüòàò� (2, 0) (0, 2)(3, 0)1 3ïîëó÷àåòñ� ìàòðèö� B = . Îòñþä� íàõîäè� ðåøå(0, 3)3 1 íè� èñõîäíî� èãðû: 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 ≤ p0 1 ≤ 2/3}. Âòîðî� èãðî� èìåå� åäèíñòâåííó� îïòèìàëüíó� ÷èñòó� ñòðàòåãè� 2.
240 22. Ðåøåíè� óïðàæíåíè�5.4. Ïðåäïîëîæèì, ÷ò� òî÷ê� z 0 í� ÿâëÿåòñ� êðàéíå� òî÷êî� ìíîæåñòâ� Z � ïðåäñòàâèì� � âèä� z 0 = λz � + (1 − λ)z 00 , z � 6= z 0� ∈ Z, 0 < λ < 1. Ïîñêîëüê� ôóíêöè� |z|2 ñòðîã� âûïóêë� í� ìíîæåñòâ� Z (ñì. óïðàæíåíè� 2.4), |z 0 |2 = |λz � + (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 0 z∈Z − åã� êðàéíÿ� òî÷êà. Ïîêàæåì, ÷ò� z 0 − êðàéíÿ� òî÷ê� ìíîæåñòâ� Z. Ïóñòü, íàïðîòèâ, íàéäóòñ� òàêè� òî÷ê� z � 6= z 0� ìíîæåñòâ� Z � òàêî� ÷èñë� 0 < λ < 1, ÷ò� z 0 = λz � + (1 − λ)z 00 . Òîãä� ï� êðàéíå� ìåð� îäí� è� òî÷å� z � èë� z 0� í� ïðèíàäëåæà� ìíîæåñòâ� Z ∗ . Ïîýòîì� h(z 0 ) = λh(z 0 ) + (1 − λ)h(z 00 ) < max h(z) (ïðîòèâîðå÷è� � îïðåäåëåíèå� z 0 ). z∈Z 5.6. Ïóñò� îïòèìàëüíà� ñòðàòåãè� p0 ïåðâîã� èãðîê� óäîâëåòâîðÿå� ñèñòåì� óðàâíåíè� (5.3), ãä� v − çíà÷åíè� èãðû, � ìàòðèö� B = (ail jt )k×k − íåâûðîæäåííàÿ.
Ïîêàæåì, ÷ò� p0 − êðàéíÿ� îïòèìàëüíà� ñìåøàííà� ñòðàòåãèÿ. Ïðåäïîëîæè� ïðîòèâíîå, ò.å. p0 ïðåäñòàâèì� � âèä� p0 = λp� + (1 − λ)p00 , ãä� p� =6 p0� ∈ P 0 , 0 < λ < 1. È� ðàâåíñò� p 0 i = 0 = λp0i + (1 − λ)p00i ∀i =6 il , l = 1, ..., k, ñëåäóåò, ÷ò� p0i = p00i = 0 ∀i =6 il , l = 1, ..., k. Ïîñêîëüê� p0 , p0� − îïòèìàëüíû� ñìåøàííû� ñòðàòåãèè, 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 ⇒ p� = p0� (ïðîòèâîðå÷èå).241 22. 5.7.
Ïóñò� B = ðåííà� ìàòðèö� Ðåøåíè� óïðàæíåíè�−1 0 . Òîãä� ìàòðèö� ñèñòåì� (5.3) � å� ðàñøè0 1 ⎞ −1 0 −1 | 0 0 1 −1 | 0⎠ 1 1 0 | 1 èìåþ� ðàíã� 2 � 3 ñîîòâåòñòâåííî. Ñëåäîâàòåëüíî, ï� òåîðåì� ÊðîíåêåðàÊàïåëë� ñèñòåì� (5.3) í� èìåå� ðåøåíèÿ. 5.8. Ïðîäåëàå� 8 øàãî� ï� àëãîðèòì� Áðàóíà. Ïðîäîëæåíè� òàáëèö� 5.1.
k 11 12 13 14 15 16 17 18 ik 3 3 3 2 2 2 2 2 c1 () 10 10 10 10 10 10 10 10 c2 () 8 11 14 17 20 23 26 29 c3 () 17 14 11 8 5 2 -1 -4 v1 () jk 17/11 2 7/6 3 14/13 3 17/14 3 4/3 3 23/16 3 26/17 3 29/18 3 d1 () 13 12 11 13 15 17 19 21 d2 () 11 14 17 17 17 17 17 17 d3 () 9 6 3 6 9 12 15 18 v2 () 9/11 1/2 3/13 3/7 3/5 3/4 15/17 17/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. def def Ñëåäîâàòåëüíî, 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 ) = 4� 1 j=1 4[1 − (x1 − y1j )2 − (x2 − y2j )2 ]242 22. Ðåøåíè� óïðàæíåíè�ñòðîã� âîãíóò� ï� x = (x1 , x2 ). Èìåå� Fx0 1 = − 4X(x1 − y1j )= 0,Fx0 2 = − j=1 4X(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 c 21 /n + (c1 − 1)2 x 2 + 2c2 (c1 − 1)x + c2 2 .Ñòðàòåãè� ñòàòèñòèê� y 0 (z) = c01 z +c0 2 áóäå� âûðàâíèâàþùåé, åñë� c0 1 = 1. Ïð� ýòî� çíà÷åíè� ôóíêöè� ðèñê� áóäå� ìèíèìàëüíûì, åñë� c0 2 = 0. Åñë� c1 6= 1, ò� sup F (x, c) = +∞. Ñëåäîâàòåëüíî, íàéäåííà� ðåøàþùà� x≥0 ôóíêöè� y (z) = z − ìèíèìàêñíà� ñòðàòåãè� ñòàòèñòèêà. 7.1. Çàìåòèì, ÷ò� sup F (x, d0 ) = sup p1 (x) = 1 � ñòðàòåãè� y = d0 00≤x≤d0 0≤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≤y y<x≤d0 Ôóíêöè� 1 − p2 (y) âîçðàñòàåò, � ôóíêöè� p1 (y) óáûâàå� ï� y. Ñëåäîâàòåëüíî, ôóíêöè� max[1−p2 (y), p1 (y)] äîñòèãàå� ìèíèìóì� � òî÷ê� y = d∗ . Èòàê, v = p1 (d∗ ). 8.1. Ïîëîæè� w = max min max · · · min x1 ∈U1 y1 ∈V1 x2 ∈U2 (x1 ,y1 ) y2 ∈V2 (x1 ,y1 ) max min xT ∈UT (αT ) yT ∈VT (βT ) F (xT , y T ). Îïðåäåëè� ñòðàòåãè� x̃0 = (x̃0 t , t = 1, ..., T ) ïåðâîã� èãðîêà: ïð� ëþáû� t = 1, ..., T � αt = (xt−1 , y t−1 ) x̃0t (αt ) ∈ Arg max min · · · xt ∈Ut (αt ) yt ∈Vt (βt ) max min xT ∈UT (αT ) yT ∈VT (βT ) 243 F (xT , y T ). 22.
Ðåøåíè� óïðàæíåíè�Òîãä� äë� ëþáî� ñòðàòåãè� ỹ âòîðîã� èãðîê� F (˜x 0 , ỹ) ≥ = max min xT ∈UT (αT ) ỹT ∈VT (βT )min def x̃ 0 yT ∈VT (βT ) T F (˜x 0 , y T −1 , yT ) = F (x̃0 1 , ..., x̃0 T −1 , xT , ỹ1 , ..., y˜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 min max yt ∈Vt (βt ) xt+1 ∈Ut+1 (αt+1 ) · · · min yT ∈VT (βT ) F (x̃0 1 , ..., x̃0 t , 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 0 5 2 2, (F1 (α, β))2×2 = 2 3 2 3 v = max min F11 (α, β)) = 2, v = min max F12 (α, β)) = 3. α=1,2 β=1,2 β=1,2 α=1,2 9.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
