Диссертация (1149954), страница 26
Текст из файла (страница 26)
Áóäåì ñðàçó ðàññìàòðèâàòü ãðóïïîâûå ñåòåâûå èãðû â îáùåì ñëó÷àå äëÿ ìóëüòèãðàîâ.Îïðåäåëåíèå 55. ðóïïîâàÿ ñåòåâàÿ èãðà áåç ñîâìåñòíûõ âåðøèí(N, ((L, M, s, e), l, (Xi )i∈N ), G, g, (Hi)i∈N ),• N = {1, . . . , n} ýòî ñåòåâàÿ èãðàãäå ìíîæåñòâî èãðîêîâ;• (L, M, s, e) ìóëüòèãðàèãðû (L ìíîæåñòâî âåðøèí ãðàà, ìíîæåñòâî ðåáåð). Áóäåì îáîçíà÷àòüM(a,b)M ìíîæåñòâî äóã, ìíîæåñòâî äóã ìåæäóìíîæåñòâî äóã ìåæäó âåðøèíàìè èç ïîäìíîæåñòâAèB;aèb, M(A,B)M117• l: L → N óíêöèÿ, ñîïîñòàâëÿþùàÿ êàæäîé âåðøèíå ãðàà èãðîêà, óïðàâëÿþùåãîýòîé âåðøèíîé;• Xi ⊂ Xi0i-ãî ìíîæåñòâî ñòðàòåãèé2M(l−1 (i),L\l−1 (i))èãðîêà, ãäåXi0 = Xi0ext × Xi0int , ìíîæåñòâî âñåõ âîçìîæíûõ ïðåäëîæåíèéíèþ åãî âåðøèí ñ âåðøèíàìè äðóãèõ èãðîêîâ,íîXi ⊆ 2M(l−1 (i),L) , X =i∈NXi ⊆ 2M(L,L)i-ãîXi0ext =èãðîêà ïî ñîåäèíå-Xi0int = 2M(l−1 (i),l−1 (i))âñåõ âíóòðåííèõ ñîåäèíåíèé (ñâÿçåé) ìåæäó âåðøèíàìèQi-ãîãäå ìíîæåñòâîèãðîêà.
Ñîîòâåòñòâåí- ìíîæåñòâî ñèòóàöèé â èãðå, êîòîðîåìîæíî, ïî àíàëîãèè ñ îáû÷íîé ñåòåâîé èãðîé ïðåäñòàâèòü ìàòðèöåé (òîëüêî èãðîêèóæå îïðåäåëÿþò íå ñòðîêè, à ãðóïïû ñòðîê);• g(x) = min(x, xT ),êàê è â îáû÷íîé ñåòåâîé èãðå.Óòâåðæäåíèå 3.2.8. Äëÿ ëþáîé ãðóïïîâîé ñåòåâîé èãðû ìîæíî îïðåäåëèòü èçîìîðíóþïàðàìåòðè÷åñêóþ ñåòåâóþ èãðó íà àãðåãèðîâàííîì (âëîæåííîì) ìóëüòèãðàå, â êîòîðîé:• N ìíîæåñòâî âåðøèí ãðàà, êîòîðîå ïðîñòî ñîâïàäàåò ñ ìíîæåñòâîì èãðîêîâ;• U(i,i) = 2Fl(j)=l(k)=iM(j,k) ìíîæåñòâî ïîäñåòåé, ïîðîæäåííûõ âåðøèíàìè l−1 (i);• Si = G(Xiint ) ìíîæåñòâî ñîñòîÿíèé i-ãî èãðîêà, çàâèñÿùåå îò ìíîæåñòâà åãî äî-ïóñòèìûõ âíóòðåííèõ ñîåäèíåíèé;• U(i,j) = 2Fi′ ∈l−1 (i), j ′ ∈l−1 (j)M(i′ ,j ′ ) ìíîæåñòâî ñîñòîÿíèé ñâÿçåé ìåæäó èãðîêàìè i è j ,ò.å., ìíîæåñòâ äóã èëè àãðåãèðîâàííûõ äóã ìåæäó ìíîæåñòâàìè âåðøèí èãðîêîâi è j , ñ åñòåñòâåííîé ñòðóêòóðîé íèæíåé ïîëóðåøåòêè íà ìíîæåñòâàõ;• Ui (si ) = Xiext (xinti ) çàâèñèìîñòü âíåøíèõ ñîåäèíåíèé îò âíóòðåííèõ;• ñèòóàöèÿ x ïîðîæäàåò ñåòü g ′(x) = A(g(x)), ãäå A îïåðàöèÿàãðåãèðîâàíèÿãðàà,òî åñòü, ìîðèçì â ìóëüòèãðà (N = A(L), M ′ , s′ , e′ ), ïðè êîòîðîì âñå âåðøèíû,ïðèíàäëåæàùèå îäíîìó èãðîêó, ïåðåõîäÿò â îäíó âåðøèíó.Ýòà ïàðàìåòðè÷åñêàÿ ñåòåâàÿ èãðà îïðåäåëÿåò èãðó â íîðìàëüíîé îðìå, èçîìîðíóþèñõîäíîé ãðóïïîâîé ñåòåâîé èãðå.
Åñëè èñõîäíàÿ èãðà áûëà èãðîé ñîãëàñèÿ, òî àãðåãèðîâàííàÿ òîæå áóäåò èãðîé ñîãëàñèÿ.Äîêàçàòåëüñòâî.Íåñëîæíî âèäåòü, ÷òî îïèñàííîå ïðåîáðàçîâàíèå äåéñòâèòåëüíî îïðåäåëÿ-åò ïàðàìåòðè÷åñêóþ ñåòåâóþ èãðó. Ïðè ýòîì ìíîæåñòâà ñòðàòåãèé è óíêöèè âûèãðûøà íåìåíÿþòñÿ. Åñëè â àãðåãèðîâàííîé èãðåx ≤ x′ ,òî â èñõîäíîé òåì áîëååx ≤ x′ ,ïîñêîëüêóêîëè÷åñòâî êîìïîíåíò, ïî êîòîðûì ïðîèçâîäèòñÿ ñðàâíåíèå, óâåëè÷èëîñü ëèøü íà òå êîìïîíåíòû, ãäå áûëî ðàâåíñòâî.118Àíàëîãè÷íî, ìîæíî îïðåäåëèòü ïàðàìåòðè÷åñêèå ãðóïïîâûå èãðû.
Èõ ìîæíî ñâåñòè êïàðàìåòðè÷åñêèì (íå ãðóïïîâûì) èãðàì.Ïðèìåð 13.Ïîñêîëüêó ëþáóþ ÎÄÑ ñ äèñêðåòíûì âðåìåíåì ìîæíî ïðåäñòàâèòü ãðàîì,ïîî÷åðåäíàÿ ìíîãîøàãîâàÿ èãðà ñ ïîçèöèîííûìè ñòðàòåãèÿìè ýòî ãðóïïîâàÿ ñåòåâàÿ èãðà,â êîòîðîé èêñèðîâàíà íåêîòîðàÿ âåðøèíà íà÷àëüíàÿ ïîçèöèÿ. Ñòðàòåãèÿ èãðîêà ñîñòîèòâ òîì, ÷òî â êàæäîé âåðøèíå îí âûáèðàåò îäíó è òîëüêî îäíó èñõîäÿùóþ èç âåðøèíû äóãó,åñëè èñõîäÿùèå äóãè ñóùåñòâóþò.  èãðàõ ñ íåïîëíîé èíîðìàöèåé íàëîæåíû îãðàíè÷åíèÿ íà âûáîð èñõîäÿùèõ äóã, ñâÿçûâàþùèå âûáîðû èãðîêà â ðàçíûõ âåðøèíàõ: ñóùåñòâóþòíåêîòîðûå ýêâèâàëåíòíîñòè âåðøèí (èíîðìàöèîííûåìíîæåñòâà )è èçîìîðèçìû èñõî-äÿùèõ äóã, òàê ÷òî èãðîê îáÿçàí âûáèðàòü èçîìîðíûå äóãè.
Ñèòóàöèÿ â èãðå ïîðîæäàåòåäèíñòâåííûé ïóòü èç íà÷àëüíîé ïîçèöèè, êîòîðûé è îïðåäåëÿåò èñõîä èãðû.Ïîñêîëüêó íà êàæäóþ äóãó âëèÿåò òîëüêî îäèí èãðîê, òàêàÿ èãðà íå ÿâëÿåòñÿ èãðîé ñîãëàñèÿ ñêîðåå, åå ïðîòèâîïîæíîñòüþ. Íî, êàê è â èãðå ñîãëàñèÿ, â èãðå ñ ïîëíîé èíîðìàöèåéãàðàíòèðîâàíî ñóùåñòâîâàíèå ðàâíîâåñèÿ (ñîâåðøåííî äðóãîãî òèïà).Åñòåñòâåííîå îáîáùåíèå èãðû íà ãðàå, â êîòîðûõ íà âûáîð äóãè, èñõîäÿùåé èç âåðøèíû, âëèÿåò íåñêîëüêî èãðîêîâ.
Ýòî óæå îáùàÿ ãðóïïîâàÿ èãðà ñ ìíîæåñòâàìè ñòðàòåãèéXiS .Îáùèå ãðóïïîâûå èãðûÎáùàÿ ãðóïïîâàÿ èãðà îáîáùàåò èãðû îðìèðîâàíèÿ ñåòåé è èãðû íà ñåòÿõ. Áóäåì ñðàçóãîâîðèòü îá îáùèõ ãðóïïîâûõ èãðàõ êàê î ïàðàìåòðè÷åñêèõ, ïîñêîëüêó ýòî áîëåå óäîáíî,÷åì èñïîëüçîâàòü êðàòíûå äóãè.Îïðåäåëåíèå56.Îáùàÿãðóïïîâàÿ(N, (L, M, s, e), ρ, (Xi )i∈N , G, g, (Hi )i∈N ),•ìíîæåñòâî èãðîêîâNñåòåâàÿèãðàýòîñåòåâàÿèãðàãäåè ìóëüòèãðà(L, M, s, e) îïðåäåëÿþòñÿ òàê æå, êàê è â ãðóïïîâîéèãðå áåç ñîâìåñòíûõ âåðøèí;• ρ⊆L×N äâóìåñòíîå îòíîøåíèå, ïîêàçûâàþùåå, êàêèå èãðîêè ó÷àñòâóþò â óïðàâ-ëåíèè êàêèìè âåðøèíàìè;• Xi ⊂ Xi0 ,• SliãäåXi0 =ilρi (SlQ× Uli ); ñîñòîÿíèÿ âåðøèíû l , êîòîðûå âûáèðàåò• Uli = Uli1 × Uli2 × · · · × Ulin óïðàâëåíèåi-ãîi-éèãðîê;èãðîêà èñõîäÿùèìè äóãàìè;119• Ulij =ij• Um•Qm:s(m)=l ìíîæåñòâî ñîåäèíåíèé ìíîæåñòâî ñîåäèíåíèéi-ãîìíîæåñòâî ñîñòîÿíèé âåðøèíûæå èãðîêà•ijUmlèãðîêà ñèãðîêàii-ãîj -ìèãðîêà ñïî äóãåj -ìèç âåðøèíû l ;m;çàâèñèò îò ñîñòîÿíèé âõîäÿùèõ âläóã òîãîSli ({uiim }e(m)=l );ìíîæåñòâî âîçìîæíûõ ñîñòîÿíèé äóã çàâèñèò îò ñîñòîÿíèÿ íà÷àëüíîé âåðøèíû:• G(X), g, (Hi )ni=1Uli (sil );îïðåäåëÿþòñÿ òàê æå, êàê â ïàðàìåòðè÷åñêîé ãðóïïîâîé èãðå áåçñîâìåñòíûõ âåðøèí.Äàííîå îïðåäåëåíèå îáîáùàåò êàê îïðåäåëåíèå ñòàòè÷åñêîé óïðàâëÿåìîé ñèñòåìû â äèñêðåòíîì ïðîñòðàíñòâå (åñëèN = L, ρ = I ).n = 1),òàê è îïðåäåëåíèå ïàðàìåòðè÷åñêîé ñåòåâîé èãðû (åñëè òàêîé èãðå ìåæäó âåðøèíàìèaèb,êîòîðûìè óïðàâëÿþò íåñêîëüêî èã-ðîêîâ, ìîæåò áûòü íåñêîëüêî ïàðàëëåëüíûõ ñîåäèíåíèé.
 èõ ÷èñëî âõîäÿò è ñîåäèíåíèÿèãðîêà ñàìîãî ñ ñîáîé.Ïðèìåð 14.Ìíîãîøàãîâàÿ èãðà ñ ïîçèöèîííûìè ñòðàòåãèÿìè, â êîòîðîé ìîãóò õîäèòüîäíîâðåìåííî íåñêîëüêî èãðîêîâ ýòî îáùàÿ ãðóïïîâàÿ èãðà ñî ñòðàòåãèÿìè èçXiS .Óòâåðæäåíèå 3.2.9. Îáùóþ ãðóïïîâóþ èãðó ìîæíî ñâåñòè ê ãðóïïîâîé èãðå áåç ñîâ-ìåñòíûõ âåðøèí, åñëè ðàçìíîæèòü âåðøèíû: êàæäóþ âåðøèíó a, óïðàâëÿåìóþ èãðîêàìèi1 , . . . ik , ïðåâðàòèòü â k âåðøèí (a, i1 ), . . . (a, ik ). Ïðè ýòîì ïîëó÷èòñÿ èçîìîðíàÿ èãðà.Äîêàçàòåëüñòâî.Ñëåäóåò èç ñîïîñòàâëåíèÿ îïðåäåëåíèé 55 è 56.ðóïïîâóþ èãðó áåç ñîâìåñòíûõ âåðøèí, â ñâîþ î÷åðåäü, ìîæíî ñâåñòè ê ïàðàìåòðè÷åñêîéèãðå. Òàêèì îáðàçîì, äóãè ñåòè â îáùåé ãðóïïîâîé èãðå äåëÿòñÿ íà 2 êëàññà:1.åáðà âçàèìîäåéñòâèÿ M piñâåðøèíàìè èãðîêàj.ìåæäó ðàçíûìè èãðîêàìèièjñîåäèíÿþò âåðøèíû èãðîêàÎíè ñîõðàíÿþòñÿ è ñëèâàþòñÿ â îäíî ðåáðî(i, j)ïðè ïðåîáðà-çîâàíèè èãðû â íå ãðóïïîâóþ ïàðàìåòðè÷åñêóþ èãðó.2.Ñòðóêòóðíûå äóãè M s ,èãðîêài.ïðèíàäëåæàùèå èãðîêói,ñîåäèíÿþò ìåæäó ñîáîé âåðøèíûÎíè èñ÷åçàþò ïðè ïðåîáðàçîâàíèè èãðû â íå ãðóïïîâóþ ïàðàìåòðè÷åñêóþèãðó.Èãðû íà ñåòÿõÎïðåäåëåíèå 57.
Èãðà íà ñåòè[42℄ ýòî îáùàÿ ãðóïïîâàÿ èãðà, â êîòîðîé êàæäûé èãðîêóïðàâëÿåò êàæäîé âåðøèíîé è íåò âçàèìîäåéñòâèÿ ìåæäó ðàçíûìè èãðîêàìè (òî åñòü âñåäóãè ñòðóêòóðíûå).120Òàêèì îáðàçîì, â èãðå íà ñåòè êàæäûé èãðîê íåçàâèñèìî îò îñòàëüíûõ óïðàâëÿåò ðàñïðåäåëåííîé ñòàòè÷åñêîé ñèñòåìîé â äèñêðåòíîì ïðîñòðàíñòâå. Âàæíûé ÷àñòíûé ñëó÷àé èãðíà ñåòÿõ:Îïðåäåëåíèå 58. Ñåòåâàÿ èãðà óïðàâëåíèÿ ïîòîêàìèæåñòâî ñòðàòåãèéXièãðîêài[70℄ èãðà íà ñåòè, â êîòîðîé ìíî- ýòî ìíîæåñòâî îáîáùåííûõ ïîòîêîâ â ñåòè.Òàêèì îáðàçîì, èãðîêè íåçàâèñèìî äðóã îò äðóãà ïóñêàþò ïî ñåòè ïàðàëëåëüíûå ìíîãîïðîäóêòîâûå ïîòîêèg.g1 , . .
. , gnè ïîëó÷àþò âûèãðûø, çàâèñÿùèé îò ðåçóëüòèðóþùåãî ïîòîêàÇàäà÷à ìàêñèìèçàöèè ïîòîêà ïðè ýòîì òðèâèàëüíà, ïîñêîëüêó ïîòîêè íå çàâèñÿò äðóãîò äðóãà, à ñëåäîâàòåëüíî, çàäà÷à ðàñïàäàåòñÿ â ïðÿìîå ïðîèçâåäåíèå çàäà÷ ìàêñèìèçàöèèïîòîêà äëÿ êàæäîãî èãðîêà.Èíîå äåëî åñëè íà êàæäîé äóãå çàäàíà óíêöèÿ ñòîèìîñòè, çàâèñÿùàÿ îò âñåõ ïîòîêîââ ñåòè.  ýòîì ñëó÷àå, äàæå ïðîñòåéøèå ñåòåâûå èãðû óïðàâëåíèÿ ïîòîêàìè â ñåòÿõ áåçóñèëåíèé ñ íåëèíåéíîé óíêöèåé ñòîèìîñòè ïðåäñòàâëÿþò èíòåðåñ.
Íàïðèìåð, äëÿ ñåòåéáåç óñèëåíèé ñ âîãíóòûìè óíêöèÿìè ñòîèìîñòè äîêàçàíî ñóùåñòâîâàíèå ðàâíîâåñèÿ [70℄.Âàæíûé ÷àñòíûé ñëó÷àé èãðû ìàðøðóòèçàöèè, â êîòîðûõ êàæäûé èãðîê âûáèðàåò îäèíïóòü â ñåòè, òî åñòü ïîòîê âåëè÷èíû 1 [8℄Òðåáîâàíèå îòñóòñòâèÿ âçàèìîäåéñòâèé ìåæäó èãðîêàìè â èãðå óïðàâëåíèÿ ïîòîêàìè âîçíèêàåò ïîòîìó, ÷òî èíà÷å íåçàâèñèìîñòü ñòðàòåãèé èãðîêîâ íå ïîçâîëÿåò âûïîëíèòü óñëîâèÿïîòîêà.Ïðèìåð 15.Ïóñòü èìåþòñÿ 3 âåðøèíû è 3 èãðîêà, êîòîðûå ïîëíîñòüþ óïðàâëÿþò ñîîòâåò-ñòâåííî âåðøèíàìè1, 2, 3.òå÷åò êëàññè÷åñêèé ïîòîêÏóñòü â ãðàå âîçìîæíû òîëüêî äóãèg,óäîâëåòâîðÿþùèé óñëîâèþ(1, 2) (2, 3),g(1, 2) = g(2, 3)âåðøèíó ñòîëüêî èç íåå è âûòåêàåò). Òîãäà äëÿ ñòðàòåãèé÷åðåç êîòîðûå(ñêîëüêî âòåêàåò âs1 , (s12 , s22 ), s3 ñîîòâåòñòâåííî ïåð-âîãî, âòîðîãî è òðåòüåãî èãðîêà, îïðåäåëÿþùèõ íåîòðèöàòåëüíîå çíà÷åíèå ïîòîêà â äóãàõ,äîëæíî âûïîëíÿòüñÿ óñëîâèåmin(s1 , s12 ) = min(s22 , s3 ).Î÷åâèäíî, íåçàâèñèìîñòü ñòðàòåãèé èãðîêîâ è ýòî óñëîâèå íå ïðîòèâîðå÷àò äðóã äðóãóòîëüêî â òîì ñëó÷àå, êîãäà äëÿ ëþáûõ ñòðàòåãèés12 = s22 ≤ s1 , s3 .Íî ýòî çíà÷èò, ÷òî çíà÷å-íèå ïîòîêà â ñåòè ïîëíîñòüþ îïðåäåëÿåò 2-é èãðîê è ðåàëüíîãî âçàèìîäåéñòâèÿ ñ äðóãèìèèãðîêàìè íåò.Àíàëîãè÷íî, è â áîëåå ñëîæíûõ ñëó÷àÿõ â ñòàòè÷åñêîé ñåòåâîé èãðå âçàèìîäåéñòâèå èãðîêîâ íåâîçìîæíî, ïîñêîëüêó èãðîêè íå ìîãóò äîãîâîðèòüñÿ çàðàíåå î ñîáëþäåíèè óñëîâèé121ïîòîêà.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
