[учебник] Введение в теорию игр (с приложениями к экономике). Васин, Морозов (2003) ([учебник] Введение в теорию игр (с приложениями к экономике). Васин, Морозов (2003).pdf), страница 13

Ïîýòîìó ïðåäïîëîæèì,÷òî ôóíêöèÿ ðàñïðåäåëåíèÿ ϕ0 (x) èìååò ñêà÷îê âåëè÷èíû σ â íóëå. Òîãäàóðàâíåíèÿ (7.2)−(7.4) èçìåíÿòñÿ:ZyZaσy + (1 − x)yf (x)dx + (1 − x)f (x)dx = v,(7.2)0y0"#c1σ+− 1 = 1,2 (1 − a)2"#1σy + c− 1 − y = v.1−a(7.3)0(7.4)0Äëÿ òîãî ÷òîáû óðàâíåíèå (7.4)0 âûïîëíÿëîñü êàê òîæäåñòâî, íåîáõîäèìîïîëîæèòü σ = c.

Èç óðàâíåíèé (7.3)0 , (7.4)0 ïîëó÷àåì"#c1ca+1=1,= v.(7.5)2 (1 − a)21−aÈç ñâîéñòâà äîïîëíÿþùåé íåæåñòêîñòè òàêæå ñëåäóåò, ÷òîF (x, ψ 0 ) = v ∀ x ∈ [0, a] èëèZaZxZaF (x, y)g(y)dy = (1 − x)g(y)dy + (1 − x)yg(y)dy = v.00x74(7.6)Ÿ 8. Ìíîãîøàãîâûå àíòàãîíèñòè÷åñêèå èãðûÎòñþäà, êàê è âûøå, ïîëó÷èì g(y) = c1 (1 − y)−3 . Ïîäñòàâëÿÿ g(y) âóðàâíåíèå (7.6), íàõîäèì#" ZxZay1c1 (1 − x)dy +dy = v(1 − y)3(1 − y)3x0èëè, èñïîëüçóÿ óñëîâèå íîðìèðîâêèR1Rag(y)dy = c1 (1 − y)−3 dy = 1,0"(1 − x) 1 −0#c1c1+= v.1−a 1−xÄëÿ òîãî ÷òîáû ïîñëåäíåå ðàâåíñòâî âûïîëíÿëîñü òîæäåñòâåííî, íåîáõîäèìî, ÷òîáû c1 = v = 1 − a. Îòñþäà è èç (7.5) íàõîäèì√√√2− 2a = 2 − 2, c1 = v = 2 − 1, c = σ =.2Îêîí÷àòåëüíî!√212−+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̃, ỹ íåçàâèñèìî äðóã îò äðóãà äî èãðû,à âî âðåìÿ èãðû − ïðèìåíÿòü èõ "àâòîìàòè÷åñêè."Ëþáîé ïàðå ñòðàòåãèé(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̃ è ỹ .

Èòàê, ìíîãîøàãîâàÿèãðà ñ ïîëíîéèíôîðìàöèåé îïðåäåëåíà â íîðìàëüíîé ôîðìå Γ = X̃, Ỹ , F (x̃, ỹ) . äàëüíåéøåì áóäåì ðàññìàòðèâàòü äâà êëàññà èãð:èãðà Γ0 , â êîòîðîé âñå ìíîæåñòâà Ut (·), Vt (·) êîíå÷íû;èãðà Γ00 , â êîòîðîé âñå ìíîæåñòâà Ut (·) ≡ Ut , Vt (·) ≡ Vt íå çàâèñÿò îòïðåäûñòîðèè è ÿâëÿþòñÿ êîìïàêòàìè ìåòðè÷åñêèõ ïðîñòðàíñòâ, à ôóíêöèÿ F (xT , y T ) íåïðåðûâíà íà ïðîèçâåäåíèèU1 × · · · × UT × V1 × · · · × VT .Îïðåäåëèì ïàðó ñòðàòåãèéx̃0 = (x̃0t , t = 1, ..., T ), ỹ 0 = (ỹt0 , 1, ..., T ),èñïîëüçóÿ ìåòîä äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ. Äîîïðåäåëèì ôóíêöèþ F íà âñåõ îòðåçêàõ ïàðòèè âèäà (xt , y t−1 ) èëè (xt , y t ) è íàçîâåìåå ôóíêöèåé Áåëëìàíà. Êîìïîíåíòû ñòðàòåãèé x̃0t , ỹt0 áóäåì çàäàâàòü âïîðÿäêå, îáðàòíîì âûáîðàì èãðîêîâ.Îïðåäåëèì ñíà÷àëà ỹT0 .

