Диссертация (1149954), страница 21
Текст из файла (страница 21)
Âàæíî çíàòü, â êàêèõ ñëó÷àÿõ âåðíî îáðàòíîå: ò.å.ðåêóððåíòíàÿ ñèòóàöèÿ ñóùåñòâóåò, îïòèìàëüíà è ÿâëÿåòñÿ ÏÄÓ.Ââåäåì óäîáíîå ñîêðàùåíèå:íîé ñèòóàöèè. Ôàêòè÷åñêè,ivali (x, t) = H(x,t)(p(x, u)),vali (x, t)ãäåu óïðàâëåíèå â ðåêóððåíò- ýòî îöåíêà âûãîäíîñòè ïîçèöèèêà. ëàâíûé åå íåäîñòàòîê â òîì, ÷òî çíà÷åíèåvali (x, t)(x, t)äëÿ i-ãî èãðî-â íåêîòîðûõ ñëó÷àÿõ íååäèíñòâåí-íî. Ïðåæäå ÷åì îïèñàòü äîñòàòî÷íî îáùèå óñëîâèÿ åäèíñòâåííîñòè, áóäåì îáîçíà÷àòü ÷åðåçVali (x, t) ìíîæåñòâîâñåõ âîçìîæíûõ îöåíîê.  ýòîì ñëó÷àå ðåêóððåíòíûå ñîîòíîøåíèÿ ïðè-íèìàþò âèäu(x, t) ∈ φu (Val(x, t))...u(x, m − 1) ∈ φu (Val(x, m))Val(x, m) = {H(x, m)}Òåîðåìà 14(îá àáñîëþòíîì ðàâíîâåñèè).Ïóñòü M äèíàìè÷åñêèé èãðîâîé ìåõàíèçì.Åñëè äàíî åñòåñòâåííîå ñåìåéñòâî çàäà÷ (M, (H j )(x,t) , NE) ñ îáîáùåííûì èíòåãðàëüíûìj(h) = ft (h(t)) ∗ ft+1 (h(t + 1)) ∗ · · · ∗ fm (h(m)) íà óïîðÿäî÷åííîé ïîëóãðóïïå,âûèãðûøåì H(x,t)è ðåêóððåíòíàÿ ñèòóàöèÿ ðàâíîâåñèÿ ñóùåñòâóåò, òî îíà îïòèìàëüíà è ÿâëÿåòñÿ ÏÄÓ.Äîêàçàòåëüñòâî.Γ(x, tm−1 )Îáðàòíàÿ èíäóêöèÿ ïîtk .Áàçà èíäóêöèè:k = m − 1. êàæäîé ïîäûãðåìíîæåñòâî ðàâíîâåñèé, è ÄÓ-ðàâíîâåñèé òîæå (ïîñêîëüêó ó òàêîé îäíîõîäîâîéèãðû íåò íåòðèâèàëüíûõ ïîäûãð â ðàçâåðíóòîé îðìå) ñîâïàäàåò ñ ìíîæåñòâîì ðàâíîâåñèéâ îäíîõîäîâîé èãðå ñ âûèãðûøàìèH j .
Íî ýòî, ïî îïðåäåëåíèþ, è åñòü ìíîæåñòâî ðåêóððåíò-íûõ ñòðàòåãèé.Èíäóêöèîííûéáîðïåðåõîä.(s1 (x, k), . . . sn (x, k))Ïóñòüäîêàçàíîäëÿt > k,äîêàæåìäëÿk.Ïóñòüíà-ïðèíàäëåæèò ìíîæåñòâó ðåêóððåíòíûõ ñèòóàöèé. Äîêàæåì, ÷òî(s1 (x, k), . . . sn (x, k)) ∈ AE.àññìîòðèì ñïåðâà ïðîèçâîëüíîãî èãðîêàj ∈ i(x, k).Åãî óïðàâëåíèåîïðåäåëåíèþ ðåêóððåíòíîé ñòðàòåãèè, äîñòàâëÿåò ìàêñèìóì âûðàæåíèþu ∈ Uj (x, k),ïîvj (π(x, k)(u), k + 1).Ïóñòü îí îòêëîíèòñÿ îò ðåêóððåíòíîé ñòðàòåãèè. Îí ìîæåò îòêëîíèòüñÿ äâîÿêî: ñðàçó æå, â ìîìåíòíèåu′ ,k,èëè íåñêîëüêî ïîçæå. Îòêëîíèâøèñü ñðàçó æå, ò.å. âûáðàâ óïðàâëå-íå ÿâëÿþùååñÿ ìàêñèìèçèðóþùèì, îí ïîïàäàåò â ïîäûãðó â ðàçâåðíóòîé îðìåΓ(x′ , k + 1), x′ = π(x, k)(u′ ),íî âîçìîæíîãîêîòîðàÿ èìååò çíà÷åíèåvalj (π(x, k)(u), k + 1).valj (x′ , k + 1),íå áîëüøåå ìàêñèìàëü-Íî, åñëè äðóãèå èãðîêè ïðîäîëæàþò ñîáëþäàòü ñâîèñòðàòåãèè, îí íå ñìîæåò ïîëó÷èòü â ýòîé ïîäûãðå â ðàçâåðíóòîé îðìå âûèãðûø, áîëüøèé,95÷åì åå çíà÷åíèå. Äåéñòâèòåëüíî, ïî èíäóêöèîííîìó ïðåäïîëîæåíèþ, ñóæåíèÿ ðåêóððåíòíûõñòðàòåãèé(s1 (x′ , k + 1), .
. . sn (x′ , k + 1))Íî òîãäà îòêëîíåíèå îò íèõ èãðîêàÀíàëîãè÷íî, åñëè èãðîêjjðàâíîâåñíû, èáî îíè ñàìè ÿâëÿþòñÿ ðåêóððåíòíûìè.íå ïîçâîëèò åìó ïîëó÷èòü áîëüøèé âûèãðûø.èëè äðóãèå èãðîêè îòêëîíÿòñÿ îò ðåêóððåíòíûõ ñòðàòåãèé íåñðàçó, à íåñêîëüêî ïîçæå, ýòî áóäåò îçíà÷àòü îòêëîíåíèå îò ðåêóððåíòíûõ, à çíà÷èò, ïîèíäóêöèîííîìó ïîëîæåíèþ, ðàâíîâåñíûõ ñòðàòåãèé â ïîäûãðå â ðàçâåðíóòîé îðìå ò.å.ïîëó÷åíèå íå áîëüøåãî âûèãðûøà.Óòâåðæäåíèå 3.1.3.
Ïóñòü ïðèíöèï îïòèìàëüíîñòè êîàëèöèîííîå ðàâíîâåñèå îòíîñè-òåëüíî ïðîèçâîëüíûõ ñâåðòîê êðèòåðèåâ. Òîãäà â êîíå÷íîé ïîî÷åðåäíîé ïîçèöèîííîé èãðåðåêóððåíòíûå ñòðàòåãèè ñóùåñòâóþò.Äîêàçàòåëüñòâî.Ñëåäóåò èç òîãî, ÷òî íà êàæäîì øàãåφu ïðèíöèï îïòèìàëüíîñòè â çà-äà÷å óïðàâëåíèÿ ñ îäíèì èãðîêîì è êîíå÷íûì ìíîæåñòâîì óïðàâëåíèé. Òàêèì îáðàçîì, çàäà÷à îïðåäåëåíèÿ êîàëèöèîííîãî ðàâíîâåñèÿ ñâîäèòñÿ ê ìàêñèìèçàöèè ñâåðòêè, à ìàêñèìóìíà êîíå÷íîì ìíîæåñòâå âñåãäà äîñòèãàåòñÿ.Ñëåäñòâèå 14.1. Ïóñòü M ïîî÷åðåäíûé êîíå÷íûé äèíàìè÷åñêèé èãðîâîé ìåõàíèçì. Åñ-ëè äàíî åñòåñòâåííîå ñåìåéñòâî çàäà÷ (M, (H j )(x,t) , NE) ñ îáîáùåííûì èíòåãðàëüíûì âûjèãðûøåì H(x,t)(h) = ft (h(t)) ∗ ft+1 (h(t + 1)) ∗ · · · ∗ fm (h(m)) íà óïîðÿäî÷åííîé ïîëóãðóïïå, òîðåêóððåíòíàÿ ñèòóàöèÿ ðàâíîâåñèÿ ñóùåñòâóåò, îïòèìàëüíà è ÿâëÿåòñÿ ÏÄÓ.Çàìå÷àíèå3.1.13.  ýòîì ñëó÷àå èç ïîî÷åðåäíîñòè ìåõàíèçìà ñëåäóåòvi(x,t) (x, t) = max (fi (x, t) ∗ vi(x,t) (π(x, t)(u), t + 1)) = fi (x, t) ∗ max vi(x,t) (π(x, t)(u), t + 1)u∈U (x,t)ãäåv ∈ Val ïðîèçâîëüíûé ñåëåêòîð (âûíîñu∈U (x,t)fi (x, t)çà ñêîáêè âîçìîæåí ïî îïðåäåëåíèþóïîðÿäî÷åííîé ïîëóãðóïïû).Çàìå÷àíèå3.1.14.
Ýòî ñëåäñòâèå îáîáùàåò òåîðåìó Êóíà íà ñëó÷àé èíòåãðàëüíûõ âûèãðû-øåé èç óïîðÿäî÷åííûõ ïîëóãðóïï.Àíàëîãè÷íàÿ òåîðåìà âåðíà äëÿ êîàëèöèîííîãî ðàâíîâåñèÿ:Òåîðåìà 15(îá àáñîëþòíîì êîàëèöèîííîì ðàâíîâåñèè).Ïóñòü M äèíàìè÷åñêèé èãðîâîéìåõàíèçì. Åñëè äàíî åñòåñòâåííîå ñåìåéñòâî çàäà÷ (M, (H j )(x,t) , NE) ñ îáîáùåííûì èíòåjãðàëüíûì âûèãðûøåì H(x,t)(h) = ft (h(t)) ∗ ft+1 (h(t + 1)) ∗ · · · ∗ fm (h(m)) íà óïîðÿäî÷åííîéïîëóãðóïïå, è ðåêóððåíòíàÿ ñèòóàöèÿ (ñëàáîãî) êîàëèöèîííîãî ðàâíîâåñèÿ ñóùåñòâóåò, òîîíà îïòèìàëüíà è ÿâëÿåòñÿ ÏÄÓ.96Äîêàçàòåëüñòâî.Àíàëîãè÷íî äîêàçàòåëüñòâó ïðåäûäóùåé òåîðåìû.Äëÿ íàõîæäåíèÿ êîàëèöèîííûõ ðàâíîâåñèé ñ ìíîæåñòâîì êîàëèöèéCâ ñòàòè÷åñêîé èãðåíà êàæäîì øàãå ìîæíî âîñïîëüçîâàòüñÿ äâóìÿ àëãîðèòìàìè.
 îáîèõ àëãîðèòìàõ ïåðåáèðàþòñÿ âñå âîçìîæíûå ñèòóàöèè è ïðîâåðÿþòñÿ íà ðàâíîâåñíîñòü.  ïåðâîìàëãîðèòìåíàõîæäåíèÿ êîàëèöèîííûõ ðàâíîâåñèé ðàññìàòðèâàåì êàæäóþ ñèòóàöèþ è äëÿ ïðîâåðêè íàðàâíîâåñíîñòü ïåðåáèðàåì âñå âîçìîæíûå îòêëîíåíèÿ êîàëèöèé èçàëãîðèòìà ÂòîðîéO(uPnS∈C (|S|uàëãîðèòì|S|)) = O(c2c un+c ),ãäåC.Ñëîæíîñòü ïåðâîãîc = |C|.íàõîæäåíèÿ êîàëèöèîííûõ ðàâíîâåñèé ðàáîòàåò òàê:(s1 , s2 ).•àññìàòðèâàåì âñå ïàðû ñèòóàöèé•Äëÿ êàæäîé ïàðû ïðîâåðÿåì, îòêëîíåíèÿ êàêèõ èãðîêîâ íåîáõîäèìû äëÿ òîãî, ÷òîáûèçs1 ïîëó÷èòü s2 . Ìíîæåñòâî òàêèõ èãðîêîâ äåëèì íà 3 ïîäìíîæåñòâà: âûèãðûâàþùèõ,ïðîèãðûâàþùèõ è íå ìåíÿþùèõ ñâîé âûèãðûø.•àññìàòðèâàåì âñå êîàëèöèè, íå âêëþ÷àþùèå â ñåáÿ ïðîèãðûâàþùèõ èãðîêîâ.
