[учебник] Введение в теорию игр (с приложениями к экономике). Васин, Морозов (2003) (1186146), страница 26
Текст из файла (страница 26)
Ðàññìîòðèì ìíîæåñòâî 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, îòâå÷àþùèé ñîâåðøåííîìó ïîäûãðîâîìó ðàâíîâåñèþ.  ëþáîé ñèòóàöèè ðàâíîâåñèÿ µ̂ ïðè äîñòàòî÷íî ìàëûõ ε > 0µ̂a (x) = µa (x), ïîñêîëüêó âåðîÿòíîñòü îñóùåñòâëåíèÿ ïîçèöèè x ïîëîæèòåëüíà è ëþáîé äðóãîé âûáîð ïðèâåäåò ê ñòðîãî ìåíüøåìó âûèãðûøó.Äàëåå ðàññìàòðèâàþòñÿ âåðøèíû èç Z2 , Z3 , ..., ïðîâîäÿòñÿ àíàëîãè÷íûåðàññóæäåíèÿ ïî èíäóêöèè è äîêàçûâàåòñÿ, ÷òî µ̂ = µ.Ñëåäñòâèå.
Ïóñòü G − ïîçèöèîííàÿ èãðà, äëÿ êîòîðîé ñóùåñòâóåòåäèíñòâåííîå ñîâåðøåííîå ïîäèãðîâîå ðàâíîâåñèå µ. Òîãäà èãðà â íîðìàëüíîé ôîðìå Γ(G) ðàçðåøèìà ïî äîìèíèðîâàíèþ, à âûèãðûøè èãðîêîâ ua (µ), a ∈ A, çàäàþòñÿ àëãîðèòìîì Êóíà. ñëåäóþùåì ïðèìåðå (ðèñ. 13.6) ñîâåðøåííîå ïîäûãðîâîå ðàâíîâåñèåñòðîãî õóæå äëÿ èãðîêîâ, ÷åì äðóãàÿ ñèòóàöèÿ.1b@@×(2, 2)×(5, 5)@@ b2@@@@@×(0, 6)Ðèñ. 13.6152 14. Ïîçèöèîííûå èãðû îáùåãî âèäà 14.Ïîçèöèîííûå èãðû îáùåãî âèäàÎñíîâíîå îòëè÷èå ïîçèöèîííûõ èãð ñ íåïîëíîé èíôîðìàöèåé îò èãðñ ïîëíîé èíôîðìàöèåé ñîñòîèò â òîì, ÷òî èãðîê â ìîìåíò ïðèíÿòèÿ ðåøåíèÿ íå çíàåò òî÷íî ñîñòîÿíèå èãðû, òî åñòü íå ðàçëè÷àåò íåêîòîðûåâåðøèíû ìåæäó ñîáîé.
Îòìåòèì, ÷òî íåòî÷íàÿ èíôîðìàöèÿ î òåêóùåìñîñòîÿíèè òèïè÷íà äëÿ ðåàëüíûõ êîíôëèêòîâ. Îáùåå ïîíÿòèå ïîçèöèîííîé èãðû (ñ íåïîëíîé èíôîðìàöèåé) îòëè÷àåòñÿ îò äàííîãî âûøå îïðåäåëåíèÿ èãðû ñ ïîëíîé èíôîðìàöèåé â ñëåäóþùåì îòíîøåíèè. Äëÿ êàæäîãî èãðîêà a ââîäèòñÿ äîïîëíèòåëüíîå ðàçáèåíèå ìíîæåñòâà åãî ïîçèöèé íà èíôîðìàöèîííûå ìíîæåñòâà. Èíôîðìàöèîííîå ìíîæåñòâî − ýòîñîâîêóïíîñòü ñîñòîÿíèé ïîçèöèîííîé èãðû, êîòîðûå èãðîê íå ðàçëè÷àåòìåæäó ñîáîé. Íåîáõîäèìûì óñëîâèåì äëÿ âñåõ ïîçèöèé îäíîãî èíôîðìàöèîííîãî ìíîæåñòâà ÿâëÿåòñÿ îäèíàêîâîå ÷èñëî àëüòåðíàòèâ, ò.å.
ïîñëåäóþùèõ ïîçèöèé, â êàæäîé òàêîé âåðøèíå. Êðîìå òîãî, èíôîðìàöèîííîåìíîæåñòâî íå äîëæíî ñîäåðæàòü äâóõ ïîçèöèé, ïðèíàäëåæàùèõ îäíîìóïóòè, ñîåäèíÿþùåìó íà÷àëüíóþ âåðøèíó ñ íåêîòîðîé ôèíàëüíîé. Çàíóìåðóåì ýòè ìíîæåñòâà äëÿ êàæäîãî èãðîêà è îáîçíà÷èì èíôîðìàöèîííîåìíîæåñòâî ñ íîìåðîì j èãðîêà a ∈ A ÷åðåç Z aj .Êàê è â èãðå ñ ïîëíîé èíôîðìàöèåé, â ïðîèçâîëüíîé ïîçèöèîííîéèãðåDS aG = A, (X, σ), ua (x), x ∈ T, a ∈ A; X\T =X ∪ X 0,a∈AE∀ x ∈ X 0 ∃ p(x0 |x), x0 ∈ σ −1 (x) ,çàäàíû• A − ìíîæåñòâî èãðîêîâ;• (X, σ) − êîíå÷íîå äåðåâî (îðèåíòèðîâàííûé ãðàô áåç öèêëîâ), ãäåX − ìíîæåñòâî ïîçèöèé (âåðøèí) ñ íà÷àëüíîé âåðøèíîé x0 è σ : X → X− îòîáðàæåíèå, ñîïîñòàâëÿþùåå êàæäîé âåðøèíå äåðåâà (X, σ) åå áëèæàéøåãî ïðåäøåñòâåííèêà, ïðè÷åì1) σ(x0 ) = x0 ,2) íàéäåòñÿ öåëîå l ≥ 0, ÷òî σ l (x) = x0 ∀ x ∈ X; íàèìåíüøåå òàêîål íàçûâàåòñÿ äëèíîé äåðåâà (X, σ);• T = {x ∈ X | σ −1 (x) = ∅} − ìíîæåñòâî ôèíàëüíûõ âåðøèí;• R = {X a , a ∈ A, X 0 } − ðàçáèåíèå ìíîæåñòâà X\T íà ïîïàðíîíåïåðåñåêàþùèåñÿ ïîäìíîæåñòâà;• X a − ìíîæåñòâî ëè÷íûõ ïîçèöèé, â êîòîðûõ äåëàåò õîä èãðîê a ∈A;153ÃËÀÂÀ III.
ÈÃÐÛ ÌÍÎÃÈÕ ËÈÖ• X 0 − ìíîæåñòâî ïîçèöèé, â êîòîðûõ "äåëàåò õîä"ñëó÷àé;• ua : T → E 1 − ôóíêöèÿ âûèãðûøà èãðîêà a;• äëÿ êàæäîãî x ∈ X 0 çàäàíû âåðîÿòíîñòèPp(x0 |x) > 0,p(x0 |x) = 1,x0 ∈σ −1 (x)0−1ïåðåõîäà èç ïîçèöèè x â ïîçèöèè x ∈ σ (x).Êðîìå òîãî, äëÿ êàæäîãî a ∈ A çàäàíîS aj ðàçáèåíèåaX =Zj∈J aíà èíôîðìàöèîííûå ìíîæåñòâà Z , j ∈ J a , âêëþ÷àþùèå ïîçèöèè ñ îäèíàêîâûì ÷èñëîì àëüòåðíàòèâ, ðàâíûì k(j). Àëüòåðíàòèâû êàæäîé ïîçèöèè x ∈ Z aj ïðîíóìåðîâàíû ñëåâà íàïðàâî ÷èñëàìè îò 1 äî k(j). Èãðîê aäåëàåò õîä, íå ðàçëè÷àÿ ïîçèöèè èç Z aj ìåæäó ñîáîé.
×òîáû îòðàçèòü ýòîîáñòîÿòåëüñòâî, îáîçíà÷èì ÷åðåç Alaj = {1, ..., k(j)} ìíîæåñòâî íîìåðîâàëüòåðíàòèâ äëÿ èíôîðìàöèîííîãî ìíîæåñòâà Z aj èãðîêà a ∈ A. Âî âñåõïîçèöèÿõ x ∈ Z aj ìíîæåñòâî Alaj èçîìîðôíî ìíîæåñòâó ïîçèöèé σ −1 (x).Îáîçíà÷èì ÷åðåç ξ(x, k) âåðøèíó, ñëåäóþùóþ çà x è ñîîòâåòñòâóþùóþàëüòåðíàòèâå ñ íîìåðîì k ∈ Alaj ïðè óêàçàííîì èçîìîðôèçìå.ajÎïðåäåëåíèå. ×èñòîé ñòðàòåãèåé èãðîêà a ∈ A íàçûâàåòñÿ îòîáðàæåíèå µa , îïðåäåëÿþùåå äëÿ êàæäîãî èíôîðìàöèîííîãî ìíîæåñòâà Z ajàëüòåðíàòèâó µa (Z aj ) ∈ Alaj , êîòîðóþ èãðîê âûáèðàåò â ëþáîé èç âåðøèí ýòîãî ìíîæåñòâà. Íàáîð òàêèõ ñòðàòåãèéµ = (µa , a ∈ A) íàçûâàåòñÿ ñèòóàöèåé.Âåðîÿòíîñòü ïîïàñòü â ïîçèöèþ x ∈ X , íåïîñðåäñòâåííî ñëåäóþùóþçà âåðøèíîé σ(x) ∈ Z aj ïðè èñïîëüçîâàíèè ñèòóàöèè µ, îïðåäåëÿåòñÿ ïîôîðìóëå p(x|µ) = p(σ(x)|µ)p(x|σ(x), µ), ãäå(1, åñëè x = ξ(σ(x), µa (Z aj )),p(x|σ(x), µ) =0â ïðîòèâíîì ñëó÷àå.Åñëè æå σ(x) ∈ X 0 − ïîçèöèÿ ñëó÷àÿ, òî âåðîÿòíîñòü p(x|σ(x), µ) =p(x|σ(x)) çàäàíà óñëîâèÿìè èãðû.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
