Диссертация (1149954), страница 27
Текст из файла (страница 27)
Êàê ìû óâèäèì äàëüøå, ñèòóàöèÿ ìåíÿåòñÿ â äèíàìè÷åñêîé èãðå, ãäå èãðîê, õîäÿùèéðàíüøå, ìîæåò íàâÿçàòü íåêîòîðîå çíà÷åíèå ïîòîêà èãðîêó, õîäÿùåìó ïîçæå.3.3Äèíàìè÷åñêèå ñåòåâûå èãðû äàííîì ðàçäåëå îïðåäåëÿþòñÿ äèíàìè÷åñêèå ñåòåâûå èãðû ñ äèñêðåòíûì âðåìåíåì è èññëåäóþòñÿ ñâîéñòâà ðàâíîâåñèÿ â äèíàìè÷åñêîé ñåòåâîé èãðå.
Áîëüøàÿ ÷àñòü ñîäåðæàíèÿðàçäåëà îïóáëèêîâàíà àâòîðîì â [45℄ è [44℄.3.3.1Îïðåäåëåíèå äèíàìè÷åñêîé ñåòåâîé èãðûÄèíàìè÷åñêàÿ ñåòåâàÿ èãðà ýòî ìîäåëü äèñêðåòíîãî ïðîñòðàíñòâà-âðåìåíè, â êîòîðîì äåéñòâóåò ìíîæåñòâî àãåíòîâ, ïðåñëåäóþùèõ íåêèå èíòåðåñû. àíåå ðàññìàòðèâàëèñü äèíàìè÷åñêèå ñåòåâûå èãðû ñ ïîëíîé èíîðìàöèåé, ò.å. ïîî÷åðåäíûå èãðû, â êîòîðûõ ñîñòîÿíèå èãðûíà êàæäîì øàãå ýòî ãðà âçàèìîäåéñòâèé èãðîêîâ, ò.å. ñåòü, â êîòîðîé åñòü ëèøü ïðîñòûåäóãè âçàèìîäåéñòâèÿ [65, 85, 55℄.
Ïðè ýòîì ìîäåëèðîâàëñÿ äèíàìè÷åñêèé ïðîöåññ îðìèðîâàíèÿ ñòàòè÷åñêîé ñåòè ñ ïîìîùüþ ïîî÷åðåäíûõ õîäîâ èãðîêîâ. Èíà÷å ãîâîðÿ, öåëüþ èãðûÿâëÿåòñÿ ñîçäàíèå ñòàáèëüíîé ñåòè íà ïîñëåäíåì øàãå, à âûèãðûø ÿâëÿåòñÿ òåðìèíàëüíûì.Àâòîðîì äàííîé ðàáîòû ïîñòðîåíà îáùàÿ ìîäåëü äèíàìè÷åñêîé ñåòåâîé èãðû ñ îäíîâðåìåííûìè õîäàìè èãðîêîâ è òðåìÿ âèäàìè äóã: äóãàìè âçàèìîäåéñòâèÿ, ñòðóêòóðíûìè äóãàìèè äèíàìè÷åñêèìè äóãàìè [45℄. Ïðè ýòîì, êàê è â ñòàòè÷åñêîé èãðå, ñòðóêòóðíûå äóãè ìîæíîóñòðàíèòü, ïðèâåäÿ èãðó ê ýêâèâàëåíòíîìó âèäó áåç ñòðóêòóðíûõ äóã.
Íî íàëè÷èå äèíàìè÷åñêèõ äóã ýòî ñóùåñòâåííîå ñâîéñòâî äèíàìè÷åñêîé ñåòåâîé èãðû, äåëàþùåå åå îáîáùåíèåìêàê ïîâòîðÿþùåéñÿ ñòàòè÷åñêîé ñåòåâîé èãðû, òàê è ìíîãîøàãîâîé èãðû ñ îäíîâðåìåííûìèõîäàìè èãðîêîâ. Òàêèì îáðàçîì, ìîæíî ìîäåëèðîâàòü ðàçëè÷íûå äèíàìè÷åñêèå ïðîöåññû âäèñêðåòíîì ïðîñòðàíñòâå, â òîì ÷èñëå è ñ èíòåãðàëüíûì âûèãðûøåì.×òîáû îïðåäåëèòü äèíàìè÷åñêóþ ñåòåâóþ èãðó, íóæíî ïðåæäå âñåãî îïðåäåëèòü ïðîñòðàíñòâî è âðåìÿ èãðû. Áóäåì ðàññìàòðèâàòü ñàìûé ïðîñòîé âàðèàíò øêàëû âðåìåíè: êîíå÷íîå âðåìÿT = {t1 , t2 , . .
. , tm }.Ìîæíî äàæå ñ÷èòàòü, ÷òîT = {1, 2, . . . , m}.Ïðîñòðàíñòâî èãðû, î÷åâèäíî, äîëæíî áûòü ïðîñòðàíñòâîì ñåòåéG.Ïðèìåì, äëÿ ïðî-ñòîòû, ñëåäóþùèå ïðåäïîëîæåíèÿ:1. Ìíîæåñòâî âåðøèíLíå çàâèñèò îò âûáîðà ñåòè èçG.Ýòî ïðåäïîëîæåíèå íå óìàëÿåòîáùíîñòè, ïîñêîëüêó âñåãäà ìîæíî ïåðåèìåíîâàíèåì âåðøèí è äîáàâëåíèåì èêòèâíûõ âåðøèí (ñ åäèíñòâåííûì ñîñòîÿíèåì, íå ñâÿçàííûõ ñ äðóãèìè âåðøèíàìè) äîáèòüñÿ, ÷òîáû ìíîæåñòâà âåðøèí ó âñåõ ñåòåé ñîâïàëè.
Ò.å. ñòðóêòóðà ñåòè íå ìåíÿåòñÿ122ñ òå÷åíèåì âðåìåíè, à ìåíÿþòñÿ òîëüêî ñîñòîÿíèÿ âåðøèí è ñîåäèíåíèé.2. Îòíîøåíèå óïðàâëåíèÿρ îäíî è òî æå äëÿ âñåõ ñåòåé. Ýòî ïðåäïîëîæåíèå òàêæå íå óìà-ëÿåò îáùíîñòè, ïîñêîëüêó âñåãäà ìîæíî ñ÷èòàòü, ÷òî êàæäûé èãðîê óïðàâëÿåò êàæäîéâåðøèíîé ïðîñòî íåêîòîðûå ìíîæåñòâà óïðàâëåíèÿ ñîñòîÿò èç 1 ýëåìåíòà.3. Ìíîæåñòâî ñîåäèíåíèéîò ñîñòîÿíèé âåðøèíijU(a,b)(sa , sb )ìåæäó âåðøèíàìèa, b èãðîêîâ i è jçàâèñèò òîëüêîa, b è íå çàâèñèò îò ñîñòîÿíèé äðóãèõ âåðøèí.
Ýòî ïðåäïîëîæåíèåâûòåêàåò èç îïðåäåëåíèÿ äèñêðåòíîãî ïðîñòðàíñòâà.Îïðåäåëåíèå 59. Äèíàìè÷åñêàÿ ñåòåâàÿ èãðà ýòî äèíàìè÷åñêàÿ èãðà ñ îäíîâðåìåííûìèõîäàìè, â êîòîðîé:•Ïðîñòðàíñòâî èãðû ýòî ìíîæåñòâî ñåòåéG = (L, M), M = M p ∪ M s ∪ M dñ íà-ãðóæåííûìè âåðøèíàìè è íàãðóæåííûìè äóãàìè òðåõ âèäîâ: ðåáðàìè âçàèìîäåéñòâèÿM p,•ñòðóêòóðíûìè äóãàìèMsÂðåìÿ èãðû ýòî ìíîæåñòâîè äèíàìè÷åñêèìè äóãàìèT = {0, 1, . . .
, m}, ãäå 0 óñëîâíûéêîòîðîãî çàäàíî èêñèðîâàííîå óñëîâíîå ñîñòîÿíèåîïðåäåëèòü ìíîæåñòâî óïðàâëåíèé â ìîìåíòx0Âåðøèíû ñåòè íàãðóæåíû ìíîæåñòâàìè ñîñòîÿíèé•Â êàæäûé ìîìåíò(îíî íóæíî, ÷òîáû êîððåêòíîSli (t)i∈N,i-ãî èãðîêà ñ j -ì ïî äóãå m (íèæíèå ïîëóðåøåòêè),•djUm(t), m ∈ MsiUm(t), m ∈ MijUm(t), m ∈ M(ïðîèç-ñîåäèíåíèéà äèíàìè÷åñêèå äóãè ìíîæåñòâà-(ïðîèçâîëüíûå ìíîæåñòâà);Ìíîæåñòâî óïðàâëåíèéìîìåíò âðåìåíèl∈L, t∈T ;ñòðóêòóðíûå äóãè íàãðóæåíû ñîñòîÿíèÿìèâîëüíûå ìíîæåñòâà), ðåáðà âçàèìîäåéñòâèÿ ìíîæåñòâàìèìèìîìåíò âðåìåíè, äëÿt = 1);•tM p;U i (x, t)êàæäîãî èãðîêàiâ êàæäîì ñîñòîÿíèèx(t)â êàæäûét ñîñòîèò èç óïðàâëåíèé èãðîêà âåðøèíàìè, ñòðóêòóðíûìè äóãàìè, äó-ãàìè âçàèìîäåéñòâèÿ è äèíàìè÷åñêèìè äóãàìè è, ñòðîãî ãîâîðÿ, îïðåäåëÿåò ñîñòîÿíèåâ ñëåäóþùèé ìîìåíò âðåìåíè:U i (x, t) =YUli (sil (t), t)l∈Lãäå•Uli (sil (t), t) ⊆ Sli (t) × Ulsi (t + 1) ×ÌíîæåñòâîSliñîñòîÿíèé âåðøèíûQj6=i,e(m)=llèãðîêàijUm(t + 1) × Uldi (t + 1);içàâèñèò îò ñîñòîÿíèé âõîäÿùèõ â íååñòàòè÷åñêèõ äóã â äàííûé ìîìåíò âðåìåíè, à òàêæå äèíàìè÷åñêèõ äóã è ðåáåð âçàèìîäåéñòâèÿ â ïðåäûäóùèé ìîìåíò âðåìåíè (çàâèñèìîñòü ìíîæåñòâà óïðàâëåíèé â ìîìåíò123tîò ñîñòîÿíèÿ â ìîìåíòt):Sli (t + 1) = Sli ({usim (t + 1)}m∈M s ,ji{inf(uij(k,l) (t), u(l,k) (t))}j∈N,•dje(m)=l , {um (t)}j∈N, m∈M d , e(m)=l ,(k,l)∈M p , t+ 1)Ìíîæåñòâî âîçìîæíûõ ñîñòîÿíèé âñåõ äóã äëÿ êàæäîãî èãðîêàiçàâèñèò îò ñîñòîÿíèÿíà÷àëüíîé âåðøèíû (ò.å.
ìíîæåñòâî óïðàâëåíèé â êàæäûé ìîìåíò âðåìåíè íåïðÿìîóãîëüíî îäíè åãî êîìïîíåíòû îïðåäåëÿþò ìíîæåñòâî âîçìîæíûõ ñîñòîÿíèé äðóãèõêîìïîíåíò):uil ∈ Uli (sil (t), t).Äèíàìè÷åñêèå äóãèMdäîáàâëåíû ê ñòðóêòóðíûì äóãàì è ðåáðàì âçàèìîäåéñòâèÿ, èñõîäÿèç îïðåäåëåíèÿ ÎÄÑ â äèñêðåòíîì ïðîñòðàíñòâå-âðåìåíè. Îíè èíòåðïðåòèðóþòñÿ òàê: â ñåòèåñòü äóãà(a, b) ∈ M d ,åñëè èãðîêè, óïðàâëÿþùèå âåðøèíîéìåíÿòü ñîñòîÿíèå âåðøèíûb.Åñëèa,ìîãóò, âëèÿÿ íà åå ñîñòîÿíèå,íå ó÷èòûâàòü ñòðóêòóðíûõ ðåáåð, ñõåìà î÷åíü ïðîñòà:èãðîê âûáèðàåò ñîñòîÿíèå êàæäîé âåðøèíû, çàâèñÿùèå îò ðåáåð âçàèìîäåéñòâèÿ è äèíàìè÷åñêèõ äóã, ñâÿçàííûõ ñ âåðøèíîé â ïðåäûäóùèé ìîìåíò âðåìåíè.
Ïîñëå ýòîãî îí âûáèðàåòñîñòîÿíèÿ ñòàòè÷åñêèõ è äèíàìè÷åñêèõ äóã è ïðåäëàãàåìûå âçàèìîäåéñòâèÿ ñ äðóãèìè èãðîêàìè, çàâèñÿùèå îò âûáðàííûõ èì ñîñòîÿíèé âåðøèí. Äëÿ ñòðóêòóðíûõ äóã ñîñòîÿíèÿâåðøèí è äóã èãðîêà çàâèñÿò äðóã îò äðóãàâ îäèí è òîò æå ìîìåíò âðåìåíè.Èíà÷åãîâîðÿ, èãðîê â êàæäûé ìîìåíò âðåìåíè îïðåäåëÿåò ãëîáàëüíî ñîãëàñîâàííûé ñòàòè÷åñêèéïîòîê â ñåòè. Ñîñòîÿíèÿ ðåáåð âçàèìîäåéñòâèÿ â êàæäûé ìîìåíò âðåìåíè îïðåäåëÿþòñÿ,èñõîäÿ èç ïðåäëîæåíèé èãðîêîâ äðóã äðóãó â ýòîò ìîìåíò âðåìåíè.Êàê è â ñòàòè÷åñêîé ãðóïïîâîé èãðå, â äèíàìè÷åñêîé ìîæíî ðàçäåëèòü ñîâìåñòíî óïðàâëÿåìûå âåðøèíû è ñëèòü âåðøèíû, óïðàâëÿåìûå ðàçíûìè èãðîêàìè.  ðåçóëüòàòå ìíîæåñòâîâåðøèí áóäåò ñîâïàäàòü ñ ìíîæåñòâîì èãðîêîâ, à ñòðóêòóðíûå äóãèMsèñ÷åçíóò.
Ïîýòîìó,åñëè íå îãîâîðåíî îáðàòíîå, â ðàáîòå ðàññìàòðèâàþòñÿ äèíàìè÷åñêèå èãðû áåç ñòðóêòóðíûõäóã.Íàïîìíèì, ÷òî â äèíàìè÷åñêîé èãðåu ∈ Uj (g, t),çàäàííîå äëÿ êàæäîé ñåòèïîçèöèîííàÿ ñòðàòåãèÿg = x(t)èãðîêà ýòî óïðàâëåíèåè êàæäîãî ìîìåíòà âðåìåíèt.Äàëåå áóäåìðàññìàòðèâàòü òîëüêî ïîçèöèîííûå ñòðàòåãèè. Êàê îáû÷íî, êàæäûé íàáîð ñòðàòåãèé îïðåäåëÿåòlïàðòèþ ò.å. ïîñëåäîâàòåëüíîñòü ñîñòîÿíèé ñåòè, ïðè÷åì ñîñòîÿíèå êàæäîé âåðøèíûâ ìîìåíò âðåìåíètçàâèñèò òîëüêî îò ñîñòîÿíèÿ äóã, âõîäÿùèõ âÏàðòèþ ìîæíî èçîáðàçèòü ãðàîìêîòîðîì ìíîæåñòâî âåðøèí ãäå(a, b) ∈ M = M p ∪ M d .âõîäÿùèõ â íåå äóã (ðåáðàMpL×Tgt ,lâ ìîìåíò âðåìåíèt − 1.ðàçâåðíóòûì âî âðåìåíè òî åñòü, ãðàîì, âè ìíîæåñòâî äèíàìè÷åñêèõ äóã òèïà((a, t), (b, t + 1)),Ïðè ýòîì ñîñòîÿíèå êàæäîé âåðøèíû çàâèñèò îò ñîñòîÿíèéîòëè÷àþòñÿ îò äóãMdòîëüêî òåì, ÷òî îíè íåîðèåíòèðîâàííû124è ñîñòîÿíèå êàæäîãî ðåáðà íèæíÿÿ ãðàíü óïðàâëåíèé èãðîêîâ, êîòîðûõ îíî ñîåäèíÿåò).Áîëåå òîãî:Óòâåðæäåíèå 3.3.1.
Äëÿ êàæäîé ðàçâåðíóòîé âî âðåìåíè ñåòè gt , â êîòîðîé çàâèñèìîñòüñîñòîÿíèÿ êàæäîé âåðøèíû îò ñîñòîÿíèé âõîäÿùèõ äóã ñîáëþäàåòñÿ, ñóùåñòâóåò ïàðòèÿâ äèíàìè÷åñêîé ñåòåâîé èãðå, ïîðîæäàþùàÿ ýòó ñåòü.Äîêàçàòåëüñòâî.Îïðåäåëèì ñòðàòåãèè èãðîêîâ, çàâèñÿùèå òîëüêî îò âðåìåíè è ðåàëèçó-þùèå èìåííî òàêèå ñîñòîÿíèÿ âåðøèí è äóãèçMpM p, M dâ êàæäûé ìîìåíò âðåìåíè (äëÿ äóãñòðàòåãèè èãðîêîâ íà îáîèõ êîíöàõ äóãè äîëæíû áûòü îäèíàêîâû). Î÷åâèäíî, îíè èïîðîæäàþò èñêîìóþ ñåòü.Çàìå÷àíèå3.3.1. Íå íóæíî ïóòàòü ðàçâåðíóòóþ âî âðåìåíè ñåòüèãðû íà ãðàå.  ñåòègtðàññìàòðèâàåòñÿòîëüêî îäíà ïàðòèÿ.gtñ ãðàîì äèíàìè÷åñêîéÎïðåäåëÿÿ ðàçëè÷íûå ñî-ñòîÿíèÿ åå âåðøèí è äóã, ìîæíî îïðåäåëÿòü ðàçëè÷íûå ïàðòèè èãðû.
 ãðàå èãðû ðàññìàòðèâàþòñÿ âñå âîçìîæíûå ïàðòèè, íî áåç ó÷åòà ñåòåâîé ñòðóêòóðû èãðû â êàæäûé ìîìåíòâðåìåíè ñåòü èãðû ñëèïàåòñÿ â òî÷êó.Çàìå÷àíèå3.3.2. Äàííîå îïðåäåëåíèå äèíàìè÷åñêîé ñåòåâîé èãðû ïîçâîëÿåò ïî-íîâîìóâçãëÿíóòü íà èåðàðõè÷åñêèå èãðû [50℄.Èåðàðõè÷åñêàÿ ñåòåâàÿ èãðàñòî äèíàìè÷åñêàÿ ñåòåâàÿ èãðà, â êîòîðîé ìíîæåñòâî èãðîêîâA1 ∪ A2 ∪ · · · ∪ An = Nóðîâíè,Mp•Ñòàòè÷åñêèå äóãè•Äèíàìè÷åñêèå äóãèNèçnóðîâíåé ýòî ïðî-äåëèòñÿ íà ïîäìíîæåñòâàïðè÷åì:ñîåäèíÿþò òîëüêî èãðîêîâ îäíîãî óðîâíÿ.Mdèäóò òîëüêî îò ïðåäûäóùåãî (i-ãî) óðîâíÿ ê ïîñëåäóþùåìó((i + 1)-ìó). Òàêèì îáðàçîì, ñåòü ðàñïàäàåòñÿ íàn ñåòåé,ïîñëåäîâàòåëüíî ñîåäèíåííûõäèíàìè÷åñêèìè äóãàìè.•Âûèãðûø èãðîêài-ãîóðîâíÿ çàâèñèò òîëüêî îò ñîñòîÿíèÿi-éñåòè è ïîñëåäóþùèõñåòåé.Îáû÷íàÿ èåðàðõè÷åñêàÿ èãðà [50℄ ýòî ñåòåâàÿ èåðàðõè÷åñêàÿ èãðà, â êîòîðîé íåò ñòàòè÷åñêèõ äóãM p,à åñòü òîëüêî äóãèM d,ñîåäèíÿþùèå ìåæäó ñîáîé ðàçíûå óðîâíè.
Êðîìåòîãî, âûèãðûøè èãðîêîâ ïîä÷èíåííûõ óðîâíåé ìîãóò áûòü íåçàâèñèìû. Ýòî çíà÷èò, ÷òî âñîîòâåòñòâóþùèõ ïîäûãðàõ â ðàçâåðíóòîé îðìå ïðîùå íàõîäèòü ðàâíîâåñèÿ.  îñòàëüíîì,èåðàðõè÷åñêèå èãðû íè÷åì íå îòëè÷àþòñÿ îò ïðî÷èõ äèíàìè÷åñêèõ ñåòåâûõ èãð â òîì÷èñëå, â íèõ âîçìîæíû ñòðàòåãèè íàêàçàíèÿ è ìíîæåñòâî íåàáñîëþòíûõ ðàâíîâåñèé.Äðóãîé ïðèìåð èåðàðõè÷åñêîé ñåòåâîé èãðû ðàññìîòðåí â ïðèëîæåíèè.125Îïðåäåëåíèå 60.
Äèíàìè÷åñêàÿ èãðà íà ñåòèíåò äóã âçàèìîäåéñòâèÿ ìåæäó èãðîêàìè: ýòî äèíàìè÷åñêàÿ ñåòåâàÿ èãðà, â êîòîðîéM p = ∅.Îïðåäåëåíèå 61. Äèíàìè÷åñêàÿ èãðà óïðàâëåíèÿ ïîòîêàìèñåòè, â êîòîðîé ñòàòè÷åñêèå äóãèMjs ýòî äèíàìè÷åñêàÿ èãðà íàäëÿ êàæäîãî èãðîêà â êàæäûé ìîìåíò âðåìåíè îïðå-äåëÿþò ñòàòè÷åñêèé ïîòîê äàííîãî èãðîêà â êàæäûé ìîìåíò âðåìåíè, à äèíàìè÷åñêèå äóãèM d îïðåäåëÿþò äèíàìè÷åñêèé ïîòîê (îáùèé äëÿ âñåõ èãðîêîâ).  îáùåì ñëó÷àå, ñòàòè÷åñêèåïîòîêè è äèíàìè÷åñêèé ïîòîê çàâèñÿò äðóã îò äðóãà. ñëó÷àå, êîãäà íåò äóãM d,ñîñòîÿíèå èãðû â ïîñëåäóþùèé ìîìåíò âðåìåíè íå çàâèñèòîò ñîñòîÿíèÿ â ïðåäûäóùèé ìîìåíò.
Èãðà ðàñïàäàåòñÿ â ïîâòîðÿþùóþñÿ èãðó óïðàâëåíèÿñòàòè÷åñêèìè ïîòîêàìè. ñëó÷àå, êîãäà íåò äóãM s,ñîñòîÿíèå êàæäîé âåðøèíû çàâèñèò îò ñîñòîÿíèÿ ñîñåäíèõâåðøèí â ïðåäûäóùèé ìîìåíò âðåìåíè. Èãðà ïðåâðàùàåòñÿ â èãðó óïðàâëåíèÿ äèíàìè÷åñêèì ïîòîêîì. Ïðèìåð òàêîé èãðû îáû÷íàÿ èåðàðõè÷åñêàÿ èãðà [50℄. Ñåòü, ðàçâåðíóòàÿ âîâðåìåíè,gtâ òàêîé èãðå áåñêîíòóðíàÿ. Ýòî çíà÷èò, ÷òî ìîæíî îïðåäåëèòü íåêîòîðóþ äî-ïóñòèìóþ ïàðòèþ èãðû (äèíàìè÷åñêèé ïîòîê), ðàññìàòðèâàÿ ïîî÷åðåäíî âåðøèíû ñíà÷àëàâ 1-é ìîìåíò âðåìåíè, ïîòîì âî 2-é, è.ò.ä. äî êîíöà.3.3.2Òåîðåìà î íåîáõîäèìûõ è äîñòàòî÷íûõ óñëîâèÿõ ðàâíîâåñèÿ âäèíàìè÷åñêîé ñåòåâîé èãðåÏóñòü èìååòñÿ êîíå÷íàÿ äèíàìè÷åñêàÿ ñåòåâàÿ èãðà ñ îáîáøåííûìè èíòåãðàëüíûìè âûèãðûøàìè, çàâèñÿùèìè îò ñòîèìîñòåé ïîòîêîâ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