Åñëèêàêàÿ-òî èç ýòèõ êîàëèöèé èìååò õîòü îäíîãî âûèãðûâàþùåãî èãðîêà, ñèòóàöèÿs1íåÿâëÿåòñÿ êîàëèöèîííî ðàâíîâåñíîé.Ñëîæíîñòü âòîðîãî àëãîðèòìà O(u2n (n + ch)),ãäåO(h) ñëîæíîñòü ïðîâåðêè òîãî,âêëþ÷àåò ëè â ñåáÿ äàííîå ìíîæåñòâî êàêóþ-ëèáî êîàëèöèþ. Íàïðèìåð, äëÿ ðàâíîâåñèé ïîÍýøó, ñèëüíûõ ðàâíîâåñèé èk -ðàâíîâåñèé h = 1.  îáùåì ñëó÷àå, h = nc = O(n2n ). Ýòîçíà-÷èò, ÷òî ïðè íàõîæäåíèè ðàâíîâåñèÿ Íýøà âñåãäà áîëåå ýåêòèâåí ïåðâûé àëãîðèòì, ïðèíàõîæäåíèè ñèëüíîãî ðàâíîâåñèÿ âòîðîé.
 îáùåì ñëó÷àå, ìîæåò áûòü áîëåå ýåêòèâåíêàê ïåðâûé, òàê è âòîðîé àëãîðèòì.Ïîëó÷àåì äëÿ åñòåñòâåííîãî ñåìåéñòâà çàäà÷ ïåðâûé àëãîðèòì íàõîæäåíèÿ âñåõ àáñîëþòíûõ êîàëèöèîííûõ ðàâíîâåñèé ñëîæíîñòüþàëãîðèòìà O(xmv w u2n (n + ch)).O(xmv w c2c un+c ), ãäå c = |C|. Ñëîæíîñòü âòîðîãîÑëåäñòâèå 15.1.  ïîî÷åðåäíîé êîíå÷íîé äèíàìè÷åñêîé èãðå ñóùåñòâóåò àáñîëþòíîå êî-àëèöèîííîå ðàâíîâåñèå. Îíî îïðåäåëÿåòñÿ ðåêóððåíòíîé ñèòóàöèåé.Îñòàëîñü ïîíÿòü, â êàêèõ ñëó÷àÿõ çíà÷åíèÿìíîæåñòâàVali (x, t)vali (x, t)îïðåäåëÿþòñÿ îäíîçíà÷íî ò.å.îäíîýëåìåíòíû.
