А.А. Васин, В.В. Морозов - Введение в теорию игр с приложениями к экономике (1184512), страница 29
Текст из файла (страница 29)
Òåîðåì� 12.5. Ïóñò� ïîñëåäîâàòåëüíîñò� ìíîæåñò� ñèòóàöè� S = S1 ⊃ S2 ⊃ ... ⊃ Sk ïîëó÷åí� � ðåçóëüòàò� ïîñëåäîâàòåëüíîã� èñêëþ÷åíè� ñòðàòåãèé, ñòðîã� äîìèíèðóåìû� ñìåøàííûì� ñòðàòåãèÿìè, � g a ∈ Sra \Sra +1 äë� íåêîòîðû� a ∈ A, r ∈ {1, ..., k − 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, ìîæí� îãðàíè÷èòüñ� ðåäóöèðîâàííî� èãðî� � ìíîæåñòâàì� ñòðàòåãè� Sra , a ∈ A. Âîçüìå� g a ∈ Sra \Sra +1 .
� ðàññìàòðèâàåìî� ðåäóöèðîâàííî� èãð� ñòðàòåãè� g a ñòðîã� äîìèíèðóåì� � sa (t + 1) 6= sa ïð� ëþáû� t ≥ r. 143ÃËÀÂ� III. ÈÃÐ� ÌÍÎÃÈ� ËÈ�Ïåðåéäå� � äîìèíèðîâàíè� ñìåøàííûì� ñòðàòåãèÿìè. Ïóñò� ñìåøàííà� ñòðàòåãè� π a ñòðîã� äîìèíèðóå� ñòðàòåãè� g a , ò.å. r = 1.
Òîãä� äë� ëþáî� ñèòóàöè� s(t) íàéäåòñ� ÷èñòà� ñòðàòåãè� sa , äë� êîòîðî� πsa a > 0 � ua (s(t)||sa ) > ua (s(t)||g a ). Ñëåäîâàòåëüíî, sa (t + 1) =6 g a ïðèëþáû� t ≥ 1. Äîêàçàòåëüñòâî, êà� � äë� ñëó÷à� äîìèíèðîâàíè� ÷èñòûì� ñòðàòåãèÿìè, çàâåðøàåòñ� èíäóêöèå� ï� r. 2) Ïóñò� sa � g a .
Òîãä� ñòðàòåãè� g a í� ÿâëÿåòñ� íàèëó÷øè� îòâåòî� èãðîê� a ïð� t ≥ 2, � íà÷èíà� � øàã� T + 1, îí� í� âõîäè� � ïðàâû� ÷àñò� (12.1) � í� âëèÿå� í� ïîâåäåíè� îñòàëüíû� èãðîêîâ. Ïîýòîì� ïð� t ≥ T + 1 ìîæí� ðàññìàòðèâàò� ðåäóöèðîâàííó� èãð� � ìíîæåñòâàì� ñòðàòåãè� S2 b ∀ b ∈ A. Äàëå� ïðîâîäÿòñ� ðàññóæäåíè� ï� èíäóêöèè.
Ïóñò� òåïåð� ñòðàòåãè� g a ñòðîã� äîìèíèðóåòñ� ñìåøàííî� ñòðàòåãèa å� äë� ëþáî� ñèòóàöè� s(τ ) âûïîëíåí� íåðàâåíñòâ� P πa . Òîãä� aπsa u (s(τ )||sa ) > ua (s(τ )||g a ), � îòñþä� sa Xsa πsaa Xλat,τ u a (s(τ )||s a ) > τ ≤t Xλat,τ u a (s(τ )||g a ). τ ≤t Ñëåäîâàòåëüíî, íàéäåòñ� ñòðàòåãè� sa , äë� êîòîðî� πsa a > 0 � PP òàêà� a aaa aaa6 g a ïð� τ ≤t λt,τ u (s(τ )||s ) > τ ≤t λt,τ u (s(τ )||g ). Ïîýòîì� s (t + 1) =t ≥ 1, � ïð� t ≥ T + 1 ñòðàòåãè� g a í� âëèÿå� í� âûáîð� äðóãè� èãðîêîâ.
Ïîýòîìó, íà÷èíà� � øàã� T + 1, ìîæí� ðàññìàòðèâàò� ðåäóöèðîâàííó� èãð� � ìíîæåñòâàì� ñòðàòåãè� S2 b ∀ b ∈ A. Äàëå� ïðîâîäÿòñ� ðàññóæäåíè� ï� èíäóêöèè. Óòâåðæäåíè� 12.2. Ïóñò� òðàåêòîðè� {s(t)} ñîîòâåòñòâóå� íàáîð� àäàïòèâíû� ïðàâè� pa , a ∈ A � s(t) ≡ s ïð� ðàâíîâåñè� ï� Íýø� èãð� Γ. Äîêàçàòåëüñòâî. È� óñëîâè� âûòåêàåò, ÷ò� t ≥ t.
Òîãä� s −lim p a (s A\{a} )|ht ) = 0 t→∞ ïð� ëþáû� sA\{a} 6= (sb , b ∈ A\{a}). Ñëåäîâàòåëüíî, lim p a (s b , b ∈ A\{a})|ht ) = 1 ∀ a ∈ A. t→∞ (12.2) Ïðåäïîëîæèì, ÷ò� s í� ÿâëÿåòñ� ñèòóàöèå� ðàâíîâåñèÿ. Òîãä� íàéäåòñ� òàêà� ñòðàòåãè� sa íåêîòîðîã� èãðîê� a, ÷ò� ua (s||sa ) > ua (s). � ó÷åòî� 144 13.
Ïîçèöèîííû� èãð� � ïîëíî� èíôîðìàöèå�(12.2) ïð� äîñòàòî÷í� áîëüøî� t XXp a (s A\{a} | ht )u a (s A\{a} , s a ) >sA\{a} p a (s A\{a} | ht )u a (s A\{a} , s a ). sA\{a} Îòñþä� sa (t + 1) 6= sa , ÷ò� ïðîòèâîðå÷è� óñëîâèþ. Áîëüøî� èíòåðå� ïðåäñòàâëÿþ� îáðàòíû� ðåçóëüòàò� − � ñõîäèìîñò� àäàïòèâíû� ïðîöåññî� � ðàâíîâåñèÿ� ï� Íýø� (ñì.
òåîðåì� 5.3 � 10.5). 13. Ïîçèöèîííû� èãð� � ïîëíî� èíôîðìàöèå� Ìíîãè� ðåàëüíû� êîíôëèêòíû� ñèòóàöè� èìåþ� äëèòåëüíû� õàðàêòåð. È� ó÷àñòíèê� äåéñòâóþ� íåîäíîêðàòí� � � ó÷åòî� èíôîðìàöè� � ïðåäøåñòâóþùå� ðàçâèòè� êîíôëèêòà. Äë� ñîîòâåòñòâóþùè� ìîäåëå� îáùè� òåîðåì� ñóùåñòâîâàíè� ðåøåíè� äë� èã� � íîðìàëüíî� ôîðì� í� ïîçâîëÿþ� íàõîäèò� èë� äàæ� êîíêðåòèçèðîâàò� îïòèìàëüíî� ïîâåäåíè� èç-ç� áîëüøîã� ÷èñë� âîçìîæíû� ñòðàòåãèé.
Äë� ðåøåíè� äèíàìè÷åñêè� èã� � êîíå÷íû� ÷èñëî� èãðîêî� ÷àñò� óäîáí� èñïîëüçîâàò� ïîçèöèîííî� ïðåäñòàâëåíè� èãðû. Íàèáîëå� ïðîñòû� êëàññî� ïîçèöèîííû� èã� ÿâëÿåòñ� êëàñ� êîíå÷íîøàãîâû� ïîçèöèîííû� èã� � ïîëíî� èíôîðìàöèåé. � òàêî� èãð� í� êàæäî� øàã� èãð� äåëàå� õî� ëèø� îäè� èãðîê, èìåþùè� ïîëíó� èíôîðìàöè� � òåêóùå� ñîñòîÿíèè, âñå� ïðîèñõîäÿùè� äåéñòâèÿ� � îáùå� ñòðóêòóð� èãðû. Ýò� ïðåäïîëîæåíè� îáû÷í� õàðàêòåðèçóåòñ� êà� ïîëíà� èíôîðìàöèÿ. Õîðîø� èçâåñòíûì� ïðèìåðàì� òàêè� èã� ÿâëÿþòñ� øàøê� � øàõìàòû. Ìíîãîøàãîâû� àíòàãîíèñòè÷åñêè� èãð� � ïîëíî� èíôîðìàöèå� ðàññìàòðèâàëèñ� � 8. � ýòî� ïàðàãðàô� áóäó� ïîëó÷åí� áîëå� îáùè� ðåçóëüòàòû.
Íàïîìíè� ïðèìå� 9.1 âçàèìîäåéñòâè� ïðîäàâö� (èãðîê� 1) � ïîêóïàòåë� (èãðîê� 2). � ïðîäàâö� äâ� ñòðàòåãèè: "÷åñòíîñòü"� "îáìàí". � ïîêóïàòåë� òàêæ� äâ� ñòðàòåãèè: "ïîâåðèòü"� "ïðîâåðèòü". Ìàòðèö� âûèãðûøå� èãðîêî� èìåþ� âè� A = ÷åñò� îáìà� ïî� 01 ïðî� 0 ,−1 B = ÷åñò� îáìà� ïî� 0 −1ïðî� −1/2 .1/2 Ðàññìîòðè� äèíàìè÷åñêó� ìîäèôèêàöè� èãðû: ïóñò� ïîêóïàòåë� ñïîñîáå� çàìåòèòü, îáâåøèâàå� åã� ïðîäàâå� èë� íåò, ò.å. î� âûáèðàå� ñâî� 145ÃËÀÂ� III. ÈÃÐ� ÌÍÎÃÈ� ËÈ�âàðèàí� ïîâåäåíèÿ, çíà� ïîâåäåíè� ïðîäàâöà. Ñîîòâåòñòâóþùà� ñõåì� èçîáðàæåí� í� ðèñ. 13.1.
1ïî� b(0, 0) � HHHH÷åñò� îáìà� HHH2� H2� � ïðî� @@ ïðî� ïî� @@@@� @@@b@ �b(0, −1/2) (1, −1) (−1, 1/2) Ðèñ. 13.1 Èíòóèòèâí� ïîíÿòíî, ÷ò� ðàöèîíàëüíû� ïîâåäåíèå� ïîêóïàòåë� ÿâëÿåòñ� âûáî� îïòèìàëüíîã� îòâåòà, âûäåëåííîã� í� ðèñóíê� æèðíûì� ëèíèÿìè. � ñâî� î÷åðåäü, ïðîäàâå� ìîæå� âûáðàò� îïòèìàëüíó� ñòðàòåãèþ, çíà� ðåàêöè� ïîêóïàòåëÿ. Íèæ� äàåòñ� îáîáùåíè� ýòîã� ìåòîä� ðåøåíè� äë� ëþáî� èãð� � ïîëíî� èíôîðìàöèåé. Ïðèâåäå� ñîîòâåòñòâóþùè� ôîðìàëüíû� îïðåäåëåíèÿ. Îïðåäåëåíèå.
Êîíå÷íû� äåðåâîì, èë� îðèåíòèðîâàííû� ãðàôî� áå� öèêëîâ, íàçûâàåòñ� ïàð� (X, σ), ãä� X − êîíå÷íî� ìíîæåñòâ� âåðøèí, èë� ïîçèöèé, � îòîáðàæåíè� σ : X → X ñîïîñòàâëÿå� êàæäî� âåðøèíåå� áëèæàéøåã� ïðåäøåñòâåííèêà, ïðè÷å� • ñóùåñòâóå� åäèíñòâåííà� íà÷àëüíà� âåðøèí� x0 , òàêàÿ, ÷ò� σ(x0 ) = x0 ; • ñóùåñòâóå� öåëî� l ≥ 0 , ÷ò� σ l (x) = x0 äë� âñå� x ∈ X ; íàèìåíüøå� òàêî� l íàçûâàåòñ� äëèíî� äåðåâ� (X, σ). Ëþáà� âåðøèí� x, äë� êîòîðî� σ −1 (x) = ∅, íàçûâàåòñ� ôèíàëüíî� âåðøèíî� äåðåâ� (X, σ), � ìíîæåñòâ� âñå� òàêè� âåðøè� îáîçíà÷àåòñ� ÷åðå� T.
Äë� íåôèíàëüíû� âåðøè� x ìíîæåñòâ� σ −1 (x) ñîñòîè� è� ïðååìíèêî� x, ò.å. è� ñëåäóþùè� ç� x âåðøèí. Ðåáð� äåðåâ� (X, σ) íàçûâàþòñ� àëüòåðíàòèâàìè. Îïðåäåëåíèå. Ïîçèöèîííî� èãðî� � ïîëíî� èíôîðìàöèå� íàçûâàåòñ� ñëåäóþùà� ñîâîêóïíîñòü: D a G = A, (X, σ), ua (x), x ∈ T, a ∈ A; X\T = X ∪ X 0 , � a∈A 0 0� −1∀ x ∈ X ∃ p(x |x), x ∈ σ (x) , ãä� • A − ìíîæåñòâ� èãðîêîâ; 146 13. Ïîçèöèîííû� èãð� � ïîëíî� èíôîðìàöèå�• (X, σ) − êîíå÷íî� äåðåâ� � íà÷àëüíî� âåðøèíî� x0 � ìíîæåñòâî� T ôèíàëüíû� âåðøèí; • R = {X a , a ∈ A, X 0 } − ðàçáèåíè� ìíîæåñòâ� X\T í� ïîïàðí� íåïåðåñåêàþùèåñ� ïîäìíîæåñòâà; • X a − ìíîæåñòâ� ïîçèöèé, � êîòîðû� äåëàå� õî� èãðî� a ∈ A; X a íàçûâàåòñ� ìíîæåñòâî� ëè÷íû� ïîçèöè� èãðîê� a.
• X 0 − ìíîæåñòâ� ïîçèöèé, � êîòîðû� "äåëàå� õîä"ñëó÷àé; • ua : T → E 1 − ôóíêöè� âûèãðûø� èãðîê� a;• äë� êàæäîã� x ∈ X 0 çàäàí� âåðîÿòíîñò�Pp(x0 |x) > 0,p(x0 |x) = 1,x0 ∈σ −1 (x) � −1ïåðåõîä� è� ïîçèöè� � � ïîçèöè� x ∈ σ(x). Ðàçáèåíè� R îïðåäåëÿåò, êàêî� èãðî� (èë� ñëó÷àé, åñë� x ∈ X 0 ) õîäè� � êàæäî� êîíêðåòíî� íåôèíàëüíî� âåðøèí� x. Åñë� x0 ∈ X a , a ∈ A, ò� èãð� íà÷èíàåòñ� � òîãî, ÷ò� èãðî� a äîëæå� âûáðàò� ñëåäóþùó� ç� x0 âåðøèíó, ñêàæåì, x1 ∈ σ −1 (x0 ).
Åñë� x1 − ôèíàëüíà� âåðøèíà, ò� èãð� îêîí÷åí� � âûèãðûø� èãðîêî� ñóò� ua (x1 ), a ∈ A. Åñë� x1 − íåôèíàëüíà� âåðøèíà, ò� èãðî� b, äë� êîòîðîã� x1 ∈ X b , èìåå� ïðàâ� õîä� � âûáèðàå� ñëåäóþùó� ç� x1 âåðøèíó, ñêàæåì, x2 ∈ σ −1 (x1 ) � ò.ä. Åñë� � êàêîé-ò� ìîìåí� ì� ïîïàäàå� � âåðøèí� x ∈ X 0 (� êîòîðî� õîäè� ñëó÷àé), ò� � âåðîÿòíîñòü� p(x0 |x) ì� ïåðåõîäè� � îäíî� è� âåðøè� x� ∈ σ −1 (x), � êîòîðî� ïðîäîëæàå� äåéñòâîâàò� ñïîñîáîì, îïèñàííû� âûøå.
Åñë� èãðî� a � âåðøèí� x ∈ X a âûáèðàå� âåðøèí� x� ∈ σ −1 (x), ò� òàêæ� áóäå� ãîâîðèòü, ÷ò� î� âûáèðàå� ñîîòâåòñòâóþùó� àëüòåðíàòèâ� − ðåáð� äåðåâà, ñîåäèíÿþùåã� âåðøèí� x � x0 . 1bPPP× ×PPb2 @× @× PPPP b0PPPPPP b1b3@@× × @× × × @× Ðèñ. 13.2 Í� ðèñ. 13.2 îòìå÷åííû� êðåñòèêàì� âåðøèí� ÿâëÿþòñ� ôèíàëüíûìè.
� âåðøèí� 0 õîäè� ñëó÷àé, � îñòàëüíû� − èãðîê� 1, 2 � 3. ×òîá� îïðåäåëèò� èñõî� ïîçèöèîííî� èãðû, äë� êàæäî� ïîçèöè� ëþ147ÃËÀÂ� III. ÈÃÐ� ÌÍÎÃÈ� ËÈ�áîã� èãðîê� äîëæí� áûò� óêàçàí� âåðøèíà, êóä� î� ïåðåéäåò. Ââåäå� äë� ýòîã� íåñêîëüê� ïîíÿòèé. Îïðåäåëåíèå. Ñòðàòåãèå� èãðîê� a ∈ A íàçûâàåòñ� îòîáðàæåíè� µa , îïðåäåëÿþùå� äë� êàæäî� âåðøèí� x ∈ X a ïîçèöèþ, � êîòîðó� î� ïåðåéäåò: ∀ x ∈ X a µa (x) ∈ σ −1 (x).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
