[учебник] Введение в теорию игр (с приложениями к экономике). Васин, Морозов (2003) (1186146), страница 24
Текст из файла (страница 24)
Àíàëîãè÷íî, (1,0,1) è (0,1,1) − òàêæå ñèòóàöèè ðàâíîâåñèÿ.1231Ïóñòü k > 0, k , k < 0. òîãäà p1 = 1 è p2 = p3 = 0, k = −1 −ïðîòèâîðå÷èå.Àíàëîãè÷íî, íåò è äðóãèõ ñèòóàöèé ðàâíîâåñèÿ, ñîîòâåòñòâóþùèõañëó÷àþ îäíîé ïîëîæèòåëüíîé è äâóõ îòðèöàòåëüíûõ âåëè÷èí k .aÏóñòü k < 0, a = 1, 2, 3; òîãäà ñèòóàöèÿ ðàâíîâåñèÿ (0,0,0).aÏóñòü k = 0, a = 1, 2, 3. Ðåøàÿ ïîëó÷åííóþ ñèñòåìó, íàéäåì äâåñèòóàöèè√ ðàâíîâåñèÿ:√√√√√((3 − 3)/6, (3 − 3)/6, (3 − 3)/6) è ((3 + 3)/6, (3 + 3)/6, (3 + 3)/6).a3Ïóñòü k = 0, a = 1, 2, k > 0; òîãäà p3 = 1. Ðåøàÿ ñîîòâåòñòâóþùóþañèñòåìó, ïîëó÷àåì ñèòóàöèþ ðàâíîâåñèÿ (2/3, 2/3, 1). Åñëè k = 0, a =331, 2, k < 0, òî p3 = 0, p1 = p2 = 1/3, k = 1/3 − ïðîòèâîðå÷èå.Àíàëîãè÷íî, (1, 2/3, 2/3) è (2/3, 1, 2/3) − ñèòóàöèè ðàâíîâåñèÿ.Íàêîíåö, ðàññóæäàÿ àíàëîãè÷íî, óáåæäàåìñÿ, ÷òî íåò ñèòóàöèé ðàâaíîâåñèÿ, ñîîòâåòñòâóþùèõ îäíîé èç âåëè÷èí k , ðàâíîé íóëþ, è äâóì,îòëè÷íûì îò íóëÿ.Èòàê, â èãðå Γ äåâÿòü ñèòóàöèé ðàâíîâåñèÿ â ÷èñòûõ è ñìåøàííûõñòðàòåãèÿõ.Äîìèíèðîâàíèå â èãðàõ ìíîãèõ ëèöÏîíÿòèÿ è ðåçóëüòàòû î äîìèíèðîâàíèè ñòðàòåãèé â èãðàõ äâóõ ëèö,èçëîæåííûå â 10., ëåãêî îáîáùàþòñÿ íà èãðû ìíîãèõ ëèö Γ.Îïðåäåëåíèå.
Áóäåì ãîâîðèòü, ÷òî ñòðàòåãèÿ ha ñòðîãî äîìèíèðóåòñòðàòåãèþ g a (ha g a ) íà ìíîæåñòâå ñèòóàöèé S ⊆ S, åñëè âûïîëíåíîíåðàâåíñòâî ua (s||ha ) ≥ ua (s||g a ) ∀ s ∈ S. Áóäåì ãîâîðèòü î ñëàáîìäîìèíèðîâàíèè (ha g a ), åñëè ua (s||ha ) ≥ ua (s||g a ) ∀ s ∈ S.Îïðåäåëåíèå. Áóäåì ãîâîðèòü, ÷òî ìíîæåñòâî S ñòðîãî (ñîîòâåòñòâåííî ñëàáî) äîìèíèðóåò ìíîæåñòâî S (îáîçíà÷àåòñÿ S S è S S ñîîòâåòñòâåííî), åñëè îíî ìîæåò áûòü ïîëó÷åíî èç S â ðåçóëüòàòå ïî139ÃËÀÂÀ III. ÈÃÐÛ ÌÍÎÃÈÕ ËÈÖñëåäîâàòåëüíîãî èñêëþ÷åíèÿ ñòðîãî (ñîîòâåòñòâåííî ñëàáî) äîìèíèðóåìûõ ñòðàòåãèé, ò.å. ñóùåñòâóåò ïîñëåäîâàòåëüíîñòü âëîæåííûõ ìíîæåñòâS = S1 ⊃ S2 ⊃ ... ⊃ Sk = S , äëÿ êîòîðîé ïðè ëþáîì l = 1, ..., k − 1 âûïîëíåíûóñëîâèÿ:N ñëåäóþùèåaaSl =Sl è äëÿ ëþáûõ a ∈ A, g a ∈ Sla \Sl+1íàéäåòñÿ òàêàÿ ñòðàòåãèÿa∈Aaha ∈ Sl+1, ÷òî ha g a (ha g a ) íà Sl .Ïðîöåäóðà ïîñëåäîâàòåëüíîãî èñêëþ÷åíèÿ äîìèíèðóåìûõ (â ñòðîãîìèëè ñëàáîì ñìûñëå) ñòðàòåãèé ñîñòîèò â ñëåäóþùåì.
Íà ïåðâîì øàãå âûÿñíÿåì äëÿ êàæäîãî èãðîêà, êàêèå ñòðàòåãèè ÿâëÿþòñÿ äîìèíèðóåìûìèíà ìíîæåñòâå âñåõ ñèòóàöèé S1 = S è âûáðàñûâàåì èõ. Ïîëó÷àåì ñóæåííîå ìíîæåñòâî S2 . Òåïåðü ñòðàòåãèè, êîòîðûå íå áûëè äîìèíèðóåìûìèíà ìíîæåñòâå S1 , ìîãóò îêàçàòüñÿ äîìèíèðóåìûìè íà ìíîæåñòâå S2 . Íàñëåäóþùåì øàãå ìû èõ âûêèäûâàåì, ïîëó÷àåì ìíîæåñòâî S3 è ò.ä.Îïðåäåëåíèå. Áóäåì ãîâîðèòü, ÷òî èãðà Γ ðàçðåøèìà ïî äîìèíèðîâàíèþ, åñëè äëÿ íåêîòîðîãî ñëàáî äîìèíèðóþùåãî ìíîæåñòâà S äëÿ êàæäîãî a ∈ A ôóíêöèÿ ua (s) íå çàâèñèò îò sa íà S, ò.å. äëÿ ëþáûõ s ∈ S èaha ∈ S ua (s) = ua (s||ha ).Îïðåäåëåíèå.
Áóäåì ãîâîðèòü, ÷òî ñìåøàííàÿ ñòðàòåãèÿ π a ñòðîãîäîìèíèðóåò ñòðàòåãèþ g a (π a g a ) íà ìíîæåñòâå ñèòóàöèé S ⊆ S, åñëèâûïîëíåíî íåðàâåíñòâî ua (s||π a ) > ua (s||g a ) ∀ s ∈ S. Áóäåì ãîâîðèòü îñëàáîì äîìèíèðîâàíèè (π a g a ), åñëèua (s||π a ) ≥ ua (s||g a ) ∀ s ∈ S.Îïðåäåëåíèå. Áóäåì ãîâîðèòü, ÷òî ìíîæåñòâî S ñòðîãî (ñîîòâåòñòâåííî ñëàáî) äîìèíèðóåò ìíîæåñòâî S â ñìåøàííûõ ñòðàòåãèÿõ (îáîçíà÷àåòñÿ S S è S S ñîîòâåòñòâåííî), åñëè ñóùåñòâóåò ïîñëåäîâàòåëüíîñòüâëîæåííûõ ìíîæåñòâ S = S1 ⊃ S2 ⊃ ... ⊃ Sk = S , äëÿ êîòîðîé ïðè ëþáîìl = 1, N..., k − 1 âûïîëíåíû ñëåäóþùèå óñëîâèÿ:aSl =Sla è äëÿ ëþáûõ a ∈ A, g a ∈ Sla \Sl+1íàéäåòñÿ òàêàÿ ñòðàòåãèÿa∈Aaaπ a ∈ Sl+1, ÷òî π a g a (π a g a ) íà Sl è πsaa = 0 ∀ sa ∈/ Sl+1.Ñëåäóþùåå óòâåðæäåíèå àíàëîãè÷íî òåîðåìåN 10.4.Òåîðåìà 12.4.
1) Ïóñòü ìíîæåñòâî S̃ =S̃ a ñòðîãî äîìèíèðóåòa∈Aìíîæåñòâî S â ñìåøàííûõ ñòðàòåãèÿõ. Òîãäà äëÿ ëþáîãî ñìåøàííîãîðàâíîâåñèÿ ïî Íýøó π = (π a , a ∈ A) âûïîëíåíî óñëîâèå:äëÿ ëþáûõ a ∈ A è sa ∈/ S̃ a íåîáõîäèìî π asa = 0.140 12. Ðàâíîâåñèå ïî Íýøó. Ðåøåíèå èãð â íîðìàëüíîé ôîðìå2) Ïóñòü ìíîæåñòâî S̃ =NS̃ a ñëàáî äîìèíèðóåò ìíîæåñòâî S â ñìå-a∈Aøàííûõ ñòðàòåãèÿõ èD π̃ = (π̃saa , sa ∈ S̃ a , aE∈ A) − ñìåøàííîå ðàâíîâåñèåïî Íýøó â èãðå Γ̃ = A, S̃ a , ua (s), a ∈ A ñ ñîêðàùåííûìè ìíîæåñòâàìè ñòðàòåãèé. Îïðåäåëèì ñèòóàöèþ â ñìåøàííûõ ñòðàòåãèÿõ π èñõîäíîéèãðû Γ : äëÿ ëþáîãî a ∈ A(π̃saa , åñëè sa ∈ S̃ a ,π asa =0,åñëè sa ∈/ S̃ a .Òîãäà π − ðàâíîâåñèå ïî Íýøó â èñõîäíîé èãðå Γ.Ìîäåëè èãðîâîé äèíàìèêèÌîäåëè ýòîãî òèïà ðàçâèòû êàê àëüòåðíàòèâà ñòàòè÷åñêèì ïðèíöèïàì îïòèìàëüíîñòè (òàêèì, êàê ðàâíîâåñèå ïî Íýøó, ðåøåíèÿ ïî äîìèíèðîâàíèþ).
Óêàçàííûå ïðèíöèïû ïðèíÿòèÿ ðåøåíèÿ òðåáóþò äëÿ ñâîåéðåàëèçàöèè ïîëíîé èíôîðìèðîâàííîñòè èãðîêîâ îòíîñèòåëüíî óñëîâèéèãðû (ò.å. îòíîñèòåëüíî ìíîæåñòâ ñòðàòåãèé è ôóíêöèé âûèãðûøà âñåõó÷àñòíèêîâ). Áîëåå òîãî, èãðîêè äîëæíû áûòü ðàöèîíàëüíû â ïðèíÿòèè ñîáñòâåííûõ ðåøåíèé è ïðåäïîëàãàòü òàêóþ æå ðàöèîíàëüíîñòü îòñâîèõ ïàðòíåðîâ. Ðàññìàòðèâàåìûå äèíàìè÷åñêèå ìîäåëè ïðåäúÿâëÿþòçíà÷èòåëüíî ìåíüøå òðåáîâàíèé ê èíôîðìèðîâàííîñòè è ðàöèîíàëüíîñòè èãðîêîâ è áîëüøå ïîõîæè íà ðåàëüíûå ìåòîäû ïðèíÿòèÿ ðåøåíèé.÷òî Ïðåäïîëîæèì, êîíôëèêòíàÿ ñèòóàöèÿ îïèñûâàåòñÿ èãðîé Γ =A, S a , ua (s), a ∈ A ñ êîíå÷íûìè ìíîæåñòâàìè ñòðàòåãèé S a , a ∈ A.Ïóñòü èãðà ïîâòîðÿåòñÿ â ïåðèîäû âðåìåíè t = 1, 2, ....
Êàæäûé èãðîêâûáèðàåò ñòðàòåãèþ sa (t + 1) íà ïåðèîä (øàã) t + 1, èñõîäÿ èç èñòîðèèht = {s(τ ) = (sa (τ ), a ∈ A)}τ ≤t , ñëîæèâøåéñÿ ê ýòîìó ïåðèîäó. Áåñêîíå÷íóþ ïîñëåäîâàòåëüíîñòü ñèòóàöèé {s(t)} áóäåì íàçûâàòü òðàåêòîðèåéïðîöåññà. Îáîçíà÷èì ÷åðåç H ìíîæåñòâîS t âñåâîçìîæíûõ èñòîðèé, ò.å.H = {h }.t≥1Ïðàâèëî ïîâåäåíèÿ èãðîêàçàäàåòñÿ îòîáðàæåíèåì â aýòîì ïðîöåññåaaµ : H → S . Ñîâîêóïíîñòü Γ; µ , a ∈ A íàçûâàåòñÿ äåòåðìèíèðîâàííûì èãðîâûì ïðîöåññîì.Îïðåäåëèì ïîíÿòèå àäàïòèâíîãî ïîâåäåíèÿ. Ñìûñë åãî ñîñòîèò â òîì,÷òî èãðîê ïðîãíîçèðóåò âåðîÿòíîñòè ðåàëèçàöèè ñòðàòåãèé ïàðòíåðîâsA\{a} = (sb , b ∈ A\{a}), èñõîäÿ èç ïðåäûñòîðèè, è ìàêñèìèçèðóåò ñîáñòâåííûé âûèãðûø íà îñíîâàíèè òàêîãî ïðîãíîçà.
 êà÷åñòâå ïðèìåðà141ÃËÀÂÀ III. ÈÃÐÛ ÌÍÎÃÈÕ ËÈÖðàññìîòðèì ìîäåëü íàèëó÷øèõ îòâåòîâ.Ïðîöåññ íà÷èíàåòñÿ ñ âûáîðà èãðîêàìè ïðîèçâîëüíûõ ñòðàòåãèéas (1), a ∈ A. Äàëåå ïîñëå t øàãîâ íà ñëåäóþùåì, (t + 1)-ì øàãåsa (t + 1) ∈ Arg maxua (s(t)||sa ), a ∈ A.aas ∈SÒàêèì îáðàçîì, èãðîê ìàêñèìèçèðóåò ñîáñòâåííûé âûèãðûø, èñõîäÿ èçïðåäïîëîæåíèÿ, ÷òî äðóãèå èãðîêè íå ìåíÿþò ñâîèõ ñòðàòåãèé ïî ñðàâíåíèþ ñ ïðåäûäóùèì øàãîì. áîëåå îáùåì ñëó÷àå ïðåäïîëîæåíèÿ î ïîâåäåíèè ïàðòíåðîâ â ìîìåíò âðåìåíè t + 1 ìîæíîíàáîðîì ïàðàìåòðîâPõàðàêòåðèçîâàòüaa{λt,τ ≥ 0}τ ≤t , òàêèì, ÷òîλt,τ = 1.
Èãðîê a ñ÷èòàåò, ÷òî ñ âåðîÿòíîñòüþτ ≤tλat,τ â ìîìåíò t + 1 ïîâòîðèòñÿ íàáîð ñòðàòåãèé äðóãèõ èãðîêîâ sA\{a} (τ ),ñëó÷èâøèéñÿ â ìîìåíò τ. Èñõîäÿ èç ýòîãî, èãðîê a ìàêñèìèçèðóåò ìàòåìàòè÷åñêîå îæèäàíèå ñâîåãî âûèãðûøà. Ñëåäîâàòåëüíî,sa (t + 1) ∈ Arg maxaas ∈SXλat,τ ua (s(τ )||sa ), a ∈ A.(12.1)τ ≤tÎïðåäåëåíèå. Ïóñòü T − ìèíèìàëüíîå ÷èñëî ïåðèîäîâ, äëÿ êîòîðîãît−τ > T ⇒ λat,τ = 0 ∀ a ∈ A, t, τ. Òîãäà T íàçûâàåòñÿ ïàìÿòüþ èãðîâîãîïðîöåññà (èãðîêè íå ïîìíÿò òî, ÷òî ïðîèñõîäèëî T øàãîâ íàçàä).Ïðèìåðîì ïðîöåññà ñ áåñêîíå÷íîé ïàìÿòüþ ÿâëÿåòñÿ èòåðàöèîííûéïðîöåññ Áðàóíà äëÿ ìàòðè÷íûõ èãð, èçëîæåííûé â 5., èëè àíàëîãè÷íûéïðîöåññ äëÿ áèìàòðè÷íûõ èãð èç 10., ãäå λat,τ = 1/t äëÿ âñåõ òàêèõ τ èt, ÷òî τ ≤ t.  îáùåì ñëó÷àå ïðàâèëî ïðîãíîçèðîâàíèÿ ìîæíî çàäàòüîòîáðàæåíèåì pa (sA\{a} |ht ), îïðåäåëÿþùåì äëÿ èãðîêà a ñóáúåêòèâíóþâåðîÿòíîñòü ðåàëèçàöèè sA\{a} â çàâèñèìîñòè îò èñòîðèè ht .
Ïðè èñïîëüçîâàíèè ïðàâèë ïðîãíîçèðîâàíèÿ pa , a ∈ A, íà (t + 1)-ì øàãå èãðîêèâûáèðàþò ñòðàòåãèè ïî ïðàâèëósa (t + 1) ∈ Arg maxaas ∈SXpa (sA\{a} | ht )ua (sA\{a} , sa ), a ∈ A.sA\{a}Àäàïòèâíûå ïðàâèëà ñîîòâåòñòâóþò ñèòóàöèè, êîãäà êàæäûé èãðîêñ÷èòàåò ïîâåäåíèå ïàðòíåðîâ, íå çàâèñÿùèì îò åãî ñîáñòâåííîãî âûáîðà.Îí ëèáî íå ó÷èòûâàåò âîçìîæíîãî âëèÿíèÿ âûáîðà â òåêóùèé ïåðèîä142 12. Ðàâíîâåñèå ïî Íýøó. Ðåøåíèå èãð â íîðìàëüíîé ôîðìåíà ïîñëåäóþùèå ïîâòîðåíèÿ, ëèáî îíè åãî íå èíòåðåñóþò (íå ñëó÷àéíî äðóãèì íàçâàíèåì ìîäåëè íàèëó÷øèõ îòâåòîâ ÿâëÿåòñÿ "áëèçîðóêîåïðèñïîñîáëåíèå").Äèíàìèêà èãðîâûõ ïðîöåññîâ ñ àäàïòèâíûìè ïðàâèëàìè ïîâåäåíèÿîêàçûâàåòñÿ äëÿ ìíîãèõ èãð õîðîøî ñîãëàñîâàííîé ñ óêàçàííûìè âûøåñòàòè÷åñêèìè ïðèíöèïàìè îïòèìàëüíîñòè.
Ïðèâîäèìûå íèæå óòâåðæäåíèÿ ïîäòâåðæäàþò âîçìîæíîñòü èñïîëüçîâàíèÿ ïîíÿòèé ðàâíîâåñèÿ ïîÍýøó è äîìèíèðóþùèõ ìíîæåñòâ äëÿ îïèñàíèÿ ïîâåäåíèÿ èíäèâèäóóìîâ ñ îãðàíè÷åííîé ðàöèîíàëüíîñòüþ.Îïðåäåëåíèå. Ïðàâèëî ïðîãíîçèðîâàíèÿ pa íàçîâåì àäàïòèâíûì, åñëè äëÿ ëþáîé òðàåêòîðèè {s(t)} è ëþáîãî íàáîðà ñòðàòåãèé sA\{a} , êîòîðûé âñòðå÷àåòñÿ â {s(t)} ëèøü êîíå÷íîå ÷èñëî ðàç, ñóáúåêòèâíàÿ âåðîÿòíîñòü pa (sA\{a} |ht ) ñòðåìèòñÿ ê íóëþ ïðè t → ∞, ãäå {ht } − ïîñëåäîâàòåëüíîñòü èñòîðèé, îòâå÷àþùèõ òðàåêòîðèè {s(t)}.Óïðàæíåíèå 12.2. Ïîêàæèòå, ÷òî â ïðîöåññå Áðàóíà èãðîêè èñïîëüçóþò àäàïòèâíûå ïðàâèëà ïðîãíîçèðîâàíèÿ.Òåîðåìà 12.5. Ïóñòü ïîñëåäîâàòåëüíîñòü ìíîæåñòâ ñèòóàöèéS = S1 ⊃ S2 ⊃ ...
⊃ Sk ïîëó÷åíà â ðåçóëüòàòå ïîñëåäîâàòåëüíîãî èñêëþ÷åíèÿ ñòðàòåãèé, ñòðîãî äîìèíèðóåìûõ ñìåøàííûìè ñòðàòåãèÿìè, èaäëÿ íåêîòîðûõ a ∈ A, r ∈ {1, ..., k − 1}. Òîãäà ñïðàâåäëèâûg a ∈ Sra \Sr+1ñëåäóþùèå óòâåðæäåíèÿ.1) Äëÿ ëþáîé òðàåêòîðèè {s(t)} ìîäåëè íàèëó÷øèõ îòâåòîâsa (t + 1) 6= g a ïðè t ≥ r.2) Äëÿ âñÿêîé àäàïòèâíîé äèíàìèêè ñ íàáîðîì ïàðàìåòðîâ {λt,τ } èïàìÿòüþ T sa (t + 1) 6= g a ïðè t ≥ rT.Äîêàçàòåëüñòâî. 1) Ïðåäïîëîæèì ñíà÷àëà, ÷òî ñòðàòåãèÿ g a ïîëó÷åíà â ðåçóëüòàòå ïîñëåäîâàòåëüíîãî èñêëþ÷åíèÿ ñòðàòåãèé, ñòðîãî äîìèíèðóåìûõ ÷èñòûìè ñòðàòåãèÿìè. Ïðîâåäåì äîêàçàòåëüñòâî ìåòîäîììàòåìàòè÷åñêîé èíäóêöèè ïî r. Ïóñòü sa g a , ò.å. r = 1. Òîãäà ñòðàòåãèÿ g a íå ÿâëÿåòñÿ íàèëó÷øèì îòâåòîì íà ëþáûå ñòðàòåãèè äðóãèõèãðîêîâ.
Ñëåäîâàòåëüíî, sa (t + 1) 6= g a ïðè t ≥ 1. Ïóñòü óòâåðæäåíèåäîêàçàíî äëÿ ëþáûõ ñòðàòåãèé èç ìíîæåñòâà S1 \Sr . Ïî èíäóêòèâíîìóïðåäïîëîæåíèþ s(t) ∈ Sr ïðè ëþáûõ t ≥ r. Ïîýòîìó, íà÷èíàÿ ñ øàãàr, ìîæíî îãðàíè÷èòüñÿ ðåäóöèðîâàííîé èãðîé ñ ìíîæåñòâàìè ñòðàòåãèéaSra , a ∈ A. Âîçüìåì g a ∈ Sra \Sr+1.  ðàññìàòðèâàåìîé ðåäóöèðîâàííîéaèãðå ñòðàòåãèÿ g ñòðîãî äîìèíèðóåìà è sa (t + 1) 6= sa ïðè ëþáûõ t ≥ r.143ÃËÀÂÀ III.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