Äëÿ ýòîãî çàôèêñèðóåì ïðîèçâîëüíîå çíà÷åíèå àðãóìåíòîâ (xT , y T −1 ) è çàäàäèì çíà÷åíèå ôóíêöèèdefỹT0 (xT , y T −1 ) = yT0 :defF (xT , y T −1 , yT0 ) = min F (xT , y T −1 , yT ) = F (xT , y T −1 ).yT ∈VT (·)Îïðåäåëèì ôóíêöèþ x̃0T . Çàôèêñèðóåì ïðîèçâîëüíîå çíà÷åíèå àðãóìåíòîâ (xT −1 , y T −1 ) è çàäàäèì çíà÷åíèå ôóíêöèèdefx̃0T (xT −1 , y T −1 ) = x0T :defF (xT −1 , x0T , y T −1 ) = max F (xT −1 , xT , y T −1 ) = F (xT −1 , y T −1 ).xT ∈UT (·)Ïóñòü îïðåäåëåíû êîìïîíåíòû ñòðàòåãèé è çíà÷åíèÿ ôóíêöèè Áåëëìàíà0ỹT0 , x̃0T , ..., ỹt+1, x̃0t+1 , F (xT , y T −1 ), ..., F (xt , y t ).Òîãäà ỹt0 , x̃0t , F (xt , y t−1 ), F (xt−1 , y t−1 ) çàäàþòñÿ ïî ïðèâåäåííûì âûøåôîðìóëàì ñ çàìåíîé T íà t.Ïîêàæåì, ÷òî ñòðàòåãèè x̃0 , ỹ 0 îïðåäåëåíû êîððåêòíî äëÿ èãð Γ0 è Γ00 .Äåéñòâèòåëüíî, â èãðå Γ0 âñå ìíîæåñòâà Ut (·), Vt (·) êîíå÷íû è ïîýòîìó77ÃËÀÂÀ I.

ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛìàêñèìóìû è ìèíèìóìû, ôèãóðèðóþùèå â îïðåäåëåíèÿõ x̃0 , ỹ 0 , äîñòèãàþòñÿ. Àíàëîãè÷íîå óòâåðæäåíèå ñïðàâåäëèâî è äëÿ èãðû Γ00 , ïîñêîëüêóïî òåîðåìå 2.2 ôóíêöèÿ Áåëëìàíà íåïðåðûâíà íà ñîîòâåòñòâóþùèõ êîìïàêòàõ.Îïðåäåëèì âåëè÷èíódef F (x1 )ṽ = max F (x1 )x1 ∈U1=max min F (x1 , y1 ) = ...x1 ∈U1 y1 ∈V1 (·)= max min ... maxx1 ∈U1 y1 ∈V1 (·)min F (xT , y T ).xT ∈UT (·) yT ∈VT (·)Ñïðàâåäëèâà ñëåäóþùàÿÒåîðåìà 8.1 (Öåðìåëî). Âñÿêàÿ ìíîãîøàãîâàÿ àíòàãîíèñòè÷åñêàÿèãðà ñ ïîëíîé èíôîðìàöèåé Γ0 (èëè Γ00 ) èìååò ðåøåíèå (x̃0 , ỹ 0 , ṽ).Äîêàçàòåëüñòâî.

Äîêàæåì, ÷òî ôóíêöèÿ F (x̃, ỹ) èìååò ñåäëîâóþ òî÷êó (x̃0 , ỹ 0 ) íà X̃ × Ỹ . Äëÿ ýòîãî äîñòàòî÷íî äîêàçàòü, ÷òî1) F (x̃0 , ỹ) ≥ ṽ ∀ ỹ ∈ Ỹ ;2) F (x̃, ỹ 0 ) ≤ ṽ ∀ x̃ ∈ X̃.Äîêàæåì íåðàâåíñòâî 1). ÈìååìF (x̃0 , ỹ) ≥ min F (x̃0 , ỹ1 , ..., ỹT −1 , yT ) = F (x̃0 , ỹ1 , ..., ỹT −1 ) =yT ∈VT (·)def x̃T0=max F (x̃01 , ..., x̃0T −1 , xT , ỹ1 , ..., ỹT −1 ) =xT ∈UT (·)= F (x̃01 , ..., x̃0T −1 , ỹ1 , ..., ỹT −1 ) ≥ ... ≥ F (x̃01 , ỹ1 ) ≥ max F (x1 ) = ṽ.x1 ∈U1Íåðàâåíñòâî 2) äîêàçûâàåòñÿ àíàëîãè÷íî.Ïðèìåð 8.1. Ïîêàæåì, ÷òî èãðà "øàõìàòû"èìååò ðåøåíèå.

