[учебник] Введение в теорию игр (с приложениями к экономике). Васин, Морозов (2003) (1186146), страница 10
Текст из файла (страница 10)
Ìåòîäû ðåøåíèÿ ìàòðè÷íûõ èãðÈç (5.15) è (5.16) ïîëó÷àåì11∆(k) ≤ 4ak1 + ε(t − h)k1 ≤ (4a + εt)k1 .22Ñëó÷àé 2.  êàæäîì îòðåçêå [(θ + h − 1)k1 , (θ + h)k1 ], h = 1, ..., t,íåêîòîðàÿ ñòðîêà èëè ñòîëáåö íåñóùåñòâåííû. Ñëåäîâàòåëüíî, êàê è ïðèâûâîäå (5.15),11∆(k) ≤ ∆(θk1 ) + εtk1 ≤ (2aθ + εt)k1 .22 îáîèõ ñëó÷àÿõ, èñïîëüçóÿ íåðàâåíñòâî tk1 ≤ k, ïîëó÷èì∆(k) ≤ (4a + 12 εt)k1 ≤ 4ak1 + 12 εk ≤ εk ïðè k ≥ 8ak1 /ε.Èç ëåììû 5.2 âûòåêàåò íåðàâåíñòâî (5.9) è ñõîäèìîñòü ïîñëåäîâàòåëüíîñòåé v1 (k), v2 (k), k = 0, 1, ..., ê çíà÷åíèþ èãðû v.Âåðíåìñÿ ê ìåòîäó Áðàóíà. Ñôîðìóëèðóåì ïðàâèëî îñòàíîâêè.
Ïóñòüçàäàíî ÷èñëî ε > 0. Áóäåì îñòàíàâëèâàòüñÿ íà øàãå k0 , êîãäà âïåðâûåâûïîëíåíî íåðàâåíñòâîv1 (k0 ) − v2 (k0 ) ≤ ε.(5.17)Èç (5.7) è (5.17) ñëåäóåò, ÷òî âåëè÷èíû v1 (k0 ), v2 (k0 ) ïðèáëèæàþò çíà÷åíèå v ìàòðè÷íîé èãðû ñ òî÷íîñòüþ äî ε. Ïîêàæåì, ÷òî p(k0 ) − εìàêñèìèííàÿ ñòðàòåãèÿ ïåðâîãî èãðîêà. Äåéñòâèòåëüíî,min A(p(k0 ), j) = v2 (k0 ) ≥ v − ε.1≤j≤nÀíàëîãè÷íî, q(k0 ) −ε-ìèíèìàêñíàÿ ñòðàòåãèÿ âòîðîãî èãðîêà.Òåîðåìà 5.3.  ìåòîäå Áðàóíà lim v1 (k) = lim v2 (k) = v, à ëþáûåk→∞k→∞ïðåäåëüíûå òî÷êè p0 , q 0 ïîñëåäîâàòåëüíîñòåé {p(k)}, {q(k)} ÿâëÿþòñÿ îïòèìàëüíûìè ñìåøàííûìè ñòðàòåãèÿìè èãðîêîâ.Äîêàçàòåëüñòâî. Ñõîäèìîñòü ïîñëåäîâàòåëüíîñòåé {v1 (k)} è {v2 (k)}ê çíà÷åíèþ èãðû v âûòåêàåò èç ëåììû 5.2.
Ïóñòü p0 − ëþáàÿ ïðåäåëüíàÿ òî÷êà ïîñëåäîâàòåëüíîñòè {p(k)}. Ïîêàæåì, ÷òî p0 − îïòèìàëüíàÿñìåøàííàÿ ñòðàòåãèÿ ïåðâîãî èãðîêà. Äåéñòâèòåëüíî, ïîñêîëüêó ïîñëåäîâàòåëüíîñòü {p(k)} ïðèíàäëåæèò êîìïàêòó P, áåç ïîòåðè îáùíîñòè(âûäåëÿÿ ñîîòâåòñòâóþùóþ ïîäïîñëåäîâàòåëüíîñòü) ìîæíî ñ÷èòàòü, ÷òîîíà ñõîäèòñÿ ê p0 . Òîãäàmin A(p(k), j) ≥ v − εk , k = 1, 2, ...,1≤j≤m55ÃËÀÂÀ I.
ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛãäå εk → 0 + . Ïåðåõîäÿ â ýòèõ íåðàâåíñòâàõ ê ïðåäåëó ïðè k → ∞, ïîëó÷èì íåðàâåíñòâî min A(p0 , j) ≥ v, ÷òî îçíà÷àåò îïòèìàëüíîñòü ñòðà1≤j≤mòåãèè p0 . Àíàëîãè÷íî äîêàçûâàåòñÿ îïòèìàëüíîñòü äëÿ âòîðîãî èãðîêàëþáîé ïðåäåëüíîé òî÷êè q 0 ïîñëåäîâàòåëüíîñòè {q(k)}.Îöåíèì ñêîðîñòü ñõîäèìîñòè ïîñëåäîâàòåëüíîñòåé {v1 (k)} è {v2 (k)}ê çíà÷åíèþ èãðû v.Ïóñòü Al , l ≥ 0 − ïîäìàòðèöà, ïîëó÷åííàÿ èç ìàòðèöû A âû÷åðêèâàíèåì êàêèõ-ëèáî l ñòðîê èëè ñòîëáöîâ, à {v1l (k)}, {v2l (k)} − ïîñëåäîâàòåëüíîñòè îáîáùåííîãî èòåðàöèîííîãî ïðîöåññà, ñîîòâåòñòâóþùåãî ïîäìàòðèöå Al . Îáîçíà÷èì ÷åðåç kl ÷èñëî ïîâòîðåíèé èãðû, ïðè êîòîðîì äëÿëþáîé ïîäìàòðèöû Al è ëþáûõ íà÷àëüíûõ âåêòîðîâ cl (0), dl (0) âûïîëíåíî íåðàâåíñòâî v1l (k) − v2l (k) ≤ 2−l ε ∀k ≥ kl . Ïðîñìàòðèâàÿ äîêàçàòåëüñòâî ëåììû 5.2, çàìå÷àåì, ÷òî km+n−1 = 1 è k0 ≥ 8ak1 ε−1 .
Àíàëîãè÷íûìíåðàâåíñòâîì ñâÿçàíû kl è kl+1 : kl ≥ 2l 8akl+1 ε−1 , l = 0, 1, ..., m + n − 2.Îòñþäà!!8ak0 ≥ k1 ≥ε≥8aε28aε2k2 ≥8aε!m+n−11+2+...+m+n−2238aεkm+n−1 =2 · 22 k3 ≥ ...!m+n−12(m+n−2)(m+n−1)2.Òàêèì îáðàçîì, ïðè ëþáîì k ≥ k0 âûïîëíåíû íåðàâåíñòâàdefv1 (k) − v2 (k) ≤ ε = 2m+n−2218ak1! m+n−1.Èòàê, ïîëó÷åííàÿ îöåíêà ñêîðîñòè ñõîäèìîñòü ïðîöåññà Áðàóíà ìàëîýôôåêòèâíà ïðè áîëüøèõ ðàçìåðàõ ìàòðèöû A. Ïðàêòè÷åñêè íàáëþäàåìàÿñêîðîñòü ñõîäèìîñòè ñóùåñòâåííî âûøå. çàêëþ÷åíèå ðàññìîòðèì ìîäèôèêàöèþ ïðàâèëà îñòàíîâêè ïî ìåòîäó Áðàóíà.
Ïîëîæèìv1∗ (k) = min v1 (t), v2∗ (k) = max v2 (t), k = 1, 2, ...1≤t≤k1≤t≤kÈç íåðàâåíñòâ (5.7) ñëåäóåò, ÷òîv2∗ (k) ≤ v ≤ v1∗ (k), k = 1, 2, ....56(5.18) 5. Ìåòîäû ðåøåíèÿ ìàòðè÷íûõ èãðÒàêèì îáðàçîì, v2∗ (k), v1∗ (k) − íàèëó÷øèå îöåíêè ñíèçó è ñâåðõó äëÿçíà÷åíèÿ èãðû v çà k åå ïîâòîðåíèé. Ïðè çàäàííîì ε > 0 áóäåì îñòàíàâëèâàòü ïðîöåññ íà øàãå k0 , êîãäà âïåðâûå âûïîëíåíî íåðàâåíñòâîv1∗ (k0 ) − v2∗ (k0 ) ≤ ε. Ïðè ýòîì âåëè÷èíû v1∗ (k0 ), v2∗ (k0 ) ïðèáëèæàþò çíà÷åíèå èãðû v ñ òî÷íîñòüþ äî ε.
Ïóñòü v1∗ (k0 ) = v1 (t1 ), v2∗ (k0 ) = v2 (t2 ).Ïîêàæåì, ÷òî p(t2 ) − ε-ìàêñèìèííàÿ ñòðàòåãèÿ ïåðâîãî èãðîêà. Äåéñòâèòåëüíî, èñïîëüçóÿ íåðàâåíñòâî (5.18) ïðè k = k0 , ïîëó÷èìmin A(p(t2 ), j) = v2 (t2 ) = v2∗ (k0 ) ≥ v − ε.1≤j≤nÀíàëîãè÷íî, q(t1 ) − ε-ìèíèìàêñíàÿ ñòðàòåãèÿ âòîðîãî èãðîêà.Ïðèìåð 5.5. Ïóñòü ε = 1/5, à ìàòðèöà èãðû −2 1 0A = 2 0 3 .−1 3 −3Îòìåòèì, ÷òî ðåøåíèå èãðû â ñìåøàííûõ ñòðàòåãèÿõ èìååò âèäp0 = q 0 = (0, 2/3, 1/3), v = 1.Ïðèìåíÿÿ ìåòîä Áðàóíà, íàéäåì ïðèáëèæåííîå çíà÷åíèå èãðû, à òàêæåε-ìàêñèìèííóþ è ε-ìèíèìàêñíóþ ñìåøàííûå ñòðàòåãèè èãðîêîâ.
Âû÷èñëåíèÿ óäîáíî ïðîèçâîäèòü â ôîðìå òàáëèöû.  êàæäîé åå k -îé ñòðîêåïîä÷åðêíóòû íàèáîëüøèå çíà÷åíèÿ âåëè÷èí ci (k), i = 1, 2, 3 è íàèìåíüøèå çíà÷åíèÿ âåëè÷èí dj (k), j = 1, 2, 3.Òàáë. 5.1k12345678910ik1122222233c1 (·)2223456789c2 (·)2588888888c3 (·)-1-4-7-4-12581114v1 (·)25/28/328/54/38/7111/97/557jk1332222222d1 (·)2468101214161514d2 (·)1222222258d3 (·)003691215181512v2 (·)002/31/22/51/32/71/45/94/5ÃËÀÂÀ I.
ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛv1∗ (10) = 1, v2∗ (10) = 4/5, t1 = 8, t2 = 10,p(10) = (1/5, 3/5, 1/5), q(8) = (1/8, 5/8, 1/4).Óïðàæíåíèå 5.8. Ïðîâåðèòü 1/5-îïòèìàëüíîñòü ïîëó÷åííûõ ñòðàòåãèé. Ñäåëàòü åùå 8 øàãîâ ïî àëãîðèòìó è óëó÷øèòü òî÷íîñòü äî ε = 1/18. 6.Èãðû ñ âîãíóòîé ôóíêöèåé âûèãðûøàÎïðåäåëåíèå. Àíòàãîíèñòè÷åñêàÿ èãðà Γ = X, Y, F (x, y) íàçûâàåòñÿèãðîé ñ âîãíóòîé ôóíêöèåé âûèãðûøà, åñëè X ⊂ E m , Y ⊂ E n − âûïóêëûå êîìïàêòû åâêëèäîâûõ ïðîñòðàíñòâ, ôóíêöèÿ F (x, y) íåïðåðûâíà íàX × Y è ïðè ëþáîì y ∈ Y îíà âîãíóòà ïî x.Èãðà Γ íàçûâàåòñÿ èãðîé ñ âûïóêëîé ôóíêöèåé âûèãðûøà, åñëè (âìåñòî òðåáîâàíèÿ âîãíóòîñòè) ïðè ëþáîì x ∈ X ôóíêöèÿ F (x, y) âûïóêëàïî y.Òåîðåìà 6.1 (Õåëëè).
 åâêëèäîâîì ïðîñòðàíñòâå E m èìååòñÿ ñå-ìåéñòâî Dα , α ∈ {α} âûïóêëûõ êîìïàêòîâ, îáëàäàþùåå ñëåäóþùèìm+1TDαj 6= ∅. Òîãäàñâîéñòâîì: äëÿ ëþáûõ α1 , ..., αm+1j=1TDα 6= ∅.α∈{α}Äîêàçàòåëüñòâî òåîðåìû ñì. â Ïðèëîæåíèè Ï2.Óïðàæíåíèå 6.1. Äîêàæèòå òåîðåìó ïðè m = 1.Òåîðåìà 6.2.
