Диссертация (1149954), страница 23
Текст из файла (страница 23)
èãðîêè ìîãóò îáðàçîâûâàòü ñîåäèíåíèÿ äðóã ñ äðóãîì, îðìèðóÿ ñåòü. Ýòî èãðûîðìèðîâàíèÿ ñåòè.Èíà÷å ãîâîðÿ, äëÿ ìîäåëèðîâàíèÿ ëîãèñòè÷åñêîé ñèñòåìû íóæíà ñåòåâàÿ èãðà, îáîáùàþùàÿ ñåòåâûå èãðû óïðàâëåíèÿ ïîòîêàìè è èãðû îðìèðîâàíèÿ ñåòåé.  [42℄ òàêæå îòìå÷åíàíåîáõîäèìîñòü îáúåäèíåíèÿ ýòèõ äâóõ êëàññîâ èãð.  äàííîé ðàáîòå êàê ðàç è ñòðîèòñÿ îáùååêîíñòðóêòèâíîå îïðåäåëåíèå ñåòåâîé èãðû, îáîáùàþùåå èãðû îðìèðîâàíèÿ ñåòåé è èãðûíà ñåòÿõ êàê â ñòàòè÷åñêîì, òàê è â äèíàìè÷åñêîì ñëó÷àå. äèíàìè÷åñêîì ñëó÷àå íóæíî ó÷èòûâàòü, ÷òî â ðåàëüíûõ ýêîíîìè÷åñêèõ ñèñòåìàõ âðåìÿíåïðåðûâíî.
Åãî ìîæíî ìîäåëèðîâàòü äèñêðåòíûì âðåìåíåì, íî òîãäà íóæíî ñ÷èòàòü, ÷òîàãåíòû ïðèíèìàþò ðåøåíèå îäíîâðåìåííî, òî åñòü ðàçûãðûâàåòñÿ ïîâòîðÿþùàÿñÿ ìîäåëüîáìåíà èëè îëèãîïîëèè [10℄.  îáùåì ñëó÷àå, òàêóþ ñèñòåìó öåëåñîîáðàçíî ìîäåëèðîâàòüäèíàìè÷åñêîé ñåòåâîé èãðîé ñ îäíîâðåìåííûìè õîäàìè èãðîêîâ.1033.2.2Èãðû îðìèðîâàíèÿ ñåòåé47. Èãðà îðìèðîâàíèÿÎïðåäåëåíèå(N, (Xi )i∈N , G, g, (Hi)i∈N ),• Nñåòè[79,42℄ýòîñåòåâàÿèãðàΓ=ãäå ìíîæåñòâî èãðîêîâ;• Xi ⊆ Xi0 ìíîæåñòâî äîïóñòèìûõ ñòðàòåãèéi-ãîïåðåìåííàÿxoutijïîêàçûâàåò, æåëàåò ëè èãðîêout ïðè ïåðåìåííîé ïîêàçûâàåò, ÷òî ñâÿçüiXi0 = (Xi0èãðîêà, ãäåìíîæåñòâî ïàð âõîäÿùèõ è èñõîäÿùèõ âåêòîðîâ, ãäå•Xi0outoutin= Xi0 = {0, 1}nîáðàçîâàòü ñâÿçü ñ èãðîêîì(i, j)in, Xi0 )ïî îòíîøåíèþ ê èãðîêóij(èíäåêñÿâëÿåòñÿèñõîäÿùåé);•àíàëîãè÷íî, ïåðåìåííàÿîò èãðîêà••xinijïîêàçûâàåò, ÷òî èãðîêiñîãëàñåí íà îáðàçîâàíèå äóãè(j, i)j;ìîæíî îïðåäåëèòüx = (xout , xin ),X=Qni=1Xi ìíîæåñòâî ñèòóàöèé â èãðå; ñèòóàöèÿ ïàðà ìàòðèöñòðîêè êîòîðîé ñòðàòåãèè èãðîêîâ;ìàòðèöà ñìåæíîñòè ðåçóëüòèðóþùåé ñåòèíåîðèåíòèðîâàííîì ñëó÷àå èg(x)îïðåäåëÿåòñÿ òàê:Tg(x) = min(xout , xin )g(x) = min(x, xT )â îðèåíòèðîâàííîì ñëó÷àå, ãäåâmin ïîýëåìåíòíûé ìèíèìóì ìàòðèö. îðèåíòèðîâàííîì ñëó÷àå ìåæäó äâóìÿ èãðîêàìè ìîãóò îáðàçîâàòüñÿ 2 ñâÿçè, èäóùèå âðàçíûå ñòîðîíû.
Êàæäàÿ ñòðàòåãèÿ èãðîêà îïðåäåëÿåò, ïî ñóòè, ìíîæåñòâî åãî îïïîíåíòîâ,ê êîòîðûì èãðîê õî÷åò îáðàçîâàòü ñâÿçü. Åñëè èñêëþ÷èòü ïåòëè, ñîåäèíÿþùèå èãðîêà ññàìèì ñîáîé, òî êîëè÷åñòâî âñåõ âîçìîæíûõ ñòðàòåãèé èãðîêà ñëó÷àå è22(n−1)â îðèåíòèðîâàííîì ñëó÷àå, ãäån = |N|íåò îãðàíè÷åíèé íà ñòðàòåãèè èãðîêîâ, èìååòñÿ âñåãî2n−1â íåîðèåíòèðîâàííîì ÷èñëî èãðîêîâ.  ñëó÷àå, êîãäà2n−1ðàçëè÷íûõ ñèòóàöèé â íåîðèåí-22n(n−1) = 4n(n−1) â îðèåíòèðîâàííîì ñëó÷àå.
Êîëè÷åñòâî âîçìîæQ|G(X)| ≤ |X| = ni=1 |Xi |.  îáùåì ñëó÷àå, èìååòñÿ 2n(n−1)/2 ðàçëè÷íûõ ñåòåé âòèðîâàííîì ñëó÷àå èíûõ ñåòåé:íåîðèåíòèðîâàííîì ñëó÷àå è2n(n−1)ñåòåé â îðèåíòèðîâàííîì ñëó÷àå, ÷òî ãîðàçäî ìåíüøåêîëè÷åñòâà ñèòóàöèé (ïîðÿäêà êâàäðàòíîãî êîðíÿ èç êîëè÷åñòâà ñèòóàöèé).Çàìå÷àíèåñòâèåì,3.2.1. Èíîãäà èñïîëüçóåòñÿ èíàÿ òåðìèíîëîãèÿ: ñòðàòåãèÿ èãðîêà íàçûâàåòñÿà ñèòóàöèÿ Çàìå÷àíèåïðîèëåì äåéñòâèéäåé-[17℄.3.2.2. àíåå ðàññìàòðèâàëèñü è ñåòåâûå èãðû íà îðèåíòèðîâàííûõ ãðààõ, â êîòî-ðûõ èìåþò çíà÷åíèå íå äâîéíûå ñîåäèíåíèÿ (ñâÿçè), à ñîåäèíåíèÿ èãðîêîâ â òðîéêè, ÷åòâåðêè, è.ò.ï.
[40℄. Íî òàêèå ñîåäèíåíèÿ ñâîäèëèñü ê ìíîæåñòâàì äâîéíûõ ñîåäèíåíèé, à ïîäîáíûåèãðû ê ñåòåâûì èãðàì.104Òàáëèöà 3.1: Ïàðû èãðîêîâij{0}{0}{0} {0, 1}{0}{1}{0, 1} {0, 1}{0, 1} {1}{1}{1}(i, j)000inf(xi , xj )xi1äóãàèãðà ñîãëàñèÿ ïî [17℄èãðà ñîãëàñèÿ ïî àâòîðóäàäàíåòäàäàíåòäàäàíåòíåòäàíåòÈãðû ñîãëàñèÿÂ [17℄ èãðû ñîãëàñèÿ îïðåäåëÿþòñÿ òàê. Ïóñòü ìíîæåñòâà äåéñòâèéåñëèi-éèãðîê ìîæåò èìåòü èëè íå èìåòü ïðåäëîæåíèå êj -ìóXièãðîêîâ òàêîâû, ÷òîèãðîêó, òîj -éèãðîê ìîæåòïðèíÿòü, à ìîæåò è íå ïðèíÿòü ýòî ïðåäëîæåíèå.
Òîãäà áóäåì ãîâîðèòü, ÷òî â ñåòåâîé èãðåäëÿ îáðàçîâàíèÿ ñâÿçè òðåáóåòñÿ ñîãëàñèå îáîèõ èãðîêîâ, è íàçûâàòü òàêèå èãðûñîãëàñèÿ.Äàäèì èíîå îïðåäåëåíèå:Îïðåäåëåíèå 48.x′i ≤ xièãðàìèÑåòåâàÿ èãðà(N, (Xi ), (Hi ))(ïîýëåìåíòíîå íåðàâåíñòâî) ñëåäóåòÿâëÿåòñÿèãðîé ñîãëàñèÿ,åñëè èçx′i ∈ Xixi ∈ XièÅñòü ëè ðàçíèöà ìåæäó ýòèìè îïðåäåëåíèÿìè? Íà ìíîæåñòâà ñòðàòåãèé êàæäîãî èãðîêàXiíàëîæåíû îãðàíè÷åíèÿ, ïðè÷åì ýòè îãðàíè÷åíèÿ íåçàâèñèìû äëÿ ðàçíûõ èãðîêîâ.
Òîãäàïàðû èãðîêîâ(i, j)(ñîîòâåòñòâåííî íåîðèåíòèðîâàííûå ëèáî îðèåíòèðîâàííûå) ïðè èêñè-ðîâàííîì îêðóæåíèè ò.å. ñòðàòåãèÿõ èãðîêîâi è j , íå ñâÿçàííûõ ñ ýòèìè äóãàìè äåëÿòñÿíà êëàññû, ïåðå÷èñëåííûå â òàáëèöå 3.1 (íå ñ÷èòàÿ ñèììåòðè÷íûõ âàðèàíòîâ).Òå ñëó÷àè, â êîòîðûõ äóãà(i, j)îáðàçóåòñÿ âñåãäà, ðàâíî êàê è òå ñëó÷àè, â êîòîðûõ îíàíå îáðàçóåòñÿ íèêîãäà, íåèíòåðåñíû è ýêâèâàëåíòíû äðóã äðóãó îòíîñèòåëüíî âñåõ ðàññìàòðèâàåìûõ â äàííîì ðàçäåëå óòâåðæäåíèé. Ñëåäîâàòåëüíî, ìîæíî ñâåñòè âñå ýòè ñëó÷àè êxi = xj = {0}îäíîìó: êîãäàè äóãà íå îáðàçóåòñÿ íèêîãäà.
Òàêîé ñëó÷àé âîçìîæåí äëÿ èãðûñîãëàñèÿ ïî îáîèì îïðåäåëåíèÿì. Îñòàþòñÿ 2 ñëó÷àÿ: çàâèñèìîñòü îáðàçîâàíèÿ äóãè îò îäíîãî èãðîêà ëèáî îò îáîèõ èãðîêîâ. È ïî îïðåäåëåíèþ [17℄, è ïî îïðåäåëåíèþ àâòîðà, ïåðâûéñëó÷àé íåâîçìîæåí äëÿ èãðû ñîãëàñèÿ, à âòîðîé âîçìîæåí. Ñëåäîâàòåëüíî, îïðåäåëåíèÿýêâèâàëåíòíû.Ïðèìåð 12.Èãðà, íå ÿâëÿþùàÿñÿ èãðîé ñîãëàñèÿ.
Ïóñòü èãðîêè íå ìîãóò ïðåïÿòñòâîâàòüîáðàçîâàíèþ âõîäÿùèõ ñâÿçåé. Òîãäà ìíîæåñòâî ñòðàòåãèéi-ãîèãðîêà ñîñòîèò òîëüêî èçñòðàòåãèé, â êîòîðûõ îí ñîãëàñåí íà îáðàçîâàíèå ëþáûõ âõîäÿùèõ ñâÿçåé:Xi = {xi ∈ Xi0 | ∀j ∈ N, j 6= i xinij = 1}.105Ïðè ýòîì ðåçóëüòèðóþùàÿ ñåòüg = xout .Îáîçíà÷èì òàêîå ìíîæåñòâî äåéñòâèé ÷åðåçXiS .Ïîñêîëüêó ðåçóëüòèðóþùàÿ ñåòü â èãðàõ, â êîòîðûõ äëÿ îáðàçîâàíèÿ ñâÿçè òðåáóåòñÿæåëàíèå òîëüêî îäíîãî èãðîêà, âçàèìíî îäíîçíà÷íî îïðåäåëÿåòñÿ âåêòîðîì ñòðàòåãèé,xoutg=òî äëÿ ïðîèçâîëüíîé èãðû â íîðìàëüíîé îðìå, â êîòîðîé êàæäûé èç èãðîêîâ èìååò íåáîëåå2n−1 âîçìîæíûõ äåéñòâèé, ñóùåñòâóåò ñåòåâàÿ èãðà ñ òàêèìè æå óíêöèÿìè âûèãðûøàè ìíîæåñòâàìè ñòðàòåãèéXi ⊆ XiS .Ýòî çíà÷èò, ÷òî íèêàêèõ ïðåäñêàçàíèé î ðåøåíèÿõâ òàêèõ ñåòåâûõ èãðàõ, áîëåå îáùèõ, ÷åì äëÿ íåêîîïåðàòèâíûõ èãð, ñäåëàòü íåâîçìîæíî.Ïîýòîìó â ðàáîòå ðàññìàòðèâàþòñÿ, â ïåðâóþ î÷åðåäü, èãðû ñîãëàñèÿ.3.2.3Ñòðàòåãè÷åñêèå ïðèíöèïû îïòèìàëüíîñòè â ñåòåâûõ èãðàõ äàííîì ðàçäåëå èññëåäóþòñÿ îñíîâíûå ïðèíöèïû îïòèìàëüíîñòè è ñòðîÿòñÿ àëãîðèòìûíàõîæäåíèÿ ðåøåíèé â èãðàõ îðìèðîâàíèÿ ñåòè.
àíåå îíè ïóáëèêîâàëèñü àâòîðîì â ðàáîòå[39℄.àâíîâåñèåÎïðåäåëåíèå 49.Ñåòüg íàçûâàåòñÿ ñòàáèëüíîé ïî Íýøó[73℄, åñëè ñóùåñòâóåò ðàâíîâåñíàÿïî Íýøó ñèòóàöèÿ, ïðèâîäÿùàÿ ê äàííîé ñåòè.Ëåãêî ïðîâåðèòü, ÷òî â èãðå ñîãëàñèÿ, â êîòîðîé çàïðåùåíû ïåòëè (ñîåäèíåíèÿ èãðîêàñ ñàìèì ñîáîé) ïóñòàÿ ñåòü âñåãäà ñòàáèëüíà ïî Íýøó. Ïîýòîìó ðàâíîâåñèå ïî Íýøó â èãðåñîãëàñèÿ âñåãäà ñóùåñòâóåò áîëåå òîãî, ñóùåñòâóåò î÷åíü ìíîãî ðàâíîâåñèé.  ñëó÷àå æå,êîãäà äëÿ îáðàçîâàíèÿ ñâÿçè òðåáóåòñÿ æåëàíèå òîëüêî îäíîãî èãðîêà, âîçìîæíû ëþáûåâàðèàíòû ìíîæåñòâà ðàâíîâåñèé. [17℄ äîêàçàíû ñëåäóþùèå ñâîéñòâà ðàâíîâåñèÿ Íýøà â èãðàõ ñîãëàñèÿ:Óòâåðæäåíèå 3.2.1.
Åñëè â èãðå ñîãëàñèÿ ñèòóàöèÿ x ÿâëÿåòñÿ ðàâíîâåñèåì Íýøà è ïðèTâîäèò ê ðåçóëüòèðóþùåé ñåòè g , òî ñèòóàöèÿ x′ , â êîòîðîé x′ in = x′ out = g , òàêæå áóäåòðàâíîâåñèåì Íýøà (â ñèòóàöèè x′ îòñóòñòâóþò áåçîòâåòíûå ïðåäëîæåíèÿ).Ñëåäñòâèå 17.1.  èãðå ñîãëàñèÿ ñåòü g ∈ G(X) ñòàáèëüíà ïî Íýøó òîãäà è òîëüêî òîãäà,Têîãäà ñèòóàöèÿ, â êîòîðîé x′ in = x′ out = g , ÿâëÿåòñÿ ðàâíîâåñèåì Íýøà.Ñëåäñòâèå 17.2.  èãðå ñîãëàñèÿ ñåòü g ∈ G(X) ñòàáèëüíà ïî Íýøó òîãäà è òîëüêî òîãäà,êîãäà ëþáîé èç èãðîêîâ íå ìîæåò âûèãðàòü îò îäíîñòîðîííåãî ðàçðûâà ëþáîãî êîëè÷åñòâàñâîèõ âõîäÿùèõ èëè èñõîäÿùèõ ñâÿçåé (â ïðåäåëàõ, äîçâîëåííûõ ìíîæåñòâàìè ñòðàòåãèéXi èãðîêîâ).106 îáùåì ñëó÷àå, åäèíñòâåííûé âîçìîæíûé àëãîðèòì íàõîæäåíèÿ ðàâíîâåñèé ïî Íýøó ïîëíûé ïåðåáîð ñåòåé. Äåéñòâèòåëüíî, â îáùåì ñëó÷àå, íå ïåðåáðàâ âñå ñåòè, íåëüçÿ áûòüóâåðåííûì, ÷òî íå ñóùåñòâóåò ñåòè, âûèãðûøè â êîòîðîé ñòðîãî äîìèíèðóþò âûèãðûøè âîâñåõ îñòàëüíûõ ñåòÿõ.Òàêèì îáðàçîì, äëÿ íàõîæäåíèÿ ðàâíîâåñíûõ ñåòåé è ðàâíîâåñíûõ âûèãðûøåé, êàê äîêàçàíî â óòâåðæäåíèè 3.2.1, äîñòàòî÷íî ïåðåáðàòü ñåòè è ïðîâåðèòü êàæäóþ èç íèõ íà ñòàáèëüíîñòü ïî Íýøó.
Ïðîâåðêó ñåòè íà ñòàáèëüíîñòü ïî Íýøó ìîæíî ïðîèçâîäèòü äâóìÿñïîñîáàìè. Ïåðâûé ñïîñîá ïðîâåðêà âîçìîæíûõ îòêëîíåíèé êàæäîãî èãðîêà çàíèìàåòO(|X1| + · · · + |Xn |)âðåìåíè. Âòîðîé ñïîñîá ïðîâåðêà âñåõ ñåòåé íà ïðåäìåò óâåëè÷åíèÿóíêöèè âûèãðûøà êàêîãî-ëèáî èãðîêà è åãî îòêëîíåíèÿ çàíèìàåòêóO(n2 |G(X)|). Ïîñêîëü-|X1 |+· · ·+|Xn | ≤ n maxi |Xi | < n2 |G(X)|, ïåðâûé ñïîñîá âñåãäà âûãîäíåå âòîðîãî. Èòîãî àë-ãîðèòì íàõîæäåíèÿ ðàâíîâåñèé ïî Íýøó òðåáóåòO(|G(X)|(|X1|+· · ·+|Xn |)) ≤ O(2(n2 +n−2)/2n)âðåìåíè.Ýòî àëãîðèòì ýêñïîíåíöèàëüíîé âðåìåííîé ñëîæíîñòè áîëåå òîãî, â ïîêàçàòåëå ñòåïåíèñòîèò íån, à (n2 + n − 2)/2, òî åñòü ñëîæíîñòü åùå áîëüøå, êâàäðàòè÷íî-ýêñïîíåíöèàëüíàÿ.Íî âñå æå ïðè ìàëûõïðèn=4 ïîðÿäêànàëãîðèòì ïåðåáèðàåò îáîçðèìîå êîëè÷åñòâî âàðèàíòîâ íàïðèìåð,êîëè÷åñòâî âàðèàíòîâ âñåãî ïîðÿäêà1011 ,512,ïðèn=5 ïîðÿäêà20000,ïðèn=8÷òî, íàïðèìåð, íà ïðîöåññîðå ñ áûñòðîäåéñòâèåì 1ãö òðåáóåò íåñêîëüêèõìèíóò ðàáîòû, ïðèòîê ðàáîòû), ïðèn=9n = 10 ïîðÿäêà1014(÷òî óæå òðåáóåò íåñêîëüêèõ ÷àñîâ èëè äàæå ñó-ñêîðîñòü âû÷èñëåíèé íà îáû÷íîì êîìïüþòåðå ñòàíîâèòñÿ ñëèøêîììåäëåííîé, õîòÿ âû÷èñëåíèå åùå âîçìîæíî íà ñóïåðêîìïüþòåðå, à ïðèn = 11óæå è ñóïåð-êîìïüþòåð íå ñïðàâèòñÿ.Ïðè ýòîì òðàäèöèîííûé àëãîðèòì íàõîæäåíèÿ ðàâíîâåñèÿ ïåðåáîðîì âñåõ ñèòóàöèé èìååò âðåìåííóþ ñëîæíîñòüO(2n2 −1n). îáùåì ñëó÷àå êîëè÷åñòâî ñèòóàöèé ïîðÿäêà êâàä-ðàòà îò êîëè÷åñòâà ñåòåé.
Òàêèì îáðàçîì, åñëè, íàïðèìåð, ìàêñèìàëüíî âîçìîæíîå âðåìÿðàáîòû äëÿ àëãîðèòìà ïåðåáîðà ñåòåé ðàâíîóìíîæåíèå íàñòâînnCn(ïîñêîëüêó êîëè÷åñòâî èãðîêîâ íåâåëèêî,ïðèíöèïèàëüíî íå èçìåíèò ïîêàçàòåëè àëãîðèòìà), ìàêñèìàëüíîå êîëè÷å-èãðîêîâ, äëÿ êîòîðûõ îí ðàáîòîñïîñîáåí, îïðåäåëÿåòñÿ êàê ðåøåíèå óðàâíåíèÿ2(n2 + n − 2)/2 = C ⇔ n2 +n−2 = 2 log2 C ⇒ n =−1 +pp9 + 8 log2 C= −1/2+ 1.125 + 2 log2 C.2Äëÿ òðàäèöèîííîãî àëãîðèòìà ïåðåáîðà ñèòóàöèé ïîëó÷èì2(n2 − 1)/2 = C ⇔ n2 − 1 = log2 C ⇒ n =nêàê ðåøåíèå óðàâíåíèÿp1 + log2 C,107òî åñòü àëãîðèòì ïåðåáîðà ñåòåé ïîçâîëÿåò óâåëè÷èòü êîëè÷åñòâî èãðîêîâ ïðèìåðíî â1.4√2≈ðàçà ñêàæåì, ñ 7 äî 10.Åñëè íàñ èíòåðåñóþò íå òîëüêî ðàâíîâåñíûå ñåòè è âûèãðûøè, íî è ñàìè ðàâíîâåñíûåñòðàòåãèè, òî àëãîðèòì îêàçûâàåòñÿ íåìíîãî ñëîæíåå.  ýòîì ñëó÷àå äëÿ êàæäîé ñòàáèëüíîéñåòègíóæíî íàéòè ðàâíîâåñíûå ñèòóàöèè, ïîðîæäàþùèå ýòó ñòàáèëüíóþ ñåòü.
Åñëè â ñåòèåñòü äóãàäóãè(i, j), òî â ëþáîé ðàâíîâåñíîé ñèòóàöèè, ðàçóìååòñÿ, x′out= x′inijji = 1. Åñëè â ñåòè íåò(j, i),òî âîçìîæíû 3 ñëó÷àÿ:îáðàçîì, íàéäÿk′out′outx′out= x′in= 0, x′in= 1, x′inijji = 0; xijji = 1; xijji = 0.ÒàêèìO(3n(n−1)/2 )ñèòóà-ñòàáèëüíûõ ñåòåé, íóæíî äëÿ êàæäîé èç íèõ ïðîâåðèòüöèé íà ðàâíîâåñíîñòü çàO(|X1 | + · · · + |Xn |)âñå ðàâíîâåñíûå ñèòóàöèè çàâðåìåíè.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