Ñóùåñòâóåò òàêîå öåëîå ÷èñëî T, ÷òî â ñîîòâåòñòâèè ñ ïðàâèëàìè èãðû ëþáàÿøàõìàòíàÿ ïàðòèÿ çàêàí÷èâàåòñÿ íå ïîçäíåå õîäà T. Ïîýòîìó áåç ïîòåðèîáùíîñòè ìîæíî ñ÷èòàòü, âñå ïàðòèè ïðîäîëæàþòñÿ T õîäîâ1 . Øàõìàòûÿâëÿþòñÿ èãðîé âèäà Γ0 . Ut (xt−1 , y t−1 ) åñòü ìíîæåñòâî ðàçðåøåííûõ ïðàâèëàìè àëüòåðíàòèâíûõ âûáîðîâ õîäà áåëûìè (ïåðâûì èãðîêîì) íà t-ìõîäó â ïîçèöèè, îïðåäåëÿåìîé ïðåäûäóùèìè õîäàìè èãðîêîâ (xt−1 , y t−1 ).1 Åñëèïàðòèÿ çàêàí÷èâàåòñÿ ðàíüøå, òî èãðîêè äåëàþò íåîáõîäèìîå ÷èñëî ôèêòèâíûõ õîäîâ, íå âëèÿþùèõ íà èñõîä èãðû.78Ÿ 8. Ìíîãîøàãîâûå àíòàãîíèñòè÷åñêèå èãðûÀíàëîãè÷íî èíòåðïðåòèðóåòñÿ ìíîæåñòâî Vt (xt , y t−1 ) âûáîðîâ õîäà ÷åðíûìè íà t-ì õîäó. Âûèãðûø áåëûõ îïðåäåëÿåòñÿ ïî ïðàâèëóåñëè âûèãðàëè áåëûå,1,F (xT , y T ) = 0,åñëè âûèãðàëè ÷åðíûå,1/2, åñëè ñûãðàëè âíè÷üþ.Ïî òåîðåìå Öåðìåëî èãðà "øàõìàòû"èìååò ðåøåíèå. Ïðàêòè÷åñêîåçíà÷åíèå ýòîò ðåçóëüòàò èìååò äëÿ ïîçèöèé ýíäøïèëÿ, ãäå îáû÷íî èùóòôîðñèðîâàííûé âûèãðûø, ëèáî íè÷üþ.Ïðèìåð 8.2.

Ðàññìîòðèì ìàòðèöó52A=343720123240.35Ðàçîáüåì ìíîæåñòâî åå ñòðîê íà ïîäìíîæåñòâà M1 = {1, 2} è M2 ={3, 4}, à ìíîæåñòâî ñòîëáöîâ − íà ïîäìíîæåñòâà N1 = {1, 2} è N2 ={3, 4}. Îïðåäåëèì äâóõøàãîâóþ èãðó ñ ïîëíîé èíôîðìàöèåé.Øàã 1. Ñíà÷àëà ïåðâûé èãðîê âûáèðàåò íîìåð α ∈ {1, 2} ìíîæåñòâàMα , èç êîòîðîãî îí áóäåò íà âòîðîì øàãå äåëàòü âûáîð ñòðîêè ìàòðèöûA. Çàòåì âòîðîé èãðîê, çíàÿ α, âûáèðàåò íîìåð β ∈ {1, 2} ìíîæåñòâà Nβ ,èç êîòîðîãî îí áóäåò íà âòîðîì øàãå âûáèðàòü íîìåð ñòîëáöà ìàòðèöûA.Øàã 2. Ïåðâûé èãðîê âûáèðàåò íîìåð ñòðîêè i ∈ Mα , çíàÿ α, β , çàòåìâòîðîé èãðîê âûáèðàåò íîìåð ñòîëáöà j ∈ Nβ , çíàÿ α, β, i.Âûèãðûø ïåðâîãî èãðîêà ðàâåí aij .Äëÿ ðåøåíèÿ çàäà÷è âîñïîëüçóåìñÿ ïîçèöèîííîé ôîðìîé èãðû, êîòîðóþ áóäåì îòîáðàæàòü íà ïëîñêîñòè â âèäå äåðåâà.79ÃËÀÂÀ I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛk 2 PPPP2PPP1 1k@@12@k J2Jkk32111kBB2 1BB3 25B2B72k11BB@@2@k31@3kJJ 2JBB31B4B43230k2kBBBB0 3JJ 4J2143 J4Jkk320kB2B0BBBB3BBB 4 1 B2B B2k3B4B33 2B4B5Ðèñ.