[учебник] Введение в теорию игр (с приложениями к экономике). Васин, Морозов (2003) (1186146), страница 12
Текст из файла (страница 12)
Ïóñòü A è B − êîëè÷åñòâà ñðåäñòâ íàïàäåíèÿ è îáîðîíû. Ýòè ñðåäñòâà ïðåäïîëàãàþòñÿ áåñêîíå÷íî-äåëèìûìè.Ñòðàòåãèÿ ïåðâîãî èãðîêà (íàïàäåíèÿ) ñîñòîèò â ðàñïðåäåëåíèè ñâîèõñðåäñòâ ïî ïóíêòàì â ñîîòâåòñòâèè ñ âåêòîðîìx = (x1 , ..., xn ) ∈ X = {x |nXxi = A,xi ≥ 0, i = 1, ..., n}.i=1Âòîðîé èãðîê (îáîðîíà) èñïîëüçóåò àíàëîãè÷íóþ ñòðàòåãèþy = (y1 , ..., yn ) ∈ Y = {y |nXyi = B,yi ≥ 0, i = 1, ..., n}.i=1Ïóñòü µi − êîëè÷åñòâî ñðåäñòâ íàïàäåíèÿ, êîòîðîå ìîæåò óíè÷òîæèòüîäíà åäèíèöà ñðåäñòâ îáîðîíû íà i-îì ïóíêòå.
Åñëè xi > µi yi , òî ÷åðåçi-é ïóíêò ïðîðûâàåòñÿ xi − µi yi ñðåäñòâ íàïàäåíèÿ. Åñëè xi ≤ µi yi , òî ÷åðåç ýòîò ïóíêò íàïàäåíèå íå ïðîðâåòñÿ. Îáúåäèíÿÿ îáà ñëó÷àÿ, íàõîäèìôîðìóëó äëÿ êîëè÷åñòâà ñðåäñòâ íàïàäåíèÿ, ïðîðâàâøåãîñÿ ÷åðåç i-éïóíêò: max[xi − µi yi , 0]. Îïðåäåëèì ôóíêöèþ âûèãðûøà ïåðâîãî èãðîêàF (x, y) =nXmax[xi − µi yi , 0]i=1− îáùåå êîëè÷åñòâî ñðåäñòâ íàïàäåíèÿ, ïðîðâàâøååñÿ ÷åðåç âñå ïóíêòû.Çàìåòèì, ÷òî ôóíêöèÿ F (x, y) âûïóêëà ïî y . Ïî òåîðåìå 6.4 çíà÷åíèåèãðû v = v è ìèíèìàêñíàÿ ñòðàòåãèÿ y 0 îáîðîíû îïòèìàëüíà. Çàéìåìñÿèññëåäîâàíèåì ýòîé èãðû â ÷èñòûõ è ñìåøàííûõ ñòðàòåãèÿõ.
Áåç ïîòåðèîáùíîñòè ïðåäïîëîæèì, ÷òî êîýôôèöèåíòû ýôôåêòèâíîñòè îáîðîíû µióïîðÿäî÷åíû: µ1 ≥ µ2 ≥ ... ≥ µn è n-é ïóíêò îáîðîíû ÿâëÿåòñÿ ñëàáåéøèì.à) Ïîêàæåì, ÷òîv = max min F (x, y) = max[A − µn B, 0],x∈X y∈Yx(n) = (0, ..., 0, A)− ìàêñèìèííàÿ ñòðàòåãèÿ íàïàäåíèÿ, ñîñòîÿùàÿ â íàíåñåíèè "êîíöåíòðèðîâàííîãî"óäàðà ïî ñëàáåéøåìó ïóíêòó.68 7. Èññëåäîâàíèå èãðîâûõ ìîäåëåéÄëÿ ëþáîé ñòðàòåãèè íàïàäåíèÿ x îïðåäåëèì âñïîìîãàòåëüíóþ ñòðàòåãèþ îáîðîíû y :y i = Bxi µinXxk −1k=1µkÒîãäàmin F (x, y) ≤ F (x, y) =y∈YÅñëè B ≥nPk=1xk,µk, i = 1, ..., n.nXmax[xi − µi y i , 0].i=1òî y i ≥ xi /µi , i = 1, ..., n ⇒ F (x, y) = 0. ïðîòèâíîì ñëó÷àå y i ≤ xi /µi , i = 1, ..., n, èF (x, y) =nX(xi − µi y i ) ≤ A − µnnXi=1y i = A − µn B.i=1Òàêèì îáðàçîì, äëÿ ëþáîé ñòðàòåãèè xmin F (x, y) ≤ max[A − µn B, 0] = min max[A − µn yn , 0] = min F (x(n) , y)y∈Yy∈Yy∈Yè x(n) − ìàêñèìèííàÿ ñòðàòåãèÿ íàïàäåíèÿ.á) Ïîêàæåì, ÷òînX1 −1v = min max F (x, y) = max[A − B, 0],y∈Y x∈Xµkk=1à0y :yi0nX1 −1= B µi, i = 1, ..., n,µkk=1− ìèíèìàêñíàÿ ñòðàòåãèÿ îáîðîíû.Ñíà÷àëà äîêàæåì ðàâåíñòâîmax F (x, y) = max F (x(i) , y) ∀ y ∈ Y,x∈X1≤i≤n(7.1)ãäå x(i) = (0, ..., |{z}A , 0, ..., 0) − ñòðàòåãèÿ íàïàäåíèÿ, ñîñòîÿùàÿ â íàíåñåiíèè êîíöåíòðèðîâàííîãî óäàðà ïî i-ìó ïóíêòó.69ÃËÀÂÀ I.
ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛÏðåäñòàâèì ñòðàòåãèþ x â âèäå x =nPi=1ëîé ôóíêöèèF (x, y) ≤nXxii=1Axi (i)x .AÏî îïðåäåëåíèþ âûïóê-F (x(i) , y) ≤ max F (x(i) , y).1≤i≤nÑëåäîâàòåëüíî,max F (x, y) ≤ max F (x(i) , y) ≤ max F (x, y)1≤i≤nx∈Xx∈Xè (7.1) äîêàçàíî. Äàëåå èìååìv = min max F (x, y) = min max F (x(i) , y) =y∈Y 1≤i≤ny∈Y x∈X= min max max[A − µi yi , 0] = min max[A − min µi yi , 0] =y∈Y 1≤i≤n1≤i≤ny∈Y= max[A − B max min µi yi /B, 0] = [çàìåíà ïåðåìåííûõy∈Y 1≤i≤np = y/B ∈ P = {p = (p1 , ..., pn ) |nPpi = 1, pi ≥ 0, i = 1, ..., n}] =i=1= max[A − B max min µi pi , 0] =p∈P 1≤i≤nP−1n1=[ ñì. ïðèìåð 4.4] = max[A − B, 0].µkk=1Ïðè ýòîìyi0=Bp0inX1 −1= B µi, i = 1, ..., n.µkk=1Êîãäà â èãðå ñóùåñòâóåò ðåøåíèå â ÷èñòûõ ñòðàòåãèÿõ?nP1Åñëè B ≥ A, òî v = 0 ≥ v ≥ 0 è, ñëåäîâàòåëüíî, v = v = 0.µkk=1Äëÿ íàïàäåíèÿ ëþáàÿ ñòðàòåãèÿ îïòèìàëüíà.
 ýòîì ñëó÷àå îáîðîíà òàêìîæåò ðàñïðåäåëèòü ñâîè ñèëû, ÷òîáû íå ïîçâîëèòü íàïàäåíèþ, èñïîëüçóþùåìó êîíöåíòðèðîâàííûé óäàð, ïðîðâàòüñÿ íà êàêîì-ëèáî ïóíêòå.nP1, òî ôóíêöèÿ F (x, y) ñåäëîâîé òî÷êè íå èìååò. ÄåéÅñëè B < Aµkñòâèòåëüíî,k=1nX 1 −11 −1v =A−B>A−B= A − µn B.µkµnk=170 7. Èññëåäîâàíèå èãðîâûõ ìîäåëåéÇàìåòèì, ÷òî v > 0 . Ïîýòîìó v > max[A − µn B, 0] = v.â) Ïîêàæåì, ÷òî â èãðå ñóùåñòâóåò ðåøåíèå â ñìåøàííûõ ñòðàòåãèÿõ âèäà (ϕ0 , y 0 , v), ãäå y 0 − ÷èñòàÿ ìèíèìàêñíàÿ ñòðàòåãèÿ îáîðîíû, àîïòèìàëüíàÿ ñìåøàííàÿ ñòðàòåãèÿ äëÿ íàïàäåíèÿ èìååò âèä0ϕ =nXp0i Ix(i) ,i=1p0inX1 −1= µi, i = 1, ..., n.µkk=1Ïîñêîëüêó ôóíêöèÿ F (x, y) âûïóêëà ïî y, äîñòàòî÷íî ïðîâåðèòü óñëîâèå (∗) äëÿ ñìåøàííîé ñòðàòåãèè ϕ0 :F (ϕ0 , y) ≥ v ∀y ∈ Y.ÈìååìZ0F (ϕ , y) =F (x, y)dϕ0 (x) ==p0imax[A − µi yi , 0] =i=1≥ max[nXp0i F (x(i) , y) =i=1XnXnXnXmax[p0i A − µi p0i yi , 0] ≥i=1(p0i A−µi p0i yi ), 0]i=1= max[A − BnnXX1 −1= max[A −yi, 0] =µki=1k=1nX1 −1, 0] = v.µkk=1Çäåñü ìû âîñïîëüçîâàëèñü ýëåìåíòàðíûì íåðàâåíñòâîìnXmax[ai , bi ] ≥ max[i=1nXi=1ai ,nXbi ],i=1ñïðàâåäëèâîì äëÿ ëþáûõ âåùåñòâåííûõ ÷èñåë ai , bi , i = 1, ..., n.Ìîäåëü äóýëè. äóýëè ïðèíèìàþò ó÷àñòèå äâà äóýëÿíòà ( ïåðâûé è âòîðîé èãðîêè). íà÷àëüíûé ìîìåíò âðåìåíè äóýëÿíòû íàõîäÿòñÿ íà ðàññòîÿíèè d0 èïî êîìàíäå íà÷èíàþò ñáëèæàòüñÿ.
 ðàñïîðÿæåíèè êàæäîãî äóýëÿíòàèìååòñÿ îäèí âûñòðåë, êîòîðûé îí ìîæåò ïðîèçâåñòè â ïðîòèâíèêà ñëþáîãî ðàññòîÿíèÿ (êîíå÷íî, ïðè óñëîâèè, ÷òî äóýëÿíò æèâ), îí äàæåìîæåò ïîäîéòè ê ïðîòèâíèêó âïëîòíóþ.71ÃËÀÂÀ I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛÏóñòü pk (d) − ôóíêöèÿ ìåòêîñòè k -ãî äóýëÿíòà, ðàâíàÿ âåðîÿòíîñòèïîðàæåíèÿ ïðîòèâíèêà, åñëè âûñòðåë áûë ïðîèçâåäåí ñ ðàññòîÿíèÿ d.Ïðåäïîëîæèì, ÷òî ôóíêöèè pk (d) íåïðåðûâíû è óáûâàþò íà îòðåçêå[0, d0 ] è áåç ïîòåðè îáùíîñòè pk (0) = 1, pk (d0 ) = 0, k = 1, 2.Îïðåäåëèì àíòàãîíèñòè÷åñêóþ èãðó. Ïóñòü x ∈ X = [0, d0 ] − ðàññòîÿíèå, ñ êîòîðîãî ïåðâûé èãðîê íàìå÷àåò ïðîèçâåñòè ñâîé âûñòðåë. Àíàëîãè÷íî, y ∈ Y = [0, d0 ] − ðàññòîÿíèå, ñ êîòîðîãî íàìå÷àåò ñâîé âûñòðåëâòîðîé èãðîê.