Äëÿ èãðû Γ ñ âîãíóòîé ôóíêöèåé âûèãðûøà ñïðàâåä-ëèâî ðàâåíñòâîv = max min F (x, y) =x∈X y∈Yminjy ∈Yj=1,...,m+1maxminx∈X 1≤j≤m+1F (x, y j ).Äîêàçàòåëüñòâî. Îáîçíà÷èì ïîñëåäíþþ âåëè÷èíó ÷åðåç w. Äëÿ ëþáûõ y 1 , ..., y m+1 ∈ Y ñïðàâåäëèâî íåðàâåíñòâîmaxminx∈X 1≤j≤m+1F (x, y j ) ≥ max min F (x, y) = v.x∈X y∈YÑëåäîâàòåëüíî, w ≥ v. Äîêàæåì íåðàâåíñòâî w ≤ v. Ïî îïðåäåëåíèþ wäëÿ ëþáûõ y 1 , ..., y m+1 ∈ Ymaxminx∈X 1≤j≤m+1F (x, y j ) ≥ w ⇒58 6. Èãðû ñ âîãíóòîé ôóíêöèåé âûèãðûøà⇒ ∃ x ∈ X : F (x, y j ) ≥ w, j = 1, ..., m + 1.Ââåäåì ìíîæåñòâà Dy = {x ∈ X | F (x, y) ≥ w}, y ∈ Y, ïðåäñòàâëÿþùèåñîáîé âûïóêëûå êîìïàêòû â E m . Èç ïîñëåäíèõ íåðàâåíñòâ âûòåêàåò, ÷òîm+1TDyj 6= ∅ ïðè ëþáûõ y 1 , ..., y m+1 ∈ Y.
Ñëåäîâàòåëüíî, âûïîëíåíû óñëîj=1Tâèÿ òåîðåìû 6.1 èDy 6= ∅, ò.å.y∈Y∃x∈\Dy ⇒ F (x, y) ≥ w ∀ y ∈ Y ⇒ min F (x, y) ≥ w.y∈Yy∈YÎòñþäà v ≥ w ⇒ v = w.Ïîëîæèì Q = {q ∈ E m+1 |m+1Pqj = 1, qj ≥ 0, j = 1, ..., m + 1}.j=1Òåîðåìà 6.3. Èãðà Γ ñ âîãíóòîé ôóíêöèåé âûèãðûøà èìååò ðåøåíèåâ ñìåøàííûõ ñòðàòåãèÿõ âèäà (x0 , ψ 0 , v), ãäå x0 − ìàêñèìèííàÿ ñòðàòåãèÿïåðâîãî èãðîêà,ψ0 =m+1X0qj0 Iyj , q 0 = (q10 , ..., qm+1) ∈ Q,j=1(y j , j = 1, ..., m + 1) ∈ Argminjmaxy ∈Yj=1,...,m+1minx∈X 1≤j≤m+1F (x, y j ),à q 0 − ìèíèìàêñíàÿ ñòðàòåãèÿ â çàäà÷åmin max Φ(x, q),q∈Q x∈XΦ(x, q) =m+1XF (x, y j )qj .j=1Äîêàçàòåëüñòâî. Ïî òåîðåìå 6.2 è ïî âûáîðóy j , j = 1, ..., m + 1,v = w = maxminx∈X 1≤j≤m+1F (x, y j ).Ôóíêöèÿ Φ(x, q) íåïðåðûâíà, ëèíåéíà ïî q è âîãíóòà ïî x.
Ñëåäîâàòåëüíî, ïî òåîðåìå 2.3 îíà èìååò ñåäëîâóþ òî÷êó. Ïîýòîìóv = maxminx∈X 1≤j≤m+1F (x, y j ) = max min Φ(x, q) =x∈X q∈Q= min max Φ(x, q) = max Φ(x, q 0 ) =q∈Q x∈Xx∈X59ÃËÀÂÀ I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛ= maxx∈Xm+1XF (x, yj)qj0j=1ZF (x, y)dψ 0 (y) = max F (x, ψ 0 ).= maxx∈Xx∈XYÎòñþäà ñëåäóþò ðàâåíñòâàmax F (x, ψ 0 ) = v = min F (x0 , y)x∈Xy∈Yè ïî òåîðåìå 4.1 òðîéêà (x0 , ψ 0 , v) − ðåøåíèå èãðû â ñìåøàííûõ ñòðàòåãèÿõ.Çàìå÷àíèå.
 äîêàçàòåëüñòâàõ òåîðåì 5.2 è 5.3 âûïóêëîñòü ìíîæåñòâàY íå èñïîëüçîâàëàñü. Y ìîæíî áûëî ñ÷èòàòü êîìïàêòîì ìåòðè÷åñêîãîïðîñòðàíñòâà.Àíàëîãè÷íî äîêàçûâàåòñÿ ñëåäóþùåå óòâåðæäåíèå.n+1PÏîëîæèì P = {p ∈ E n+1 |pi = 1, pi ≥ 0, i = 1, ..., n + 1}.i=1Òåîðåìà 5.4. Èãðà Γ ñ âûïóêëîé ôóíêöèåé âûèãðûøà èìååò ðåøåíèåâ ñìåøàííûõ ñòðàòåãèÿõ âèäà (ϕ0 , y 0 , v), ãäå y 0 − ìèíèìàêñíàÿ ñòðàòåãèÿïåðâîãî èãðîêà,0ϕ =n+1Xp0i Ixi , p0 = (p0i , i = 1, ..., n + 1) ∈ P,i=1min max F (xi , y),(xi , i = 1, ..., n + 1) ∈ Arg maxix ∈Xi=1,...,n+1y∈Y 1≤i≤n+1à p0 − ìàêñèìèííàÿ ñòðàòåãèÿ â çàäà÷å1max min Φ (p, y),p∈P y∈Y1Φ (p, y) =n+1Xpi F (xi , y).i=1Ïðèìåð 6.1.
