Введение в теорию игр (сторонняя методичка) (Введение в теорию игр (сторонняя методичка).PDF), страница 10

Ïðîñìàòðèâàÿ äîêàçàòåëüñòâî ëåììû 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.

Îòñþäà ñòðàòåãèÿ x = q2ìàêñèìèçèðóåò ôóíêöèþ Φ(x, q) ïî ïåðåìåííîé x. Ñëåäîâàòåëüíî,max Φ(x, q) = 1 − q1 (1 − q1 ) ⇒ q10 = q20 =0≤x≤1111⇒ ψ 0 = I0 + I1 .222Îòìåòèì, ÷òî ïîëó÷åííîå ðåøåíèå èãðû ìîæíî áûëî ïðåäóãàäàòü è ïðîâåðèòü ëèøü óñëîâèå (∗).Óïðàæíåíèå 6.2. Ðåøèòå èãðó ñ âîãíóòîé ôóíêöèåé âûèãðûøàX = {(x1 , x2 ) | 0 ≤ xi ≤ 1, i = 1, 2}, Y = X,F (x1 , x2 , y1 , y2 ) = 1 − (x1 − y1 )2 − (x2 − y2 )2 .Øèðîêèé êëàññ èãð ñ âûïóêëûìè ôóíêöèÿìè âûèãðûøà îáðàçóþòñòàòèñòè÷åñêèå èãðû.

Äàäèì íåîáõîäèìûå îïðåäåëåíèÿ.Ñòàòèñòèê íàáëþäàåò ðåàëèçàöèè zi íåçàâèñèìûõ, îäèíàêîâî ðàñïðåäåëåííûõ ñëó÷àéíûõ âåëè÷èí Zi , i = 1, ..., n, èìåþùèõ ïëîòíîñòü ðàñïðåäåëåíèÿ g(zi |x), çàâèñÿùóþ îò âåêòîðà íåèçâåñòíûõ ïàðàìåòðîâ x ∈ X.Çäåñü X − âûïóêëîå ìíîæåñòâî åâêëèäîâà ïðîñòðàíñòâà. Ïóñòü Z =61ÃËÀÂÀ I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛ(Z1 , ..., Zn ) − âåêòîðíàÿ ñëó÷àéíàÿ âåëè÷èíà, ïðèíèìàþùàÿ çíà÷åíèÿnQz = (z1 , ..., zn ) ∈ Z è èìåþùàÿ ïëîòíîñòü ðàñïðåäåëåíèÿ g(z|x) =g(zi |x).i=1Ñòàòèñòèê îöåíèâàåò âåêòîð x, èñïîëüçóÿ ðåøàþùóþ ôóíêöèþ y :Z → A = X. Âåëè÷èíà a = y(z) íàçûâàåòñÿ îöåíêîé âåêòîðà x èç ìíîæåñòâà îöåíîê A.

Îøèáêà â îïðåäåëåíèè âåêòîðà x çàäàåòñÿ ñ ïîìîùüþôóíêöèè ïîòåðü L(x, a). Ìàòåìàòè÷åñêîå îæèäàíèå ýòîé ôóíêöèèZdefF (x, y) = E[L(x, y(Z))] = L(x, y(z))g(z|x)dzZíàçûâàåòñÿ ôóíêöèåé ðèñêà.Ñòàòèñòèê (âòîðîé èãðîê) èñïîëüçóåò ðåøàþùåå ïðàâèëî (ñòðàòåãèþ)y èç íåêîòîðîãî ìíîæåñòâà Y è ñòðåìèòñÿ ìèíèìèçèðîâàòü ôóíêöèþðèñêà. Ïðèðîäà (ïåðâûé èãðîê) ñòðåìèòñÿ åå ìàêñèìèçèðîâàòü, âûáèðàÿx ∈ X. Ïîñòðîåííàÿ àíòàãîíèñòè÷åñêàÿ èãðàΓ = X, Y, F (x, y) íàçûâàåòñÿ ñòàòèñòè÷åñêîé.Ïóñòü îöåíèâàåìûé âåêòîð ÿâëÿåòñÿ ñëó÷àéíîé âåëè÷èíîé X, ïðèíèìàþùåé çíà÷åíèÿ x ∈ X è èìåþùåé ïëîòíîñòü ðàñïðåäåëåíèÿ f. Ñèãðîâîé òî÷êè çðåíèÿ ýòî îçíà÷àåò, ÷òî ïðèðîäà èñïîëüçóåò ñìåøàííûåñòðàòåãèè f ∈ {f }.Îáû÷íî èñïîëüçóåòñÿ ñëåäóþùèé ìåòîä ðåøåíèÿ ñòàòèñòè÷åñêîé èãðû. Ñíà÷àëà ñòðîèòñÿ óðàâíèâàþùàÿ ðèñê ðåøàþùàÿ ôóíêöèÿ ñòàòèñòèêà y 0 : F (x, y 0 ) ≡ const íà X.

