Диссертация (1149954), страница 37
Текст из файла (страница 37)
Ò.å. êàæäûéèãðîê ïåðåáðàñûâàåò ìÿ÷ äðóãîìó èãðîêó è ñòðåìèòñÿ ê òîìó, ÷òîáû ìÿ÷ áûë ó íåãî êàêìîæíî ðåæå.179èñ. A.4: Ñåòü, ðàçâåðíóòàÿ âî âðåìåíèÇàìå÷àíèåA.5.1. Èãðà ñ íåñêîëüêèìè ìÿ÷àìè, íå âëèÿþùèìè äðóã íà äðóãà ýòî ïðÿìàÿñóììà èãð ñ îäíèì ìÿ÷îì. Ïîýòîìó äàëåå áóäåì ñ÷èòàòü, ÷òî ìÿ÷ òîëüêî îäèí.Òàêèì îáðàçîì, ýòî èãðà óïðàâëåíèÿ äèñêðåòíûì äèíàìè÷åñêèì ïîòîêîì áåç ñîõðàíåíèÿñ êðèòåðèåì ìèíèìèçàöèè ñòîèìîñòè, â êîòîðîé åñòü òîëüêî äèíàìè÷åñêèå äóãèêàæäàÿ äóãà òàêæå ìîæåò íàõîäèòüñÿ òîëüêî â 2 ñîñòîÿíèÿõâ 3 ñîñòîÿíèÿõèãðîêàxA = (1, 0, 0), xB = (0, 1, 0), xC = (0, 0, 1)A, B, C ).Ýòî èãðà ñ ïîñòîÿííîé ñóììîé:(x, t),ãäåïðè÷åìÑåòü ìîæåò íàõîäèòüñÿ(ñîîòâåòñòâåííî ìÿ÷ íàõîäèòñÿ óHA + HB + HC = −4.Íàéäåì ñïåðâà ìàêñèìèííûå âûèãðûøè èãðîêîâíóòîé îðìå{0, 1}.M d,HA∗ , HB∗ , HC∗x ∈ {xA , xB , xC }, t ∈ {0, 1, 2, 3}.âî âñåõ ïîäûãðàõ â ðàçâåð-Ìàêñèìèíû ëåãêî ïîñ÷èòàòü ðåêóð-180ðåíòíî ìåòîäîì äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ (îáðàòíûì õîäîì), è îíè òàêîâû:t=3:HA∗ (xA , 3) = −1, HB∗ (xA , 3) = 0HC∗ (xA , 3) = 0HA∗ (xC , 3) = 0,HC∗ (xC , 3) = −1HA∗ (xB , 3) = 0,HB∗ (xB , 3) = −1 HC∗ (xB , 3) = 0HB∗ (xC , 3) = 0t=2:HA∗ (xA , 2) = −1, HB∗ (xA , 2) = −1 HC∗ (xA , 2) = −1HA∗ (xB , 2) = −1, HB∗ (xB , 2) = −1 HC∗ (xB , 2) = −1HA∗ (xC , 2) = −1, HB∗ (xC , 2) = 0HC∗ (xC , 2) = −1t=1:HA∗ (xA , 1) = −2, HB∗ (xA , 1) = −1 HC∗ (xA , 1) = −1HA∗ (xB , 1) = −1, HB∗ (xB , 1) = −1 HC∗ (xB , 1) = −1HA∗ (xC , 1) = −1, HB∗ (xC , 1) = −1 HC∗ (xC , 1) = −2t=0:HA∗ (xA , 0) = −2, HB∗ (xA , 0) = −1 HC∗ (xA , 0) = −2HA∗ (xB , 0) = −2, HB∗ (xB , 0) = −2 HC∗ (xB , 0) = −2HA∗ (xC , 0) = −2, HB∗ (xC , 0) = −1 HC∗ (xC , 0) = −2Î÷åâèäíî,âêàæäîéHA′ (x, t), HB′ (x, t), HC′ (x, t)íèé è ñîîòíîøåíèÿïîäûãðåâðàçâåðíóòîéíå ìåíüøå ìàêñèìèííûõ:îðìåΓ(x,t)ðàâíîâåñíûåH ′(x, t) ≥ H ∗ (x, t).HA′ (x, t) + HB′ (x, t) + HC′ (x, t) = 4 − tâûèãðûøèÈç íàéäåííûõ çíà÷å-âèäíî, ÷òî ìàêñèìèííûå âûèãðûøèâî ìíîãèõ ñëó÷àÿõ ñîâïàäàþò ñ ðàâíîâåñíûìè ò.å.
èãðîê íå ïîëó÷àåò áîëüøå âûèãðûøà,êîòîðûé åìó ãàðàíòèðîâàí. Êðîìå òîãî, ìàêñèìèííûé âûèãðûø èãðîêà ÷àñòî íå çàâèñèò îòíà÷àëüíîé ïîçèöèè ñëåäîâàòåëüíî, ðàâíîâåñèé î÷åíü ìíîãî. Íî åñòü è ïîäûãðû â ðàçâåðíóòîé îðìå, â êîòîðûõHA∗ (x, t) + HB∗ (x, t) + HC∗ (x, t) < 4 − t,à ñëåäîâàòåëüíî, íå âñÿêàÿìàêñèìèííàÿ ñèòóàöèÿ ÿâëÿåòñÿ ðàâíîâåñèåì.Àáñîëþòíîå ðàâíîâåñèå òàêæå íå åäèíñòâåííî. Íàéäåì (òàêæå íååäèíñòâåííîå, íî ñ åäèíñòâåííûì âåêòîðîì âûèãðûøåé) àáñîëþòíîå ðàâíîâåñèå â òèï-ñòðàòåãèÿõ [50℄, ò.å.
â ëåêñèêîãðàè÷åñêîé èãðå, â êîòîðîéH A = (HA , HB , HC ), H B = (HB , HC , HA ), H C = (HC , HA , HB ).Èç ðåêóððåíòíûõ ñîîòíîøåíèé ñëåäóþò ðàâíîâåñíûå õîäû, êîòîðûå âûäåëåíû æèðíûìè ëèíèÿìè íà ðèñóíêå A.5.181èñ. A.5: àâíîâåñíûå õîäû â èãðå êàðòîøêàñ òàêèìè âûèãðûøàìè ïðè ðàçíûõ íà÷àëüíûõ ïîçèöèÿõxA , xB , xC :HA′ (xA ) = −2 HB′ (xA ) = 0HC′ (xA ) = −2HA′ (xC ) = −2 HB′ (xC ) = 0HC′ (xC ) = −2HA′ (xB ) = −2 HB′ (xB ) = −1 HC′ (xB ) = −1àññìîòðèì òåïåðü ìîäèèöèðîâàííóþ èãðó, â êîòîðîé åñòü äóãè âçàèìîäåéñòâèÿïðè÷åìM p,Uip = {∅, {j}, j 6= i}, ò.å. êàæäûé èãðîê ìîæåò ñîåäèíèòüñÿ òîëüêî ñ îäíèì äðóãèì èã-ðîêîì ëèáî íè ñ êåì íå ñîåäèíÿòüñÿ. Òàêèì îáðàçîì, ýòî èãðà ñîãëàñèÿ. Ïóñòü òåïåðü ñîñòîÿíèå êàæäîé âåðøèíû ñîñòîèò èç 6 ýëåìåíòîâ:Si = {0, 1}×{1, 2, 3}, ãäå ïåðâàÿ êîìïîíåíòà âåê-òîðà ñîñòîÿíèÿ îïðåäåëÿåò, åñòü ëè ó èãðîêà ìÿ÷, à âòîðàÿ ñ êàêèì èãðîêîì îí ñîåäèíèëñÿ,ëèáî i, åñëè îí íè ñ êåì íå ñîåäèíèëñÿ.
Ò.å.Si (t + 1) = {(P3dj=1 uij (t), j| inf(upij (t), upji (t)) = 1)}.Ïóñòü íà êàæäîì øàãå ïðîèãðûø èãðîêà, íå ñîåäèíèâøåãîñÿ íè ñ êåì, îïðåäåëÿåòñÿ òàê æå,êàê è â ïðåäûäóùåì ñëó÷àå, à ïðîèãðûø ñîåäèíèâøåãîñÿ èãðîêà ðàâåí0,åñëè ìÿ÷ ó åãî ñîñåäà ïî êîàëèöèè, èfi ((s1 (t), s2 (t)), t) =−b,−2b, åñëè ìÿ÷ ó íåãî,åñëè ìÿ÷ íå ïîïàë íè ê êîìó:−s1i (t),s2i (t) = i−bs1 (t) − b(1 − s1 (t)) s2 (t) = j 6= iijiÌîæíî èíòåðïðåòèðîâàòü ýòî òàê: ïëàòà çà ñîåäèíåíèå èãðîêîâ ðàâíà−2b,çàòî ñîåäèíåíèåçàùèùàåò îò ìÿ÷à. Åñëè ìÿ÷ ïîïàë â îäíîãî èç ñîåäèíèâøèõñÿ èãðîêîâ, òî îí îòäàåò âñþïëàòó çà ñîåäèíåíèå, èíà÷å ïëàòà äåëèòñÿ ïîðîâíó.Èòàê, ïî ñðàâíåíèþ ñ ïðåäûäóùåé èãðîé êîëè÷åñòâî ñîñòîÿíèé ñåòè íà êàæäîì øàãåóâåëè÷èëîñü â4ðàçà: ê êàæäîìó ñîñòîÿíèþxiäîáàâèëèñü ñîñòîÿíèÿâåòñòâóþùèìè ñîåäèíåíèÿìè èãðîêîâ íàïðèìåð,õîäîâ íà êàæäîì øàãå óâåëè÷èëîñü â33 = 27BCACxABi , xi , xi= ((1, 1), (0, 3), (0, 2)).xBCAñ ñîîò-Êîëè÷åñòâîðàç, ïîñêîëüêó êàæäûé èãðîê âûáèðàåò, ñ êåì182åìó ñîåäèíÿòüñÿ.
Êðîìå òîãî, èãðà, áëàãîäàðÿ âîçìîæíîñòè êîîïåðàöèè, ïåðåñòàëà áûòü èãðîé ñ ïîñòîÿííîé ñóììîé. Íî, âîñïîëüçîâàâøèñü ñâîéñòâàìè èãð ñîãëàñèÿ, ìû ìîæåì ðåøèòüýòó èãðó ïî÷òè òàê æå ïðîñòî, êàê ïðåäûäóùóþ.i,Äåéñòâèòåëüíî, ìàêñèìèííûå ñòðàòåãèè èãðîêàñåòÿìè, â êîòîðûõ èãðîêiïî óòâåðæäåíèþ 3.3.2, îïðåäåëÿþòñÿíå ñîåäèíÿåòñÿ ñ äðóãèìè èãðîêàìè. Ñîåäèíåíèå æå îñòàâøèõñÿèãðîêîâ ìåæäó ñîáîé ìîæíî íå ó÷èòûâàòü, ïîñêîëüêó îíî íå âëèÿåò íà âûèãðûø èãðîêài.Òàêèì îáðàçîì, ìàêñèìèííûå ñòðàòåãèè è âûèãðûøè òå æå, ÷òî è â ïðåäûäóùåé èãðå.Ïðè ïîèñêå àáñîëþòíûõ ðàâíîâåñèé ìîæíî âîñïîëüçîâàòüñÿ óòâåðæäåíèåì 3.3.3 è èñêàòüñòàáèëüíûå ñåòè, íå ðàññìàòðèâàÿ òå õîäû, â êîòîðûõ èãðîêè îáðàçóþò áåçîòâåòíûå ñîåäèíåíèÿ.
Òàêèì îáðàçîì, íà êàæäîì øàãå ìû âìåñòåáåç ñîåäèíåíèé, ñ ñîåäèíåíèåìAB ,2 · 27 õîäîâ ðàññìàòðèâàåìñ ñîåäèíåíèåìBCè ñ ñîåäèíåíèåìâñåãîAC .2 · 4 õîäà:Ïî ñâîéñòâóèãðû ñîãëàñèÿ, íàéäåííûå â ïðåäûäóùåé èãðå ñòàáèëüíûå ñåòè áåç ñîåäèíåíèé ñòàáèëüíû èâ ìîäèèöèðîâàííîé èãðå, à ñîîòâåòñòâóþùèå ñèòóàöèè, ê êîòîðûì, âîçìîæíî, äîáàâëåíûáåçîòâåòíûå ïðåäëîæåíèÿ àáñîëþòíî ðàâíîâåñíû. Ïðîâåðèì òåïåðü íà ñòàáèëüíîñòü ñåòèñ ñîåäèíåíèÿìè, äëÿ êàæäîãî ñîåäèíåíèÿ ïðîâåðÿÿ, íå âûèãðàåò ëè èãðîê îò åãî ðàçðûâà. ñëó÷àå, åñëèb ≥ 1/2,ñòðàòåãèè áåç ñîåäèíåíèé âñåãäà áóäóò äîìèíèðóþùèìè, à ñåòè ñëþáûìè ñîåäèíåíèÿìè íåñòàáèëüíûìè.àññìîòðèì òåïåðü íàèáîëåå èíòåðåñíûé ñëó÷àé ñøàãå, íà êîòîðîì ìÿ÷ ïîïàë ê èãðîêóþòñÿ åùå 2 ñåòè, â êîòîðûõåìó ìÿ÷!).
Äåéñòâèòåëüíî,iii,0 < b < 1/2. ýòîì ñëó÷àå íà êàæäîìñòàáèëüíûìè, êðîìå ñåòè áåç ñîåäèíåíèé, îêàçûâà-ñîåäèíèëñÿ ñ ëþáûì äðóãèì èãðîêîì (äàæå ñ òåì, êòî ïîñëàëîò ðàçðûâà ñâÿçè òåðÿåò, ïîëó÷àÿðîê íå âûèãðûâàåò, â îáîèõ ñëó÷àÿõ ïîëó÷àÿ0.−1âìåñòî−2b,à äðóãîé èã-Îïÿòü æå, ê ñòðàòåãèÿì, ïîðîæäàþùèìýòè ñåòè, ìîæíî äîáàâèòü ëþáûå áåçîòâåòíûå ïðåäëîæåíèÿ, ñîõðàíèâ ðàâíîâåñèå. Ñåòü æå, âêîòîðîé ñîåäèíÿþòñÿ èãðîêè, íå ïîëó÷èâøèå ìÿ÷, âñåãäà íåñòàáèëüíà, èáî êàæäîìó èç íèõâûãîäíî ðàçîðâàòü ñîåäèíåíèå, ïîëó÷èâ0 âìåñòî −b.
 íàèáîëåå áëàãîïðèÿòíûõ äëÿ èãðîêîâñèòóàöèÿõ âñå ðàâíîâåñíûå ïðîèãðûøè íàäî óìíîæèòü íàA.5.32b < 1.Ïðèìåð 10: êîìïðîìèññíîå ðåøåíèå â äâóõøàãîâîé èåðàðõè÷åñêîé ñåòåâîé èãðåàññìîòðèì äâóõøàãîâóþ (ò.å., äâóõóðîâíåâóþ) èåðàðõè÷åñêóþ èãðó, ìîäåëèðóþùóþ óïðàâëåíèå â îðãàíèçàöèîííîé ñèñòåìå, è ïîñòðîèì àëãîðèòì íàõîæäåíèÿ êîìïðîìèññíîãî ðåøåíèÿ â òàêîé èãðå. [17℄ ðàññìàòðèâàåòñÿ îðãàíèçàöèîííàÿ ñèñòåìà, ñîñòîÿùàÿ èç óïðàâëÿþùåãî îðãàíà öåíòðà èn óïðàâëÿåìûõñóáúåêòîâ àãåíòîâ. Àãåíòû âîâëå÷åíû â ñåòåâóþ èãðó(N, Xi , Hi ).183Âûèãðûø êàæäîãî àãåíòà çàâèñèò îò òîãî, êàêàÿ ñåòüñâîè ïðåäïî÷òåíèÿΦ(g)àññìàòðèâàåòñÿg ∈ G(X) ðåàëèçîâàëàñü.íà ìíîæåñòâå âîçìîæíûõ ñåòåéìîòèâàöèîííîå óïðàâëåíèå,Öåíòð èìååòG(X).ò.å.
âîçäåéñòâèå öåíòðà íà âûïëàòû, ïîëó-÷àåìûå àãåíòàìè â ðåçóëüòàòå ñåòåâîãî âçàèìîäåéñòâèÿ. Äëÿ òîãî ÷òîáû âîçäåéñòâîâàòü íàñåòåâîå âçàèìîäåéñòâèå àãåíòîâ, öåíòð äîëæåí èìåòü âîçìîæíîñòü èçìåíÿòü âûèãðûøè àãåíòîâ ïðè ðåàëèçàöèè òîé èëè èíîé ñåòè, ò.å. âûèãðûøi-ãîàãåíòàHi (·) = Hi (g, u),íåêîòîðîå óïðàâëåíèå öåíòðà èç ìíîæåñòâà äîïóñòèìûõ óïðàâëåíèéU.èãðûø öåíòðà â îáùåì ñëó÷àå çàâèñèò îò âûáèðàåìîãî èì óïðàâëåíèÿ:ñîîáùàåò àãåíòàì óïðàâëåíèåèëè èíóþ ñåòüΦ(g, u),g ∈ G(X),u ∈ U,ãäåuÎ÷åâèäíî, ÷òî è âû-Φ(·) = Φ(g, u). Öåíòðçàòåì àãåíòû ïðè çàäàííîì óïðàâëåíèè ðåàëèçóþò òóïîñëå ÷åãî âñå ó÷àñòíèêè ÎÑ ïîëó÷àþò ñâîè âûèãðûøè: öåíòð fi (g, u) i ∈ N .àãåíòû Òàêèì îáðàçîì, ýòî èåðàðõè÷åñêàÿ ñåòåâàÿ èãðà èç 2 óðîâíåé, â êîòîðîé íà 1-ì óðîâíååñòü òîëüêî 1 èãðîê è îòñóòñòâóþò ñòðóêòóðíûå äóãèíî íàçâàòüäðåâîâèäíîé,M s.ïîñêîëüêó äèíàìè÷åñêèå äóãèMdÒàêóþ èåðàðõè÷åñêóþ èãðó ìîæîáðàçóþò äåðåâî, ìîäåëèðóþùååèåðàðõè÷åñêóþ ñòðóêòóðó óïðàâëåíèÿ.àññìîòðèì çàäà÷ó íàõîæäåíèÿ êîìïðîìèññíîãî ðåøåíèÿ äëÿ ñîãëàñîâàíèÿ èíòåðåñîâöåíòðà è àãåíòîâ.
 ðàññìàòðèâàåìûõ çàäà÷àõ óïðàâëåíèÿ öåíòð íàâÿçûâàåò àãåíòàì òàêîåðåøåíèå, êîòîðîå óäîâëåòâîðÿåò íåêîòîðûì óñëîâèÿì ñòàáèëüíîñòè: ò.å. ïðîèçâîäèòñÿ âûáîðèç ðàâíîâåñíûõ,k -ðàâíîâåñíûõ,ñèëüíî ðàâíîâåñíûõ, ïîïàðíî-ñòàáèëüíûõ èëè ãèáðèäíî-ñòàáèëüíûõ ñåòåé.  ëþáîì ñëó÷àå, áóäåì îáîçíà÷àòü ìíîæåñòâî òàêèõ ñåòåéP (σ),ãäåσ äîïëàòû, êîòîðûå öåíòð äåëàåò èãðîêàì. Ýòî çíà÷èò, ÷òî êîìïðîìèññíîå ðåøåíèå:∗ming∈P (σ(g)),σ(g)≥0ãäåH∗ðûømax(H − Φ(g) +nXi=1σi (g), H1∗ − f10 (g) − σ10 (g), .
. . H n∗ − fn0 (g) + σn0 (g)) ìàêñèìàëüíî âîçìîæíûé âûèãðûø öåíòðà,i-ãîHi∗ ìàêñèìàëüíî âîçìîæíûé âûèã-àãåíòà.Äëÿ êàæäîé ñåòèg ∈ G ìíîæåñòâî óïðàâëåíèé σ , óäîâëåòâîðÿþùèõ óñëîâèþ g ∈ P (σ(g)),èëè ïóñòî, èëè ÿâëÿåòñÿn-ìåðíûììíîãîãðàííèêîì, ïîñêîëüêó óïðàâëåíèÿ äîëæíû óäîâëå-òâîðÿòü ñèñòåìå ëèíåéíûõ íåðàâåíñòâ (âèä ýòîé ñèñòåìû çàâèñèò îò òîãî, êàêèå ïðåäïîëàãàþòñÿ óñëîâèÿ ñòàáèëüíîñòè). Ïîñêîëüêó âñåãî ñóùåñòâóåò2n(n−1)/2âîçìîæíûõ ñåòåé, ýòîçíà÷èò, ÷òî äëÿ íàõîæäåíèÿ êîìïðîìèññíîãî ðåøåíèÿ ïðÿìûì ïåðåáîðîì òðåáóåòñÿ:1. åøèòüçàäà÷ån2n(n−1)/2çàäà÷ ëèíåéíîãî ïðîãðàììèðîâàíèÿ äëÿ êàæäîé ñåòèïåðåìåííûõ è, â ëó÷øåì ñëó÷àå,2. Âûáðàòü òó ñåòüg∗,O(n)îãðàíè÷åíèé.êîòîðàÿ äîñòàâëÿåò òðåáóåìûé ìèíèìóì.g. êàæäîé184ßñíî,÷òîO(2n(n−1)/2 n3 ))òàêîéàëãîðèòìòðåáóåòñëèøêîìáîëüøèõâðåìåííûõçàòðàò(ïîðÿäêàäàæå äëÿ íåáîëüøèõ ñåòåé.
Ïîýòîìó äëÿ ÷àñòíûõ ñëó÷àåâ ñëåäóåò èñïîëü-çîâàòü áîëåå ýåêòèâíûå àëãîðèòìû..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
