А.А. Васин, В.В. Морозов - Введение в теорию игр с приложениями к экономике (1184512), страница 13
Текст из файла (страница 13)
� òàêè� ñëó÷àÿ� ìèíèìàêñíó� ñòðàòåãè� ñòàòèñòèê� y 0 ìîæí� íàéòè, ðåøà� íåïîñðåäñòâåíí� çàäà÷� v = min max F (x, y) = max F (x, y 0 ). y∈Y x∈Xx∈X Ïðèìå� 6.3. Ñòðàõîâà� êîìïàíè� îñóùåñòâëÿå� ñòðàõîâàíè� ãðàæäàíñêî� îòâåòñòâåííîñò� àâòîìîáèëèñòîâ. Âîäèòåë� îáû÷í� ðàçáèâàþòñ� í� ãðóïï� ï� íåñêîëüêè� ïðèçíàêà� (ïðîôåññèÿ, ñòà� âîæäåíè� � ò.ï.). Ðàññìîòðè� íåêîòîðó� ãðóïïó, ñîñòîÿùó� è� n âîäèòåëåé. Òðåáóåòñ� îöåíèò� ñðåäíå� ÷èñë� x äîðîæíû� ïðîèñøåñòâè� � ðàñ÷åò� í� îäíîã� âîäèòåëÿ, êîòîðû� ïðîèçîéäó� � òå÷åíè� áëèæàéøåã� ãîäà, èñõîä� è� èíôîðìàöè� � ïðîèñøåñòâèÿ� ïðîøåäøåã� ãîäà.
Çàäà÷� ìîæí� ñâåñò� � ðåøåíè� ñòàòèñòè÷åñêî� èãðû. Ïóñò� ÷èñë� äîðîæíû� ïðîèñøåñòâè� � âîäèòåëå� i ÿâëÿåòñ� ñëó÷àéíî� âåëè÷èíî� Zi , ðàñïðåäåëåííî� ï� çàêîí� Ïóàññîí� g(zi |x) = xzi e−x , zi ∈ Z = {0, 1, 2, ..., }. zi ! Çäåñ� EZi = x, V arZi = D(x) = x, x ∈ X = [0, x∗ ], ãä� x∗ − âåðõíÿ� ãðàí� âîçìîæíû� çíà÷åíè� ïàðàìåòð� x. Èìåå� D(x) x + (c1 x − x + c2 )2 = c 2 1 + (c1 x − x + c2 )2 . nn Íåòðóäí� ïðîâåðèòü, ÷ò� í� ñóùåñòâóå� âûðàâíèâàþùå� ðåøàþùå� ôóíêöèè.
Îáîçíà÷è� M (c) = sup F (x, c) � íàéäå� F (x, c) = c2 10≤x≤x∗ v = min M (c) = M (c 0 ). c1 ,c2 ≥0 Ïîñêîëüê� F (x, c) âûïóêë� ï� x, M (c) = max[F (0, c), F (x∗ , c)]. Óòâåðæäåíè� 6.2. Äë� ìèíèìàêñíî� ñòðàòåãè� y 0 (z) = c01 z + c0 2 âûïîëíåí� óñëîâè� F (0, c0 ) = F (x∗ , c0 ) èë� c0 2 = + (c01 − 1)2 x∗ . 2(1 − c01 )1 0 2 (c )n 166 6. Èãð� � âîãíóòî� ôóíêöèå� âûèãðûø�Äîêàçàòåëüñòâî. Äîïóñòèì, ÷ò� F (x∗ , c0 ) > F (0, c0 ). Åñë� c0 1 > 0, ò� ïð� ìàëî� ε > 0 (c01 )2 x∗ F (x , c ) = + (c0 1 x∗ + c0 2 − x∗ )2 > F (x∗ , c 0 1 − ε, c02 + εx∗ ) = n ∗0(c0 1 − ε)2 x∗ =+ (c01 x∗ + c02 − x∗ )2 > F (0, c 0 1 − ε, c02 + εx∗ ) = (c0 2 + εx∗ )2 n 0 � M (c1 − ε, c02 + εx∗ ) < M (c0 ) (ïðîòèâîðå÷èå).
Åñë� c0 1 = 0, ò� F (x∗ , c 0 ) = (c0 2 − x∗ )2 > F (0, c 0 ) = (c 02 )2 .Îòñþä� ñëåäóåò, ÷ò� c0 2 < x∗ /2. Óâåëè÷èâà� c0 2 í� ìàëî� ε > 0, ïðèäå� � ïðîòèâîðå÷èþ. Ñëó÷à� F (x∗ , c0 ) < F (0, c0 ) ðàçáèðàåòñ� àíàëîãè÷íî. È� äîêàçàííîã� óòâåðæäåíè� âûòåêàåò, ÷ò� !21 2 2 ∗ (c)+(c− 1)x11 n min M (c) = min . c1 ,c2 ≥00≤c1 <1 2(1 − c1 ) Ïîñëåäíè� ìèíèìó� äîñòèãàåòñ� ïð� √√x∗ n + 1 − 1x∗ n + 1 − x∗ n + 1 00 c1 = ⇒ c= . 2 x∗ n + 1 n Òàêè� îáðàçîì, ïð� îöåíê� ïàðàìåòð� ðàñïðåäåëåíè� Ïóàññîí� √√x∗ n + 1 − 1 x∗ n + 1 − x∗ n + 1 0y (z) = z + x∗ n + 1 n − ìèíèìàêñíà� ñòðàòåãè� ñòàòèñòèêà. � ÷àñòíî� ñëó÷à� ïð� n = 30, x∗ = 0.5, z = 0.2 ïîëó÷àå� îöåíê� y 0 (z) = 0.16. Óïðàæíåíè� 6.3. Ïóñò� âñ� ñëó÷àéíû� âåëè÷èí� Zi èìåþ� íîðìàëüíî� ðàñïðåäåëåíè� � ïëîòíîñòü� g(zi |x) = √(zi −x)2 1 e− 2σ2 , zi ∈ E 1 ,2πσ ãä� äèñïåðñè� σ 2 ñòàòèñòèê� èçâåñòíà, � ìàòåìàòè÷åñêî� îæèäàíè� x −íåò: x ∈ X = E 1 .
Ïîêàçàòü, ÷ò� êëàññè÷åñêà� ðåøàþùà� ôóíêöè� z ÿâëÿåòñ� âûðàâíèâàþùå� � ìèíèìàêñíî� ñòðàòåãèå� ñòàòèñòèêà. 67 ÃËÀÂ� I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈ� ÈÃÐ� 7. Èññëåäîâàíè� èãðîâû� ìîäåëå� Ìîäåë� "íàïàäåíèå-îáîðîíà". Èìååòñ� n îáîðîíÿåìû� ïóíêòî� � íîìåðàì� i = 1, ..., n âîçìîæíîã� ïðîðûâ� ñðåäñò� íàïàäåíèÿ. Ïóñò� 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∈Y x(n) = (0, ..., 0, A) − ìàêñèìèííà� ñòðàòåãè� íàïàäåíèÿ, ñîñòîÿùà� � íàíåñåíè� "êîíöåíòðèðîâàííîãî"óäàð� ï� ñëàáåéøåì� ïóíêòó.
68 7. Èññëåäîâàíè� èãðîâû� ìîäåëå�Äë� ëþáî� ñòðàòåãè� íàïàäåíè� x îïðåäåëè� âñïîìîãàòåëüíó� ñòðàòåãè� îáîðîí� y : � y i = Bxi µi n� xk −1 k=1 µkÒîãä� min F (x, y) ≤ F (x, y) = y∈Y Åñë� B ≥ nPk=1 xk, µ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 − µn nXi=1 y i = A − µn B. i=1 Òàêè� îáðàçîì, äë� ëþáî� ñòðàòåãè� x min 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) − ìàêñèìèííà� ñòðàòåãè� íàïàäåíèÿ. á) Ïîêàæåì, ÷ò� n � 1 −1 v = min max F (x, y) = max[A − B, 0], y∈Y x∈X µkk=1 � 0 y : yi 0 n� 1 −1 = B µi , i = 1, ..., n, µkk=1 � − ìèíèìàêñíà� ñòðàòåãè� îáîðîíû.
Ñíà÷àë� äîêàæå� ðàâåíñòâ� max F (x, y) = max F (x(i) , y) ∀ y ∈ Y, x∈X 1≤i≤n (7.1) ãä� x(i) = (0, ..., |{z}A , 0, ..., 0) − ñòðàòåãè� íàïàäåíèÿ, ñîñòîÿùà� � íàíåñåi íè� êîíöåíòðèðîâàííîã� óäàð� ï� i-ì� ïóíêòó. 69 ÃËÀÂ� I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈ� ÈÃÐ�Ïðåäñòàâè� ñòðàòåãè� x � âèä� x = nPi=1 ëî� ôóíêöè� F (x, y) ≤ nXxi i=1 A xi (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∈X x∈X � (7.1) äîêàçàíî. Äàëå� èìåå� v = min max F (x, y) = min max F (x(i) , y) = y∈Y 1≤i≤n y∈Y x∈X= min max max[A − µi yi , 0] = min max[A − min µi yi , 0] = y∈Y 1≤i≤n1≤i≤n y∈Y = max[A − B max min µi yi /B, 0] = [çàìåí� ïåðåìåííû� y∈Y 1≤i≤n p = 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≤n � � −1 n1 =[ ñì. ïðèìå� 4.4] = max[A − B , 0].
µk k=1 Ïð� ýòî� yi 0 = Bp0 i n� 1 −1 = B µi , i = 1, ..., n. µkk=1 � Êîãä� � èãð� ñóùåñòâóå� ðåøåíè� � ÷èñòû� ñòðàòåãèÿõ? nP1 Åñë� B ≥ A , ò� v = 0 ≥ v ≥ 0 è, ñëåäîâàòåëüíî, v = v = 0. µk k=1 Äë� íàïàäåíè� ëþáà� ñòðàòåãè� îïòèìàëüíà.
� ýòî� ñëó÷à� îáîðîí� òà� ìîæå� ðàñïðåäåëèò� ñâî� ñèëû, ÷òîá� í� ïîçâîëèò� íàïàäåíèþ, èñïîëüçóþùåì� êîíöåíòðèðîâàííû� óäàð, ïðîðâàòüñ� í� êàêîì-ëèá� ïóíêòå. nP1 Åñë� B < A , ò� ôóíêöè� F (x, y) ñåäëîâî� òî÷ê� í� èìååò. Äåéµk ñòâèòåëüíî, k=1n� � 1 −11 −1 v = A − B > A − B = A − µn B.µk µnk=1 70 7. Èññëåäîâàíè� èãðîâû� ìîäåëå�Çàìåòèì, ÷ò� v > 0 . Ïîýòîì� v > max[A − µn B, 0] = v. â) Ïîêàæåì, ÷ò� � èãð� ñóùåñòâóå� ðåøåíè� � ñìåøàííû� ñòðàòåãèÿ� âèä� (ϕ0 , y 0 , v), ãä� y 0 − ÷èñòà� ìèíèìàêñíà� ñòðàòåãè� îáîðîíû, � îïòèìàëüíà� ñìåøàííà� ñòðàòåãè� äë� íàïàäåíè� èìåå� âè� 0 ϕ = nXp 0 i Ix(i) ,i=1 p 0 i n� 1 −1 = µi , i = 1, ..., n. µkk=1 � Ïîñêîëüê� ôóíêöè� F (x, y) âûïóêë� ï� y, äîñòàòî÷í� ïðîâåðèò� óñëîâè� (∗) äë� ñìåøàííî� ñòðàòåãè� ϕ0 : F (ϕ0 , y) ≥ v ∀y ∈ Y. Èìåå� � 0 F (ϕ , y) = F (x, y)dϕ0 (x) = = p 0 i max[A − µi yi , 0] = i=1 ≥ max[ n� p0i F (x(i) , y) = i=1X nXnXnXmax[p 0 i A − µi p 0 i yi , 0] ≥ i=1 (p 0 i A − µi p 0 i yi ), 0] i=1 = max[A − Bnn � X1 −1 = max[A − yi , 0] = µki=1 k=1 n � 1 −1, 0] = v.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