Îïðåäåëèì ôóíêöèþ âûèãðûøà F (x, y) ïåðâîãî èãðîêà.Ðàññìîòðèì ñíà÷àëà øóìíóþ äóýëü, êîãäà ïðîòèâíèêè ñëûøàò âûñòðåëû äðóã äðóãà. Òîãäà(p1 (x),0 ≤ y ≤ x ≤ d0 ,F (x, y) =1 − p2 (y), 0 ≤ x < y ≤ d0 .Ïî ñìûñëó F (x, y) åñòü âåðîÿòíîñòü ïîðàæåíèÿ ïåðâûì èãðîêîì âòîðîãî. Åñëè x < y è âòîðîé èãðîê ïðîìàõíåòñÿ, òî ïåðâûé, óñëûøàâ âûñòðåë ïðîòèâíèêà, ñòðåëÿåò â íåãî ñ ðàññòîÿíèÿ 0 âìåñòî x.
Îòìåòèì, ÷òîF (x, y) ÿâëÿåòñÿ îñðåäíåíèåì ôóíêöèè, ïðèíèìàþùåé çíà÷åíèå 1 èëè 0â çàâèñèìîñòè îò òîãî, óáèò âòîðîé äóýëÿíò èëèíåò. Èòàê, øóìíàÿäóýëüîïðåäåëåíà êàê èãðà â íîðìàëüíîé ôîðìå Γ = X, Y, F (x, y) .Ïîêàæåì, ÷òî øóìíàÿ äóýëü èìååò ðåøåíèå â ÷èñòûõ ñòðàòåãèÿõ∗ ∗(d , d , v = p1 (d∗ )), ãäå d∗ − åäèíñòâåííûé êîðåíü óðàâíåíèÿ p1 (d) =1 − p2 (d).
Ïðîâåðèì íåðàâåíñòâà èç îïðåäåëåíèÿ ñåäëîâîé òî÷êèF (x, d∗ ) ≤ p1 (d∗ ) = F (d∗ , d∗ ) ≤ F (d∗ , y) ∀ x ∈ X, ∀ y ∈ Y.Èìååì(p1 (x) ≤ p1 (d∗ ),d∗ ≤ x ≤ d0 ,F (x, d∗ ) =1 − p2 (d∗ ) = p1 (d∗ ), 0 ≤ x < d∗ ,(p1 (d∗ ),0 ≤ y ≤ d∗ ,∗F (d , y) =1 − p2 (y) ≥ 1 − p2 (d∗ ) = p1 (d∗ ), d∗ < y ≤ d0 .Åñëè ôóíêöèè ìåòêîñòè èãðîêîâ îäèíàêîâû, òî èç óðàâíåíèÿp1 (d) = 1 − p1 (d) íàõîäèì, ÷òî çíà÷åíèå èãðû ðàâíî 1/2, à d∗ ÿâëÿåòñÿêîðíåì óðàâíåíèÿ p1 (d) = 1/2. áåñøóìíîé äóýëè èãðîêè íå ñëûøàò âûñòðåëû äðóã äðóãà è(p1 (x),0 ≤ y ≤ x ≤ d0 ,F (x, y) =p1 (x)(1 − p2 (y)), 0 ≤ x < y ≤ d0 .72 7.
Èññëåäîâàíèå èãðîâûõ ìîäåëåéÏîêàæåì, ÷òî áåñøóìíàÿ äóýëü íå èìååò ðåøåíèÿ â ÷èñòûõ ñòðàòåãèÿõ.Íàéäåì âåëè÷èíó v = sup inf F (x, y). Ñòðàòåãèÿ x = d0 íå ìîæåò0≤x≤d0 0≤y≤d0áûòü ìàêñèìèííîé, ïîñêîëüêó F (d0 , y) = p1 (d0 ) = 0 ïðè âñåõ y ∈ Y.Ïóñòü 0 ≤ x < d0 . Òîãäàinf F (x, y) = min[ inf F (x, y), inf F (x, y)] =0≤y≤x0≤y≤d0x<y≤d0= min[p1 (x), p1 (x)(1 − p2 (x))] = p1 (x)(1 − p2 (x)).Îòñþäà v = max p1 (x)(1 − p2 (x)).0≤x≤d0Óïðàæíåíèå 7.1. Äîêàæèòå, ÷òîv = infsup F (x, y) = p1 (d∗ ).0≤y≤d0 0≤x≤d0Òàêèì îáðàçîì, v = max p1 (x)(1 − p2 (x)) <0≤x≤d0< max min[p1 (x), 1 − p2 (x)] = p1 (d∗ ) = v.0≤x≤d0Ðåøåíèå áåñøóìíûõ äóýëåé îáû÷íî ñâîäèòñÿ ê èíòåãðèðîâàíèþ îáûêíîâåííûõ äèôôåðåíöèàëüíûõ óðàâíåíèé. Ìû îãðàíè÷èìñÿ èññëåäîâàíèåì êîíêðåòíîãî ïðèìåðà.Ïðèìåð 7.1.
Ðàññìîòðèì áåñøóìíóþ äóýëü ñ îäèíàêîâûìè ôóíêöèÿìè ìåòêîñòè èãðîêîâ p1 (d) = p2 (d) = 1 − d, 0 ≤ d ≤ d0 = 1. Òîãäà(1 − x,0 ≤ y ≤ x ≤ 1,F (x, y) =(1 − x)y, 0 ≤ x < y ≤ 1.Ïðåäïîëîæèì, ÷òî îïòèìàëüíûå ñìåøàííûå ñòðàòåãèè èãðîêîâ ϕ0 (x)è ψ 0 (y) èìåþò ñîâïàäàþùèå ñïåêòðû Sp(ϕ0 ) = Sp(ψ 0 ) = [0, a], ãäå a ≤ 1− ïàðàìåòð, ïîäëåæàùèé îïðåäåëåíèþ. Ïóñòü íà îòðåçêå [0, a] ôóíêöèèðàñïðåäåëåíèÿ ϕ0 (x) è ψ 0 (y) íåïðåðûâíû è èìåþò ïðîèçâîäíûå (ïëîòíîñòè ðàñïðåäåëåíèÿ) f (x) è g(y).Ïî ñâîéñòâó äîïîëíÿþùåé íåæåñòêîñòè (òåîðåìà 4.3)F (ϕ0 , y) = v ∀ y ∈ [0, a] èëèZyZa(1 − x)yf (x)dx +F (x, y)f (x)dx =0Za0(1 − x)f (x)dx = v.y73(7.2)ÃËÀÂÀ I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛÄèôôåðåíöèðóÿ äâàæäû ïî y èíòåãðàëüíîå óðàâíåíèå (7.2), ïîëó÷èìäèôôåðåíöèàëüíîå óðàâíåíèå 3f (y) = (1 − y)f 0 (y), èìåþùåå (ïîñëå çàìåíû y íà x ) îáùåå ðåøåíèå âèäà f (x) = c(1 − x)−3 .
Ïî îïðåäåëåíèþR1ïëîòíîñòè f (x)dx = 1 (óñëîâèå íîðìèðîâêè). Îòñþäà0Zac"#1c1dx =− 1 = 1.(1 − x)32 (1 − a)2(7.3)0Íàéäåííàÿ ïëîòíîñòü f (x) äîëæíà òàêæå óäîâëåòâîðÿòü èñõîäíîìó èíòåãðàëüíîìó óðàâíåíèþ (7.2), ò.å."#1c− 1 − y = v.(7.4)1−aÏîñêîëüêó óðàâíåíèå (7.4) íå ÿâëÿåòñÿ òîæäåñòâîì ïî y, ñìåøàííàÿñòðàòåãèÿ ϕ0 (x) óêàçàííîãî âèäà íå ñóùåñòâóåò.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
