[учебник] Введение в теорию игр (с приложениями к экономике). Васин, Морозов (2003) (1186146), страница 25
Текст из файла (страница 25)
ÈÃÐÛ ÌÍÎÃÈÕ ËÈÖÏåðåéäåì ê äîìèíèðîâàíèþ ñìåøàííûìè ñòðàòåãèÿìè. Ïóñòü ñìåøàííàÿ ñòðàòåãèÿ π 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, ò.å. èç ñëåäóþùèõ çà x âåðøèí. Ðåáðà äåðåâà (X, σ) íàçûâàþòñÿàëüòåðíàòèâàìè.Îïðåäåëåíèå. Ïîçèöèîííîé èãðîé ñ ïîëíîé èíôîðìàöèåé íàçûâàåòñÿñëåäóþùàÿ ñîâîêóïíîñòü:DS aG = A, (X, σ), ua (x), x ∈ T, a ∈ A; X\T =X ∪ X 0,E a∈A000−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) = 1,p(x0 |x) > 0,x0 ∈σ −1 (x)0−1ïåðåõîäà èç ïîçèöèè x â ïîçèöèè 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) ìû ïåðåõîäèì ê îäíîé èç âåðøèíx0 ∈ σ −1 (x), â êîòîðîé ïðîäîëæàåì äåéñòâîâàòü ñïîñîáîì, îïèñàííûìâûøå.Åñëè èãðîê a â âåðøèíå x ∈ X a âûáèðàåò âåðøèíó x0 ∈ σ −1 (x), òîòàêæå áóäåì ãîâîðèòü, ÷òî îí âûáèðàåò ñîîòâåòñòâóþùóþ àëüòåðíàòèâó− ðåáðî äåðåâà, ñîåäèíÿþùåãî âåðøèíû x è x0 .1bPPPPPP××b2@× @×PP 0P bPPPPP 13Pbb@@× × @× × × @×Ðèñ.
13.2Íà ðèñ. 13.2 îòìå÷åííûå êðåñòèêàìè âåðøèíû ÿâëÿþòñÿ ôèíàëüíûìè.  âåðøèíå 0 õîäèò ñëó÷àé, â îñòàëüíûõ − èãðîêè 1, 2 è 3.×òîáû îïðåäåëèòü èñõîä ïîçèöèîííîé èãðû, äëÿ êàæäîé ïîçèöèè ëþ147ÃËÀÂÀ III. ÈÃÐÛ ÌÍÎÃÈÕ ËÈÖáîãî èãðîêà äîëæíà áûòü óêàçàíà âåðøèíà, êóäà îí ïåðåéäåò. Ââåäåì äëÿýòîãî íåñêîëüêî ïîíÿòèé.Îïðåäåëåíèå. Ñòðàòåãèåé èãðîêà a ∈ A íàçûâàåòñÿ îòîáðàæåíèå µa ,îïðåäåëÿþùåå äëÿ êàæäîé âåðøèíû x ∈ X a ïîçèöèþ, â êîòîðóþ îí ïåðåéäåò: ∀ x ∈ X a µa (x) ∈ σ −1 (x). Ìíîæåñòâî âñåõ ñòðàòåãèé èãðîêà aîáîçíà÷èì ÷åðåç {µa }.Íàáîð òàêèõ ñòðàòåãèé µ = (µa , a ∈ A) íàçûâàåòñÿ ñèòóàöèåé. Äëÿêàæäîãî x ∈ X äëÿ äàííîé ñèòóàöèè µ ìîæíî îïðåäåëèòü âåðîÿòíîñòüp(x|µ) ïåðåõîäà â ïîçèöèþ x. Ïðè ýòîì p(x0 |µ) = 1 − èãðà âñåãäà íà÷èíàåòñÿ ñ ïîçèöèè x0 . îáùåì ñëó÷àå âåðîÿòíîñòü ïîïàñòü â ïîçèöèþ x, íåïîñðåäñòâåííîñëåäóþùóþ çà ïîçèöèåé èãðîêà σ(x) ∈ X a , a ∈ A, îïðåäåëÿåòñÿ ïî ôîðìóëå p(x|µ) = p(σ(x)|µ)p(x|σ(x),( µ), ãäå1, åñëè µa (σ(x)) = x,p(x|σ(x), µ) =0â ïðîòèâíîì ñëó÷àå.0Åñëè æå σ(x) ∈ X − ïîçèöèÿ ñëó÷àÿ, òî âåðîÿòíîñòü p(x|σ(x), µ) =p(x|σ(x)) çàäàíà óñëîâèÿìè èãðû.
Òàêèì îáðàçîì, äëÿ ëþáîé ñèòóàöèèµ äëÿ êàæäîãî èãðîêà a ∈ A îïðåäåëåíî ñðåäíåå çíà÷åíèå ôóíêöèè âûèãðûøàPua (µ) = E(ua (x)|µ) =p(x|µ)ua (x).x∈TÓïðàæíåíèå 13.1. Íà ðèñ. 13.3 ðåáðà äåðåâà, ñîîòâåòñòâóþùèå ñèòóàöèè µ, âûäåëåíû æèðíûìè ëèíèÿìè, à ôèíàëüíûå ïîçèöèè ïðîíóìåðîâàíû îò 1 äî 6, ò.å.
T = {1, ..., 6}. Íàéäèòå âåðîÿòíîñòèp(x|µ), x ∈ T.0bHH3/41bHH b2@@@ 12b@×@b×34@@@×@×××1/41526Ðèñ. 13.3DEaaÎïðåäåëåíèå. Èãðà Γ(G) = A, {µ }, u (µ), a ∈ A íàçûâàåòñÿ íîðìàëüíîé ôîðìîé ïîçèöèîííîé èãðû G.Äëÿ ëþáîé âåðøèíû z ∈ X ìîæíî ðàññìîòðåòü ïîçèöèîííóþ ïîäû148 13. Ïîçèöèîííûå èãðû ñ ïîëíîé èíôîðìàöèåéãðó, íà÷èíàþùóþñÿ èç ýòîé òî÷êè:DEGz = A, (Xz , σz ), Xz0 , Xza , uaz (x), a ∈ A ,ãäå• Xz = {x |ñóùåñòâóåò òàêîå öåëîå l ≥ 0, ÷òî σ l (x) = z};• σz åñòü ñóæåíèå îòîáðàæåíèÿ σ íà Xz è σz (z) = z ;• Xza = X a ∩ Xz , a ∈ A, Xz0 = X 0 ∩ Xz ;• uaz (x) = ua (x), åñëè x ∈ Xz ∩ T .Ïóñòü µ = (µa , a ∈ A) − ñèòóàöèÿ â èãðå Γ(G).
Îáîçíà÷èì ÷åðåç µz =(µaz , a ∈ A) − åå ñóæåíèå íà Xz , à ÷åðåç ua (µz ) − çíà÷åíèå âûèãðûøàèãðîêà a â ñèòóàöèèµz . Òàêèì îáðàçîì,DE äëÿ ëþáîãî z ∈ X îïðåäåëåíàaaèãðà Γ(Gz ) = A, {µz }, uz (µz ), a ∈ A − íîðìàëüíàÿ ôîðìà äëÿ èãðûGz .Óïðàæíåíèå 13.2. Íà ðèñ. 13.4 èçîáðàæåíî äåðåâî èãðû G.  ôèíàëüíûõ ïîçèöèÿõ óêàçàíû âåêòîðû âûèãðûøåé èãðîêîâ u(x) = (u1 (x), u2 (x))èëè èñõîäû èãðû.0bHH3/41bHH b2z@@ 12b@×@b×(−2,2)(1,−3)@@@×@×××1/4(−1,1)(3,−1)(1,−2)(−1,2)Ðèñ.
13.4Çàïèøèòå íîðìàëüíóþ ôîðìó äàííîé èãðû G è ïîäûãðû Gz , ñîîòâåòñòâóþùåé ñëó÷àéíîìó âûáîðó ïðàâîé àëüòåðíàòèâû.Îïðåäåëåíèå. Ñèòóàöèÿ µ = (µa , a ∈ A) íàçûâàåòñÿ ñîâåðøåííûìïîäûãðîâûì ðàâíîâåñèåì, èãðû G, åñëè äëÿ êàæäîé âåðøèíû z ∈ X ñèòóàöèÿ µz = (µaz , a ∈ A), ãäå µaz − ñóæåíèå ñòðàòåãèè µa íà ïîäûãðóΓ(Gz ), ÿâëÿåòñÿ ðàâíîâåñèåì ïî Íýøó â èãðå Γ(Gz ).Àëãîðèòì îïðåäåëåíèÿ ñîâåðøåííîãî ïîäûãðîâîãîðàâíîâåñèÿ (àëãîðèòì Êóíà)Àëãîðèòì Êóíà ñîñòîèò èç ïîñëåäîâàòåëüíûõ ðåäóêöèé èãðû G.Øàã 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
