Введение в теорию игр (сторонняя методичка) (1184510), страница 26
Текст из файла (страница 26)
èç ñëåäóþùèõ çà 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. Ðàññìîòðèì ìíîæåñòâî Z1 ïðåäôèíàëüíûõ âåðøèí, äëÿ êîòîðûõ âñå ïîñëåäóþùèå âåðøèíû ÿâëÿþòñÿ ôèíàëüíûìè: Z1 = {x | σ −1 (x) ⊆T }.
Äëÿ êàæäîé âåðøèíû x ∈ Z1 äåéñòâóåì ñëåäóþùèì îáðàçîì.149ÃËÀÂÀ III. ÈÃÐÛ ÌÍÎÃÈÕ ËÈÖ1) Åñëè â äàííîé âåðøèíå õîäèò èãðîê a ∈ A (x ∈ Z1 ∩X 0 ), òî íàõîäèìåãî íàèëó÷øèé âûáîð â ýòîé âåðøèíåµa (x) ∈ Arg maxua (y)−1y∈σ(x)è äîîïðåäåëÿåì âåêòîð âûèãðûøåé èãðîêîâ â âåðøèíådefu(x) = (ub (x), b ∈ A) = (ub (µa (x)), b ∈ A).2) Åñëè â äàííîé âåðøèíå õîäèò ñëó÷àé (x ∈ Z1 ∩X 0 ), òî ïðèïèñûâàåìýòîé âåðøèíå ñðåäíåå çíà÷åíèå âåêòîðà âûèãðûøåé ñðåäè âîçìîæíûõàëüòåðíàòèâPu(x) =p(y|x)u(y).y∈σ −1 (x) ðåçóëüòàòå ïîëó÷èëè ðåäóöèðîâàííóþ èãðó ñ ìíîæåñòâîì ôèíàëüíûõ âåðøèí Z1 .Øàã 2. Äëÿ ýòîé èãðû àíàëîãè÷íî øàãó 1 íàõîäèì ìíîæåñòâî íåôèíàëüíûõ âåðøèí Z2 , äëÿ êîòîðûõ âñå ïîñëåäóþùèå âåðøèíû â íîâîìäåðåâå ÿâëÿþòñÿ ôèíàëüíûìè: Z2 = {x | σ −1 (x) ⊂ T ∪ Z1 }. Äëÿ êàæäîé âåðøèíû x ýòîãî ìíîæåñòâà àíàëîãè÷íî ïóíêòàì 1) è 2) îïðåäåëÿåìâûáîðû µa (x) ïðè x ∈ X a è âåêòîð âûèãðûøåé u(x).Äàëåå àíàëîãè÷íî ïðîäîëæàåì ýòîò ïðîöåññ äëÿ ìíîæåñòâZ3 = {x | σ −1 (x) ⊂ T ∪ Z1 ∪ Z2 },Z4 = {x | σ −1 (x) ⊂ T ∪ Z1 ∪ Z2 ∪ Z3 }è ò.ä., ïîêà î÷åðåäíîå ìíîæåñòâî Zl íå áóäåò ñîñòîÿòü òîëüêî èç íà÷àëüíîé âåðøèíû x0 .
Ïðè ýòîì ïîëó÷åííàÿ ñèòóàöèÿ µ = (µa , a ∈ A) áóäåòñîâåðøåííûì ïîäûãðîâûì ðàâíîâåñèåì èñõîäíîé èãðû G. Òàêèì îáðàçîì, äîêàçàíî ñëåäóþùåå óòâåðæäåíèå.Òåîðåìà 13.1.  ëþáîé êîíå÷íîé ïîçèöèîííîé èãðå ñ ïîëíîé èíôîð-ìàöèåé ñóùåñòâóåò ñîâåðøåííîå ïîäûãðîâîå ðàâíîâåñèå. Ñîîòâåòñòâóþùèå ñòðàòåãèè è âûèãðûøè èãðîêîâ çàäàþòñÿ àëãîðèòìîì Êóíà.Óïðàæíåíèå 13.3. Íàéòè ñîâåðøåííîå ïîäûãðîâîå ðàâíîâåñèå â ïîçèöèîííîé èãðå G, èçîáðàæåííîé íà ðèñ. 13.4.Ïðèìåð 13.1. Ìîäåëü âíóòðèâåäîìñòâåííîãî ýêîëîãè÷åñêîãî êîíòðîëÿ. Ïóñòü ïåðâûé èãðîê − ïðåäïðèÿòèå, èìåþùåå äâå ñòðàòåãèè: 1 −ïðèìåíÿòü ýêîëîãè÷åñêè ÷èñòûé ñïîñîá ïðîèçâîäñòâà è 2 − ïðèìåíÿòü"ãðÿçíûé", íî áîëåå äåøåâûé ñïîñîá.
Âòîðîé èãðîê − êîíòðîëèðóþùèéîðãàí, ïðèíàäëåæàùèé òîìó æå âåäîìñòâó, ÷òî è ïðåäïðèÿòèå. Îí èìååòäâå ñòðàòåãèè: 1 − øòðàôîâàòü çà ïðèìåíåíèå "ãðÿçíîãî"ñïîñîáà ïðîèçâîäñòâà, 2 − ïðîïóñêàòü ýêîëîãè÷åñêîå íàðóøåíèå ("çàêðûâàòü ãëàçà").150 13. Ïîçèöèîííûå èãðû ñ ïîëíîé èíôîðìàöèåé1b÷èñò @@@ ãðÿç@@ b2×@(1, 1)@ ïðîïøòð@@@××(−5, −2)(2, −1)Ðèñ. 13.5Âíà÷àëå õîäèò ïåðâûé èãðîê, à çàòåì − âòîðîé, çíàÿ âûáîð ïåðâîãî.Íà ðèñ. 13.5 èçîáðàæåíî äåðåâî èãðû.  ôèíàëüíûõ âåðøèíàõ äåðåâàóêàçàíû óñëîâíûå âûèãðûøè èãðîêîâ. Íàïðèìåð, åñëè îáà èãðîêà ïðèìåíÿþò âòîðûå ñòðàòåãèè, òî ïåðâûé âûèãðàåò 2, à âòîðîé ïðîèãðàåò 1,ïîñêîëüêó ïðè ýòîì ïðîèçîøëî çàãðÿçíåíèå îêðóæàþùåé ñðåäû.Ëåãêî âèäåòü, ÷òî ñîâåðøåííûì ïîäûãðîâûì ðàâíîâåñèåì â äàííîìñëó÷àå ÿâëÿåòñÿ íàáîð µ = (2, 2), ïðèâîäÿùèé ê èñõîäó (2, −1).
Îäíàêî,â ýòîé èãðå ñóùåñòâóåò ðàâíîâåñèå ïî Íýøó, áîëåå âûãîäíîå äëÿ âòîðîãîèãðîêà : îí ìîæåò èñïîëüçîâàòü "ñòðàòåãèþ íàêàçàíèÿ"(ñì. 11.) è ïðèâûáîðå ïåðâûì èãðîêîì âòîðîé ñòðàòåãèè âûáèðàòü ñòðàòåãèþ "øòðàôîâàòü", ÷òî ïðèâîäèò ê èñõîäó (−5, −2) (íåñìîòðÿ íà òî, ÷òî ýòî åìó íå âûãîäíî). Òîãäà ïåðâûé èãðîê, ÷òîáû íå ïîëó÷èòü −5, ïðåäïî÷òåò âûáðàòüïåðâóþ ñòðàòåãèþ.
 èòîãå ïîëó÷èòñÿ ñèòóàöèÿ ðàâíîâåñèÿ µ = (1, 1),êîòîðàÿ íå ÿâëÿåòñÿ ñîâåðøåííûì ïîäûãðîâûì ðàâíîâåñèåì. Îòìåòèì,÷òî ñèòóàöèþ (2, 2) ìîæíî òàêæå ïîëó÷èòü èñêëþ÷åíèåì äîìèíèðóåìûõñòðàòåãèé â èãðå Γ(G) ñ ìàòðèöàìèøòð ïðîïøòð ïðîïãðÿç11ãðÿç11A=, B=.÷èñò −52÷èñò −2−1Íåòðóäíî âèäåòü, ÷òî ñòðàòåãèÿ 1 âòîðîãî èãðîêà ñëàáî äîìèíèðóåòñÿñòðàòåãèåé 2. Åñëè åå âû÷åðêíóòü, òî ïîëó÷àåòñÿ èãðà, ãäå ñòðàòåãèÿ 2ïåðâîãî èãðîêà ñòðîãî äîìèíèðóåò ñòðàòåãèþ 1.
 ðåçóëüòàòå èñêëþ÷åíèÿ äîìèíèðóåìûõ ñòðàòåãèé îñòàíåòñÿ ñèòóàöèÿ (2,2), êîòîðàÿ îáû÷íîè âîçíèêàåò ïðè âíóòðèâåäîìñòâåííîì êîíòðîëå.  ýòîì ïðèìåðå èãðàΓ(G) ðàçðåøèìà ïî äîìèíèðîâàíèþ.Âîîáùå äëÿ èãð ñ ïîëíîé èíôîðìàöèåé òèïè÷íà ñèòóàöèÿ, êîãäà ñîâåðøåííîå ïîäûãðîâîå ðàâíîâåñèå îäíî, à ïðî÷èõ ðàâíîâåñèé ïî Íýøó,ñâÿçàííûõ ñî ñòðàòåãèÿìè íàêàçàíèÿ, ìíîãî.151ÃËÀÂÀ III. ÈÃÐÛ ÌÍÎÃÈÕ ËÈÖÐàññìîòðèì ñëåäóþùåå âîçìóùåíèå èãðû G: ïóñòü â êàæäîé ïîçèöèèñ íåêîòîðîé äîñòàòî÷íî ìàëîé âåðîÿòíîñòüþ ε > 0 âñå èãðîêè îøèáàþòñÿ. êàæäîé ïîçèöèè èãðîêà a ñ âåðîÿòíîñòüþ 1 − ε ðåàëèçóåòñÿ íàìå÷åííàÿ èì àëüòåðíàòèâà, à ñ âåðîÿòíîñòüþ ε ïðîèñõîäèò õîä ñëó÷àÿ è ðàâíîâåðîÿòíî ðåàëèçóåòñÿ ëþáàÿ äðóãàÿ àëüòåðíàòèâà. Îáîçíà÷èì ÷åðåçGε óêàçàííóþ âîçìóùåííóþ èãðó. Î÷åâèäíî, ÷òî ìíîæåñòâà ñòðàòåãèéîñòàþòñÿ òàêèìè æå, êàê â èãðå G, è ëþáàÿ âåðøèíà èñõîäíîé èãðû ââîçìóùåííîé èãðå Gε ðåàëèçóåòñÿ ñ ïîëîæèòåëüíîé âåðîÿòíîñòüþ ïðèëþáûõ ñòðàòåãèÿõ èãðîêîâ.Òåîðåìà 13.2.
Ïóñòü â èñõîäíîé èãðå G ñóùåñòâóåò åäèíñòâåííîå ñîâåðøåííîå ïîäûãðîâîå ðàâíîâåñèå. Òîãäà äëÿ ëþáîãî äîñòàòî÷íî ìàëîãîε > 0 â èãðå Gε ñóùåñòâóåò åäèíñòâåííîå ðàâíîâåñèå ïî Íýøó, ñîâïàäàþùåå ñ ñîâåðøåííûì ïîäûãðîâûì ðàâíîâåñèåì èñõîäíîé èãðû.Äîêàçàòåëüñòâî ïîâòîðÿåò ñõåìó àëãîðèòìà Êóíà.  ëþáîé ïðåäôèíàëüíîé ïîçèöèè x ∈ Z1 ∩ X a ñóùåñòâóåò åäèíñòâåííûé íàèëó÷øèéâûáîð µa (x) èãðîêà a, îòâå÷àþùèé ñîâåðøåííîìó ïîäûãðîâîìó ðàâíîâåñèþ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
