А.А. Васин, В.В. Морозов - Введение в теорию игр с приложениями к экономике (1184512), страница 25
Текст из файла (страница 25)
� ñëó÷à� ïóñòîã� Y (f ) áóäå� ñ÷èòàòü, ÷ò� âòîðî� èãðî� ìîæå� âûáðàò� ëþáó� ñòðàòåãè� y ∈ Y. Îïðåäåëè� ìíîæåñòâ� (Y (f ), Y (f ) 6= ∅,Y ∗ (f ) = Y, Y (f ) = ∅. � ñäåëàííû� ïðåäïîëîæåíèÿ� âòîðî� èãðî� âûáèðàå� y ∈ Y ∗ (f ) � îöåíê� ýôôåêòèâíîñò� ñòðàòåãè� f çàäàåòñ� ôîðìóëî� W (f ) = inf ∗ F (f (y), y). y∈Y (f ) Íàèëó÷øè� ãàðàíòèðîâàííû� ðåçóëüòà� ïåðâîã� èãðîê� èìåå� âè� F2 = sup inf ∗ F (f (y), y).
f ∈{f } y∈Y (f ) Îïðåäåëåíèå. Ïóñò� çàäàí� ε > 0. Ñòðàòåãè� f ε íàçûâàåòñ� ε-îïòèìàëüíî� � èãð� Γ2 , åñë� W (f ε ) ≥ F2 − ε. Ïîèñ� âåëè÷èí� F2 ï� óêàçàííî� ôîðìóë� âåñüì� ñëîæåí, òà� êà� ñâÿçà� � ðåøåíèå� îïòèìèçàöèîííî� çàäà÷� í� ìíîæåñòâ� ôóíêöè� {f }. Ì� äàëå� óïðîñòè� ôîðìóë� äë� F2 òàêè� îáðàçîì, ÷òîá� îïòèìèçàöè� âåëàñ� ï� èñõîäíû� ìíîæåñòâà� X � Y. Èãð� Γ3 .
Ïóñò� âòîðî� èãðî� èãðàå� ïðîòè� ïåðâîã� � èãð� Γ∗ 2 , ò.å. 124 11. Èåðàðõè÷åñêè� èãð� äâó� ëè�ñîîáùàå� åì� ñòðàòåãè� g : X → Y (ôóíêöè� îòâåòà). Ïåðâû� èãðî� � èãð� Γ3 ïåðâû� ñîîáùàå� âòîðîì� ñòðàòåãè� f1 : {g} → X. Ñõåì� 21 2ñîîáùåíè� � èãð� Γ3 : f1 → g → x = f1 (g) → y = g(x). Ýêîíîìè÷åñêà� èíòåðïðåòàöèÿ: f1 (g) − âåëè÷èí� ðåñóðñà, êîòîðû� âûäåëÿå� öåíò� ïðîèçâîäèòåë� ïðîäóêöèè, êîãä� òî� ñîîáùàå� åì� ñâî� ïðîèçâîäñòâåííû� âîçìîæíîñò� ( ôóíêöè� g ). Íàèëó÷øè� ãàðàíòèðîâàííû� ðåçóëüòà� ïåðâîã� èãðîê� � èãð� Γ3 èìåå� âè� F3 = sup inf F (f1 (g), g), ∗f1 ∈{f1 } g∈Y (f1 ) ãä� (Y (f1 ), Y (f1 ) 6= ∅,Y (f1 ) = {g},Y (f1 ) = ∅, ∗Y (f1 ) = Arg max G(f1 (g), g). g∈{g} Âåðíåìñ� � èãð� Γ2 .
Íàéäå� áîëå� ïðîñòó� ôîðìóë� äë� F2 . Ïîëîæè� X(y) =Argmax F (x, y) − ìíîæåñòâ� íàèëó÷øè� îòâåòî� ïåðâîã� èãðîêà, x∈X X ∗ (y) =Ar� max G(x, y) − ìíîæåñòâ� íàèëó÷øè� îòâåòî� ïåðâîã� èãðîx∈X(y) êà, áëàãîæåëàòåëüíû� ï� îòíîøåíè� ê� âòîðîìó.
Îïðåäåëè� ñòðàòåãè� ïåðâîã� èãðîê� f ∗ : f ∗ (y) ∈ X ∗ (y) ∀y ∈ Y. Ëåìì� 11.1. Ôóíêöè� G(f ∗ (y), y) ïîëóíåïðåðûâí� ñâåðõ� � ëþáî� òî÷ê� y 0 ∈ Y, ò.å. äë� ëþáî� ïîñëåäîâàòåëüíîñò� {y k }, ñõîäÿùåéñ� � y 0 , âûïîëíåí� íåðàâåíñòâ� lim G(f ∗ (y k ), y k ) ≤ G(f ∗ (y 0 ), y 0 ).
k→∞ (11.1) Äîêàçàòåëüñòâî. Ïóñò� � íåêîòîðî� òî÷ê� y 0 ∈ Y ôóíêöè� G(f ∗ (y), y) í� ÿâëÿåòñ� ïîëóíåïðåðûâíî� ñâåðõó. Òîãä� íàéäåòñ� òàêà� ïîñëåäîâàòåëüíîñò� {y k }, ñõîäÿùàÿñ� � y 0 , ÷ò� def G� = lim G(f ∗ (y k ), y k ) > G(f ∗ (y 0 ), y 0 ). k→∞ (11.2)Áå� ïîòåð� îáùíîñò� ñ÷èòàå� (âûäåëÿ� ñîîòâåòñòâóþùó� ïîäïîñëåäîâàòåëüíîñòü), ÷ò� f ∗ (y k ) → x0 . È� íåïðåðûâíîñò� ôóíêöè� G(x, y) ñëåäóå� G� = lim G(f ∗ (y k ), y k ) = G(x0 , y 0 ). k→∞ 125 ÃËÀÂ� II.
ÈÃÐ� ÄÂÓ� ËÈ�Ïîêàæåì, ÷ò� x� ∈ X(y 0 ). Äåéñòâèòåëüíî, ï� îïðåäåëåíè� ôóíêöè� f ∗ èìåå� F (f ∗ (y k ), y k ) ≥ F (x, y k ) ∀ x ∈ X, k = 1, 2, .... Îòñþäà, ïåðåõîä� � ïîñëåäíå� íåðàâåíñòâ� � ïðåäåë� ïð� k → ∞, ïîëó÷è� F (x0 , y 0 ) ≥ F (x, y 0 ) ∀ x ∈ X ⇒ x� ∈ X(y 0 ). Èòàê, íåðàâåíñòâ� (11.2) ìîæí� çàïèñàò� � âèä� G� = G(x0 , y 0 ) > G(f ∗ (y 0 ), y 0 ). Îí� ïðîòèâîðå÷è� òîìó, ÷ò� f ∗ (y 0 ) ∈ X ∗ (y 0 ). Íà� ïîòðåáóåòñ� ñëåäóþùè� âåëè÷èí� � ìíîæåñòâà: G2 = max min G(x, y) − íàèëó÷øè� ãàðàíòèðîâàííû� ðåçóëüòà� âòîy∈Y x∈X ðîã� èãðîê� ïð� óñëîâèè, ÷ò� ïåðâû� ïðèìåíÿå� ï� îòíîøåíè� � íåì� ñòðàòåãè� "íàêàçàíèÿ"f � : f í (y) ∈Argmin G(x, y) ∀ y ∈ Y ; x∈X E =Argmax min G(x, y) − ìíîæåñòâ� ìàêñèìèííû� ñòðàòåãè� âòîðîã� y∈Y x∈X èãðîêà; D = {(x, y) ∈ X × Y | G(x, y) > G2 }; ⎨ sup F (x, y), D �= ∅,K = (x,y)∈D ⎩ −∞,D = ∅; M = min max F (x, y).
y∈E x∈X Òåîðåì� 11.1 (Ãåðìåéåð). � ñäåëàííû� ïðåäïîëîæåíèÿ� íàèëó÷øè� ãàðàíòèðîâàííû� ðåçóëüòà� ïåðâîã� èãðîê� � èãð� Γ2 ðàâå� F2 = max[K, M ]. Çàìå÷àíèå. Äë� íàõîæäåíè� F2 íåîáõîäèì� ðåøèò� îïòèìèçàöèîííû� çàäà÷� í� èñõîäíû� ìíîæåñòâà� X � Y. Îïòèìàëüíû� (ε-îïòèìàëüíûå) ñòðàòåãèè, îáåñïå÷èâàþùè� max[K, M ], áóäó� óêàçàí� � ïåðâî� ÷àñò� äîêàçàòåëüñòâ� òåîðåìû. Ðåçóëüòà� max[K, M ] äîâîëüí� âåëèê. ×òîá� � ýòî� óáåäèòüñÿ, ðàññìîòðè� ÷àñòíû� ñëó÷àé.
Äîïóñòèì, ÷ò� ñóùåñòâóå� ïàð� (x0 , y 0 ) ∈Ar� max F (x, y) ∩ D. Òîãä� (x,y)∈X×Y K = sup F (x, y) = (x,y)∈D max (x,y)∈X×Y F (x, y) = F2 , ò.å. ðåçóëüòà� F2 ðàâå� ìàêñèìóì� ôóíêöè� F (x, y) í� X × Y. Äîêàçàòåëüñòâî. Ïåðâà� ÷àñòü. Ïîñòðîè� ñòðàòåãè� ïåðâîã� èãðîêà, îáåñïå÷èâàþùè� åì� ðåçóëüòà� max[K, M ].
Ðàññìîòðè� äâ� ñëó÷àÿ. 126 11. Èåðàðõè÷åñêè� èãð� äâó� ëè�1) K > M ⇒ D �= ∅. Ïîêàæåì, ÷ò� äë� âñÿêîã� ε > 0 íàéäåòñ� òàêà� ñòðàòåãè� f ε , ÷ò� W (f ε ) ≥ K − ε. Ï� îïðåäåëåíè� âåðõíå� ãðàí� K íàéäåòñ� òàêà� ïàð� (xε , y ε ) ∈ D, ÷ò� F (xε , y ε ) ≥ K − ε. Ïîëîæè� (xε , y = y ε , εf (y) = f í (y), y =6 y ε . Ïîêàæåì, ÷ò� W (f ε ) = F (xε , y ε ) ≥ K − ε. Äåéñòâèòåëüíî, âòîðî� èãðîê, ïîëó÷è� ñîîáùåíè� � f ε , âûáåðå� y = y ε , òà� êà� � ïðîòèâíî� ñëó÷à� î� ïîëó÷è� âûèãðû� G(f í (y), y) = min G(x, y) ≤ G2 < G(xε , y ε ).
Ïîñêîëüx∈X ê� âòîðî� èãðî� ìàêñèìèçèðóå� ñâî� âûèãðûø, î� âûáåðå� y = y ε , ò.å. Y ∗ (f ε ) = {y ε }. 2) K ≤ M. Óêàæå� ñòðàòåãè� f 0 , äë� êîòîðî� W (f 0 ) ≥ M. Ïîëîæè� (f ∗ (y), y ∈ E, f 0 (y) =f í (y), y ∈ / E, ãä� ñòðàòåãè� f ∗ áûë� îïðåäåëåí� âûø� ïåðå� ëåììî� 11.1. Ïîëó÷è� ñîîáùåíè� � f 0 , âòîðî� èãðî� âûáåðå� y ∈ E. Äåéñòâèòåëüíî, åñë� y ∈ / E, í0ò� G(f (y), y) = min G(x, y) < G2 . Äàëåå, ïð� y ∈ E G(f (y), y) = x∈X G(f ∗ (y), y) ≥ min G(x, y) = G2 .
Ôóíêöè� G(f ∗ (y), y) ïîëóíåïðåðûâí� x∈X ñâåðõ� í� êîìïàêò� E, ïîýòîì� Y ∗ (f 0 ) =Argmax G(f ∗ (y), y) ⊆ E. Îòñþä� y∈E W (f 0 ) = min F (f ∗ (y), y) ≥∗ 0y∈Y (f ) ≥ min F (f ∗ (y), y) = min max F (x, y) = M. y∈Ey∈E x∈X Âòîðà� ÷àñòü. Äîêàæåì, ÷ò� äë� ïðîèçâîëüíî� ñòðàòåãè� f ∈ {f }W (f ) ≤ max[K, M ]. Èìåå� sup G(f (y), y) ≥ max min G(x, y) = G2 . y∈Yy∈Y x∈X Ðàññìîòðè� äâ� ñëó÷àÿ.
1) sup G(f (y), y) > G2 . � ýòî� ñëó÷à� íàéäåòñ� òàêà� ñòðàòåãè� âòîðîy∈Y ã� èãðîê� y 0 ∈ Y ∗ (f ), ÷ò� G(f (y 0 ), y 0 ) > G2 , ò.å. (f (y 0 ), y 0 ) ∈ D. Äåéñòâèòåëüíî, åñë� sup äîñòèãàåòñÿ, ò� Y (f ) 6= ∅ � y 0 âîçüìå� ðåàëèçóþùè� y∈Y sup . Åñë� sup í� äîñòèãàåòñÿ, ò� Y ∗ (f ) = Y � ñòðàòåãè� y 0 íàéäåòñ� ï� y∈Yy∈Y 127ÃËÀÂ� II. ÈÃÐ� ÄÂÓ� ËÈ�îïðåäåëåíè� sup . Îòñþä� y∈Y W (f ) = inf y∈Y ∗ (f ) F (f (y), y) ≤ F (f (y 0 ), y 0 ) ≤ K ≤ max[K, M ].
2) sup G(f (y), y) = G2 . Ïîêàæåì, ÷ò� E ⊂ Y ∗ (f ). Äåéñòâèòåëüíî, y∈Y ïóñò� y ∈ E. Òîãä� G2 = min G(x, y) ≤ G(f (y), y) ≤ sup G(f (y), y) = G2 . x∈Xy∈Y � ýòî� öåïî÷ê� íåðàâåíñòâ� âûïîëíåí� êà� ðàâåíñòâà. Îòñþä� y ∈ Y ∗ (f ) � E ⊆ Y ∗ (f ). Èòàê, W (f ) = inf ∗ F (f (y), y) ≤y∈Y (f ) ≤ inf F (f (y), y) ≤ min max F (x, y) = M ≤ max[K, M ]. y∈Ey∈E x∈X Ñôîðìóëèðóå� àíàëîãè÷íû� ðåçóëüòà� äë� èãð� Γ3 . Íàïîìíèì, ÷ò� � èãð� Γ3 âòîðî� èãðî� âûáèðàå� y, êîãä� âûáî� ñòðàòåãè� x ïåðâîã� åì� èçâåñòåí.
Âòîðî� èãðî� èñïîëüçóå� ñòðàòåãè� g : X → Y. Îïðåäåëèìñëåäóþùè� âåëè÷èí� � ìíîæåñòâî: G3 = min max G(x, y) = max G(xí , y) − íàèëó÷øè� ãàðàíòèðîâàííû� x∈X y∈Yy∈Y ðåçóëüòà� âòîðîã� èãðîêà, êîãä� ïåðâû� ïðèìåíÿå� ñòðàòåãè� íàêàçàíè� xí ; D0 = {(x, y) ∈ X × Y | G(x, y) > G3 }; ⎨ sup F (x, y), D� =6 ∅, � K = (x,y)∈D� ⎩−∞,D� = ∅. Òîãä� ìîæí� äîêàçàòü, ÷ò� F3 = max[K 0 , F1 ] (ñì.
óïðàæíåíè� 11.12). Åñë� F1 ≥ K 0 , ò� ïåðâû� èãðî� ïðèìåíÿå� ε-îïòèìàëüíó� ñòðàòåãè� èãð� Γ1 . Ïóñò� F1 < K 0 . � ýòî� ñëó÷à� íàéäåòñ� òàêà� ïàð� (xε , y ε ) ∈ D0 , ÷ò� F (xε , y ε ) ≥ K � − ε. Óïðàæíåíè� 11.1. Äîêàæèòå, ÷ò� äë� ñòðàòåãè� (xε , g(xε ) = y ε ,f1 ε (g) = x� , g(xε ) 6= y ε , îöåíê� ýôôåêòèâíîñò� W (f1 ε ) ≥ K � − ε.Óïðàæíåíè� 11.2. Äîêàæèòå, ÷ò� äë� ëþáî� ñòðàòåãè� f1 ïåðâîã� èãðîê� � èãð� Γ3 W (f1 ) ≤ max[K 0 , F1 ]. 128 11.
Èåðàðõè÷åñêè� èãð� äâó� ëè�Óïðàæíåíè� 11.3. Äîêàæèòå, ÷ò� � èãð� Γ1 � íîðìàëüíî� ôîðì� âñåãä� ñóùåñòâóå� ñèòóàöè� ðàâíîâåñèÿ. Óïðàæíåíè� 11.4. Äîêàæèòå, ÷ò� F1 ≤ F3 ≤ F2 . Ïðèìå� 11.1. Ðåøè� èãð� Γ1 , Γ2 , Γ3 äë� èãð� Γ � ìàòðèöàì� ⎛ ⎞ ⎛ ⎞ 3 6 8 7 4 3 3 2 ⎠ , B = 7 7 3⎠ . A = 4 7 −5 −1 4 6 6 Èãð� Γ1 . F1 = max min aij = max W (i), Y (i) = Arg max bij , W (1) = 1≤i≤3 j∈Y (i)1≤i≤31≤j≤3 W (2) = 3, W (3) = −5 ⇒ F1 = 3 � i0 = 1, 2 − îïòèìàëüíû� ñòðàòåãèè. Èãð� Γ2 . G2 = max min bij = 4, E = {1, 2}, D = {(i, j) | bij > 4}, 1≤j≤3 1≤i≤3 K = max aij = 4, M = min max aij = 6 ⇒ F2 = M = 6 1≤j≤2 1≤i≤3 (i,j)∈D (3, j = 1, � f 0 (j) = − îïòèìàëüíà� ñòðàòåãèÿ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