Çàòåì ïîäáèðàåòñÿ ñòðàòåãèÿ ïðèðîäû − ïëîòíîñòü ðàñïðåäåëåíèÿ f 0 , îòíîñèòåëüíî êîòîðîé ðåøàþùàÿôóíêöèÿ y 0 ÿâëÿåòñÿ áàéåñîâñêîé, ò.å. ìèíèìèçèðóþùåé ôóíêöèþ ðèñêà:F (f 0 , y 0 ) = min F (f 0 , y). Òîãäà â ñîîòâåòñòâèè ñ ðåçóëüòàòîì óïðàæíåíèÿy∈Y4.3 f , y − îïòèìàëüíûå ñòðàòåãèè ïðèðîäû è ñòàòèñòèêà. Ïëîòíîñòüðàñïðåäåëåíèÿ f 0 íàçûâàåòñÿ àïðèîðíîé.Ïîêàæåì, ÷òî äëÿ ïëîòíîñòè ðàñïðåäåëåíèÿ f 0 ïðè êâàäðàòè÷íîéôóíêöèè ïîòåðü L(x, a) = |x − a|2 áàéåñîâñêàÿ ðåøàþùàÿ ôóíêöèÿ y 0îïðåäåëÿåòñÿ îäíîçíà÷íî. Îïðåäåëèì àïîñòåðèîðíóþ ïëîòíîñòü ðàñïðåäåëåíèÿ f 0 (x|z) = g(z|x)f 0 (x)/p(z), ãäåZp(z) = g(z|x)f 0 (x)dx.00XÓòâåðæäåíèå 6.1.

Ïóñòü y 0 − áàéåñîâñêàÿ ðåøàþùàÿ ôóíêöèÿ îòíîñèòåëüíî ïëîòíîñòè ðàñïðåäåëåíèÿ f 0 . Òîãäà ïðè êâàäðàòè÷íîé ôóíêöèè62Ÿ 6. Èãðû ñ âîãíóòîé ôóíêöèåé âûèãðûøàïîòåðüdef0y (z) = E[X|z] =Zxf 0 (x|z)dx ∀ z ∈ Z.(6.1)XÄîêàçàòåëüñòâî. Ïîñêîëüêó ìíîæåñòâî X âûïóêëî, ìîæíî ïîêàçàòü,÷òî y 0 (z) ∈ A = X ∀ z ∈ Z. Äëÿ ïðîèçâîëüíîé ðåøàþùåé ôóíêöèè y ∈ YZ Z0F (f , y) =L(x, y(z))g(z|x)dzf 0 (x)dx =X ZZ Z= [ |x − y(z)|2 f 0 (x|z)dx]p(z)dz.ZXÏðè ôèêñèðîâàííîì z ∈ Z âíóòðåííèé èíòåãðàë ÿâëÿåòñÿ êâàäðàòè÷íîéôóíêöèåé îò a = y(z).

Ïîýòîìó åãî ìèíèìóì äîñòèãàåòñÿ ïðè a0 = y 0 (z)èç (6.1). äàëüíåéøåì áóäåì ñ÷èòàòü, ÷òî ôóíêöèÿ ðàñïðåäåëåíèÿ g êàæäîéñëó÷àéíîé âåëè÷èíû Zi çàâèñèò òîëüêî îò îäíîãî íåèçâåñòíîãî ïàðàìåòðà − ìàòåìàòè÷åñêîãî îæèäàíèÿ x. Äèñïåðñèþ ñëó÷àéíîé âåëè÷èíû Ziîáîçíà÷èì ÷åðåç D(x). Äëÿ ìàòåìàòè÷åñêîãî îæèäàíèÿ ÷àñòî èñïîëüçónPåòñÿ íåñìåùåííàÿ îöåíêà z =zi /n. Ñâîéñòâî íåñìåùåííîñòè îçíà÷àåò,i=1÷òîEEZ =nPZii=1= x.nÏîýòîìó åñòåñòâåííî ðàññìîòðåòü ìíîæåñòâî ðåøàþùèõ ïðàâèë âèäàY = {y | y(z) = c1 z + c2 , c1 , c2 ≥ 0}.Ôóíêöèþ ïîòåðü áóäåì ïðåäïîëàãàòü êâàäðàòè÷íîé:L(x, a) = (x − a)2 .