А.А. Васин, В.В. Морозов - Введение в теорию игр с приложениями к экономике (1184512), страница 14
Текст из файла (страница 14)
µkk=1 Çäåñ� ì� âîñïîëüçîâàëèñ� ýëåìåíòàðíû� íåðàâåíñòâî� nXmax[ai , bi ] ≥ max[ i=1 nXi=1 ai ,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≤x 0≤y≤d0 x<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 = inf sup 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] èë� Zy Za (1 − x)yf (x)dx + F (x, y)f (x)dx = 0Za 0 (1 − x)f (x)dx = v. y 73(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 (óñëîâè� íîðìèðîâêè). Îòñþä� 0 Za c "� 1 c 1 dx = − 1 = 1. (1 − x)3 2 (1 − a)2 (7.3)0 Íàéäåííà� ïëîòíîñò� f (x) äîëæí� òàêæ� óäîâëåòâîðÿò� èñõîäíîì� èíòåãðàëüíîì� óðàâíåíè� (7.2), ò.å. "#1 c − 1 − y = v. (7.4)1 − a Ïîñêîëüê� óðàâíåíè� (7.4) í� ÿâëÿåòñ� òîæäåñòâî� ï� y, ñìåøàííà� ñòðàòåãè� ϕ0 (x) óêàçàííîã� âèä� í� ñóùåñòâóåò.
Ïîýòîì� ïðåäïîëîæèì, ÷ò� ôóíêöè� ðàñïðåäåëåíè� ϕ0 (x) èìåå� ñêà÷î� âåëè÷èí� σ � íóëå. Òîãä� óðàâíåíè� (7.2)−(7.4) èçìåíÿòñÿ: Zy Za σy + (1 − x)yf (x)dx + (1 − x)f (x)dx = v, (7.2)� y 0 "#c 1 σ + − 1 = 1, 2 (1 − a)2 "#1 σy + c − 1 − y = v. 1 − a (7.3)� (7.4)� Äë� òîã� ÷òîá� óðàâíåíè� (7.4)� âûïîëíÿëîñ� êà� òîæäåñòâî, íåîáõîäèì� ïîëîæèò� σ = c. È� óðàâíåíè� (7.3)0 , (7.4)� ïîëó÷àå� "#c 1 ca +1 =1, = v. (7.5) 2 (1 − a)2 1 − a È� ñâîéñòâ� äîïîëíÿþùå� íåæåñòêîñò� òàêæ� ñëåäóåò, ÷ò� F (x, ψ 0 ) = v ∀ x ∈ [0, a] èë� Za Zx Za F (x, y)g(y)dy = (1 − x)g(y)dy + (1 − x)yg(y)dy = v. 00 x 74(7.6) 8.
Ìíîãîøàãîâû� àíòàãîíèñòè÷åñêè� èãð�Îòñþäà, êà� � âûøå, ïîëó÷è� g(y) = c1 (1 − y)−3 . Ïîäñòàâëÿ� g(y) � óðàâíåíè� (7.6), íàõîäè� " Zx #Za 1 y c1 (1 − x) dy + dy = v(1 − y)3 (1 − y)3 0 x èëè, èñïîëüçóÿ óñëîâèå íîðìèðîâê� R1Rag (y )dy = c1 (1 − y )−3 dy = 1,0"(1 − x) 1 − 0 #c1 c1+= v. 1 − a 1 − x Äë� òîã� ÷òîá� ïîñëåäíå� ðàâåíñòâ� âûïîëíÿëîñ� òîæäåñòâåííî, íåîáõîäèìî, ÷òîá� c1 = v = 1 − a. Îòñþä� � è� (7.5) íàõîäè� √√√2 − 2 a = 2 − 2, c1 = v = 2 − 1, c = σ =. 2 Îêîí÷àòåëüí� !⎧ √2 −21 ⎨ + 1 , 4(x − 1)2 ϕ0 (x) = ⎩1,!⎧ √2 − 11 ⎨ − 1 ,2(y − 1)2 ψ 0 (y) = ⎩1,√0 ≤ x ≤ 2 − 2,√2 − 2 < x ≤ 1,√0 ≤ y ≤ 2 − 2, √2 − 2 < y ≤ 1.0 Îñîáåííîñò� îïòèìàëüíî� ñìåøàííî� √ ñòðàòåãè� ϕ ñîñòîè� � òîì, ÷ò� 2− 2 ïåðâû� èãðî� � âåðîÿòíîñòü� σ = 2 æäå� ä� ïîëíîã� ñáëèæåíè� � √ïðîòèâíèêîì.
Îòìåòè� òàêæå, ÷ò� çíà÷åíè� èãð� v = 2 − 1 áåñøóìíî� äóýë� ìåíüø� çíà÷åíè� èãð� v = 1/2 øóìíî� äóýëè, ÷ò� îáúÿñíÿåòñ� óìåíüøåíèå� èíôîðìèðîâàííîñò� ïåðâîã� èãðîêà. 8. Ìíîãîøàãîâû� àíòàãîíèñòè÷åñêè� èãð� Îïðåäåëè� ìíîãîøàãîâó� àíòàãîíèñòè÷åñêó� èãð� � ïîëíî� èíôîðìàöèåé. Èãð� ïðîèñõîäè� � òå÷åíè� T øàãî� � íîìåðàì� t = 1, ..., T.
Í� 75ÃËÀÂ� I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈ� ÈÃÐ�êàæäî� øàã� t èãðîê� âûáèðàþ� ï� î÷åðåä� àëüòåðíàòèâ� − çíà÷åíè� ïåðåìåííû� xt , yt . Øà� 1. Ñíà÷àë� ïåðâû� èãðî� âûáèðàå� àëüòåðíàòèâ� x1 ∈ U1 , çàòå� âòîðî� èãðîê, çíà� âûáî� ïåðâîãî, âûáèðàå� àëüòåðíàòèâ� y1 ∈ V1 (x1 ) = V1 (·).Ïóñò� èãðîê� � òå÷åíè� t − 1 øàãî� âûáðàë� àëüòåðíàòèâ� x1 , ..., xt−1 , y1 , ..., yt−1 .
Ïîëîæè� xt = (x1 , ..., xt ), y t = (y1 , ..., yt ). Øà� t. Ñíà÷àë� ïåðâû� èãðîê, çíà� ïðåäûñòîðè� xt−1 , y t−1 , âûáèðàå� àëüòåðíàòèâ� xt ∈ Ut (xt−1 , y t−1 ) = Ut (·). Çàòå� âòîðî� èãðî� âûáèðàå� àëüòåðíàòèâ� yt ∈ Vt (xt , y t−1 ) = Vt (·), çíà� ïðåäûñòîðè� xt , y t−1 , âêëþ÷àÿâûáî� xt ïåðâîã� èãðîê� í� äàííî� øàãå. Ïîñë� çàâåðøåíè� øàã� T âîçíèêàå� ïàð� (xT , y T ), íàçûâàåìà� ïàðòèå� èãðû. Ï� ñìûñë� ïàðòè� èãð� − ýò� çàïèñ� âñå� àëüòåðíàòèâ, âûáðàííû� èãðîêàìè.
Äë� ëþáî� ïàðòè� (xT , y T ) çàäàåòñ� âûèãðû� F (xT , y T ) ïåðâîã� èãðîêà. Îïðåäåëè� òåïåð� èãð� � íîðìàëüíî� ôîðìå. Í� øàã� t ïåðâû� èãðî� ìîæå� âûáðàò� àëüòåðíàòèâ� xt êà� çíà÷åíè� ôóíêöè� x̃t : xt = x̃t (xt−1 , y t−1 ), êîòîðà� äîëæí� áûò� îïðåäåëåí� ïð� âñåâîçìîæíû� çíà÷åíèÿ� àðãóìåíòî� xt−1 , y t−1 . Îáîçíà÷è� ìíîæåñòâ� âñå� òàêè� ôóíêöè� x̃t ÷åðå� Ũt . Çàìåòèì, ÷ò� x̃1 = x1 , ïîñêîëüê� í� ïåðâî� øàã� ïåðâû� èãðî� íèêàêî� èíôîðìàöèå� í� ðàñïîëàãàåò.
Ñòðàòåãè� ïåðâîã� èãðîê� ïðåäñòàâëÿå� ñîáî� íàáî� ôóíêöè� x̃ = (x̃t , t = 1, ..., T ) ∈ X̃ = TYŨt . t=1 Àíàëîãè÷íî, í� øàã� t âòîðî� èãðî� ìîæå� âûáèðàò� àëüòåðíàòèâ� yt êà� çíà÷åíè� ôóíêöè� ỹt : yt = ỹt (xt , y t−1 ), êîòîðà� äîëæí� áûò� îïðåäåëåí� ïð� âñåâîçìîæíû� çíà÷åíèÿ� àðãóìåíòî� xt , y t−1 .
Îáîçíà÷è� ìíîæåñòâ� âñå� òàêè� ôóíêöè� ỹt ÷åðå� Ṽt . Ñòðàòåãè� âòîðîã� èãðîê� ïðåäñòàâëÿå� ñîáî� íàáî� ôóíêöè� ỹ = (ỹt , t = 1, ..., T ) ∈ Ỹ = TYṼt . t=1 Èãðîê� ìîãó� âûáðàò� ñòðàòåãè� x, ˜ y ˜ íåçàâèñèì� äðó� î� äðóã� ä� èãðû, � â� âðåì� èãð� − ïðèìåíÿò� è� "àâòîìàòè÷åñêè."Ëþáî� ïàð� ñòðàòåãè� (x̃, ỹ) îäíîçíà÷í� ñîîòâåòñòâóå� ïàðòè� èãðû: 76 8. Ìíîãîøàãîâû� àíòàãîíèñòè÷åñêè� èãð�x1 = x̃1 , y1 = ỹ1 (x1 ), x2 = x̃2 (x1 , y1 ) � ò.ä. defÄàëå� F (x̃, ỹ) = F (xT , y T ), ãä� (xT , y T ) − ïàðòèÿ, ñîîòâåòñòâóþùà� ñòðàòåãèÿ� x̃ � ỹ .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
