А.А. Васин, В.В. Морозов - Введение в теорию игр с приложениями к экономике (1184512), страница 28
Текст из файла (страница 28)
12.1. s1 1 1 1 1 2 2 2 2 s2 1 1 2 2 1 1 2 2 s3 1 2 1 2 1 2 1 2 u1 (s) u2 (s) u3 (s) -1 -1 -1 -1 -1 0 -1 0 -1 -4 -3 -3 0 -1 -1 -3 -4 -3 -3 -3 -4 -3 -3 -3 Ïîñòðîè� ñìåøàííî� ðàñøèðåíè� Γ. Ïóñò� pa ∈ [0, 1], a = 1, 2, 3, −âåðîÿòíîñòü, � êîòîðî� ïðåäïðèÿòè� a âûáèðàå� ñòðàòåãè� 1. Âîçìîæíû� ñèòóàöè� � èãð� Γ ñîñòàâëÿþ� ìíîæåñòâ� Π = {π = (p 1 , p 2 , p 3 ) | p a ∈ [0, 1], a = 1, 2, 3}. Ôóíêöè� âûèãðûø� ïåðâîã� ïðåäïðèÿòè� � èãð� Γ u 1 (π) = p 1 [−p 2 p 3 − p 2 (1 − p 3 ) − (1 − p 2 )p 3 − 4(1 − p 2 )(1 − p 3 )]+ +(1 − p 1 )[−3p 2 (1 − p 3 ) − 3(1 − p 2 )p 3 − 3(1 − p 2 )(1 − p 3 )] = = (−6p 2 p 3 + 3p 2 + 3p 3 − 1)p 1 + 3p 2 p 3 − 3 = k 1 (p 2 , p 3 )p 1 + l1 (p 2 , p 3 ). Àíàëîãè÷íî, u 2 (π) = k 2 (p 1 , p 3 )p 2 + l2 (p 1 , p 3 ), u 3 (π) = k 3 (p 1 , p 2 )p 3 + l3 (p 1 , p 2 ), ãä� l1 (p 2 , p 3 ) = 3p 2 p 3 − 3, l2 (p 1 , p 3 ) = 3p 1 p 3 − 3, l3 (p 1 , p 2 ) = 3p 1 p 2 − 3, k 1 (p 2 , p 3 ) = −6p 2 p 3 + 3p 2 + 3p 3 − 1, k 2 (p 1 , p 3 ) = −6p 1 p 3 + 3p 1 + 3p 3 − 1, k 3 (p 1 , p 2 ) = −6p 1 p 2 + 3p 1 + 3p 2 − 1.
138 12. Ðàâíîâåñè� ï� Íýøó. Ðåøåíè� èã� � íîðìàëüíî� ôîðì�Ïóñò� π = (pa , a = 1, 2, 3) − ïðîèçâîëüíà� ñèòóàöè� ðàâíîâåñèÿ. Ïîëîæè� 1 2 3 k = k 1 (p 2 , p 3 ), k = k 2 (p 1 , p 3 ), k = k 1 (p 1 , p 2 ). aaÇàìåòèâ, ÷ò� åñë� k > 0, ò� pa = 1, � åñë� k < 0, ò� pa = 0, ðàññìîòðè� âñ� âîçìîæíû� ñëó÷àè.
aaÏóñò� k > 0, a = 1, 2, 3; òîãä� pa = 1 � k = −1 − ïðîòèâîðå÷èå. a 3Ïóñò� k > 0, a = 1, 2, k < 0. � ýòî� ñëó÷à� ñèòóàöè� ðàâíîâåñè� (1,1,0). Àíàëîãè÷íî, (1,0,1) � (0,1,1) − òàêæ� ñèòóàöè� ðàâíîâåñèÿ. 123 1Ïóñò� 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). a 3 Ïóñò� k = 0, a = 1, 2, k > 0; òîãä� p3 = 1.
Ðåøà� ñîîòâåòñòâóþùó� añèñòåìó, ïîëó÷àå� ñèòóàöè� ðàâíîâåñè� (2/3, 2/3, 1). Åñë� k = 0, a = 3 3 1, 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 ñëåäóþùè� a Sl = Sl � äë� ëþáû� a ∈ A, g a ∈ Sla \Sla +1 íàéäåòñ� òàêà� ñòðàòåãè� a∈A ha ∈ Sla +1 , ÷ò� ha � g a (ha � g a ) í� Sl . Ïðîöåäóð� ïîñëåäîâàòåëüíîã� èñêëþ÷åíè� äîìèíèðóåìû� (� ñòðîãî� èë� ñëàáî� ñìûñëå) ñòðàòåãè� ñîñòîè� � ñëåäóþùåì. Í� ïåðâî� øàã� âûÿñíÿå� äë� êàæäîã� èãðîêà, êàêè� ñòðàòåãè� ÿâëÿþòñ� äîìèíèðóåìûì� í� ìíîæåñòâ� âñå� ñèòóàöè� S1 = S � âûáðàñûâàå� èõ. Ïîëó÷àå� ñóæåííî� ìíîæåñòâ� S2 . Òåïåð� ñòðàòåãèè, êîòîðû� í� áûë� äîìèíèðóåìûì� í� ìíîæåñòâ� S1 , ìîãó� îêàçàòüñ� äîìèíèðóåìûì� í� ìíîæåñòâ� S2 . Í� ñëåäóþùå� øàã� ì� è� âûêèäûâàåì, ïîëó÷àå� ìíîæåñòâ� S3 � ò.ä.
Îïðåäåëåíèå. Áóäå� ãîâîðèòü, ÷ò� èãð� Γ ðàçðåøèì� ï� äîìèíèðîâàíèþ, åñë� äë� íåêîòîðîã� ñëàá� äîìèíèðóþùåã� ìíîæåñòâ� S äë� êàæäîã� a ∈ A ôóíêöè� ua (s) í� çàâèñè� î� sa í� S, ò.å. äë� ëþáû� s ∈ S � a ha ∈ 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 âûïîëíåí� ñëåäóþùè� óñëîâèÿ: a Sl = Sla � äë� ëþáû� a ∈ A, g a ∈ Sla \Sl+1 íàéäåòñ� òàêà� ñòðàòåãè� a∈A π a ∈ Sla +1 , ÷ò� π a � g a (π a � g a ) í� Sl � πsa a = 0 ∀ sa ∈/ Sla +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 π̃ = (π̃sa a , sa ∈ S̃ a , a E∈ A) − ñìåøàííî� ðàâíîâåñè� ˜ = A, S̃ a , ua (s), a ∈ A � ñîêðàùåííûì� ìíîæåñòâàï� Íýø� � èãð� Γ ì� ñòðàòåãèé.
Îïðåäåëè� ñèòóàöè� � ñìåøàííû� ñòðàòåãèÿ� π èñõîäíî� èãð� Γ : äë� ëþáîã� a ∈ A � π̃sa a , åñë� sa ∈ S̃ a , π a sa = 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 ìíîæåñòâ� t âñåâîçìîæíû� èñòîðèé, ò.å. H = {h }. t≥1Ïðàâèë� ïîâåäåíè� èãðîê� çàäàåòñ� îòîáðàæåíèå� � aýòî� ïðîöåññ� a a µ : H → S . Ñîâîêóïíîñò� Γ; µ , a ∈ A íàçûâàåòñ� äåòåðìèíèðîâàííû� èãðîâû� ïðîöåññîì. Îïðåäåëè� ïîíÿòè� àäàïòèâíîã� ïîâåäåíèÿ. Ñìûñ� åã� ñîñòîè� � òîì, ÷ò� èãðî� ïðîãíîçèðóå� âåðîÿòíîñò� ðåàëèçàöè� ñòðàòåãè� ïàðòíåðî� sA\{a} = (sb , b ∈ A\{a}), èñõîä� è� ïðåäûñòîðèè, � ìàêñèìèçèðóå� ñîáñòâåííû� âûèãðû� í� îñíîâàíè� òàêîã� ïðîãíîçà.
� êà÷åñòâ� ïðèìåð� 141ÃËÀÂ� III. ÈÃÐ� ÌÍÎÃÈ� ËÈ�ðàññìîòðè� ìîäåë� íàèëó÷øè� îòâåòîâ. Ïðîöåñ� íà÷èíàåòñ� � âûáîð� èãðîêàì� ïðîèçâîëüíû� ñòðàòåãè� as (1), a ∈ A. Äàëå� ïîñë� t øàãî� í� ñëåäóþùåì, (t + 1)-� øàã� s a (t + 1) ∈ Arg max u a (s(t)||s a ), a ∈ A. aa s ∈SÒàêè� îáðàçîì, èãðî� ìàêñèìèçèðóå� ñîáñòâåííû� âûèãðûø, èñõîä� è� ïðåäïîëîæåíèÿ, ÷ò� äðóãè� èãðîê� í� ìåíÿþ� ñâîè� ñòðàòåãè� ï� ñðàâíåíè� � ïðåäûäóùè� øàãîì. � áîëå� îáùå� ñëó÷à� ïðåäïîëîæåíè� � ïîâåäåíè� ïàðòíåðî� � ìîìåí� âðåìåí� t + 1 ìîæí� íàáîðî� ïàðàìåòðî� Põàðàêòåðèçîâàò� aa {λt,τ ≥ 0}τ ≤t , òàêèì, ÷ò� λt,τ = 1. Èãðî� a ñ÷èòàåò, ÷ò� � âåðîÿòíîñòü� τ ≤t λa t,τ � ìîìåí� t + 1 ïîâòîðèòñ� íàáî� ñòðàòåãè� äðóãè� èãðîêî� sA\{a} (τ ),ñëó÷èâøèéñ� � ìîìåí� τ. Èñõîä� è� ýòîãî, èãðî� a ìàêñèìèçèðóå� ìàòåìàòè÷åñêî� îæèäàíè� ñâîåã� âûèãðûøà.
Ñëåäîâàòåëüíî, s a (t + 1) ∈ Arg max aa s ∈SXλat,τ u a (s(τ )||s a ), a ∈ A. (12.1)τ ≤t Îïðåäåëåíèå. Ïóñò� T − ìèíèìàëüíî� ÷èñë� ïåðèîäîâ, äë� êîòîðîã� t−τ > T ⇒ λa t,τ = 0 ∀ a ∈ A, t, τ. Òîãä� T íàçûâàåòñ� ïàìÿòü� èãðîâîãîïðîöåññ� (èãðîê� í� ïîìíÿ� òî, ÷ò� ïðîèñõîäèë� T øàãî� íàçàä). Ïðèìåðî� ïðîöåññ� � áåñêîíå÷íî� ïàìÿòü� ÿâëÿåòñ� èòåðàöèîííû� ïðîöåñ� Áðàóí� äë� ìàòðè÷íû� èãð, èçëîæåííû� � 5., èë� àíàëîãè÷íû� ïðîöåñ� äë� áèìàòðè÷íû� èã� è� 10., ãä� λa t,τ = 1/t äë� âñå� òàêè� τ èt, ÷ò� τ ≤ t.
� îáùå� ñëó÷à� ïðàâèë� ïðîãíîçèðîâàíè� ìîæí� çàäàò� îòîáðàæåíèå� pa (sA\{a} |ht ), îïðåäåëÿþùå� äë� èãðîê� a ñóáúåêòèâíó� âåðîÿòíîñò� ðåàëèçàöè� sA\{a} � çàâèñèìîñò� î� èñòîðè� ht . Ïð� èñïîëüçîâàíè� ïðàâè� ïðîãíîçèðîâàíè� pa , a ∈ A, í� (t + 1)-� øàã� èãðîê� âûáèðàþ� ñòðàòåãè� ï� ïðàâèë� s a (t + 1) ∈ Arg max aa s ∈SXp a (s A\{a} | ht )u a (s A\{a} , s a ), a ∈ A. sA\{a} Àäàïòèâíû� ïðàâèë� ñîîòâåòñòâóþ� ñèòóàöèè, êîãä� êàæäû� èãðî� ñ÷èòàå� ïîâåäåíè� ïàðòíåðîâ, í� çàâèñÿùè� î� åã� ñîáñòâåííîã� âûáîðà.
Î� ëèá� í� ó÷èòûâàå� âîçìîæíîã� âëèÿíè� âûáîð� � òåêóùè� ïåðèî� 142 12. Ðàâíîâåñè� ï� Íýøó. Ðåøåíè� èã� � íîðìàëüíî� ôîðì�í� ïîñëåäóþùè� ïîâòîðåíèÿ, ëèá� îí� åã� í� èíòåðåñóþ� (í� ñëó÷àéí� äðóãè� íàçâàíèå� ìîäåë� íàèëó÷øè� îòâåòî� ÿâëÿåòñ� "áëèçîðóêî� ïðèñïîñîáëåíèå"). Äèíàìèê� èãðîâû� ïðîöåññî� � àäàïòèâíûì� ïðàâèëàì� ïîâåäåíè� îêàçûâàåòñ� äë� ìíîãè� èã� õîðîø� ñîãëàñîâàííî� � óêàçàííûì� âûø� ñòàòè÷åñêèì� ïðèíöèïàì� îïòèìàëüíîñòè.
Ïðèâîäèìû� íèæ� óòâåðæäåíè� ïîäòâåðæäàþ� âîçìîæíîñò� èñïîëüçîâàíè� ïîíÿòè� ðàâíîâåñè� ï� Íýø� � äîìèíèðóþùè� ìíîæåñò� äë� îïèñàíè� ïîâåäåíè� èíäèâèäóóìî� � îãðàíè÷åííî� ðàöèîíàëüíîñòüþ. Îïðåäåëåíèå. Ïðàâèë� ïðîãíîçèðîâàíè� pa íàçîâå� àäàïòèâíûì, åñë� äë� ëþáî� òðàåêòîðè� {s(t)} � ëþáîã� íàáîð� ñòðàòåãè� sA\{a} , êîòîðû� âñòðå÷àåòñ� � {s(t)} ëèø� êîíå÷íî� ÷èñë� ðàç, ñóáúåêòèâíà� âåðîÿòíîñò� pa (sA\{a} |ht ) ñòðåìèòñ� � íóë� ïð� t → ∞, ãä� {ht } − ïîñëåäîâàòåëüíîñò� èñòîðèé, îòâå÷àþùè� òðàåêòîðè� {s(t)}. Óïðàæíåíè� 12.2. Ïîêàæèòå, ÷ò� � ïðîöåññ� Áðàóí� èãðîê� èñïîëüçóþ� àäàïòèâíû� ïðàâèë� ïðîãíîçèðîâàíèÿ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
