А.А. Васин, В.В. Морозов - Введение в теорию игр с приложениями к экономике (1184512), страница 30
Текст из файла (страница 30)
Ìíîæåñòâ� âñå� ñòðàòåãè� èãðîê� 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. 0b� HH3/4 1bH� b2 @@ 1 2b@@×@@b×3 4@@@× @×××1/41526 Ðèñ. 13.3 DEaaÎïðåäåëåíèå. Èãð� Γ(G) = A, {µ }, u (µ), a ∈ A íàçûâàåòñ� íîðìàëüíî� ôîðìî� ïîçèöèîííî� èãð� G. Äë� ëþáî� âåðøèí� z ∈ X ìîæí� ðàññìîòðåò� ïîçèöèîííó� ïîäû148 13.
Ïîçèöèîííû� èãð� � ïîëíî� èíôîðìàöèå�ãðó, íà÷èíàþùóþñ� è� ýòî� òî÷êè:DEGz = A, (Xz , σz ), Xz 0 , Xza , u az (x), a ∈ A ,ãä� • Xz = {x |ñóùåñòâóå� òàêî� öåëî� l ≥ 0, ÷ò� σ l (x) = z}; • σz åñò� ñóæåíè� îòîáðàæåíè� σ í� Xz � σz (z) = z ; • Xza = X a ∩ Xz , a ∈ A, Xz 0 = X 0 ∩ Xz ; • uaz (x) = ua (x), åñë� x ∈ Xz ∩ T .Ïóñò� µ = (µa , a ∈ A) − ñèòóàöè� � èãð� Γ(G). Îáîçíà÷è� ÷åðå� µz = (µa z , a ∈ A) − å� ñóæåíè� í� Xz , � ÷åðå� ua (µz ) − çíà÷åíè� âûèãðûø� èãðîê� a � ñèòóàöè� µz . Òàêè� îáðàçîì, D� äë� ëþáîã� z ∈ X îïðåäåëåí� aaèãð� Γ(Gz ) = A, {µz }, uz (µz ), a ∈ A − íîðìàëüíà� ôîðì� äë� èãð� Gz .
Óïðàæíåíè� 13.2. Í� ðèñ. 13.4 èçîáðàæåí� äåðåâ� èãð� G. � ôèíàëüíû� ïîçèöèÿ� óêàçàí� âåêòîð� âûèãðûøå� èãðîêî� u(x) = (u1 (x), u2 (x)) èë� èñõîä� èãðû. 0bHH3/41 bHH b2 z @@ 1 2 b@×@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), ãä� µa z − ñóæåíè� ñòðàòåãè� µa í� ïîäûãð� Γ(Gz ), ÿâëÿåòñ� ðàâíîâåñèå� ï� Íýø� � èãð� Γ(Gz ).
Àëãîðèò� îïðåäåëåíè� ñîâåðøåííîã� ïîäûãðîâîã�ðàâíîâåñè� (àëãîðèò� Êóíà)Àëãîðèò� Êóí� ñîñòîè� è� ïîñëåäîâàòåëüíû� ðåäóêöè� èãð� G. Øà� 1. Ðàññìîòðè� ìíîæåñòâ� Z1 ïðåäôèíàëüíû� âåðøèí, äë� êîòîðû� âñ� ïîñëåäóþùè� âåðøèí� ÿâëÿþòñ� ôèíàëüíûìè: Z1 = {x | σ −1 (x) ⊆T }. Äë� êàæäî� âåðøèí� x ∈ Z1 äåéñòâóå� ñëåäóþùè� îáðàçîì. 149ÃËÀÂ� III. ÈÃÐ� ÌÍÎÃÈ� ËÈ�1) Åñë� � äàííî� âåðøèí� õîäè� èãðî� a ∈ A (x ∈ Z1 ∩X 0 ), ò� íàõîäè� åã� íàèëó÷øè� âûáî� � ýòî� âåðøèí� µa (x) ∈ Ar� max ua (y) −1y∈σ(x) � äîîïðåäåëÿå� âåêòî� âûèãðûøå� èãðîêî� � âåðøèí� def u(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 ãðÿ� 11 A = , 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}
