А.А. Васин, В.В. Морозов - Введение в теорию игр с приложениями к экономике (1184512), страница 51
Текст из файла (страница 51)
Îïðåäåëåíè� ñåäëîâî� òî÷ê� (x0 , y 0 ) ôóíêöè� F (x, y) í� X × Y ìîæí� çàïèñàò� ñëåäóþùè� îáðàçîì: F (x 0 , y 0 ) = max F (x, y 0 ), −F (x 0 , y 0 ) = max (−F (x 0 , y)), x∈Xy∈Y ÷ò� ñîâïàäàå� � îïðåäåëåíèå� ñèòóàöè� ðàâíîâåñèÿ. 9.2. Ïóñò� � èãð� âîçíèêë� ñèòóàöè� (1,1). Òîãä� âûãîäí� îòêëîíèòüñ� ïåðâîì� èãðîê� � âîçíèêíå� ñèòóàöè� (2,1). Òåïåð� âûãîäí� îòêëîíèòüñ� âòîðîì� èãðîêó, âîçíèêíå� ñèòóàöè� (2,1) � ò.ä.
ï� ñõåì� (1, 1) → (2, 1) →(2, 2) → (1, 2) → (1, 1).244 22. Ðåøåíè� óïðàæíåíè�9.3. Åñë� èãðîê� îäíîâðåìåíí� ïðèìåíÿþ� ïðàâèë� ïðàâî� ðóê� (ëåâî� ðóêè), ò� ïåðâû� (âòîðîé) èãðî� ïðîåäå� � "ïîëó÷èò"1, � âòîðî� (ïåðâûé) åã� ïðîïóñòè� � ïîëó÷è� 0. Åñë� ïåðâû� ïðèìåíÿå� ïðàâèë� ïðàâî� ðóêè, � âòîðî� − ëåâîé, ò� ïðîèçîéäå� ñòîëêíîâåíè� � îá� ïðîèãðàþ� ï� 10. Åñë� − íàîáîðîò, ò� îá� áóäó� ñòîÿò� � ïðîèãðàþ� ï� 1.
9.4. � èãð� Γ äâ� ðàâíîâåñè� ï� Íýøó: (1,1) � (2,2). 9.5. � èãð� Γ åäèíñòâåííî� ðàâíîâåñè� ï� Íýøó: (1,1). 9.6. Ïóñò� (x0 , y 0 ) − ïðîèçâîëüíà� ñèòóàöè� � àíòàãîíèñòè÷åñêî� èãðå. Ïðåäïîëîæèì, ÷ò� ñèòóàöè� (x0 , y 0 ) í� ÿâëÿåòñ� îïòèìàëüíî� ï� Ïàðåòî. Òîãä� íàéäåòñ� ñèòóàöè� (x0 , y 0 ), äë� êîòîðî� âûïîëíåí� íåðàâåíñòâ� F (x0 , y 0 ) ≥ F (x0 , y 0 ), −F (x0 , y 0 ) ≥ −F (x0 , y 0 ) � ïð� ýòî� õîò� á� îäí� è� íè� âûïîëíåí� êà� ñòðîãîå. Ñêëàäûâà� ýò� íåðàâåíñòâà, ïîëó÷è� 0 > 0 (ïðîòèâîðå÷èå).
9.7. Ïóñò� ôóíêöè� f : [0, 1] → [0, 1] íåïðåðûâíà. Òîãä� äë� ôóíêöè� g(x) = f (x)−x g(0) ≥ 0 � g(1) ≤ 0. Ï� òåîðåì� ìàòåìàòè÷åñêîã� àíàëèç� � ïðîìåæóòî÷íû� çíà÷åíèÿ� íàéäåòñ� òî÷ê� x0 , äë� êîòîðî� g(x0 ) = 0.9.8. 1) f (x) = x + 1, x ∈ [0, +∞); 2) f (x) = x/2,( x ∈ (0, 1]; x + 1/2, x ∈ [0, 1/2),3) f (x) = x − 1/2, x ∈ [1/2, 1]. 0 010.1. Ïóñò� (p , q ) − ñèòóàöè� ðàâíîâåñè� � ñòðàòåãè� q 0 ïð� íåê�òîðî� v1 óäîâëåòâîðÿå� ñèñòåì� (ñì. (10.1)) 2q10 + q3 0 = q10 + 2q2 0 = q20 + 2q3 0 = v1 , q 10 + q20 + q30 = 1.Îòñþä� q 0 = (1/3, 1/3, 1/3).Ïðåäïîëîæèì, ÷ò� q 0 óäîâëåòâîðÿå� ñèñòåì�2q10 + q30 < q10 + 2q2 0 = q20 + 2q3 0 = v1 , q 10 + q20 + q30 = 1.Òîãä� q30 = 1/3, � q20 > 1/3.
Ï� ñâîéñòâ� äîïîëíÿþùå� íåæåñòêîñò�p01 = 0, p02 + 2p03 = p03 = v2 . Îòñþä� p01 = p02 = p03 = 0 (ïðîòèâîðå÷èå).Íàêîíåö, ðàçáåðå� ñëó÷àé, êîãä�2q10 + q30 , q10 + 2q20 < q20 + 2q3 0 = v1 , q 10 + q20 + q30 = 1.Òîãä� q30 > 1/3, � ï� ñâîéñòâ� äîïîëíÿþùå� íåæåñòêîñò� p01 = p02 = 0 ⇒ p03 = 1. È� ñèñòåì� (10.2) ñëåäóåò, ÷ò� v2 = B(p0 , 3) ≥ B(p0 , 2) èë� 1 ≥ 2(ïðîòèâîðå÷èå). 245 22. Ðåøåíè� óïðàæíåíè�Äðóãè� ñëó÷à� ðåàëèçàöè� ñèñòåì� (10.1) ïîëó÷àþòñ� è� ðàçîáðàííû� ïåðåñòàíîâêî� êîîðäèíàò, ïîñêîëüê� ìàòðèö� A � B − öèêëè÷åñêèå.
Àíàëîãè÷í� äîêàçûâàåòñÿ, ÷ò� p0 = (1/3, 1/3, 1/3). 10.2. Äîêàçàòåëüñòâ� òåîðåì� 10.4. 1) Ïóñò� ìíîæåñòâ� Z = Zk ⊂ Zk−1 ⊂ · · · ⊂ Z1 = Z, Zl = Xl × Yl , l = 1, ..., k, îòâå÷àþ� îïðåäåëåíè� ñòðîãîã� äîìèíèðîâàíè� Z � Z. Âîçüìå� i ∈ X1 \X2 . Òîãä� íàéäåòñ� òàêà� ñòðàòåãè� p ∈ P, ÷ò� p � i í� Y1 = Y. Îòñþä� A(p, j) > aij , j = 1, ..., n. Óìíîæà� j -� íåðàâåíñòâ� í� qj 0 � ñêëàäûâà� âñ� íåðàâåíñòâà, ïîëó÷è� A(p, q 0 ) > A(i, q 0 ). Åñë� p0 i > 0, ò� è� ñèñòåì� (10.1) âûòåêàþ� íåðàâåíñòâ� A(i, q 0 ) = v1 ≥A(i1 , q 0 ), i1 = 1, ..., m.
Óìíîæà� ýò� íåðàâåíñòâ� í� âåëè÷èí� pi1 � ñêëàäûâà� èõ, ïîëó÷è� A(i, q 0 ) ≥ A(p, q 0 ) (ïðîòèâîðå÷èå). Îòñþä� p0 i = 0 ∀ i ∈X1 \X2 . Àíàëîãè÷í� äîêàçûâàåòñÿ, ÷ò� qj 0 = 0 ∀ j ∈ Y1 \Y2 . Ïóñò� âåêòîð� p2 � q 2 ïîëó÷åí� è� p0 � q 0 îòáðàñûâàíèå� íóëåâû� êîìïîíåí� � íîìåðàì� è� ìíîæåñò� X1 \X2 � Y1 \Y2 ñîîòâåòñòâåííî. Íåòðóäí� ïîêàçàòü, ÷ò� (p2 , q 2 ) − ñèòóàöè� ðàâíîâåñè� � ðåäóöèðîâàííî� èãð� � ìàòðèöàì� A2 � B 2 , ïîëó÷åííûì� è� ìàòðè� A � B âû÷åðêèâàíèå� ñòðî� � íîìåðàì� è� X1 \X2 � ñòîëáöî� � íîìåðàì� è� Y1 \Y2 .
Ïîýòîì� ðàññóæäåíè� ìîæí� ïîâòîðèò� äë� ðåäóöèðîâàííî� èãð� � ïîëó÷èòü, ÷ò� p0 i = 0 ∀ i ∈ X2 \X3 , qj 0 = 0 ∀ j ∈ Y2 \Y3 � ò.ä. 2) Ïóñò� ìíîæåñòâ� Z = Zk ⊂ Zk−1 ⊂ · · · ⊂ Z1 = Z, Zl = Xl × Yl , l = 1, ..., k, îòâå÷àþ� îïðåäåëåíè� ñëàáîã� äîìèíèðîâàíè� Z � Z.
Ïóñò� Ak−1 � B k−1 − ïîäìàòðèö� ìàòðè� A � B � íîìåðàì� ñòðî� è� X k−1 � íîìåðàì� ñòîëáöî� è� Y k−1 . Ðàññìîòðè� âåêòî� pk−1 , ïîëó÷åííû� è� âåêòîð� p äîáàâëåíèå� íóëåâû� êîìïîíåí� � íîìåðàì� è� X k−1 \X. Àíàëîãè÷íî, âåêòî� q k−1 ïîëó÷àåòñ� è� âåêòîð� q äîáàâëåíèå� íóëåâû� êîìïîíåí� � íîìåðàì� è� Y k−1 \Y . Äîêàæåì, ÷ò� (pk−1 , q k−1 ) − ñèòóàöè� ðàâíîâåñè� � èãð� � ìàòðèöàì� Ak−1 � B k−1 . Äë� ýòîã� ïðîâåðè� óñëîâè� (∗) äë� ñèòóàöè� (pk−1 , q k−1 ). Èìåå� Ak−1 (i, q k−1 ) = A(i, q) ≤ A(p, q) = Ak−1 (pk−1 , q k−1 ) ∀ i ∈ X.
Ïóñò� i ∈ X k−1 \X. Òîãä� íàéäåòñ� òàêà� ñòðàòåãè� p, ÷ò� p � i í� Y k−1 � pi1 = 0 ∀ i1 ∈/ X. Îïðåäåëè� âåêòî� � p� = (pi1 , i1 ∈ X). Òîãä� k−1k−1A (i, q ) = aij qjk−1 ≤ j∈Y k−1 P � 0≤ ( ai1 j pi1 )q j = A(p , q) ≤ A(p, q) = Ak−1 (pk−1 , q k−1 ). j∈Y i1 ∈X � ðåçóëüòàò� äîêàçàë� íåðàâåíñòâ� 246 22. Ðåøåíè� óïðàæíåíè�Ak−1 (i, q k−1 ) ≤ Ak−1 (pk−1 , q k−1 ) ∀ i ∈ X k−1 . Àíàëîãè÷í� äîêàçûâàåòñ� âòîðà� ãðóïï� íåðàâåíñò� è� óñëîâè� (∗) B k−1 (pk−1 , j) ≤ B k−1 (pk−1 , q k−1 ) ∀ j ∈ Y k−1 . k−1 k−1Èòàê, (p , q ) − ñèòóàöè� ðàâíîâåñè� èãð� � ìàòðèöàì� Ak−1 � B k−1 .
Ðàññóæäåíè� ìîæí� ïðîäîëæèòü, àíàëîãè÷íû� îáðàçî� ââåñò� ñèòóàöè� (pk−2 , q k−2 ) � äîêàçàòü, ÷ò� îí� ÿâëÿåòñ� ðàâíîâåñèå� ï� Íýø� èãð� � ìàòðèöàì� Ak−2 � B k−2 � ò.ä. 10.3. Ïóñò� C − ñóìì� ìàòðè� A � B . Êà� îòìå÷àëîñü, C = (cij )m×n = (fj + gi )m×n . Ïîñêîëüê� f1 = 0, ðàçíîñò� j -ã� � 1-ã� ñòîëáöî� ìàòðèö� C ìîæí� çàïèñàò� � âèä� fj e, ãä� e = (1, ..., 1) ∈ E m . Îòñþä� fj = c1j − c11 , j = 1, ..., n � a0ij = aij − fj = aij − a1j − b1j + a11 + b11 ∀ i, j.
10.4. Çàìåòèì, ÷ò� äë� ëþáî� ñìåøàííî� ñòðàòåãè� q âòîðîã� èãðîê� 0A(i, q) = A (i, q) + nXfj qj , i = 1, ..., m. (22.4) j=1 Ïîýòîì� íåðàâåíñòâ� A(i, q 0 ) ≤ A(p0 , q 0 ) ðàâíîñèëüí� íåðàâåíñòâà� A0 (i, q 0 ) ≤ A0 (p0 , q 0 ), i = 1, ..., m. Àíàëîãè÷í� ïîêàçûâàåòñÿ, ÷ò� äë� ëþáî� ñìåøàííî� ñòðàòåãè� p ïåðâîã� èãðîê� 0B(p, j) = −A (p, j) + mXgi pi , j = 1, ..., n, (22.5) i=1 � ÷ò� íåðàâåíñòâ� B(p0 , j) ≤ B(p0 , q 0 ) ðàâíîñèëüí� íåðàâåíñòâà� A0 (p0 , j) ≥ A0 (p0 , q 0 ), j = 1, ..., n. Îòñþä� âûòåêàåò, ÷ò� äë� ñèòóàöè� (p0 , q 0 ) óñëîâè� (∗) � èãð� � ìàòðèöå� A� (òåîðåì� 4.10 ) ýêâèâàëåíòí� óñëîâè� (∗) � èãð� Γ (ëåìì� 10.1). 10.5.
È� ôîðìó� (22.4) � (22.5) ñëåäóåò, ÷ò� Arg max A(i, q(k)) = Arg max A0 (i, q(k)), 1≤i≤m 1≤i≤m Arg max B(p(k), j) = Arg min A0 (p(k), j). 1≤j≤n 1≤j≤n Ïîýòîì� ïîñëåäîâàòåëüíîñò� ñòðàòåãè� èãðîêî� {ik }, {jk } � ïðîöåññ� Áðàóí� äë� èãð� � ìàòðèöå� A� � � àíàëîãè÷íî� ïðîöåññ� äë� èãð� Γ ìîæí� âçÿò� ñîâïàäàþùèìè. Ï� òåîðåì� 5.3 ëþáà� ïðåäåëüíà� òî÷ê� (p0 , q 0 ) ïîñëåäîâàòåëüíîñò� {(p(k), q(k))} ÿâëÿåòñ� ñåäëîâî� òî÷êî� � ñìåøàííû� ñòðàòåãèÿ� è, ñëåäîâàòåëüíî, ñìåøàííû� ðàâíîâåñèå� ï� Íýø� èãð� Γ. 247 22. Ðåøåíè� óïðàæíåíè�11.1.
Çàìåòèì, ÷ò� Y1 ∗ (f1 ε ) = {g | g(xε ) = y ε }. Ñëåäîâàòåëüíî,W (f1ε ) = inf ∗g∈Y1 (f1 ε )F (f1ε (g), g) = F (x ε , y ε ) ≥ K � − ε.11.2. Âîçüìå� ïðîèçâîëüíó� ñòðàòåãè� f1 ∈ {f1 } � äîêàæåì, ÷ò� W (f1 ) ≤ max[K 0 , F1 ]. Ïóñò� {g ∗ } − ìíîæåñòâ� âñå� ôóíêöè� íàèëó÷øåã� îòâåò� âòîðîã� èãðîêà. Èìåå� sup G(f1 (g), g) ≥ sup inf G(x, g) ≥g∈{g} x∈X g∈{g} ≥ sup inf G(x, g ∗ ) = min max G(x, y) = G3 .g ∗ ∈{g ∗ } x∈Xx∈X y∈Y Ðàññìîòðè� äâ� ñëó÷àÿ.
1) sup G(f1 (g), g) > G3 . Òîãä� íàéäåòñ� òàêà� ôóíêöè� g∈{g} g ε ∈ Y1 ∗ (f1 ), ÷ò� ïàð� (x0 , y 0 ) = (f1 (g ε ), g ε (x0 )) ïðèíàäëåæè� ìíîæåñòâ� D0 . � ýòî� ñëó÷à� W (f1 ) = inf ∗g∈Y1 (f1 ) F (f1 (g), g) ≤ F (f1 (g ε ), g ε ) = F (x0 , y 0 ) ≤ K 0 . 2) sup G(f1 (g), g) = G3 . Ïîêàæåì, ÷ò� {g ∗ } ⊆ Y1 ∗ (f1 ). g∈{g}Äåéñòâèòåëüíî, äë� âñÿêî� ôóíêöè� íàèëó÷øåã� îòâåò� g ∗ G3 = min max G(x, y) = min G(x, g ∗ ) ≤x∈X y∈Yx∈X ≤ G(f1 (g ∗ ), g ∗ ) ≤ sup G(f1 (g), g) = G3 .
g∈{g} � ïîñëåäíè� íåðàâåíñòâà� êðàéíè� ÷ëåí� ñîâïàäàþò. Ñëåäîâàòåëüíî, âñ� íåðàâåíñòâ� âûïîëíåí� êà� ðàâåíñòâ� � {g ∗ } ⊆ Y1 ∗ (f1 ). Îïðåäåëè� g 0 ∈ {g ∗ } : g 0 (x) ∈ Arg min F (x, y) ∀x ∈ X y∈Y (x) − ôóíêöè� íàèëó÷øåã� îòâåò� âòîðîã� èãðîêà, íàèìåíå� áëàãîæåëàòåëüíîã� ï� îòíîøåíè� � ïåðâîìó. Òîãä� W (f1 ) = inf g∈Y1 ∗ (f1 ) F (f1 (g), g) ≤ F (f1 (g 0 ), g 0 ) ≤≤ sup F (x, g 0 (x)) = sup min F (x, y) = F1 . x∈Xx∈X y∈Y (x) 248 22.
Ðåøåíè� óïðàæíåíè�11.3. Çàäàäè� ñòðàòåãè� g ∗ âòîðîã� èãðîê� óñëîâèå� g ∗ (x) ∈ Arg max F (x, y) ∀x ∈ X. y∈Y (x) Îí� àíàëîãè÷í� ñòðàòåãè� ïåðâîã� èãðîê� f ∗ , îïðåäåëåííî� ïåðå� ëåììî� 11.1. È� ýòî� ëåìì� ñëåäóåò, ÷ò� ôóíêöè� F (x, g ∗ (x)) ïîëóíåïðåðûâí� ñâåðõ� í� X. Âîçüìå� x∗ ∈ Arg max F (x, g ∗ (x)). Òîãä� (x∗ , g ∗ ) −x∈X ñèòóàöè� ðàâíîâåñè� èãð� Γ1 . 11.4. Åñë� ïåðâû� èãðî� � èãð� Γ3 èñïîëüçóå� ñòðàòåãèè-êîíñòàíò� f1 (g) ≡ x, ò� î� ìîæå� îáåñïå÷èò� ñåá� òàêî� æ� ðåçóëüòàò, êà� � � èãð� Γ1 . Ñëåäîâàòåëüíî, F1 ≤ F3 .
Àíàëîãè÷í� ïîêàçûâàåòñÿ, ÷ò� F1 ≤ F2 . Äàëåå, K � ≤ K, ïîñêîëüê� D� ⊆ D. Ïîýòîì� F3 = max[K 0 , F1 ] ≤ F2 = max[K, M ]. 11.5. Ïð� α = 1 ôóíêöè� íàèëó÷øè� îòâåòî� âòîðîã� èãðîê� èìåå� âè� (� Kx/c2 − x, 0 ≤ x ≤ K/c2 , y(x) = 0, K/c2 ≤ x ≤ K/c1 . Îöåíê� ýôôåêòèâíîñò� W (x) ñòðàòåãè� x ðàâí� (√Kc2 x − c1 x, 0 ≤ x ≤ K/c2 , W (x) = F (x, y(x)) = K − c1 x, K/c2 ≤ x ≤ K/c1 , îïòèìàëüíà� ñòðàòåãè� � Kc2 /(4Kc21 )), c2 ≤ 2c1 , x∗ = K/c2 ,c2 > 2c1 � íàèëó÷øè� ãàðàíòèðîâàííû� ðåçóëüòà� äë� ïåðâîã� èãðîê� (Kc2 /(4c1 ),c2 ≤ 2c1 , F1 = max W (x) = W (x∗ ) = 0≤x≤K/c1 (c2 − c1 )K/c2 , c2 > 2c1 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
