Диссертация (1149954), страница 22
Текст из файла (страница 22)
Êðîìå òîãî, â íåàíòàãîíèñòè÷åñêèõ èãðàõ ñóùåñòâóþòåùå è ñòðàòåãèè íàêàçàíèÿ [51℄. Òàêèì îáðàçîì, âîçíèêàåò âàæíàÿ ïðîáëåìà íàõîæäåíèÿâñåõ ðàâíîâåñèé.Rij , j 6= i äàííîé ðàáîòå ðàññìàòðèâàþòñÿ òîëüêî êîíå÷íûå èãðû. Ïóñòü óïîðÿäî-÷åííûå ïîëóãðóïïû, â êîòîðûõ îòíîøåíèå ïîðÿäêà ðàçâåðíóòî â ñòîðîíó, ïðîòèâîïîëîæíóþïîðÿäêó íàRi .Ââåäåì äëÿ êàæäîãî èãðîêààíòàãîíèñòè÷åñêóþ äèíàìè÷åñêóþ èãðóiè äëÿ êàæäîé ïîçèöèèΓi (x, t),(x, t)âñïîìîãàòåëüíóþîïðåäåëÿåìóþ òàê:Γi (x, t) = (M(x, t), (Hi,(x,t) , . . .
, Hi,(x,t) , . . . Hi,(x,t) ))Çäåñü èãðîâîé ìåõàíèçì òîò æå, ÷òî â ïîäûãðå â ðàçâåðíóòîé îðìå, íà÷èíàþùåéñÿñ ïîçèöèè(x, t),íî âûèãðûøè âñåõ èãðîêîâ, êðîìåi-ãî,ïðîòèâîïîëîæíû âûèãðûøóèãðîêà. Èíà÷å ãîâîðÿ, âñå îñòàëüíûå èãðîêè èãðàþò ïðîòèâèãðåΓi (x, t)âåðõíåå çíà÷åíèåVi (x, t)i-ãî.Çàìåòèì, êñòàòè, ÷òî âäëÿ i-ãî èãðîêà îïðåäåëÿåòñÿ îäíîçíà÷íî, â îòëè÷èå îòðàâíîâåñíîãî âûèãðûøà. Ýòîé èãðå ñîîòâåòñòâóåò ñåìåéñòâî èãð êà÷åñòâàHiv (x, t) =−1, Hi (x, t) ≯ vHi (x, t) > vïîëó÷èòü ñòðîãî áîëüøå v , à âñå îñòàëüíûåðàâíî−1.i-ãîèãðîêà ðàâíî1èãðîêè ýòîìó ñîïðîòèâëÿþòñÿ.
Êàê èçâåñòíî [57℄,òîãäà è òîëüêî òîãäà, êîãäàÀíàëîãè÷íî, åñëè çàäàíî ìíîæåñòâî êîàëèöèéìîæíî ââåñòè ñåìåéñòâî èãð êà÷åñòâài ∈ S,à çíàê>C,Vi (x, t) > v ,à èíà÷åòî äëÿ êàæäîé êîàëèöèèS∈CΓvS (x, t), òîëüêî v ýòî óæå âåêòîð âûèãðûøåé èãðîêîâîçíà÷àåò äîìèíèðîâàíèå âåêòîðîâ.Ïóñòü ñèòóàöèÿs = (s1 , . . .
sn )p(s) = (x(0), x(1), . . . x(m)).åþ óïðàâëåíèåΓvi (x, t), â êîòîðûõ. Ò.å. ýòî àíòàãîíèñòè÷åñêàÿ èãðà, â êîòîðîé i-é èãðîê ïûòàåòñÿ1,âåðõíåå çíà÷åíèå äëÿi-ãîu,â äèíàìè÷åñêîé èãðåΓ = (M, (Hi )) ïîðîæäàåòàññìîòðèì ñëåäóþùåå óñëîâèå íà ñèòóàöèþsòðàåêòîðèþè ïîðîæäàåìîåîïðåäåëÿåìîå èç âñïîìîãàòåëüíûõ èãð êà÷åñòâà, êîòîðîå áóäåì íàçûâàòüK-óñëîâèåì : äëÿ ëþáîãî ìîìåíòà âðåìåíè t äëÿ ëþáîãî õîäÿùåãî â ýòîò ìîìåíò èãðîêà(êîàëèöèè) i ∈ i(x, t) äëÿ ëþáîãî àëüòåðíàòèâíîãî õîäà u′ 6= ui (x(t), t) â èãðå Γvi i (x′ , t + 1)âåðõíåå çíà÷åíèå ðàâíî −1 è îñòàëüíûå èãðîêè (êîàëèöèè) èñïîëüçóþò âûèãðûøíóþ ñòðà-99òåãèþ.Çäåñüx′ = π(x(t), t)(s(x(t), t)||u′) ïîçèöèÿ, â êîòîðóþ ïîïàäåò èãðà â ðåçóëüòàòåàëüòåðíàòèâíîãî õîäà i-ãî èãðîêà (êîàëèöèè).i-éâåêòîð âûèãðûøåé), êîòîðûé ïîëó÷èòòåîðåìó, õàðàêòåðèçóþùóþÒåîðåìà 17vi = Hi,(x(t+1),t+1) ðàâíîâåñíûé âûèãðûø (èëèèãðîê (êîàëèöèÿ), åñëè íå îòêëîíèòñÿ.
Äîêàæåìâñå ðàâíîâåñèÿâ äèíàìè÷åñêîé èãðå:(íåîáõîäèìûå è äîñòàòî÷íûå óñëîâèÿ ðàâíîâåñèÿ).1. Åñëè ñèòóàöèÿ s (êî-àëèöèîííî) ðàâíîâåñíà è ðàâíîâåñèå äèíàìè÷åñêè óñòîé÷èâî, òî âûïîëíÿåòñÿ K óñëîâèå.2. Åñëè âûèãðûø îáîáùåííûé èíòåãðàëüíûé: Hi,(x′ ,t′ ) (x) = fi (x(t′ + 1), t′ + 1) ∗ fi (x(t′ +2), t′ + 2) ∗ · · · ∗ fi (x(m), m), è âûïîëíÿåòñÿ K -óñëîâèå, òî ñèòóàöèÿ s (êîàëèöèîííî)ðàâíîâåñíà.Äîêàçàòåëüñòâî.Äåéñòâèòåëüíî, ñèòóàöèÿêîãäà äëÿ ëþáîãî èãðîêà (êîàëèöèè)(âåêòîð âûèãðûøåé)Hiisÿâëÿåòñÿ ðàâíîâåñèåì òîãäà è òîëüêî òîãäà,äëÿ ëþáîãî îòêëîíåíèÿ åãî ñòðàòåãèèíå óâåëè÷èòñÿ. Ëþáîå îòêëîíåíèå èãðîêà (êîàëèöèè)s′iâûèãðûøi îïðåäåëÿåòñÿêàêu′ 6= ui (x(t), t)•Õðîíîëîãè÷åñêèå ïåðâîå îòêëîíåíèå•Ïîñëåäóþùèå îòêëîíåíèÿ â ìåõàíèçìåM(x′ , t + 1),â ìîìåíò âðåìåíètâ êîòîðûé ïåðåéäåò èãðà â ðåçóëü-òàòå ýòîãî îòêëîíåíèÿ.Äîêàçàòåëüñòâî òåîðåìû ñëåäóåò èç î÷åâèäíîé ëåììû:Ëåììà 17.1.
Íå ñóùåñòâóåò ñòðàòåãèè i-ãî èãðîêà (êîàëèöèè) â ïîäìåõàíèçìå M(x, t),äàþùåé åìó âûèãðûø áîëüøå v , òîãäà è òîëüêî òîãäà, êîãäà âûïîëíÿþòñÿ 2 óñëîâèÿ:1. Âåðõíåå çíà÷åíèå â èãðå Γvi (x, t) ðàâíî −1.2. Îñòàëüíûå èãðîêè èñïîëüçóþò âûèãðûøíóþ ñòðàòåãèþ â Γvi (x, t).Òåïåðü äîêàçàòåëüñòâî òåîðåìû î÷åâèäíî:1. Èç ñëàáîé äèíàìè÷åñêîé óñòîé÷èâîñòè ñëåäóåò, ÷òî ñèòóàöèÿ â ïîäûãðå â ðàçâåðíóòîéîðìåíåíèåΓ(x(t),t)ðàâíîâåñíà, à çíà÷èò,u′ 6= si (x(t), t)âûèãðûø, áîëüøèéèãðîêó (êîàëèöèè) íåâûãîäíî ëþáîå îòêëî- ò.å.
îí íå ìîæåò ãàðàíòèðîâàòü ñåáå â ìåõàíèçìåM(x′ , t + 1)vi .2. Åñëè ïðè ïåðåõîäå â ìåõàíèçìM(x′ , t + 1)âàòü ñåáå îòíîñèòåëüíûé âûèãðûøðûøài-ìóvi′ ,èãðîê (êîàëèöèÿ)iíå ìîæåò ãàðàíòèðî-áîëüøèé ðàâíîâåñíîãî îòíîñèòåëüíîãî âûèã-vi , òî åìó íåâûãîäíî îòêëîíÿòüñÿ â ìîìåíò t, èáî îí íå ñìîæåò ïîëó÷èòü áîëüøå100fi (x(0), 0) ∗ · · · ∗ fi (x(t), t) ∗ vi .Ýòî çíà÷èò, ÷òî íè îäíîìó èãðîêó (êîàëèöèè) íè â îäèíìîìåíò âðåìåíè íåâûãîäíî îòêëîíÿòüñÿ îò ñâîåé ñòðàòåãèè. Ñëåäîâàòåëüíî, ñèòóàöèÿ(êîàëèöèîííî) ðàâíîâåñíà.Çàìå÷àíèå3.1.15.
Åñëè âûèãðûø îáîáùåííûé èíòåãðàëüíûé íà ñòðîãî ñëåâà óïîðÿäî-÷åííîé ïîëóãðóïïå (â ÷àñòíîñòè, òåðìèíàëüíûé), òî íåîáõîäèìûå è äîñòàòî÷íûå óñëîâèÿðàâíîâåñèÿ ñîâïàäàþò.Çàìå÷àíèå3.1.16.  ïîî÷åðåäíîé äèíàìè÷åñêîé èãðå (ñ ïîëíîé èíîðìàöèåé) âìåñòî ñëîââåðõíåå çíà÷åíèå âåçäå ìîæíî ÷èòàòü ïðîñòî çíà÷åíèå, ïîñêîëüêó âî âñåõ âñïîìîãàòåëüíûõ àíòàãîíèñòè÷åñêèõ èãðàõ ñóùåñòâóåò ðàâíîâåñèå. Èãðû êà÷åñòâà â ýòîì ñëó÷àå ÿâëÿþòñÿêîìáèíàòîðíûìè èãðàìè.Íî òåîðåìà âåðíà è äëÿ èãð, â êîòîðûõ èãðîêè (êîàëèöèè) õîäÿò îäíîâðåìåííî!  ýòîìñëó÷àå ïðè ïîèñêå âåðõíåãî çíà÷åíèÿ ìîæíî ñ÷èòàòü, ÷òî â êàæäîé ïîçèöèè ñíà÷àëà õîäÿòîñòàëüíûå èãðîêè (êîàëèöèè), çàòåìi-éèãðîê (êîàëèöèÿ). Òàê ÷òî âñïîìîãàòåëüíûå èãðûêà÷åñòâà âíîâü ñâîäÿòñÿ ê êîìáèíàòîðíûì èãðàì.Òàêèì îáðàçîì, ïîëó÷àåìàëãîðèòìðàâíîâåñèé.
Àëãîðèòì ñîñòîèò èç1. Íài-ìmèëüòðîâàííîãî ïåðåáîðà äëÿ íàõîæäåíèÿ âñåõøàãîâ è íà êàæäîì øàãå ðàáîòàåò ñëåäóþùèì îáðàçîì:øàãå, çíàÿ ðàâíîâåñíûå óïðàâëåíèÿñîñòîÿíèÿçíà÷åíèå2. Äëÿ âñåõx∈Xè âñåõ èãðîêîâVj (x, m − i)x∈Xóïðàâëåíèåìj ∈ i(x, m − i).êàæäîãî èãðîêàt > m − i,íàõîäèì âûèãðûø(x, m − i).ïåðåáèðàåì âñåÄëÿ êàæäîãî èãðîêà íàõîäèì âåðõíååu∗ ∈ U(x, m−i) ñòûêóåìíà÷èíàÿ ñ ñîñòîÿíèÿjïðè âñåõâî âñïîìîãàòåëüíîé àíòàãîíèñòè÷åñêîé èãðåäëÿ âñåõ óïðàâëåíèéu′ ,u′Γj (x, m − i).óïðàâëåíèåu∗ ñ êàæäûìÄëÿ êàæäîãî òàêîãî óïðàâëåíèÿ äëÿHxj (p(x, u∗ |u′ ))â ïîäûãðå â ðàçâåðíóòîé îðìåΓ(x,t) .3.
Äëÿ âñåõx∈Xäëÿ âñåõ óïðàâëåíèéu∗ ∈ U(x, m − i)äëÿ âñåõ èãðîêîâðàññìàòðèâàåì âñå âîçìîæíûå îòêëîíÿþùèåñÿ óïðàâëåíèÿèãðîêà. Äëÿ êàæäîãî óïðàâëåíèÿïðèìåíåíèè óïðàâëåíèÿçíà÷åíèå äëÿujîïðåäåëÿåì ñîñòîÿíèåj = 1, . . . , nuj ∈ U j (x, m − i)êàæäîãîx′ = π(x, m − i, u∗ ||uj )ïðèu∗ ||uj = (u∗ 1 , . . . , u∗ j−1, uj , u∗ j+1, .
. . , u∗ n . Åñëè ïðè ýòîì âåðõíååj -ãî èãðîêà Vj (x′ , m−i+1) > Hxj (p(u∗ )), òî óïðàâëåíèå u∗ íå ÿâëÿåòñÿ ðàâ-íîâåñíûì è äàëüøå åãî íå ðàññìàòðèâàåì. Åñëè æå ïðè âñåõ âîçìîæíûõ îòêëîíåíèÿõâåðõíåå çíà÷åíèå â îòêëîíèâøåéñÿ èãðå îêàçûâàåòñÿ íå áîëüøå âûèãðûøà, âêëþ÷àåìóïðàâëåíèåu∗â ñïèñîê ðàâíîâåñíûõ.1014. Åñëè ìíîæåñòâî ðàâíîâåñíûõ äëÿt ≥ m−ióïðàâëåíèéu∗ïóñòî, òî ðàâíîâåñèé íåñóùåñòâóåò.
Èíà÷å ïåðåõîäèì ê ñëåäóþùåìó ìîìåíòó âðåìåíè.Ñëîæíîñòü àëãîðèòìà íàõîæäåíèÿ ìàêñèìèííîãî çíà÷åíèÿ â ïîäûãðå â ðàçâåðíóòîéîðìå O(xmun ),à çíà÷èò, äëÿ âñåõ èãðîêîâ è âåðøèí O(x2 m2 nun ).Ñëåäîâàòåëü-íî, ñëîæíîñòü íàõîæäåíèÿ âñåõ ðàâíîâåñíûõ âûèãðûøåé è ðàâíîâåñíûõ òðàåêòîðèé O((x2 m2 + xmv)nun ).Ñëîæíîñòü íàõîæäåíèÿ êîàëèöèîííî ðàâíîâåñíûõ òðàåêòîðèéO(x2 m2 cuc + xmcun+c v) = O(xmcuc (xm + un v)) (â äàííîì ñëó÷àå, ìîæíî èñïîëüçîâàòü òîëüêîïåðâûé àëãîðèòì ïîèñêà êîàëèöèîííûõ ðàâíîâåñèé).3.2Îáîáùåííûå ñåòåâûå èãðû3.2.1Ëîãèñòè÷åñêèå ñåòè è èõ îðìàëèçàöèÿ ýêîíîìè÷åñêîé ñèñòåìå åñòü ìíîæåñòâî àãåíòîâ, óïðàâëÿþùèõ ìàòåðèàëüíûìè è èíàíñîâûìè ïîòîêàìè áóäåì íàçûâàòü èõèðìàìè.Êîãäà èðìû âçàèìîäåéñòâóþò äðóã ñäðóãîì è äîãîâàðèâàþòñÿ, ëîãèñòè÷åñêèå ñèñòåìû ðàçíûõ èðì îáúåäèíÿþòñÿ â åäèíóþëîãèñòè÷åñêóþ ñèñòåìó, êîòîðàÿ íàçûâàåòñÿ ëîãèñòè÷åñêîé öåïüþ [56℄ èëè ñòðàòåãè÷åñêîéñåòüþ [74℄.
ðà, îïèñûâàþùèé âçàèìîäåéñòâèå ìåæäó àãåíòàìè â îáùåì ñëó÷àå, íå öåïü,à ñåòü, ïîýòîìó ïðàâèëüíî íàçûâàòü òàêèå ñèñòåìûëîãèñòè÷åñêèìè ñåòÿìè.Òàêèì îáðàçîì, ñåòüþ óïðàâëÿåò íåñêîëüêî àãåíòîâ ñ ðàçëè÷íûìè íåàíòàãîíèñòè÷åñêèìè èíòåðåñàìè, ïðè÷åì, õîòÿ îíè è ìîãóò äîãîâàðèâàòüñÿ, íî äîãîâîðû îñíîâàíû íà òîì,÷òî êàæäûé àãåíò ñòðåìèòñÿ ê ìàêñèìèçàöèè ñîáñòâåííîãî èíòåðåñà. Ïîäîáíóþ ñèñòåìó öåëåñîîáðàçíî ìîäåëèðîâàòü áåñêîàëèöèîííîé èãðîé [20℄. Ïîñêîëüêó óïðàâëÿåìàÿ ñèñòåìà ñåòü, ðå÷ü èäåò î áåñêîàëèöèîííîé ñåòåâîé èãðå. Ñóùåñòâóåò ìíîæåñòâî ðàçíûõ îïðåäåëåíèéñåòåâûõ èãð. Èõ ìîæíî îáîáùèòü â òàêîå îïðåäåëåíèå:Îïðåäåëåíèå 46. Ñåòåâàÿ èãðà ýòà èãðà, â êîòîðîé êàæäàÿ ñèòóàöèÿ ïîðîæäàåò òó èëèèíóþ ñåòü, à óíêöèÿ âûèãðûøà çàäàíà íà íåêîòîðîì ìíîæåñòâå ñåòåé. Ôîðìàëüíî, ýòîíàáîðΓ = (I, (Si )i∈I , G, g, (Hi)i∈I ),• Iãäå êîíå÷íîå ìíîæåñòâî èãðîêîâ. Ìîæíî ñ÷èòàòü, ÷òî• Si ìíîæåñòâî ñòðàòåãèé• G íåêîòîðîå ìíîæåñòâî ñåòåé;• g: S → Gi-ãîèãðîêà;S=Qi∈ISiI = {1, .
. . , n}; ìíîæåñòâî ñèòóàöèé; óíêöèÿ, êîòîðàÿ êàæäîé ñèòóàöèè ñîïîñòàâëÿåò ñåòü, îáðàçóþùóþñÿ âýòîé ñèòóàöèè;102• Hi : G → R óíêöèÿ âûèãðûøài-ãîèãðîêà, çàäàííàÿ íà ìíîæåñòâå ñåòåé è ïðèíè-ìàþùàÿ çíà÷åíèÿ â ïðîèçâîëüíîé óïîðÿäî÷åííîé ïîëóãðóïïå.Ýòîìó íàáîðó ñîîòâåòñòâóåò èãðà â íîðìàëüíîé îðìåΓ′ = (I, (Si )i∈I , (Hi ◦ g)i∈I ).Äàííîå îïðåäåëåíèå ñëèøêîì îáùåå è íåêîíñòðóêòèâíîå. Ïîýòîìó, îáû÷íî, ðàññìàòðèâàþòñÿ ÷àñòíûå ñëó÷àè:1.èãðû îðìèðîâàíèÿ ñåòåé, â êîòîðûõ èãðîêè îòîæäåñòâëÿþòñÿñ âåðøèíàìè ñåòè, à èõâçàèìîäåéñòâèÿ ñ äóãàìè2.èãðû íà ñåòÿõ,â êîòîðûõ èãðîêè íåçàâèñèìî äðóã îò äðóãà îïðåäåëÿþò ïàðàìåòðûñåòè ìîæíî ðàññìàòðèâàòü ýòè ïàðàìåòðû êàê îáîáùåííûå ïîòîêè â ñåòè.Ôîðìàëüíî, ïîçèöèîííûå èãðû ñ äèñêðåòíûì âðåìåíåì (ìíîãîøàãîâûå èãðû) òàêæå ïîäïàäàþò ïîä îïðåäåëåíèå 46. Ïðè÷åì, åñëè â ïåðå÷èñëåííûõ êëàññàõ èãð èãðîêè âçàèìîäåéñòâóþò â äèñêðåòíîì ïðîñòðàíñòâå, òî â ïîçèöèîííûõ èãðàõ âàæåí äèíàìè÷åñêèé àñïåêòâçàèìîäåéñòâèÿ â ïðîñòðàíñòâå-âðåìåíè.
Âîçìîæíî, ïîýòîìó ïîçèöèîííûå èãðû îðìàëüíîíå ïðè÷èñëÿþò ê ñåòåâûì èãðàì. ëîãèñòè÷åñêèõ ñåòÿõ:•îäèí àãåíò ìîæåò óïðàâëÿòü ìíîæåñòâîì ýëåìåíòîâ ñèñòåìû, ñâÿçàííûõ ñ ïðîèçâîäñòâîì è òðàíñïîðòèðîâêîé òî åñòü â ñåòåâîé èãðå îäèí èãðîê ìîæåò óïðàâëÿòü ìíîæåñòâîì âåðøèí è äóã ñåòè, ÷òî ñîîòâåòñòâóåò èãðàì íà ñåòÿõ;•èðìû îáðàçóþò ëîãèñòè÷åñêèå ñåòè ïî âçàèìíîìó ñîãëàñèþ è ê âçàèìíîé âûãîäå ò.å.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