Åäèíñòâåííîñòü èìååò ñìûñë ðàññìàòðèâàòü ëèøü äëÿîáû÷íîãî ðàâíîâåñèÿ êîàëèöèîííîå ðàâíîâåñèå îáîáùàåò îïòèìàëüíîñòü ïî Ïàðåòî (ìíîãîçíà÷íûé ïðèíöèï) è ïîòîìó ñàìî ÿâëÿåòñÿ ìíîãîçíà÷íûì ïðèíöèïîì. Ñëåäóþùàÿ òåîðåìàîáîáùàåò òåîðåìó ï. 6.5.1 èç [51℄:97Òåîðåìà 16(î åäèíñòâåííîñòè ðàâíîâåñèÿ).Ïóñòü φ ðàâíîâåñèå èëè ñâåðíóòûé âûèãðûøâ ïîî÷åðåäíîì äèíàìè÷åñêîì ìåõàíèçìå. Ïóñòü äëÿ êàæäîãî t, i, j, x, y èç fi (x, t) = fi (y, t)ñëåäóåò fj (x, t) = fj (y, t).
Òîãäà â åñòåñòâåííîì ñåìåéñòâå çàäà÷ âñå îöåíêè ïîçèöèévali (x, t) åäèíñòâåííû (åñëè îíè ñóùåñòâóþò).Äîêàçàòåëüñòâî.Èíäóêöèåé ïî êîëè÷åñòâó óðîâíåéæäåíèå: äëÿ êàæäîãîÄëÿm=1t, i, jèçvali (x, t) = vali (y, t)Ïðèt=0äëÿ èãðîêà,valj (x, t) = valj (y, t).val = f .m = k , äîêàæåì ååÏóñòü åäèíñòâåííîñòü èìååò ìåñòî äëÿvalj (y, t).äîêàæåì äàæå áîëåå ñèëüíîå óòâåð-ñëåäóåòåäèíñòâåííîñòü ñëåäóåò èç òîãî, ÷òîïî èíäóêöèîííîìó ïðåäïîëîæåíèþ, ïðèmt > 0j = i(x, 0),èçäëÿm = k + 1. Äåéñòâèòåëüíî,vali (x, t) = vali (y, t)ñëåäóåòvalj (x, t) =õîäÿùåãî â äàííîé ïîçèöèè, îöåíêà åäèíñòâåííà:valj (x, 0) = fj (x, 0) ∗ max valj (π(x, 0)(u), 1))u∈U (x,0)Êàæäîìó çíà÷åíèþ âûðàæåíèÿvalj (π(x, 0)(u), 1)ïîëîæåíèþ, åäèíñòâåííîå çíà÷åíèå âûðàæåíèÿìó çíà÷åíèþ âûðàæåíèÿâûðàæåíèÿvalj (x, 0)fi (x, 0)fj (x, 0)ñîîòâåòñòâóåò, ïî èíäóêöèîííîìó ïðåä-vali (π(x, 0)(u), 1) äëÿâñåõ èãðîêîâ i.
Êàæäî-ñîîòâåòñòâóåò, ïî óñëîâèþ òåîðåìû, åäèíñòâåííîå çíà÷åíèåäëÿ âñåõ èãðîêîâi.Ýòî è çíà÷èò, ÷òî êàæäîìó çíà÷åíèþ âûðàæåíèÿñîîòâåòñòâóåò åäèíñòâåííîå çíà÷åíèå âûðàæåíèÿvali (x, 0)äëÿ âñåõ èãðîêîâi.Ñëåäñòâèå 16.1.  îïòèìèçàöèîííîé çàäà÷å ñ îäíèì êðèòåðèåì îöåíêè ïîçèöèé åäèí-ñòâåííû.Ñëåäñòâèå 16.2.  àíòàãîíèñòè÷åñêîé èãðå ñ f1 (x, t) = −f2 (x, t) îöåíêè ïîçèöèé åäèí-ñòâåííû.Ñëåäñòâèå 16.3.
 èãðå, ãäå âûèãðûø êàæäîãî èãðîêà çàâèñèò îò ðàñïðåäåëåíèÿ åãî òè-ïîâ àëüòðóèçìà èëè ýãîèçìà ïî îòíîøåíèþ ê äðóãèì èãðîêàì [51℄, îöåíêè ïîçèöèé åäèíñòâåííû.Äîêàçàòåëüñòâî.Äåéñòâèòåëüíî, âûèãðûø êàæäîãî èãðîêà ìîæíî ïðåäñòàâèòü êàê âåêòîðHj′ (s) = (Hj (s), Hp1 (s), −Hn1 (s), . . . Hpn (s) , −Hnn (s) ),ïî÷òåíèþ ïîçèòèâíûå èãðîêè äëÿ èãðîêàíåãàòèâíûå èãðîêè äëÿ èãðîêàãäå(p1 , .
. . pn ) óïîðÿäî÷åííûå ïî ïðåä-j , à (n1 , . . . nn ) óïîðÿäî÷åííûå ïî ïðåäïî÷òåíèþj . Ïîëó÷àåì, ÷òî âåêòîð-âûèãðûø îäíîãî èãðîêà Hj (s) îäíî-çíà÷íî îïðåäåëÿåò âåêòîðà-âûèãðûøè îñòàëüíûõ èãðîêîâHi (s) (îíè ñîâïàäàþòñ òî÷íîñòüþäî ïåðåñòàíîâêè). Ââîäÿ íà òàêèõ âåêòîðàõ-âûèãðûøàõ ëåêñèêîãðàè÷åñêèé ïîðÿäîê, ïîëó÷àåì èãðó ñ òåðìèíàëüíûì âûèãðûøåì èç óïîðÿäî÷åííîé ïîëóãðóïïû, äëÿ êîòîðîãî âåðíûóñëîâèÿ òåîðåìû åäèíñòâåííîñòè.983.1.6Òåîðåìà î ðåêóððåíòíûõ ñîîòíîøåíèÿõ äëÿ íàõîæäåíèÿ âñåõðàâíîâåñèé â äèíàìè÷åñêîé èãðåÈòàê, âñå àáñîëþòíûå (êîàëèöèîííûå) ðàâíîâåñèÿ óäîâëåòâîðÿþò ðåêóððåíòíûì ñîîòíîøåíèÿì äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ. Íî âñå ëè ðàâíîâåñèÿ ÿâëÿþòñÿ àáñîëþòíûìè (ò.å.ÏÄÓ-ðàâíîâåñèÿìè)? Äàæå â àíòàãîíèñòè÷åñêèõ èãðàõ ýòî íå âñåãäà òàê, ïîñêîëüêó äëÿêàæäîé ÏÄÓ-ñèòóàöèè ñóùåñòâóåò ìíîæåñòâî ýêâèâàëåíòíûõ ñèòóàöèé, íå ÿâëÿþùèõñÿ ïîçèöèîííî äèíàìè÷åñêè óñòîé÷èâûìè.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
