Диссертация (1149954), страница 19
Текст из файла (страница 19)
. . , sn ) = H i (p(s1 , . . . , sn )) è îïðåäå-ëåíèå äèíàìè÷åñêîé èãðû ñ èêñèðîâàííîé ïðîäîëæèòåëüíîñòüþ çàâåðøåíî.Çàìå÷àíèå3.1.4. Î÷åâèäíî, ó èãðû ñ êîíå÷íûìè ìíîæåñòâàìè óïðàâëåíèéU j (x, t) ìíîæåñòâîâîçìîæíûõ òðàåêòîðèé êîíå÷íî, à çíà÷èò, åé ñîîòâåòñòâóåò êîíå÷íàÿ èãðà â íîðìàëüíîéîðìå.Çàìå÷àíèå3.1.5. Ìîæíî ââåñòè ñòðàòåãèè ñ ïàìÿòüþsj : X T → U(X, T ), çàâèñÿùèå íå òîëüêîîò òåêóùåé ïîçèöèè, íî è îò ïðåäûäóùèõ ïîçèöèé. Èõ ìîæíî ñâåñòè ê ïîçèöèîííûì ñòðàòåãèÿì, ñîïîñòàâëÿÿ êàæäîé òðàåêòîðèè òî÷êó. ðà èãðû ïðè ýòîì ñòàíîâèòñÿ äåðåâîì,86à âûèãðûø òåðìèíàëüíûì. Íî êîëè÷åñòâî ïîçèöèîííûõ ñòðàòåãèé äëÿ îäíîãî èãðîêà ïîðÿäêàO(umx ),ãäåx = |X|,à êîëè÷åñòâî ñèòóàöèé â èãðå ïîðÿäêàæå ñòðàòåãèé ñ ïàìÿòüþ ïîðÿäêàO(uxm),O(umnx ).à êîëè÷åñòâî ñèòóàöèé O(unxmÊîëè÷åñòâî),÷òî ãîðàç-äî áîëüøå.
Ïîýòîìó ñâåäåíèå ãðàà èãðû ê äåðåâó, áóäó÷è îðìàëüíî ïðàâèëüíûì, ìîæåòñèëüíî óñëîæíèòü ðåøåíèå èãðû.Ïîðÿäîê õîäîâ â äèíàìè÷åñêîé èãðå îïðåäåëÿåòñÿ óíêöèåé27, ìîæíî ñ÷èòàòü, ÷òîðåêóðñèâíàÿ èãðà,i(x, t). Ñîãëàñíî îïðåäåëåíèþâ êîòîðîé âñå èãðîêè õîäÿò îäíîâðåìåííî ýòîñàìûé îáùèé ñëó÷àé.  äàííîé ðàáîòå, åñëè íå îãîâîðåíî îáðàòíîå, ðå÷ü èäåò î ðåêóðñèâíûõèãðàõ.Îïðåäåëåíèå 30. Ïîî÷åðåäíàÿ äèíàìè÷åñêàÿ èãðàèíîðìàöèåé ) ýòî äèíàìè÷åñêàÿ èãðà, â êîòîðîéòîëüêî îäèí èãðîê).  ýòîì ñëó÷àå,|i(x, t)| = 1èãðîé ñ ïîëíîé(ò.å., íà êàæäîì øàãå õîäèòU j (x, t) = U(x, t).Îïðåäåëåíèå 31. Âðåìåííîé ïîðÿäîê õîäîâîò[57℄ (åå åùå íàçûâàþò ýòî ïîðÿäîê õîäîâi(x, t),çàâèñÿùèé òîëüêît.Çàìå÷àíèå3.1.6. Êàê ïîêàçàíî â [67℄, ëþáóþ ïîî÷åðåäíóþ èãðó ìîæíî ñâåñòè ê èãðå ñ âðå-ìåííûì ïîðÿäêîì õîäîâ.Îïðåäåëåíèå 32.
Êîìáèíàòîðíàÿ èãðà[68℄ ýòî ïîî÷åðåäíàÿ èãðà êà÷åñòâà (ò.å. àíòàãî-íèñòè÷åñêàÿ èãðà ñ âûèãðûøàìè èç ìíîæåñòâà{−1, 1})ñ âðåìåííûì ïîðÿäêîì õîäîâ.Êàê ïîêàçàíî â ýòîì ðàçäåëå, ëþáàÿ èãðà ñâîäèòñÿ ê ñåðèè êîìáèíàòîðíûõ èãð (ïðè÷åìêîíå÷íàÿ èãðà ê êîíå÷íîé ñåðèè).3.1.2Ïðèíöèïû îïòèìàëüíîñòè â äèíàìè÷åñêîé èãðåÁóäåì îïðåäåëÿòü ïðèíöèïû îïòèìàëüíîñòè ïî îáðàçöó [51℄.Îïðåäåëåíèå33.Äèíàìè÷åñêèé(N, X, T, x0 , (D, U, π), i, (U j (x, t))nj=1 , S),âðåìåíè èãðûX × T,ïîðÿäêà õîäîâi(x, t),èãðîâîéìåõàíèçìMñîñòîÿùèé èç ìíîæåñòâà èãðîêîâíà÷àëüíîé ïîçèöèèx0 ,ìíîæåñòâ óïðàâëåíèéN,U i (x, t)è ìíîæåñòâ ñòðàòåãèé(H j )nj=1 .íàáîðïðîñòðàíñòâà-óïðàâëÿåìîé äèíàìè÷åñêîé ñèñòåìû(D, U, π),S.Òàêèì îáðàçîì, äèíàìè÷åñêàÿ èãðà ýòî äèíàìè÷åñêèé èãðîâîé ìåõàíèçìäîáàâëåíû óíêöèè âûèãðûøàýòîM , ê êîòîðîìóÊàê äèíàìè÷åñêîé èãðå ñîîòâåòñòâóåò èãðà â íîð-ìàëüíîé îðìå, òàê è äèíàìè÷åñêîìó èãðîâîìó ìåõàíèçìó ñîîòâåòñòâóåò èãðîâîé ìåõàíèçìâ íîðìàëüíîé îðìå (game form) [19℄.87Îïðåäåëåíèå 34.õàíèçìîìM,îòîáðàæåíèåÏóñòü äàíî ñåìåéñòâî äèíàìè÷åñêèõ èãðóäîâëåòâîðÿþùèõ òåì èëè èíûì óñëîâèÿì.G(M)ñ îäíèì è òåì æå ìå-Ïðèíöèï îïòèìàëüíîñòè ýòîφ : G(M) → 2S(M ) , ñîïîñòàâëÿþùåå êàæäîé èãðå íåêîòîðîå ìíîæåñòâî ñèòóàöèé.Îïðåäåëåíèå 35.
Ñòàòè÷åñêèé ïðèíöèï îïòèìàëüíîñòè ýòî ïðèíöèï îïòèìàëüíîñòè,êîòîðûé âûòåêàåò èç ñâåäåíèÿ äèíàìè÷åñêîé èãðû ê ÈÍÔ.Ïðèìåðû ñòàòè÷åñêèõ ïðèíöèïîâ îïòèìàëüíîñòè â äèíàìè÷åñêîé èãðå:ðàâíîâåñèå, ε-ðàâíîâåñèå, (ñëàáîå) Ïàðåòî-îïòèìàëüíîå ðåøåíèå, ñèëüíîå ðàâíîâåñèå, (ñëàáîå) êîàëèöèîííîå ðàâíîâåñèå.Áóäåì îïðåäåëÿòü êîàëèöèîííîå ðàâíîâåñèå êàê ÷àñòíûé ñëó÷àé ðàâíîâåñèÿ â êîàëèöèîííîé èãðå [9℄:Îïðåäåëåíèå 36.àöèÿs∗Ïóñòü â ÈÍÔíàçûâàåòñÿΓçàäàíî ìíîæåñòâî äîïóñòèìûõ êîàëèöèéêîàëèöèîííûì ðàâíîâåñèåìëþáîé äîïóñòèìîé êîàëèöèèd ∈ Dñòðàòåãèé êîàëèöèè íåâûãîäíî: áóäåì îáîçíà÷àòü ýòîëþáîå åå îòêëîíåíèåHu (s∗ ||sd) 6> Hu (s∗ ).s∗ ||sd,ãäåD ⊆ 2N .s∗ ∈ ED ,sd = (si )i∈dÑèòó-åñëè äëÿ âåêòîð×àñòíûå ñëó÷àè êîàëèöèîííîãî ðàâíîâåñèÿ:•ðàâíîâåñèå ïî Íýøó:D = {{1}, {2}, . .
. {n}};• k -ðàâíîâåñèå: D = {C | |C| ≤ k}•ñèëüíîå ðàâíîâåñèå:•îïòèìóì Ïàðåòî:D = 2ND = {N}.Òàêèì îáðàçîì, ñòðàòåãè÷åñêèå èãðû ñ çàäà÷åé íàõîæäåíèÿ êîàëèöèîííûõ ðàâíîâåñèéîáîáùàþò íåñòðàòåãè÷åñêèå çàäà÷è îïòèìèçàöèè, â êîòîðûõ íóæíî íàéòè îïòèìóìû Ïàðåòî.3.1.3Îïðåäåëåíèå ïîäûãðû â ðàçâåðíóòîé îðìåÄëÿ óïðàâëÿåìîé äèíàìè÷åñêîé ñèñòåìû ìîæíî åñòåñòâåííûì îáðàçîì îïðåäåëèòü ïîäñèñòåìó, íà÷èíàþùóþñÿ ñ íåêîòîðîãî ìîìåíòà âðåìåíè.Îïðåäåëåíèå 37.XÏóñòü äàíà óïðàâëÿåìàÿ äèíàìè÷åñêàÿ ñèñòåìàñ äèñêðåòíûì âðåìåíåìâðåìåíèt ∈ TT = {1, 2, .
. . , m}.Òîãäàïîäñèñòåìà,(D, U, π)ñîîòâåòñòâóþùàÿ ìîìåíòó ýòî óïðàâëÿåìàÿ äèíàìè÷åñêàÿ ñèñòåìà íà ìíîæåñòâåìîìåíòîâ âðåìåíèT ′ = {t, t + 1, . . . , m},îïðåäåëÿåìàÿ ñóæåíèåìíà ìíîæåñòâåDXñ ìíîæåñòâîìíà ìíîæåñòâîX × T ′.88Çàìå÷àíèå3.1.7. Øêàëà âðåìåíèT ′ = {t, t + 1, . . . , m}èçîìîðíà øêàëåíî äëÿ óäîáñòâà åå ðàññìàòðèâàþò, èìåííî íà÷èíàÿ ñ ìîìåíòà{1, . .
. m − t + 1},t.Îïðåäåëåíèå 38. Èãðîâîé ïîäìåõàíèçì â ðàçâåðíóòîé îðìåäëÿ èãðîâîãî ìåõàíèçìàM = (X, T, x0 , (D, U, π), i, (U j )nj=1 , S), ýòî èãðîâîé ìåõàíèçìM(x′ , t′ ) = (X, T ′ , x′ , (D′ , U ′ , π ′), i′ , (U ′ j )nj=1, S′ ),• (D′ , U ′ , π ′ )(x′ , t′ )îïðåäåëÿåìûé òî÷êîéãäå ñóæåíèå óïðàâëÿåìîé äèíàìè÷åñêîé ñèñòåìû(D, U, π)íà øêàëó âðåìåíèT ′ = T ∩ [t′ ; m];• i′ ñóæåíèå óíêöèè• U j (x, t)• S′ =iX × T ′;íà ìíîæåñòâîîïðåäåëåíû òåïåðü òîëüêî ïðèQj∈NS′j ,ãäåt ≥ t′ ;S′j = Sj ∩ Sj (x′ , t′ ,ãäåSj (x′ , t′ )(x′ , t′ ),ãî èãðîêà, îïðåäåëÿåìûõ, íà÷èíàÿ ñ òî÷êè{s : p(x′ , xm ) → U j (xm , tl(p) )}xm ∈X ,èç íà÷àëüíîé òî÷êèÇàìå÷àíèåx′ãäåp(x′ , xm )ðàçâåðíóòûé èãðîâîé ìåõàíèçìΓ(x′ , t′ ).òî÷êîé(x′ , t′ )äëÿ òî÷êè ýòî èãðà(x′ , t′ ), H ′Çàìå÷àíèå(M ′ , (H ′j )),M′ãäå ñóæåíèå ñòðàòåãèèsjíà ïîä-S′j = {sj (x′ , t′ ) | sj ∈ Sj }[67℄ äëÿ èãðû(M, (H j )),îïðåäåëÿåìàÿ èãðîâîé ïîäìåõàíèçì â ðàçâåðíóòîé îðìåM ′.3.1.9.
Íåñìîòðÿ íà ïîõîæåå íàçâàíèå, ïîäûãðà â ðàçâåðíóòîé îðìå ýòî ñî-Ïîäûãðàñóæåííûìè ìíîæåñòâàìè ñòðàòåãèé, ò.å. èãðàS′ =sj (x′ , t′ ) íåêîòîðàÿ óíêöèÿ âûèãðûøà äëÿ ïîäìåõàíèçìàâñåì íå òî æå ñàìîå, ÷òî ïðîñòî ïîäûãðà!ãäåò.å. ñåìåéñòâ îòîáðàæåíèé âèäàxm .Òàêèì îáðàçîì,Îïðåäåëåíèå 39.
Ïîäûãðà â ðàçâåðíóòîé îðìåj- ìíîæåñòâî òðàåêòîðèé, âûõîäÿùèõè çàêàí÷èâàþùèõñÿ â òî÷êå3.1.8.  äàëüíåéøåì áóäåì îáîçíà÷àòü ìíîæåñòâî âñåõ ñòðàòåãèéQj∈NS′j ,S′j ⊆ Sj .(â íîðìàëüíîé îðìå) ýòî ïðîñòî èãðà ñΓ′ = (N, X, x0 , (D, U, π), i, {U j }j∈N , S′ , {H j }j∈N ),Ïîäûãðà â ðàçâåðíóòîé îðìå (sub-extensive form game [67℄)ÿâëÿåòñÿ ïîäûãðîé ïðè ïðèâåäåíèè ê íîðìàëüíîé îðìå òîëüêî â ñëó÷àå òåðìèíàëüíîãî âûèãðûøà. Ïîäûãðà èçîìîðíà íåêîòîðîé ïîäûãðå â ðàçâåðíóòîé îðìå òîëüêî â òîì ñëó÷àå,êîãäà ïîäìíîæåñòâà ñòðàòåãèé îïðåäåëÿþòñÿ óñëîâèåì ïðîõîæäåíèÿ ÷åðåç òî÷êó(x, t).Àíàëîãè÷íî äèíàìè÷åñêèì çàäà÷àì îïòèìèçàöèè, â äèíàìè÷åñêèõ èãðàõ ìîæíî îïðåäåëèòü ñåìåéñòâî îïòèìèçàöèîííûõ çàäà÷ è åñòåñòâåííîå ñåìåéñòâî çàäà÷:Îïðåäåëåíèå 40.Ïóñòü äàí èãðîâîé ìåõàíèçìâåòñòâóþùàÿ äèíàìè÷åñêàÿ èãðàèãðûøàj -ãîìåõàíèçìóM(M, (H j ),ãäåx0M = (X, x0 , (D, U, π), i, (U j )nj=1 , S) íà÷àëüíàÿ ïîçèöèÿ,èãðîêà íà ìíîæåñòâå òðàåêòîðèé.
Òîãäà ýòî óíêöèè âûèãðûøàH(x,t)äëÿ âñåõ ïîäìåõàíèçìîâ, çàâèñÿùèõ îò òî÷åêHjñåìåéñòâî çàäà÷, óíêöèÿ âû-ñîîòâåòñòâóþùèõè ïðèíöèïû îïòèìàëüíîñòè(x, t).è ñîîò-φ(x,t) ,çàäàííûå89Îïðåäåëåíèå 41.íûì âûèãðûøåìòèìàëüíîñòèÏóñòü çàäàíà äèíàìè÷åñêàÿ èãðàH j (x1 , x2 . .
. xn ) = f1 (x1 ) ∗ f2 (x2 ) ∗ · · · ∗ fn (xn )φ. Òîãäà åñòåñòâåííîå ñåìåéñòâî çàäà÷îðìå, â êîòîðûõ âûèãðûø îïðåäåëÿåòñÿ òàê:fn (xn ),Γ = (M, (H j )) ñ îáîáùåííûì èíòåãðàëüè ñòàòè÷åñêèì ïðèíöèïîì îï- ýòî ñåìåéñòâî ïîäûãð â ðàçâåðíóòîéf(x,t) (x, xt+1 , . . . xn ) = ft (x) ∗ ft+1 (xt+1 ) ∗ · · · ∗è äëÿ âñåõ ïîäûãð â ðàçâåðíóòîé îðìå èñïîëüçóåòñÿ òîò æå ñòàòè÷åñêèé ïðèíöèïφ.3.1.4Äèíàìè÷åñêàÿ óñòîé÷èâîñòü (êîàëèöèîííûõ) ðàâíîâåñèé â äèíàìè÷åñêîé èãðå è ïðèíöèï ÁåëëìàíàÍàïîìíèì îïðåäåëåíèå äèíàìè÷åñêîé óñòîé÷èâîñòè äëÿ äèíàìè÷åñêèõ èãð [51℄. Äèíàìè÷åñêàÿ óñòîé÷èâîñòü äëÿ èãð, òàê æå, êàê è äëÿ ìíîãîêðèòåðèàëüíûõ ïðèíöèïîâ îïòèìàëüíîñòè, èìååò ñìûñë íå äëÿ îäíîé çàäà÷è (ò.å., èãðû è ïðèíöèïà îïòèìàëüíîñòè), à ëèøü äëÿñåìåéñòâà çàäà÷.Îïðåäåëåíèå 42.Ïóñòü äëÿ èãðîâîãî ìåõàíèçìàj(M(x,t) , (H(x,t)), φ(x,t) )íà:ñèòóàöèÿjs ∈ φ(M(x0 , t0 ), H(x).0 ,t0 )s,t ≥ ti ,ÑèòóàöèÿsíàçûâàåòñÿΓ(x(ti ), ti ),s(x(ti ), ti ) = (s1 (x(ti ), ti ), .
. . sn (x(ti ), ti )),îïòèìàëüíà:Îïðåäåëåíèå 43.ìåéñòâà çàäà÷ñîîòâåòñòâóþùåãî ñåìåéñòâà çàäà÷ðåàëèçóþùàÿ òðàåêòîðèþâî âñåõ ïîäûãðàõ â ðàçâåðíóòîé îðìåòóàöèÿM,(x(t1 ), x(t2 ), . . . x(tn )),îïòèìàëü-(ñëàáî) äèíàìè÷åñêè óñòîé÷èâîé,åñëè÷åðåç êîòîðûå ïðîõîäèò òðàåêòîðèÿ, ñè-ñóæàþùàÿ ñòðàòåãèè íà ìíîæåñòâî òî÷åê ñjs(x(ti ), ti ) ∈ φ(M(x(ti ), ti ), H(x(t).i ),ti )Áóäåì ãîâîðèòü, ÷òî äëÿ èãðîâîãî ìåõàíèçìàj(M(x,t) , (H(x,t))), φ(x,t)(ñëàáî) äèíàìè÷åñêè óñòîé÷èâûì,âûïîëíÿåòñÿMè ñîîòâåòñòâóþùåãî ñå-ïðèíöèï Áåëëìàíàåñëè âñÿêàÿ ñèòóàöèÿèëè ÷òî îíî ÿâëÿåòñÿs = (s1 , .
. . sn ) ∈ φ(M, (H j ))â ïîçè-öèîííûõ ñòðàòåãèÿõ ñëàáî äèíàìè÷åñêè óñòîé÷èâà.Çàìå÷àíèå3.1.10. Îáû÷íî, ãîâîðÿò î äèíàìè÷åñêè óñòîé÷èâîì ïðèíöèïå îïòèìàëüíîñòè [51℄.Íî íàäî ïîíèìàòü, ÷òî ïî óìîë÷àíèþ âñåãäà ïðåäïîëàãàåòñÿ íåêîòîðîå ñåìåéñòâî óíêöèéâûèãðûøà äëÿ âñåõ ïîäìåõàíèçìîâ. Êàê ìû óæå âèäåëè, ìîæíî òàê ïîäîáðàòü óíêöèèâûèãðûøà, ÷òî äàæå îáû÷íûé ïðèíöèï îïòèìàëüíîñòè â çàäà÷å ñ îäíèì èãðîêîì íå áóäåòäèíàìè÷åñêè óñòîé÷èâ.Ïîêàæåì òåïåðü, ÷òî äëÿ åñòåñòâåííîãî ñåìåéñòâà çàäà÷ îñíîâíûå ïðèíöèïû îïòèìàëüíîñòè â äèíàìè÷åñêèõ èãðàõ äèíàìè÷åñêè óñòîé÷èâû:Òåîðåìà 12(î äèíàìè÷åñêîé óñòîé÷èâîñòè ðàâíîâåñèÿ).Åñëè Rj ñòðîãî ñëåâà óïîðÿ-äî÷åííàÿ ïîëóãðóïïà, H j (x) = f1j (x1 ) ∗ · · · ∗ fnj (xn ) îáîáùåííûé èíòåãðàëüíûé âûèãðûø90è φ = NE ðàâíîâåñèå ïî Íýøó, òî äëÿ åñòåñòâåííîãî ñåìåéñòâà çàäà÷ âûïîëíÿåòñÿïðèíöèï îïòèìàëüíîñòè Áåëëìàíà (ò.å., îíî ñëàáî äèíàìè÷åñêè óñòîé÷èâî).Äîêàçàòåëüñòâî.àññìîòðèì ïðîèçâîëüíóþ ðàâíîâåñíóþ ñèòóàöèþñòâóþùóþ åé îïòèìàëüíóþ òðàåêòîðèþp(s) = h = (x′1 , x′2 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
