Введение в теорию игр (сторонняя методичка) (1184510), страница 25
Текст из файла (страница 25)
Èñõîäÿ èç ýòîãî, èãðîê 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. ÈÃÐÛ ÌÍÎÃÈÕ ËÈÖÏåðåéäåì ê äîìèíèðîâàíèþ ñìåøàííûìè ñòðàòåãèÿìè. Ïóñòü ñìåøàííàÿ ñòðàòåãèÿ π a ñòðîãî äîìèíèðóåò ñòðàòåãèþ g a , ò.å. r = 1.
Òîãäà äëÿ ëþáîé ñèòóàöèè s(t) íàéäåòñÿ ÷èñòàÿ ñòðàòåãèÿ sa , äëÿ êîòîðîéπsaa > 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 ìîæíî ðàññìàòðèâàòü ðåäóöèðîâàííóþ èãðó ñ ìíîæåñòâàìèñòðàòåãèé S2b ∀ b ∈ A.
Äàëåå ïðîâîäÿòñÿ ðàññóæäåíèÿ ïî èíäóêöèè.Ïóñòü òåïåðü ñòðàòåãèÿ g a ñòðîãî äîìèíèðóåòñÿ ñìåøàííîé ñòðàòåãèaåéäëÿ ëþáîé ñèòóàöèè s(τ ) âûïîëíåíî íåðàâåíñòâîP πa . Òîãäàaπsa u (s(τ )||sa ) > ua (s(τ )||g a ), à îòñþäàsaXsaπsaaXλat,τ ua (s(τ )||sa ) >τ ≤tXλat,τ ua (s(τ )||g a ).τ ≤tÑëåäîâàòåëüíî,íàéäåòñÿñòðàòåãèÿ sa , äëÿ êîòîðîé πsaa > 0 èPP òàêàÿaaaaaaaaτ ≤t λt,τ u (s(τ )||s ) >τ ≤t λt,τ u (s(τ )||g ). Ïîýòîìó s (t + 1) 6= g ïðèt ≥ 1, à ïðè t ≥ T + 1 ñòðàòåãèÿ g a íå âëèÿåò íà âûáîðû äðóãèõ èãðîêîâ.Ïîýòîìó, íà÷èíàÿ ñ øàãà T + 1, ìîæíî ðàññìàòðèâàòü ðåäóöèðîâàííóþèãðó ñ ìíîæåñòâàìè ñòðàòåãèé S2b ∀ b ∈ A. Äàëåå ïðîâîäÿòñÿ ðàññóæäåíèÿ ïî èíäóêöèè.Óòâåðæäåíèå 12.2. Ïóñòü òðàåêòîðèÿ {s(t)} ñîîòâåòñòâóåò íàáîðóàäàïòèâíûõ ïðàâèë pa , a ∈ A è s(t) ≡ s ïðèðàâíîâåñèå ïî Íýøó èãðû Γ.Äîêàçàòåëüñòâî.
Èç óñëîâèÿ âûòåêàåò, ÷òît ≥ t. Òîãäà s −lim pa (sA\{a} )|ht ) = 0t→∞ïðè ëþáûõ sA\{a} 6= (sb , b ∈ A\{a}). Ñëåäîâàòåëüíî,lim pa (sb , b ∈ A\{a})|ht ) = 1 ∀ a ∈ A.t→∞(12.2)Ïðåäïîëîæèì, ÷òî s íå ÿâëÿåòñÿ ñèòóàöèåé ðàâíîâåñèÿ. Òîãäà íàéäåòñÿòàêàÿ ñòðàòåãèÿ sa íåêîòîðîãî èãðîêà a, ÷òî ua (s||sa ) > ua (s). Ñ ó÷åòîì144 13. Ïîçèöèîííûå èãðû ñ ïîëíîé èíôîðìàöèåé(12.2) ïðè äîñòàòî÷íî áîëüøîì tXXpa (sA\{a} | ht )ua (sA\{a} , sa ) >sA\{a}pa (sA\{a} | ht )ua (sA\{a} , sa ).sA\{a}Îòñþäà sa (t + 1) 6= sa , ÷òî ïðîòèâîðå÷èò óñëîâèþ.Áîëüøîé èíòåðåñ ïðåäñòàâëÿþò îáðàòíûå ðåçóëüòàòû − î ñõîäèìîñòèàäàïòèâíûõ ïðîöåññîâ ê ðàâíîâåñèÿì ïî Íýøó (ñì. òåîðåìû 5.3 è 10.5). 13.Ïîçèöèîííûå èãðû ñ ïîëíîé èíôîðìàöèåéÌíîãèå ðåàëüíûå êîíôëèêòíûå ñèòóàöèè èìåþò äëèòåëüíûé õàðàêòåð.
Èõ ó÷àñòíèêè äåéñòâóþò íåîäíîêðàòíî è ñ ó÷åòîì èíôîðìàöèè îïðåäøåñòâóþùåì ðàçâèòèè êîíôëèêòà. Äëÿ ñîîòâåòñòâóþùèõ ìîäåëåéîáùèå òåîðåìû ñóùåñòâîâàíèÿ ðåøåíèÿ äëÿ èãð â íîðìàëüíîé ôîðìå íåïîçâîëÿþò íàõîäèòü èëè äàæå êîíêðåòèçèðîâàòü îïòèìàëüíîå ïîâåäåíèåèç-çà áîëüøîãî ÷èñëà âîçìîæíûõ ñòðàòåãèé. Äëÿ ðåøåíèÿ äèíàìè÷åñêèõèãð ñ êîíå÷íûì ÷èñëîì èãðîêîâ ÷àñòî óäîáíî èñïîëüçîâàòü ïîçèöèîííîåïðåäñòàâëåíèå èãðû. Íàèáîëåå ïðîñòûì êëàññîì ïîçèöèîííûõ èãð ÿâëÿåòñÿ êëàññ êîíå÷íîøàãîâûõ ïîçèöèîííûõ èãð ñ ïîëíîé èíôîðìàöèåé.
Âòàêîé èãðå íà êàæäîì øàãå èãðû äåëàåò õîä ëèøü îäèí èãðîê, èìåþùèéïîëíóþ èíôîðìàöèþ î òåêóùåì ñîñòîÿíèè, âñåõ ïðîèñõîäÿùèõ äåéñòâèÿõ è îáùåé ñòðóêòóðå èãðû. Ýòî ïðåäïîëîæåíèå îáû÷íî õàðàêòåðèçóåòñÿ êàê ïîëíàÿ èíôîðìàöèÿ. Õîðîøî èçâåñòíûìè ïðèìåðàìè òàêèõ èãðÿâëÿþòñÿ øàøêè è øàõìàòû. Ìíîãîøàãîâûå àíòàãîíèñòè÷åñêèå èãðû ñïîëíîé èíôîðìàöèåé ðàññìàòðèâàëèñü â 8.  ýòîì ïàðàãðàôå áóäóòïîëó÷åíû áîëåå îáùèå ðåçóëüòàòû.Íàïîìíèì ïðèìåð 9.1 âçàèìîäåéñòâèÿ ïðîäàâöà (èãðîêà 1) è ïîêóïàòåëÿ (èãðîêà 2). Ó ïðîäàâöà äâå ñòðàòåãèè: "÷åñòíîñòü"è "îáìàí".
Ó ïîêóïàòåëÿ òàêæå äâå ñòðàòåãèè: "ïîâåðèòü"è "ïðîâåðèòü". Ìàòðèöû âûèãðûøåé èãðîêîâ èìåþò âèäA=÷åñòíîáìàíïîâ01ïðîâ0,−1B=÷åñòíîáìàíïîâ0−1ïðîâ−1/2.1/2Ðàññìîòðèì äèíàìè÷åñêóþ ìîäèôèêàöèþ èãðû: ïóñòü ïîêóïàòåëü ñïîñîáåí çàìåòèòü, îáâåøèâàåò åãî ïðîäàâåö èëè íåò, ò.å. îí âûáèðàåò ñâîé145ÃËÀÂÀ III. ÈÃÐÛ ÌÍÎÃÈÕ ËÈÖâàðèàíò ïîâåäåíèÿ, çíàÿ ïîâåäåíèå ïðîäàâöà. Ñîîòâåòñòâóþùàÿ ñõåìàèçîáðàæåíà íà ðèñ. 13.1.1ïîâb(0, 0)b HHHH÷åñòíîáìàíHHH2bH2b@ ïðîâ@ ïðîâïîâ@@@@@@b@bb(1, −1)(0, −1/2)(−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, ò.å.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