Ïóñòü X = Y = [0, 1], F (x, y) = 1 − (x − y)2 − èãðà ñâîãíóòîé ôóíêöèåé âûèãðûøà. Çäåñü31v = v = max min [1 − (x − y)2 ] = , x0 = , ψ 0 = q10 Iy1 + q20 Iy2 ,0≤x≤1 0≤y≤142q10 + q20 = 1, q10 , q20 ≥ 0,600 ≤ y 1 ≤ y 2 ≤ 1. 6. Èãðû ñ âîãíóòîé ôóíêöèåé âûèãðûøàÍàéäåì âåëè÷èíów=max min[F (x, y 1 ), F (x, y 2 )].min0≤y 1 ≤y 2 ≤1 0≤x≤1Ïðè ôèêñèðîâàííûõ y 1 , y 2max min[1 − (x − y 1 )2 , 1 − (x − y 2 )2 ] = 1 −0≤x≤1y1 − y22!2.Îòñþäàw=min120≤y ≤y ≤11−y1 − y22!23= ,4y 1 = 0, y 2 = 1.Íàéäåì òåïåðü q10 , q20 , ðåøàÿ çàäà÷ómin max Φ(x, q) = min max [(1 − x2 )q1 + (1 − (x − 1)2 )q2 ].0≤q1 ≤1 0≤x≤10≤q1 ≤1 0≤x≤1Èìååì Φ0x (x, q) = −2xq1 − 2(x − 1)q2 = 0.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
