Диссертация (1149954), страница 20
Текст из файла (страница 20)
. . x′n ).åò, ÷òî íà íåé äîñòèãàåòñÿ ìàêñèìóì âûðàæåíèÿñòðàòåãèésjêàæäîãî èãðîêàíà÷èíàÿ ñ òî÷êèíèâ ñòðàòåãèþsjj -ãî(x, t).′è ñîîòâåò-Åå îïòèìàëüíîñòü îçíà÷à-f1j (x1 ) ∗ f2j (x2 ) ∗ · · · ∗ fnj (xn )ïî ìíîæåñòâój.àññìîòðèì òåïåðü ëþáóþ åå ïîäòðàåêòîðèþìèçèðóåò âûèãðûøs ∈ NE(Γ)èãðîêà(x′t , x′t+1 , . . . x′n )ftj (xt ) ∗ · · · ∗ fnj (xn )è äîêàæåì, ÷òî îíà ìàêñè-ïî âñåì åãî ñòðàòåãèÿì, îïðåäåëåííûì,Äåéñòâèòåëüíî, ïðåäïîëîæèì ïðîòèâíîå: èãðîêójâûãîäíî, ïðèìå-, îòêëîíèòüñÿ îò ðàâíîâåñíîé ñòðàòåãèè íà÷èíàÿ ñ ìîìåíòàçíà÷èò, ÷òî ñóùåñòâóåò èíàÿ ïîäòðàåêòîðèÿt′ ≥ t.Ýòî(xt , x′′t+1 , .
. . x′′n ), íà êîòîðîé äîñòèãàåòñÿ çíà÷åíèåftj (x′′t )∗· · ·∗fnj (x′′n ) > ftj (x′t )∗· · ·∗fnj (x′n ). Ýòî, ïî ñòðîãîñòè ïîëóãðóïïû âûèãðûøåé ñëåâà, îçíà÷àåò, ÷òîò.å.jjf1j (x′1 )∗· · ·∗ftj (x′t )∗ft+1(x′′t+1 )∗· · ·∗fnj (x′′n ) > f1j (x′1 )∗· · ·∗ftj (x′t )∗ft+1(x′t+1 )∗· · ·∗fnj (x′n ),′H j (s||sj ) > H j (s),÷òî ïðîòèâîðå÷èò ðàâíîâåñíîñòè ïî Íýøó â èñõîäíîé èãðåΓ.jÑëåäñòâèå 12.1. Åñëè Rj óïîðÿäî÷åííàÿ ãðóïïà è H j (x) = f1 (x1 ) ∗ · · ·∗ fnj (xn ) îáîáùåí-íûé èíòåãðàëüíûé âûèãðûø, òî äëÿ åñòåñòâåííîãî ñåìåéñòâà çàäà÷ âûïîëíÿåòñÿ ïðèíöèïîïòèìàëüíîñòè Áåëëìàíà.Ñëåäñòâèå 12.2.
Åñëè Rj ïðîèçâîëüíàÿ óïîðÿäî÷åííàÿ ïîëóãðóïïà è H j (x) = H j (xn ) òåðìèíàëüíûé âûèãðûø, òî äëÿ åñòåñòâåííîãî ñåìåéñòâà çàäà÷ âûïîëíÿåòñÿ ïðèíöèïîïòèìàëüíîñòè Áåëëìàíà.Òåîðåìà 13(î äèíàìè÷åñêîé óñòîé÷èâîñòè êîàëèöèîííîãî ðàâíîâåñèÿ).Åñëè Rj ñòðîãîñëåâà óïîðÿäî÷åííàÿ ïîëóãðóïïà, H j (x) = f1j (x1 ) ∗ · · · ∗ fnj (xn ) îáîáùåííûé èíòåãðàëüíûéâûèãðûø è φ = ED (ñëàáîå) êîàëèöèîííîå ðàâíîâåñèå, ãäå D ìíîæåñòâî êîàëèöèé, òîäëÿ åñòåñòâåííîãî ñåìåéñòâà çàäà÷ âûïîëíÿåòñÿ ïðèíöèï îïòèìàëüíîñòè Áåëëìàíà.Äîêàçàòåëüñòâî.Äîêàçûâàåòñÿ àíàëîãè÷íî óñòîé÷èâîñòè ðàâíîâåñèÿ ïî Íýøó. Åäèíñòâåí-íàÿ ðàçíèöà çàêëþ÷àåòñÿ â òîì, ÷òî âìåñòî ñðàâíåíèÿ âûèãðûøåéíÿåòñÿ ñðàâíåíèå âåêòîðîâ âûèãðûøåéjjH(x,t)(s) > H(x,t)(s′ ) âûïîë-j1jkj1jk(H(x,t)(s), . .
. H(x,t)(s)) > (H(x,t)(s′ ), . . . H(x,t)(s′ )),ãäå> ïîýëåìåíòíûé ÷àñòè÷íûé ïîðÿäîê íà ìíîæåñòâå âåêòîðîâ, ñëåäóþùèé èç íåñòðîãîãî ïîðÿäêà≥ïî êàæäîìó ýëåìåíòó è íàëè÷èÿ ñòðîãîãî ïîðÿäêà>õîòÿ áû ïî îäíîìó ýëåìåíòó.Íåñòðîãèé ïîðÿäîê ïî âñåì ýëåìåíòàì ñîõðàíÿåòñÿ â óïîðÿäî÷åííîé ïîëóãðóïïå, ñòðîãèéïîðÿäîê ïî îäíîìó ýëåìåíòó ñîõðàíÿåòñÿ â ñòðîãî ñëåâà óïîðÿäî÷åííîé ïîëóãðóïïå.Äëÿ ñëàáîãî êîàëèöèîííîãî ðàâíîâåñèÿ> ïîýëåìåíòíûé ÷àñòè÷íûé ïîðÿäîê íà ìíî-æåñòâå âåêòîðîâ, ñëåäóþùèé èç íàëè÷èÿ ñòðîãîãî ïîðÿäêà> ïî êàæäîìó ýëåìåíòó.Ñòðîãèé91ïîðÿäîê ïî êàæäîìó ýëåìåíòó ñîõðàíÿåòñÿ â ñòðîãî ñëåâà óïîðÿäî÷åííîé ïîëóãðóïïå.Ñëåäñòâèå 13.1.
Äëÿ (ñëàáîé) îïòèìàëüíîñòè ïî Ïàðåòî òàêæå âûïîëíÿåòñÿ ïðèíöèïÁåëëìàíà.Äëÿ ïðîèçâîëüíûõ óïîðÿäî÷åííûõ ïîëóãðóïï áåç ñâîéñòâà ñòðîãîñòè ñëåâà íå âûïîëíÿåòñÿ ïðèíöèï îïòèìàëüíîñòè Áåëëìàíà äàæå äëÿ èãðû ñ îäíèì èãðîêîì: ñóùåñòâóþò îïòèìàëüíûå òðàåêòîðèè, êîíå÷íûå ó÷àñòêè êîòîðûõ íåîïòèìàëüíû. Ïðîñòîé ïðèìåð ñì. âðàçäåëå, ïîñâÿùåííîì ìíîãîêðèòåðèàëüíûì çàäà÷àì.Ñèëüíàÿ äèíàìè÷åñêàÿ óñòîé÷èâîñòü è äèíàìè÷åñêàÿ ñîâìåñòèìîñòü â èãðàõ îïðåäåëÿþòñÿ áîëåå ñëîæíî, ÷åì â çàäà÷àõ ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè [51℄. Íå áóäåì ðàññìàòðèâàòü èõ â íàñòîÿùåé ðàáîòå, èáî äàæå îïòèìàëüíîñòü ïî Ïàðåòî (à çíà÷èò, è êîàëèöèîííîåðàâíîâåñèå) â áîëüøèíñòâå ñëó÷àåâ íå óäîâëåòâîðÿåò ýòèì óñëîâèÿì.3.1.5Òåîðåìà î ðåêóððåíòíûõ ñîîòíîøåíèÿõ äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ äëÿ íàõîæäåíèÿ àáñîëþòíûõ ðàâíîâåñèé â äèíàìè÷åñêîé èãðåÄëÿ íàõîæäåíèÿ îïòèìàëüíûõ ðåøåíèé ñ ïîìîùüþ ðåêóððåíòíûõ ñîîòíîøåíèé äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ òàê æå, êàê è â ñëó÷àå ìíîãîêðèòåðèàëüíûõ çàäà÷, òðåáóåòñÿ ñâîéñòâî ïîçèöèîííîé äèíàìè÷åñêîé óñòîé÷èâîñòè, áîëåå ñèëüíîå, ÷åì îáû÷íàÿ äèíàìè÷åñêàÿóñòîé÷èâîñòü.Îïðåäåëåíèåçàäà÷44.j(M(x,t) , (H(x,t)), φ(x,t) )jφ(M(x0 , t0 ), H(x).0 ,t0 )ñèòóàöèåé),öèÿÏóñòüäëÿèãðîâîãîñèòóàöèÿÑèòóàöèÿssìåõàíèçìàâíàçûâàåòñÿïîçèöèîííûõñîîòâåòñòâóþùåãîñòðàòåãèÿõñåìåéñòâàîïòèìàëüíà:s∈ïîçèöèîííî äèíàìè÷åñêè óñòîé÷èâîé (ÏÄÓ-åñëè âî âñåõ ïîäûãðàõ â ðàçâåðíóòîé îðìå(s1 (x, tk ), .
. . sn (x, tk )),Γ(x, tk )ñîîòâåòñòâóþùàÿ ñèòóà-ñóæàþùàÿ ñòðàòåãèè íà ìíîæåñòâî òî÷åê ñçíà÷èò, è ïîçèöèîííî äèíàìè÷åñêè óñòîé÷èâà):Çàìå÷àíèåM,js ∈ φ(M(x, tk ), H(x,t).k)t ≥ tk ,îïòèìàëüíà (à3.1.11.  ýòîì îïðåäåëåíèè ïîäûãðû â ðàçâåðíóòîé îðìå â áîëüøèíñòâå ñëó÷à-åâ íå èçîìîðíû íèêàêèì ïîäûãðàì â íîðìàëüíîé îðìå, ïîñêîëüêó èñêîìàÿ ñèòóàöèÿ äëÿáîëüøèíñòâà ïîäûãð â ðàçâåðíóòîé îðìåΓ(x,tk )âîîáùå íå ïîïàäàåò â ìíîæåñòâî äîïóñòè-ìûõ, åñëè ñîîòâåòñòâóþùàÿ òðàåêòîðèÿ íå ïðîõîäèò ÷åðåç òî÷êóÏóñòü äàíî ñåìåéñòâî çàäà÷(M, (H j )(x,t) , φ),íàìè÷åñêèé èãðîâîé ìåõàíèçì, àφãäå(x, tk ).M = (X, x0 , (D, U, π), i, (U j )nj=1 , S) äè- ñòàòè÷åñêèé ïðèíöèï îïòèìàëüíîñòè. Îïðåäåëèì ðå-êóððåíòíóþ ñèòóàöèþ äëÿ èãð àíàëîãè÷íî îïðåäåëåíèþ äëÿ äèíàìè÷åñêèõ ïðèíöèïîâ îïòèìàëüíîñòè:92Îïðåäåëåíèå 45.
åêóððåíòíàÿ ñèòóàöèÿçàäàþùèõ óïðàâëåíèåëþáûõu, ýòî íàáîð ïîçèöèîííûõ ñòðàòåãèé(s1 , . . . sn ),óäîâëåòâîðÿþùåå ñëåäóþùèì ðåêóððåíòíûì ñîîòíîøåíèÿì: äëÿx ∈ X, t ∈ T1u(x, t) ∈ φu (H(x,t+1)(p(x, u|{u(x′, t′ )}x∈X,n′ ′t′ >t )), . . . , H(x,t+1) (p(x, u|{u(x , t )}x′ ∈X, t′ >t )))...1nu(x, m − 1) ∈ φu (H(x,m)(p(x, u)), . . . H(x,m)(p(x, u)))ãäå| çíàê êîíêàòåíàöèè çíà÷åíèé äëÿ âðåìåíèìåíè.φutè çíà÷åíèé äëÿ áîëüøèõ ìîìåíòîâ âðå- ñòàòè÷åñêèé ïðèíöèï îïòèìàëüíîñòè â èãðå â íîðìàëüíîé îðìå, îïðåäåëÿåìîéu.óïðàâëåíèÿìèÇàìå÷àíèå3.1.12. Òàêèì îáðàçîì, îïðåäåëåíèå ðåêóððåíòíîé ñèòóàöèè, êàê è ñëåäîâàëî îæè-äàòü, ðåêóððåíòíî. Óïðàâëåíèÿ èãðîêîâ â òî÷êåðàõ â ðàçâåðíóòîé îðìåàëãîðèòìøàãîâ, ïîëó÷àåìðèòì ñîñòîèò èçΓ(x′ ,t+1) , x′ ∈ D(x, t).m(x, t)Ïîñêîëüêó èãðà âñåãäà çàêàí÷èâàåòñÿ çàmâû÷èñëåíèÿ ðåêóððåíòíûõ óïðàâëåíèé â êîíå÷íîé èãðå.
Àëãî-øàãîâ è íà êàæäîì øàãå ðàáîòàåò òàê:1. Íà i-ì øàãå, çíàÿ ðåêóððåíòíûå óïðàâëåíèÿx∈Xîïðåäåëÿþòñÿ óïðàâëåíèÿìè â ïîäûã-âñå âîçìîæíûå óïðàâëåíèÿêîòîðûå äîñòàâëÿþò îïòèìóì èçu′ïðè âñåõu ∈ U(x, m − i)t > m − i,ïåðåáèðàåì äëÿ âñåõè âûáèðàåì èç íèõ òå óïðàâëåíèÿu∗ ,φu .2. Åñëè ìíîæåñòâî îïòèìàëüíûõ óïðàâëåíèéu∗ïóñòî, òî ðåêóððåíòíûõ ñèòóàöèé íå ñó-ùåñòâóåò.3. Ñîñòûêîâûâàåì êàæäîå îïòèìàëüíîå óïðàâëåíèåðåêóððåíòíûå óïðàâëåíèÿu′ jïðèu∗ñ óïðàâëåíèÿìèu′ j ,ïîëó÷àåìt = m − i.Åñëè çàäàíî åñòåñòâåííîå ñåìåéñòâî çàäà÷ è îïòèìàëüíûé âåêòîð âûèãðûøåé åäèíñòâåííûé, òî â êàæäûé ìîìåíò âðåìåíè â êàæäîé âåðøèíå õðàíèì îïòèìàëüíûé âåêòîðâûèãðûøåé â ïîäûãðå â ðàçâåðíóòîé îðìå, íà÷èíàþùåéñÿ â ýòîé âåðøèíå.
ÏóñòüKîïåðà-öèé ñëîæíîñòü àëãîðèòìà íàõîæäåíèÿ îïòèìóìà íà êàæäîì øàãå. Ïðè ýòîì íà êàæäîìøàãå êîïèðóåì âåêòîð ðàçìåðàO(xmn)n.Èòîãî ñëîæíîñòü O(xm(K + n)),ïðè ýòîì ïîíàäîáèòñÿïàìÿòè.  ÷àñòíîñòè, â àíòàãîíèñòè÷åñêîé èãðå ñëîæíîñòü íàõîæäåíèÿ ðàâíîâåñ-íîãî âûèãðûøà (óìíîæàåì íàm,O(xmu2 )äëÿ åñòåñòâåííîãî ñåìåéñòâà çàäà÷, à â îáùåì ñëó÷àåO(xm2 u2 )ïîòîìó ÷òî âûèãðûø ïðèõîäèòñÿ ñ÷èòàòü ïî âñåé òðàåêòîðèè).Åñëè îïòèìàëüíûé âåêòîð âûèãðûøåé íå åäèíñòâåííûé, òî àëãîðèòì óñëîæíÿåòñÿ.
Âýòîì ñëó÷àå íàäî õðàíèòü â êàæäîé âåðøèíå âåñü ñïèñîê îïòèìàëüíûõ âåêòîðîâ âûèãðûøåé â ïîäûãðå â ðàçâåðíóòîé îðìå, íà÷èíàþùåéñÿ â ýòîé âåðøèíå. Äëÿ ýòîãî ïîíàäîáèòñÿ93O(xmvn)ïàìÿòè, ãäåv êîëè÷åñòâî âûèãðûøåé. Åñëè æå ñåìåéñòâî çàäà÷ íå åñòåñòâåí-íîå, ïðèõîäèòñÿ â êàæäîé âåðøèíå õðàíèòü íå îïòèìàëüíûå âåêòîðû âûèãðûøåé, à îïòèìàëüíûå òðàåêòîðèè.
Äëÿ ýòîãî ïîíàäîáèòñÿÅñëè èç âåðøèíûO(xm2 v)ïàìÿòè.(a, t) ìîæíî ïåðåéòè â âåðøèíû (b1 , t + 1), . . . , (bw , t + 1), òî, çíàÿ ñïèñêèîïòèìàëüíûõ âûèãðûøåé â âåðøèíàõòèìàëüíûõ âûèãðûøåé â âåðøèíåa(b1 , t + 1), . . . , (bw , t + 1),ìîæíî ïîëó÷èòü ñïèñîê îï-ñëåäóþùèì îáðàçîì. Ìîæíî, ïîäñòàâèâ âñå âîçìîæíûåêîìáèíàöèè âûèãðûøåé, íàéòè â êàæäîé èç ïîëó÷èâøèõñÿ èãð îïòèìóìû. Ýòî ïîòðåáóåòO(v w K)âðåìåíè äëÿ êàæäîé âåðøèíû(a, t).Åñëè ñåìåéñòâî çàäà÷ íå åñòåñòâåííîå, ìû õðà-íèì íå âûèãðûøè, à òðàåêòîðèè, è ïîýòîìó ïîíàäîáèòñÿãäåw = maxx∈X,t∈T|D(x, t)|.Çíà÷èò, ïîòðåáóåòñÿO(v w mK)âðåìåíè â îáùåì ñëó÷àå,O(xmv w K) (O(xm2 v w K)â îáùåì ñëó÷àå)âðåìåíè äëÿ âñåé èãðû.
Íî â áîëüøèíñòâå ñëó÷àåâ åñòü áîëåå ýåêòèâíûå àëãîðèòìû.Íàïðèìåð, äëÿ åñòåñòâåííîãî ñåìåéñòâà çàäà÷ è ðàâíîâåñèé ïî Íýøó äåéñòâóåì òàê. àññìàòðèâàåìñèòóàöèès(a, t)(h1 , . . . , hn )ñèòóàöèÿO(un )ñèòóàöèé, êîòîðûì ñîîòâåñòâóþò ðàçíûå âåðøèíûâ êàæäîéâûáèðàåì ïîñëåäîâàòåëüíî êàæäûé èç âîçìîæíûõ âåêòîðîâ âûèãðûøåé(bj , t + 1),ÿâëÿåòñÿ ëèi = 1, .
. . , nè ïðîâåðÿåìè ïðîâåðÿåì: åñëè ýòîò âûèãðûø ðåàëèçóåòñÿ â âåðøèíås(a, t)(bj , t + 1),ðàâíîâåñíîé? Äëÿ ýòîãî áåðåì êàæäîãî èç èãðîêîâäëÿ êàæäîãî èç åãî îòêëîíåíèé, ñóùåñòâóåò ëè òàêîé âûèãðûø â ñîîòâåòñòâóþùåé âåðøèíå,êîòîðûé áóäåò íå áîëüøåíàì ïîòðåáóåòñÿO(nun+1v 2 )âûèãðûøåé â âåðøèíåÈòîãîhi .ïîëó÷àåìÏîäîáíàÿ ïðîâåðêà ïîòðåáóåòO(nuv)âðåìåíè, à çíà÷èò, âñåãîâðåìåíè íà ïðîâåðêó âñåõ ñèòóàöèé è âñåõ âîçìîæíûõ âåêòîðîâ(a, t).äëÿíàõîæäåíèÿðàâíîâåñíûõâûèãðûøåéâîâñåéèãðåâðåìÿO(xmnun+1 v 2 ).Òàêèì îáðàçîì, ìîæíî íàéòè îïòèìàëüíûå âûèãðûøè â ïîäûãðàõ â ðàçâåðíóòîé îðìå,íà÷èíàþùèõñÿ âî âñåõ âåðøèíàõ.
Çíàÿ èõ, ëåãêî âîññòàíîâèòü îïòèìàëüíûå òðàåêòîðèè èãðûè ïîëó÷èâøèåñÿ êîíå÷íûå ïîçèöèè (åñëè ñåìåéñòâî çàäà÷ íå åñòåñòâåííîå, òî îïòèìàëüíûåòðàåêòîðèè èçíà÷àëüíî õðàíÿòñÿ â âåðøèíàõ). Îïòèìàëüíûå ñèòóàöèè âîññòàíîâèòü ñëîæíåå, õîòÿ áû ïîòîìó, ÷òî èõ ìíîãî è ñðåäè íèõ ìíîãî ýêâèâàëåíòíûõ, äàþùèõ îäíó è òó æåòðàåêòîðèþ èãðû [31℄. Ïîýòîìó íå âñåãäà èìååò ñìûñë èñêàòü âñå îïòèìàëüíûå ñèòóàöèè.Ïî îïðåäåëåíèþ, ðåêóððåíòíàÿ ñòðàòåãèÿ â èãðå ÿâëÿåòñÿ ðåêóððåíòíîé è âî âñåõ ååïîäûãðàõ â ðàçâåðíóòîé îðìå.Óòâåðæäåíèå 3.1.2. Åñëè ïðèíöèï îïòèìàëüíîñòè φ îáëàäàåò ñâîéñòâîì óñòîé÷èâîñòèïî ïîäûãðàì (èãðîâàÿ àêñèîìà íåçàâèñèìîñòè îò ïîñòîðîííèõ àëüòåðíàòèâ), òî ïîçèöèîííî äèíàìè÷åñêè óñòîé÷èâàÿ ñèòóàöèÿ (åñëè îíà ñóùåñòâóåò), ðåêóððåíòíà.Äîêàçàòåëüñòâî.Àíàëîãè÷íî äîêàçàòåëüñòâó äëÿ ìíîãîêðèòåðèàëüíûõ çàäà÷.94Ïîñêîëüêó ïðàêòè÷åñêè âñå èíòåðåñíûå ïðèíöèïû îïòèìàëüíîñòè (êðîìå òàêèõ ïðèíöèïîâ, êàê âåêòîð Øåïëè) îáëàäàþò ñâîéñòâîì óñòîé÷èâîñòè ïî ïîäûãðàì, ìîæíî ñ÷èòàòü,÷òî ÏÄÓ-ñèòóàöèÿ âñåãäà ðåêóððåíòíà.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
