Диссертация (1149954), страница 25
Текст из файла (страница 25)
 ñëó÷àå, êîãäàU(i,j) = {0, 1} × {0, 1},íåñëîæíîïîñòðîèòü èçîìîðèçì ñ èãðàìè îðìèðîâàíèÿ îðèåíòèðîâàííûõ ãðàîâ [17℄ (äîñòàòî÷íîóïîðÿäî÷èòü âåðøèíû ãðàà è äëÿ êàæäîé ïàðû èãðîêîâ äîãîâîðèòüñÿ ñ÷èòàòü ïðÿìóþäóãó ïåðâîé, à îáðàòíóþ âòîðîé).  ñëó÷àå, êîãäàU(i,j) = {0},îíè èçîìîðíû âñåì èã-ðàì â íîðìàëüíîé îðìå. Òàêèì îáðàçîì, ïàðàìåòðè÷åñêèå ñåòåâûå èãðû îáîáùåíèå òðåõóêàçàííûõ êëàññîâ èãð.
Óæå ýòî îçíà÷àåò, ÷òî íå ìîæåò áûòü íèêàêèõ îáùèõ ìåòîäîâ íàõîæäåíèÿ ïðèíöèïîâ îïòèìàëüíîñòè â ïàðàìåòðè÷åñêîé ñåòåâîé èãðå, áîëåå ýåêòèâíûõ,÷åì òàêîâûå äëÿ èãð îðìèðîâàíèÿ ñåòåé è äëÿ èãð â íîðìàëüíîé îðìå.Áóäåì íàçûâàòü ïàðàìåòðè÷åñêóþ ñåòåâóþ èãðó(u(i,1) , . . . u(i,n) ))ýëåìåíòûèãðîêièxii = six′i ≤ xièãðîé ñîãëàñèÿ,åñëè èçxi ∈ Xi (xi =(â ñìûñëå ïîýëåìåíòíîãî ÷àñòè÷íîãî ïîðÿäêà íà ïîëóðåøåòêàõ,ñ÷èòàåì ñðàâíèìûìè, òîëüêî åñëè îíè ðàâíû) ñëåäóåòèìååò ïðàâî ïðåäëîæèòü èãðîêójx′i ∈ Xi .Ò.å. åñëèîáðàçîâàòü ñâÿçü ñ áîëüøèìè ïàðàìåòðàìè, òîèìååò ïðàâî ïðåäëîæèòü îáðàçîâàòü ñâÿçü è ñ ìåíüøèìè ïàðàìåòðàìè.Ïðèíöèïû îïòèìàëüíîñòèÎïðåäåëåíèÿ äîñòèæèìîé ñåòè, ñèëüíî äîñòèæèìîé ñåòè, êîàëèöèîííî äîñòèæèìîé ñåòè, àòàêæå ñåòè, ñòàáèëüíîé ïî Íýøó, ïîïàðíî ñòàáèëüíîé, ãèáðèäíî ñòàáèëüíîé è êîàëèöèîííî ñòàáèëüíîé äëÿ ïàðàìåòðè÷åñêèõ ñåòåâûõ èãð, àáñîëþòíî àíàëîãè÷íû òàêîâûì äëÿ èãðîðìèðîâàíèÿ ñåòåé.Óòâåðæäåíèå 3.2.6.
Åñëè â ïàðàìåòðè÷åñêîé èãðå ñîãëàñèÿ ñèòóàöèÿ x ÿâëÿåòñÿ ðàâíîâå-ñèåì Íýøà (êîàëèöèîííûì ðàâíîâåñèåì, ñèëüíûì ðàâíîâåñèåì) è ïðèâîäèò ê ðåçóëüòèðóþùåé ñåòè g = inf(x, xT ), òî ñèòóàöèÿ x′ , â êîòîðîé x′ = x′T = g , òàêæå áóäåò ðàâíîâåñèåìÍýøà (êîàëèöèîííûì ðàâíîâåñèåì, ñèëüíûì ðàâíîâåñèåì).Çàìå÷àíèå3.2.4.  ïàðàìåòðè÷åñêîé èãðå ñîãëàñèÿ ñåòüg ∈ G(S, U) ñòàáèëüíà ïî Íýøó(êîàëèöèîííî ñòàáèëüíà, ñèëüíî ñòàáèëüíà) åñëè ñèòóàöèÿ, â êîòîðîé x′ = x′T = g , ÿâëÿåòñÿðàâíîâåñèåì Íýøà (êîàëèöèîííûì ðàâíîâåñèåì, ñèëüíûì ðàâíîâåñèåì).Äîêàçàòåëüñòâî.inf(x′ , x′T ).Äåéñòâèòåëüíî, ñèòóàöèÿx′ ≤ xïîðîæäàåò òó æå ñåòüÎòêëîíåíèÿ èãðîêà (êîàëèöèè) â ñòîðîíó óìåíüøåíèÿèçìåíåíèå âíóòðåííåãî ñîñòîÿíèÿs′′ 6= sg = inf(x, xT ) =x′′ ≤ x′ ≤ x,à òàêæåíå óëó÷øàò åãî ïîëîæåíèå, ñîãëàñíî îïðåäåëåíèþðàâíîâåñèÿ. À îòêëîíåíèÿ â ñòîðîíó óâåëè÷åíèÿ äàæå íå èçìåíÿò ñåòü, ïîñêîëüêóx′ ,à çíà÷èò,x′′ (i, j) = x′ (i, j)ëèáîx′′T (i, j) = x′ (i, j)(èáî ìåíÿþòñÿ ýëåìåíòû, ó êîòîðûõìíîæåñòâî íîìåðîâ ñòðîê íå ïåðåñåêàåòñÿ ñ ìíîæåñòâîì íîìåðîâ ñòîëáöîâ:ñâîéñòâà íèæíåé ïîëóðåøåòêè,x′ (i, j).x′T ={i} ∩ {j} = ∅).
Èç∀x′′ (i, j) ∈ U(i,j) inf(x′′ (i, j), x′ (i, j)) = inf(x′′ (i, j), x′T (i, j)) =113Ñëåäñòâèå 17.3.  ïàðàìåòðè÷åñêîé èãðå ñîãëàñèÿ ñåòü g ∈ G(S, U) (êîàëèöèîííî) ñòà-áèëüíà ïî Íýøó òîãäà è òîëüêî òîãäà, êîãäà ëþáîé èç èãðîêîâ íå ìîæåò âûèãðàòü îòóìåíüøåíèÿ (â ñìûñëå ÷àñòè÷íîãî ïîðÿäêà íà íèæíåé ïîëóðåøåòêå) ëþáîãî êîëè÷åñòâàïàðàìåòðîâ ñâîèõ âõîäÿùèõ èëè èñõîäÿùèõ ñâÿçåé.Óòâåðæäåíèå îá èçîëèðóþùåì ìàêñèìèíå äëÿ èãðîêà ìîæíî äîêàçàòü äàæå â áîëåå îáùåìâèäå, ðàññìàòðèâàÿ íå îäíîãî èãðîêà, à ñóììàðíûé âûèãðûø ëþáîé êîàëèöèè:Óòâåðæäåíèå 3.2.7.  êîíå÷íîé ïàðàìåòðè÷åñêîé èãðå ñîãëàñèÿ ñóùåñòâóåò òàêàÿ ìàê-ñèìèííàÿ ñèòóàöèÿ äëÿ êîàëèöèè C , ÷òî äëÿ ëþáîãî ðåáðà (i, j) òàêîãî, ÷òî i ∈ C, j ∈/ C,áóäåò u(i,j) = 0 (êîàëèöèÿ C èçîëèðîâàíà îò îñòàëüíûõ èãðîêîâ).Äîêàçàòåëüñòâî.ñòîÿíèè êîàëèöèèàññìîòðèì, äëÿ ïðîñòîòû, ìàêñèìèí ïðè èêñèðîâàííîì âíóòðåííåì ñî-C.Ìàêñèìèí ïî âñåì ñòðàòåãèÿì êîàëèöèèCðàâåí, î÷åâèäíî, ìàêñè-ìàëüíîìó èç ìàêñèìèíîâ ïî êàæäîìó âíóòðåííåìó ñîñòîÿíèþ.
Ïîýòîìó, åñëè îêàæåòñÿ, ÷òîäëÿ ìàêñèìèíà ïðè êàæäîì ñîñòîÿíèè âûïîëíÿåòñÿ óòâåðæäåíèå, òî îíî âûïîëíÿåòñÿ è äëÿîáùåãî ìàêñèìèíà.Ïóñòü íàøà ìàêñèìèííàÿ ñòðàòåãèÿ (xC , x−C ).Ïðåäëîëîæèì, ÷òî ïðè åå ïðèìåíå-íèè ïîëó÷àåòñÿ ñåòü, â êîòîðîé íàáîð ðåáåð, ñâÿçàííûõ ñ êîàëèöèåéuc = (u(i,j), u(j,i) )i∈C,j ∈C/ .(i, j)C,èìååò çíà÷åíèåÅñëè ïðè óìåíüøåíèè ïàðàìåòðîâ äëÿ íåêîòîðîãî íàáîðà ðåáåðñóììàðíûé âûèãðûø êîàëèöèè óìåíüøèòñÿ, ñèòóàöèþ íåëüçÿ ñ÷èòàòü ìàêñèìèííîé,ïîñêîëüêó òîãäà ñîîòâåòñòâóþùèå èãðîêèjìîãóò îäíîâðåìåííî óìåíüøèòü ïàðàìåòðû äëÿýòèõ ðåáåð (÷òî âîçìîæíî, ïîñêîëüêó ðàññìàòðèâàåòñÿ èãðà ñîãëàñèÿ), òàê ÷òî ñóììàðíûéâûèãðûø êîàëèöèè óìåíüøèòñÿ.Ïðåäïîëîæèì òåïåðü, ÷òî ïðè óìåíüøåíèè èãðîêàìè èç êîàëèöèèïîëó÷èòñÿ ñèòóàöèÿHC (xC , x−C ).ðåáåð(x′C , x−C )Còàêàÿ, ÷òî âûèãðûø êîàëèöèè óâåëè÷èòñÿ:Ïðè ýòîì ñòðàòåãèÿx′Cîòëè÷àåòñÿ îò ñòðàòåãèèxCïàðàìåòðîâHC (x′C , x−C ) >òîëüêî òåì, ÷òî ïàðàìåòðûu′C < uC ⇒ x′C < xC .Ïîñêîëüêó èñõîäíàÿ ñèòóàöèÿ áûëà ìàêñèìèííîé, ýòî çíà÷èò, ÷òî ñèòóàöèÿíå äîñòàâëÿåò ìèíèìóìHCïî ñòðàòåãèÿì îñòàëüíûõ èãðîêîâuCx−C(x′C , x−C )(åñëè áû îíà äîñòàâ-ëÿëà ìèíèìóì, âîçíèêëî áû ïðîòèâîðå÷èå ñ ìàêñèìèííîñòüþ îòëè÷íîé îò íåå ñèòóàöèè(xC , x−C )).àññìîòðèì òîãäà íàáîð ñòðàòåãèéþùèé ìèíèìóìHC (x′C , x′−C ) < HC (x′C , x−C ).ïàðàìåòðàìè ðåáåðu′′C = inf(xC , x′−C ).inf(x′C , x′−C ) = u′′C .x′−C 6= x−C ,êîòîðûé äîñòàâëÿåò ñîîòâåòñòâó-Ïàðå ñòðàòåãèéx′C , x′−Cñîîòâåòñòâóåò ñåòü ñÎòñþäà, ïî ñâîéñòâàì íèæíåé ïîëóðåøåòêè, ñëåäóåòÑêàçàííîå èëëþñòðèðóåò ðèñóíîê 3.1.Ïîñêîëüêó âíóòðåííåå ñîñòîÿíèå êîàëèöèèCèêñèðîâàíî, ïîëó÷àåìHC (xC , x′−C ) =114xèñ.
3.1: Ìèíèìàêñ â ñåòåâîé èãðåxC-Cx'x'-CCx'u-Cu'u''u''HC (x′C , x′−C ).Îòñþäà ñëåäóþò ñîîòíîøåíèÿHC (xC , x−C ) ≤ HC (xC , x′−C ) = HC (x′C , x′−C ) < HC (x′C , x−C ).Íî(xC , x−C )è(x′C , x′−C )ìîæíî ïåðåéòè ê ñèòóàöèè ñèòóàöèè, â êîòîðûõ äîñòèãàåòñÿ ìèíèìóì. Ýòî çíà÷èò, ÷òî(x′C , x′−C ),â êîòîðîé áóäóò ìåíüøå ïàðàìåòðû ðåáåð(i, j),è îíàòàêæå áóäåò ìàêñèìèííîé.Èòàê, âûèãðûø êîàëèöèè ïðè óìåíüøåíèè ïàðàìåòðîâ íåêîòîðûõ ðåáåð(i, j)íå ìîæåòóìåíüøèòüñÿ, à åñëè îí ìîæåò óâåëè÷èòüñÿ, òî ìîæíî ïåðåéòè ê íîâîé ìàêñèìèííîé ñèòóàöèè, â êîòîðîé ïàðàìåòðû ðåáåð(i, j)îêàçûâàþòñÿ ìåíüøå.
Ïîñêîëüêó èãðà êîíå÷íà,ïîâòîðÿÿ ýòîò ïðîöåññ, ðàíî èëè ïîçäíî ïîëó÷àåì ñèòóàöèþ, â êîòîðîé, êàêèå áû ïàðàìåòðûðåáåð íå óìåíüøàëè, âûèãðûø îñòàíåòñÿ íåèçìåííûì. Ýòî çíà÷èò, ÷òî, ïîñêîëüêó ýòî èãðàñîãëàñèÿ, ìîæíî óäàëèòü âñå ðåáðà(i, j)(ñâåñòè èõ ïàðàìåòðû ê íóëþ) è, ðàññóæäàÿ êàêâûøå, ïîëó÷èì íåêóþ ìàêñèìèííóþ ñèòóàöèþ(xC , x′−C ),â êîòîðîé íåò ðåáåð ìåæäóCèN \ C.Ýòè ñâîéñòâà ïîçâîëÿþò èñêàòü îïòèìàëüíûå ðåøåíèÿ â ïàðàìåòðè÷åñêèõ èãðàõ, ïåðåáèðàÿ íå âîçìîæíûå ñòðàòåãèè èãðîêîâ, à âîçìîæíûå ñåòè, ÷òî ñóùåñòâåííî ñîêðàùàåò êîëè÷åñòâî âàðèàíòîâ ïðè ïåðåáîðå.
Òàê æå, êàê è äëÿ èãð îðìèðîâàíèÿ ñåòåé, â ïàðàìåòðè÷åñêèõñåòåâûõ èãðàõ ìîæíî íàéòè [49℄:1. Ñòàáèëüíûå ñåòè çà âðåìÿO(|G(S, U)|(|S1|Qj|U(j,1) | + · · · + |Sn |2. Ìàêñèìèííóþ ñòðàòåãèþ çà âðåìÿO(|G(S, U)|).3. Ïîïàðíî ñòàáèëüíûå ñåòè çà âðåìÿO(|G(S, U)|4. èáðèäíî ñòàáèëüíûå ñåòè çà âðåìÿ5. Ñèëüíî ñòàáèëüíûå ñåòè çà âðåìÿPi,jO(|G(S, U)|(|S1|O(|G(S, U)|2n2 ).Qj|U(j,n) |)).|U(i,j) |).Qj|U(j,1) | + · · · + |Sn |Qj|U(j,n) |)).1156. Êîàëèöèîííî ñòàáèëüíûå ñåòè çà âðåìÿèñïîëüçîâàíèè ïåðâîãî àëãîðèòìà èO(|G(S, U)|PS∈C (|S|O(|G(S, U)|2 (n2 + h)),ãäåQi∈S,j∈NO(h)|Si ||U(i,j) |)) ïðè ñëîæíîñòü ïðî-âåðêè òîãî, âêëþ÷àåò ëè â ñåáÿ äàííîå ìíîæåñòâî êàêóþ-ëèáî êîàëèöèþ ïðè èñïîëüçîâàíèè âòîðîãî àëãîðèòìà.Åñëè êîëè÷åñòâî ñîñòîÿíèé âåðøèíû êàæäîãî èãðîêà ïîðÿäêàÿíèé äóãè ïîðÿäêàñëó÷àå ïîðÿäêàu,s,à êîëè÷åñòâî ñîñòî-òî ñëîæíîñòü àëãîðèòìà íàõîæäåíèÿ ñòàáèëüíûõ ñåòåé â õóäøåìO(sn+1u(n2 +n−2)/2n),àíàëîãè÷íî àëãîðèòìó äëÿ îáû÷íûõ (íåïàðàìåòðè÷å-ñêèõ) èãð îðìèðîâàíèÿ ñåòåé, â êîòîðûõs = 1, u = 2.Ïðè ýòîì ñëîæíîñòü àëãîðèòìàíàõîæäåíèÿ ðàâíîâåñèé ìåòîäîì ïåðåáîðà âñåõ ñèòóàöèé áûëà áû ðàâíàO(sn+1un2 −1).Åñëès = 1, òî äëÿ ìàêñèìàëüíî âîçìîæíîãî êîëè÷åñòâà èãðîêîâ âåðíû îöåíêè, àíàëîãè÷íûå îöåíêàì äëÿ íåïàðàìåòðè÷åñêèõ èãð.
Ïðè ýòîì ïåðåõîä ê àëãîðèòìó ïåðåáîðà ñåòåé ïîçâîëÿåòóâåëè÷èòü ÷èñëî èãðîêîâ ïî ñðàâíåíèþ ñ àëãîðèòìîì ïåðåáîðà ñèòóàöèé ïðèìåðíî âÍà ïðàêòèêå, äëÿ äîñòàòî÷íî áîëüøîãî ÷èñëà èãðîêîâ (n≥ 5) u âðÿä√u ðàç.ëè ìîæåò áûòü áîëüøå46, à çíà÷èò, ÷èñëî èãðîêîâ óâåëè÷èâàåòñÿ íå áîëüøå, ÷åì âäâîå.Íî êóäà áîëåå âàæíà âîçìîæíîñòü óâåëè÷èòüuïðè èêñèðîâàííîìåñëè ìàêñèìàëüíî äîïóñòèìîå âðåìÿ ðàáîòû àëãîðèòìà ïîðÿäêàn.Cnsn+1Äåéñòâèòåëüíî,(â äàííîì ñëó÷àåýòî êîíñòàíòà), òî ïîëó÷àåì äëÿ àëãîðèòìà ïåðåáîðà ñåòåéun2 −1= C ⇔ u = C 1/(n2 −1),à äëÿ àëãîðèòìà ïåðåáîðà ñèòóàöèé:u(n2 +n−2)/2÷òî îçíà÷àåò ïðè íåáîëüøèõ=C⇔u=C2/(n2 +n−2) 2−2/n2 221+1/n−2/n= C 1/(n −1),n âîçâåäåíèå â ñòåïåíü, ðàâíóþ ïðèìåðíî 1.52.
Òî åñòü u ìîæíîóâåëè÷èòü, ñêàæåì, ñ 2 äî 4 èëè ñ 3 äî 9.Åñëè ñåòü ðàçðåæåííàÿ òî åñòü êîëè÷åñòâîìåíüøå ñêàæåì, ïîðÿäêàn,mäîïóñòèìûõ äóã â íåé íå ïîðÿäêàà êîëè÷åñòâî ñîåäèíåíèé èãðîêà îãðàíè÷åíî âåëè÷èíîéñëîæíîñòü àëãîðèòìà íàõîæäåíèÿ ñòàáèëüíûõ ñåòåé îêàçûâàåòñÿ ïîðÿäêàäëÿ àëãîðèòìà ïåðåáîðà ñèòóàöèé n2 ,w,àòîO(sn+1 um+w n),àO(sn+1 u2m+w ).  äàííîì ñëó÷àå, ñëîæíîñòü àëãîðèòìà íå ýêñïîíåíöèàëüíî-êâàäðàòè÷íàÿ, à ýêñïîíåíöèàëüíàÿ, ÷òî äëÿ íåáîëüøèõs è u ïîçâîëÿåòñ÷èòàòü ðàâíîâåñèÿ äëÿ äîñòàòî÷íî áîëüøîãî ÷èñëà èãðîêîâ âïëîòü äî íåñêîëüêèõ äåñÿòêîâ. Ïðè ýòîì ïåðåõîä ê óñîâåðøåíñòâîâàííîìó àëãîðèòìó ïîçâîëèò ïðè èêñèðîâàííîìóâåëè÷èòü ÷èñëîunèãðîêîâ ïðèìåðíî ââàðèàíòîâ ñîåäèíåíèÿ â êâàäðàò.uðàç, à ïðè èêñèðîâàííîìnuâîçâåñòè êîëè÷åñòâî116Åñëè ìû íàøëèkñòàáèëüíûõ ñåòåé, ìîæíî íàéòè âñå ðàâíîâåñèÿ, ïåðåáèðàÿ â êàæäîéñòàáèëüíîé ñåòè ïîðÿäêàQm∈Mq(Um )îòêëîíåíèé, íå ìåíÿþùèõ çíà÷åíèå â ðåáðå ñåòè, ãäå2| inf(a, b) = u}|.q(Um ) = maxu∈Um |{(a, b) ∈ Umíîå ìíîæåñòâî, òîq(Um ) = 2|Um | − 1.Íàïðèìåð, åñëèUm ëèíåéíî óïîðÿäî÷åí-Ìàêñèìàëüíîå âîçìîæíîå êîëè÷åñòâî ïàð ýëåìåíòîâ î÷åâèäíî, â ïîëóðåøåòêå, â êîòîðîé äëÿ ëþáûõ äâóõ íåðàâíûõ ýëåìåíòîâinf(a, b) = 0q(Um ) = |Um |2 − |Um | + 1.
Ñîîòâåòñòâåííî, âñå ðàâíîâåñèÿ ìîæíî íàéòè çà âðåìÿQQQO(k (i,j)∈M q(Um )(|S1 | j |U(j,1) | + · · · + |Sn | j |U(j,n)|)). Àíàëîãè÷íî ñ÷èòàåòñÿ ñëîæíîñòü íà òîãäàõîæäåíèÿ âñåõ îïòèìàëüíûõ ýëåìåíòîâ äëÿ äðóãèõ ñåòåâûõ ïðèíöèïîâ îïòèìàëüíîñòè íóæíî çàìåíèòü3.2.6|G(X)|íàkQm∈Mq(Um ).Îïðåäåëåíèå ãðóïïîâîé ñåòåâîé èãðû îáû÷íîé è â ïàðàìåòðè÷åñêîé ñåòåâîé èãðå êàæäûé èãðîê ñîîòíîñèòñÿ ñ îäíîé âåðøèíîéãðàà.
Òàêèì îáðàçîì, âîçíèêàþùàÿ ñèñòåìà (ñåòü) âêëþ÷àåò â ñåáÿ ìíîæåñòâî àãåíòîâ (èãðîêîâ), óïðàâëÿþùèõ ýòîé ñèñòåìîé. Òàêîå îòîæäåñòâëåíèå óïðàâëÿþùåãî è óïðàâëÿåìîãîîáúåêòà íå ÿâëÿåòñÿ åñòåñòâåííûì. àçäåëèâ ìíîæåñòâîè ìíîæåñòâîLNèãðîêîâ (óïðàâëÿþùèõ îáúåêòîâ)âåðøèí ãðàà (óïðàâëÿåìûõ îáúåêòîâ), ïîëó÷èì ãðóïïîâûå ñåòåâûå èãðû.Äâà êëàññà ãðóïïîâûõ ñåòåâûõ èãð:•ãðóïïîâûå èãðû áåç ñîâìåñòíûõ âåðøèí îäèí èãðîê ìîæåò óïðàâëÿòü íåñêîëüêèìèâåðøèíàìè, íî îäíîé âåðøèíîé óïðàâëÿåò îäèí èãðîê;•ãðóïïîâûå èãðû ñ ñîâìåñòíûìè âåðøèíàìè îäèí èãðîê ìîæåò óïðàâëÿòü íåñêîëüêèìè âåðøèíàìè, îäíîé âåðøèíîé ìîæåò óïðàâëÿòü íåñêîëüêî èãðîêîâ.ðóïïîâûå èãðû áåç ñîâìåñòíûõ âåðøèí ïðåäûäóùåì ðàçäåëå ìû çàìåòèëè, ÷òî âîçìîæíû êàê èãðû îðìèðîâàíèÿ ïðîñòûõ ãðàîâ, òàê è èãðû îðìèðîâàíèÿ ìóëüòèãðàîâ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
