Диссертация (1149954), страница 36
Текст из файла (страница 36)
Òàêèì îáðàçîì,A(n − 1)(q1 − m1 )p1 + m1 p1 −n(q1 − m1 )p1 + m1 p1 = (n − 1)(q1 − m1 )p1 + q1 p1 ,âûãîäíî ïðîäîëæèòü èãðó.Íî â ýòîì ñëó÷àå âàæåí è âûáîð èãðîêîâ îòíîñèòåëüíî ñâÿçèu(2n−1). Ñðàâíèâ âûèãðûøèA ïðè u(2n−1) = 0 è u(2n−1) = 1, âèäèì, ÷òî A â ëþáîì ñëó÷àå íå ïîëó÷èò íèêàêîé âûãîäûîò îáðûâà ñâÿçè (âåäü ïðè ýòîì âåëè÷èíàíåâûãîäíî èãðîêóBÈãðîêóýòîìmaxt=2n−k,...,2n−1 u(t)ðàçâå ÷òî óìåíüøèòñÿ, ÷òîA).Aâûãîäíî îáîðâàòü ñâÿçü â ñëó÷àå, êîãäàsB2 (2n − 1) ≤ 1,ò.å.
ïðèâûãîäíî ïðîäîëæèòü èãðó è ïðèt = 2n − k, . . . , 2n − 2 u(t) = 0.Åñëè æå ñóùåñòâóåò òàêîåt = 2n−k, . . . , 2n−2, ÷òî u(t) = 1, òî B ìîæåò è íå îáðûâàòü ñâÿçü, ïîñêîëüêó åãî ðàâíîâåñíûéâûèãðûø îò ýòîãî íå èçìåíèòñÿ. Åñëè æåu(2n − 1)Aâûãîäíî îñòàíîâèòü èãðó, òî ñîñòîÿíèå ñâÿçèíå èìååò çíà÷åíèÿ, ïîñêîëüêó âûèãðûøè èãðîêîâ îò íåãî íå çàâèñÿò.Òàêèì îáðàçîì, ïî ñðàâíåíèþ ñΓ1 , â Γkâ ïîäèãðå â ðàçâåðíóòîé îðìåΓk2n−1íà(2n − 1)-ì øàãå ïîÿâèëîñü åùå îäíî äîïîëíèòåëüíîå ðàâíîâåñèå òî÷íåå, êëàññ ðàâíîâåñèé. Ýòèðàâíîâåñèÿ âîçìîæíû ïðèÏðè ýòîìAk≥2è äîñòèãàþòñÿ ïðèmaxt=2n−k,...,2n−2 u(t) = 1è ëþáîìu(t).ïðîäîëæàåò èãðó, è ðàâíîâåñíûå âûèãðûøè ðàâíûsA (2n − 1) > 1 ⇒ valA (sA (2n − 1), 2n − 1) = n(q1 − m1 )p1 + m1 p1sB (2n − 1) > 1 ⇒ valB (sB (2n − 1), 2n − 1) = n(q2 − m2 )p2 .Àíàëîãè÷íî, íàj -ìøàãå, ãäå2n − k ≤ j ≤ 2n − 2,åñëèmaxt=2n−k,...,j u(t) = 1,òî îáîèìèãðîêàì íåò ñìûñëà ðàçðûâàòü ñâÿçü, è îíè â ðàâíîâåñíîì ñëó÷àå õîäÿò âïðàâî.Èç óñëîâèÿ2n − 2maxt=2n−k,...,2n−2 u(t) = 1(ïðè ýòîìj -ì øàãåj ≥ 2n − k ),÷òîñëåäóåò, ÷òî ñóùåñòâóåò òàêîå ìàêñèìàëüíîåmaxt=2n−k,...,j u(t) = 0 èïðè ýòîì ýòîì ñëó÷àå íàó îäíîãî èç èãðîêîâ ïîÿâëÿåòñÿ âîçìîæíîñòü ðàçîðâàòü ñâÿçü, ÷òîáû â äàëüíåéøåìñäåëàòü õîä âíèç.
àâíîâåñèÿ â ïîëó÷èâøåéñÿ ïîäûãðåòàêîãî, ÷òîu(l) = 1.Γjk çàâèñÿò îò ìàêñèìàëüíîãî l < 2n−kÍàñ èíòåðåñóåò ñëó÷àé, êîãäà âΓjkâ ëþáîì ðàâíîâåñèè îäíîìó èçèãðîêîâ âûãîäíî íà êàêîì-òî øàãå ïîéòè âíèç è ïðè ýòîìn(q1 − m1 )p1 + m1 p1 ,â èãðåu(j) = 1.j ≤ΓlkèëèB áîëüøå, ÷åìn(q2 − m2 )p2 .Aïîëó÷àåò âûèãðûø áîëüøå ýòîì è òîëüêî â ýòîì ñëó÷àåíè îäíà ñèòóàöèÿ, â êîòîðîé âñå èãðîêè èäóò âïðàâî, íå ÿâëÿåòñÿ àáñîëþòíûì176ðàâíîâåñèåì.×òîáû èãðîêóAáûëî âûãîäíåå íà(2i + 1)-ìâïðàâî, äîëæíî âûïîëíÿòüñÿ íåðàâåíñòâîíåâîçìîæíî ïðèi < n.×òîáû èãðîêóBøàãå ïîõîäèòü âíèç, ÷åì âñå âðåìÿ èäòè(i(q1 − m1 ) + m1 )p1 > (n(q1 − m1 ) + m1 )p1 ,áûëî âûãîäíåå íàâðåìÿ èäòè âïðàâî, äîëæíî âûïîëíÿòüñÿ íåðàâåíñòâîîòêóäà ïîëó÷àåìi>n−Òàêèì îáðàçîì, ïðèðàâíîâåñèå â ïîäûãðåäîãîâîð, àABèΓlk2i-ìøàãå ïîõîäèòü âíèç, ÷åì âñå(i(q2 − m2 ) + m2 )p2 > n(q2 − m2 )p2 ,m2(â ÷àñòíîñòè, âñåãäà ïîäõîäèò ñëó÷àéq2 −m22m2, îòêóäàq2 −m2l + k = 2i > 2n −(l + k)-ãîi = n).l > 2n − k −l-ãîäîñòèãàåòñÿ â ñëó÷àå, êîãäà èãðîêè ïîñëåíà÷èíàÿ ñ÷òîøàãà õîäÿò âíèç (âåäü åñëèB2m2, àáñîëþòíîåq2 −m2øàãà íå ñîáëþäàþòâûãîäíî ïîõîäèòü âíèç,òî àáñîëþòíîå ðàâíîâåñèå â ïîäûãðå äîñòèãàåòñÿ òàì, ãäå èãðîêè ïîõîäÿò âíèç, êàê òîëüêîïåðåñòàíóò ïëàòèòü çà ýòî øòðà).
Åñëè æåâΓlkl ≤ 2n − k −2m2, òî àáñîëþòíîå ðàâíîâåñèåq2 −m2äîñòèãàåòñÿ â ñëó÷àå, êîãäà èãðîêè â êàêîé-òî ìîìåíòñîáëþäàòü äîãîâîð (u(j)= 1)i ∈ {2n − k, . . . , 2n − 2}è âñå âðåìÿ õîäÿò âïðàâî (çíà÷åíèÿu(t)ïðèt>jíà÷àëèìîãóò áûòüëþáûìè). ñëó÷àå, êîãäàl < 0,ýòî ýêâèâàëåíòíî òîìó, ÷òîu(t) = 0ïðèt < j.Òîãäà âîçìîæåí åùåj . Ýòî ìîæåò áûòü èì âûãîäíî, åñëè2m2áûòü 2n − k ≤ j ≤ 2n − max.,2q2 −m2âàðèàíò, êîãäà èãðîêè íàðóøàþò ðàâíîâåñèå äî ìîìåíòàj > 2n −2m2. Èíà÷å ãîâîðÿ, åñëèq2 −m2l < j − k,äîëæíîÊàê íè óäèâèòåëüíî, èãðîêè â ðàâíîâåñíîì ñëó÷àå ìîãóò íå çàêëþ÷àòü äîãîâîð, ïðåäóñìàòðèâàþùèé øòðà çà íàðóøåíèå, ñ íà÷àëà è ïî÷òè äî ñàìîãî êîíöà èãðû (õîòÿ áû äî ìîìåíòàt = 2n − max2m2, 2 ).q2 −m2Òàêèì îáðàçîì, âîçìîæíû 2 âèäà àáñîëþòíûõ ðàâíîâåñèé â ïîäûãðå â ðàçâåðíóòîé îðìåΓlk :1.
Ïðåäóñìàòðèâàþùèå, ÷òî èãðîêè âñå âðåìÿ õîäÿò âïðàâî. Íåîáõîäèìûå óñëîâèÿ òàêîãîðàâíîâåñèÿ:2l ≤ 2n − k − q22m,−m222n − k ≤ j ≤ 2n − max q22m,2 ;−m2(a) ëèáîu(l) = 1,ãäål = 0, u(l) = 0 è22n − max q22m,2.−m2(b) ëèáîïîñëå ýòîãîu(t) = 0ïîñëå ýòîãî2. Ïðåäóñìàòðèâàþùèå, ÷òî â êàêîé-òî ìîìåíòu(t) = 0âïëîòü äî ìîìåíòàâïëîòü äî ìîìåíòàj,ãäåj,ãäå2n − k ≤ j ≤jîäèí èç èãðîêîâ ïîõîäèò âíèç.
Íåîáõî-< l < 2n − k ,äèìûå óñëîâèÿ òàêîãî ðàâíîâåñèÿ:(a) ëèáîu(l) = 1,ãäå2n − k − maxâïëîòü äî ìîìåíòà(b) ëèáî2m2,2q2 −m2j = l + k, u(t) = 0;l = 0, u(l) = 0,è òîãäà èãðîêAõîäèò âíèç ñðàçó.è ïîñëå ýòîãî âñå âðåìÿ,177 ñëó÷àå 1à) ýòî ðàâíîâåñèå ÿâëÿåòñÿ àáñîëþòíûì ðàâíîâåñèåì è â èãðåïîñêîëüêó èãðîêA,íè åãî íàðóøåíèå â ìîìåíòj,22n − q22m,−m2íî íè íàðóøåíèå äîãîâîðà â ìîìåíò l ,max2m2,2q2 −m2≤ k ≤ 2n − max ñëó÷àå 1b) ýòî óæå ãîòîâîå àáñîëþòíîå ðàâíîâåñèå â èãðåk ≥ maxlèãðîêóìîìåíòBl′ ,â êîòîðûéu(l′ ) = 1,äîñòèãàåòñÿ ïðèíåâûãîäíî åãî íàðóøèòü â ìîìåíòñóùåñòâóåò ïðè óñëîâèÿõíûå2m2q2 −m2l′ + k> 1, 2 ≤ k ≤ 2n − íà÷àëå ìû ðàññìîòðåëè èãðóc1 = m1 p1 = 1, c2 = m2 p2 = 1Γk (50, 1, 3, 1, 1, 1, 3, 1, 1).j,ãäåÏðè ëþáîì100 − k ≤ j ≤ 98,ìîìåíòà100â ìîìåíòj,íèA,2m2,2 .q2 −m2Îíî ñóùåñòâóåò ïðèΓk â òîì ñëó÷àå, åñëè ïðåäûäóùèél′ ≤ 2n − k −íèBàu(j) = 1,2m2 â ýòîì ñëó÷àåq2 −m2è òåì áîëåå ðàíüøå.
Òàêîå ðàâíîâåñèå2m2.q2 −m2 ñëó÷àå 2b) ýòî óæå ãîòîâîå àáñîëþòíîå ðàâíîâåñèå â èãðåÏðèìåð.Γk .2m2,2 .q2 −m2 ñëó÷àå 2a) ìû ïîëó÷èì àáñîëþòíîå ðàâíîâåñèå â èãðåïåðåäBíè òåì áîëåå îäíîâðåìåííîå íàðóøåíèå, íå äîïóñêàþò òàêîãîðàâíîâåñèÿ. Îíî ñóùåñòâóåò ïðè óñëîâèÿõóñëîâèÿõâ öåëîì,êàê ìû óæå âûÿñíèëè, íå ìîæåò óëó÷øèòü ñâîå ïîëîæåíèå, à èãðîêìîã áû åãî óëó÷øèòü, ëèøü ïîõîäèâ ïîñëåΓkΓk .Îíî ñóùåñòâóåò âñåãäà.Γ1 (50, 1, 3, 1, 0, 1, 3, 1, 0).Ââåäåì øòðàû, ðàâ-è äîãîâîðû, ðàñòÿíóòûå íà ïåðèîäk ≥2ñèòóàöèÿ, â êîòîðîéu(t) = 0k.Ïîëó÷èì èãðóâïëîòü äî ìîìåíòàÿâëÿåòñÿ àáñîëþòíûì ðàâíîâåñèåì.
Äåéñòâèòåëüíî, äîíåâûãîäíî õîäèòü âíèç. Åñëè æå îäèí èç èãðîêîâ ðàçîðâåò äîãîâîðòî ïîëó÷èòñÿ ïîäûãðà, â êîòîðîé ðàâíîâåñèå äîñòèãàåòñÿ ïðè õîäå èãðîêà âíèçñðàçó â ìîìåíòj + 1.Íî, ïîñêîëüêój + 1 < 100,ýòî îòêëîíåíèå íåâûãîäíî íè îäíîìó èçèãðîêîâ.àâíîâåñèé â ñòðàòåãèÿõ íàêàçàíèÿ â èãðåΓk äîâîëüíî ìíîãî (íå ìåíüøå, ÷åì àáñîëþòíûõðàâíîâåñèé). Ïîýòîìó áóäåì èñêàòü òîëüêî ðàâíîâåñèå, ïðè êîòîðîì èãðîêàì âûãîäíî âñåâðåìÿ äâèãàòüñÿ âïðàâî. Äëÿ ýòîãî ìàêñèìèí êàæäîãî èãðîêà ïðè îòêëîíåíèè îò ðàâíîâåñèÿäîëæåí áûòü íå áîëüøå âûèãðûøà ïðè äâèæåíèè âïðàâî.
Áóäåì ïîëàãàòüïðèk = 1,k ≥ 2,ïîñêîëüêóêàê ìû óæå âûÿñíèëè, ñóùåñòâóåò åäèíñòâåííîå ðàâíîâåñèå, ïðè êîòîðîìñðàçó õîäèò âíèç. Ïðè ïîäñ÷åòå ìàêñèìèíà â ìîìåíòt,â äèíàìè÷åñêîé ñåòåâîé èãðå, ìîæíî ïðåäïîëàãàòü, ÷òîÒàêèì îáðàçîì, ìàêñèìèííûé âûèãðûø èãðîêàäîëæåí áûòü íå áîëüøåAAñîãëàñíî óòâåðæäåíèþ î ìàêñèìèíåu(τ ) = 0ïðèτ ≥ t.ïðè ëþáîì îòêëîíåíèè îò ðàâíîâåñèÿn(q1 − m1 )p1 + m1 p1 , à ìàêñèìèííûéâûèãðûø èãðîêàB íå áîëüøån(q2 −m2 )p2 . Íî âûèãðûø èãðîêà A â ëþáîì ñëó÷àå íå ìîæåò áûòü áîëüøå n(q1 −m1 )p1 +m1 p1 .×òî êàñàåòñÿ èãðîêàm2 p2 ,B , åãî ìàêñèìèííûéåñëè îí óõîäèò âíèç â ìîìåíò2jâûèãðûøïîñëå îêîí÷àíèÿ äåéñòâèÿ äîãîâîðà (óéäÿ âíèç äîýòîãî, îí â ëþáîì ñëó÷àå ïîëó÷èò ìåíüøå), èëèAóõîäèò âíèç â ìîìåíò2j + 1 ≥ t.mB (t) â ìîìåíò t ðàâåí j(q2 − m2 )p2 +ÅñëèAj(q2 − m2 )p2 + c1 maxτ =2j+1−k,...,2j u(τ ),åñëèóéäåò âíèç ïîñëå îêîí÷àíèÿ äåéñòâèÿ äîãîâîðà,178èñ.
A.3: Ñåòü èç 3 èãðîêîâòîBïîëó÷èòj(q2 − m2 )p,òî åñòü ìåíüøå ðàâíîâåñíîãî çíà÷åíèÿ.àññìîòðèì ñèòóàöèþ, â êîòîðîé èãðîêè âñå âðåìÿ õîäÿò âïðàâî, ïðè÷åìâ íå÷åòíûå ìîìåíòû âðåìåíè, åñëè îñòàëüíûå ìîìåíòû âðåìåíèäåéñòâóåò, è åñëèBu(t) = 1òîëüêîk ÷åòíîå, èëè â ÷åòíûå ìîìåíòû âðåìåíè, åñëè k íå÷åòíîå.u(t) = 0.Òàêèì îáðàçîì, ïîñêîëüêók ≥ 2,äîãîâîð âñå âðåìÿíå ðàçîðâåò äîãîâîð, òî ïîëó÷èò ìåíüøå ðàâíîâåñíîãî çíà÷åíèÿ. Åñëèðàçîðâåò äîãîâîð â ìîìåíò t, òî åñòü äåéñòâèå èñòå÷åò â ìîìåíòâ ýòîò ìîìåíò õîäèòA. Aïîõîäèò âíèç, èBt + k , à ýòî íå÷åòíîåB÷èñëî, èîïÿòü ïîëó÷èò ìåíüøå ðàâíîâåñíîãî çíà÷åíèÿ.Ñëåäîâàòåëüíî, äàííàÿ ñèòóàöèÿ ÿâëÿåòñÿ ðàâíîâåñèåì â ñòðàòåãèÿõ íàêàçàíèÿ.A.5.2Ïðèìåð 9: èãðà 3 èãðîêîâ ñ ðåáðàìè âçàèìîäåéñòâèÿàññìîòðèì äèíàìè÷åñêóþ ñåòåâóþ èãðó, ïîõîæóþ íà èçâåñòíóþ èãðó ñ ìÿ÷îì êàðòîøêà.
Ïóñòü èìååòñÿ 3 èãðîêàA, B, C ,óïðàâëÿþùèõ îäíîèìåííûìè âåðøèíàìè òî åñòüâ èãðå óæå óäàëåíû ñòàòè÷åñêèå äóãè è ìíîæåñòâî èãðîêîâ ñîâïàäàåò ñ ìíîæåñòâîì âåðøèí. Ïóñòü ìåæäó íèìè ìîãóò îáðàçîâûâàòüñÿ òîëüêî äèíàìè÷åñêèå ñâÿçè òàêèõ âèäîâ:(A, B), (A, C), (B, A), (B, C), (C, A), (C, C). Èíà÷å ãîâîðÿ, ýòîèãðà óïðàâëåíèÿ äèíàìè÷åñêèìïîòîêîì â ñåòè, èçîáðàæåííîé íà ðèñ.
A.3.Ïóñòü âñåãî 4 ìîìåíòà âðåìåíè, òàê ÷òî ñåòü, ðàçâåðíóòàÿ âî âðåìåíè, ïîêàçàíà íà ðèñ.A.4.Ïóñòü êàæäàÿ âåðøèíà ìîæåò íàõîäèòüñÿ âñåãî â 2 ñîñòîÿíèÿõ:ìÿ÷), ò.å.Si = {0, 1}. Ïóñòü,è(íåò ìÿ÷à) è1(åñòüàíàëîãè÷íî ïðèìåðó ñ äâèæóùèìñÿ îáúåêòîì, íà êàæäîì øàãåìÿ÷ ïåðåìåùàåòñÿ â äðóãóþ âåðøèíó ïî äóãå, ò.å.udi1 + udi2 + udi3 = si (t)}0Si (t + 1) = {P3Uid (si (t), t) = {(udi1, udi2 , udi3 ) ∈ {0, 1}3 |dj=1 uij (t)}. Ïóñòü âûèãðûø èãðîêà ðàâåí êîëè÷åñòâóìîìåíòîâ âðåìåíè, â êîòîðûå ó èãðîêà áûë ìÿ÷, ñî çíàêîì -:fi (s(t), t) = −si (t).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
