А.А. Васин, В.В. Морозов - Введение в теорию игр с приложениями к экономике (1184512), страница 3
Текст из файла (страница 3)
Ìàêñèìó� ôóíêöè� F (x, y) ï� x äîñòèãàåòñ� � êîíöà� îòðåçê� [0, 1] � ðàâå� def M (y) = max F (x, y) = max[F (0, y), F (1, y)] = 0≤x≤1 (2 − 3y + 2y 2 , 0 ≤ y ≤ 2/3, = max[2y 2 , 2 − 3y + 2y 2 ] = 2y 2 , 2/3 < y ≤ 1. Ìèíèìó� ôóíêöè� M (y) äîñòèãàåòñ� ïð� y 0 = 2/3 � v = M (y 0 ) = 8/9 > v = 7/8. Ñëåäîâàòåëüíî, ôóíêöè� F (x, y) í� èìåå� ñåäëîâî� òî÷êè. Óïðàæíåíè� 2.2. Íàéäèò� ìàêñèìèííó� � ìèíèìàêñíó� ñòðàòåãèè, � òàêæ� íèæíå� � âåðõíå� çíà÷åíè� èãð� Γ, � êîòîðî� X = [−2, 3], Y = [−1, 2], F (x, y) = −x 2 + 4xy − 5y 2 + 3x − 2y.
Èíîãä� � âûðàæåíèÿ� v = sup inf F (x, y), v = inf sup F (x, y) x∈X y∈Yy∈Y x∈X âíåøíè� sup � inf í� äîñòèãàþòñÿ, í� sup inf F (x, y) = inf sup F (x, y). x∈X y∈Yy∈Y x∈X 12(2.4) 2. Ñåäëîâû� òî÷ê� � àíòàãîíèñòè÷åñêè� èãð�Òîãä� ìàêñèìèííà� (èë� ìèíèìàêñíàÿ) ñòðàòåãè� í� ñóùåñòâóå� � ñåäëîâî� òî÷ê� íåò. Âîçìîæå� äðóãî� ñëó÷àé, êîãä� v < v , í� ýò� âåëè÷èí� áëèçêè.
� ïîäîáíû� ñëó÷àÿ� èñïîëüçóþ� ïîíÿòè� ε-ñåäëîâî� òî÷êè. Îïðåäåëåíèå. Ïóñò� çàäàí� ε > 0. Ïàð� (xε , y ε ) ∈ X × Y íàçûâàåòñ� ε-ñåäëîâî� òî÷êî� ôóíêöè� F (x, y) í� X × Y , åñë� F (x, y ε ) − ε ≤ F (x ε , y ε ) ≤ F (x ε , y) + ε ∀ x ∈ X, ∀ y ∈ Y.
Óïðàæíåíè� 2.3. Ïóñò� x0 , y 0 − ìàêñèìèííà� � ìèíèìàêñíà� ñòðàòåãèè, a ε = v − v > 0. Äîêàçàòü, ÷ò� (x0 , y 0 ) − ε-ñåäëîâà� òî÷ê� ôóíêöè� F (x, y). Îïðåäåëåíèå. Ïóñò� çàäàí� ε > 0. Ñòðàòåãè� ïåðâîã� èãðîê� xε íàçûâàåòñ� ε-ìàêñèìèííîé, åñë� inf F (xε , y) ≥ v − ε. Ñòðàòåãè� âòîðîã� y∈Y èãðîê� y ε íàçûâàåòñ� ε-ìèíèìàêñíîé, åñë� sup F (x, y ε ) ≤ v + ε.
x∈X Ýò� ñòðàòåãè� îáåñïå÷èâàþ� èãðîêà� ïîëó÷åíè� ñâîè� íàèëó÷øè� ãàðàíòèðîâàííû� ðåçóëüòàòî� � òî÷íîñòü� ä� ε. Ñôîðìóëèðóå� àíàëî� òåîðåì� 2.1. Òåîðåì� 2.1 0 . 1) Äë� òîã� ÷òîá� ïð� ëþáî� ε > 0 ôóíêöè� F (x, y) í� X × Y èìåë� ε-ñåäëîâó� òî÷êó, íåîáõîäèì� � äîñòàòî÷íî, ÷òîá� áûë� âûïîëíåí� ðàâåíñòâ� (2.4).
2) Ïóñò� ðàâåíñòâ� (2.4) âûïîëíåíî. Òîãä� êîìïîíåíò� ε-ñåäëîâî� òî÷ê� ÿâëÿþòñ� 2ε-ìàêñèìèííî� � 2ε-ìèíèìàêñíî� ñòðàòåãèÿìè. Îáðàòíî, ε-ìàêñèìèííà� � ε-ìèíèìàêñíà� ñòðàòåãè� îáðàçóþ� 2ε-ñåäëîâó� òî÷êó. Óïðàæíåíè� 2.4.
Äîêàæèò� òåîðåì� 2.10 . Ïðåäñòàâëÿþ� èíòåðå� óñëîâè� òîïîëîãè÷åñêîã� õàðàêòåðà, ïð� êîòîðû� ñóùåñòâóþ� ìàêñèìèííû� � ìèíèìàêñíû� ñòðàòåãèè. Òåîðåì� 2.2. Ïóñò� ôóíêöè� F (x, y) íåïðåðûâí� í� X × Y, ãä� X, Y − êîìïàêò� ìåòðè÷åñêè� ïðîñòðàíñòâ1 . Ïîëîæè� def Y (x) = Argmin F (x, y). Òîãä� y∈Y 1 Íåäîñòàòî÷í� ïîäãîòîâëåííû� ÷èòàòåë� çäåñ� � äàëå� ìîæå� çàìåíèò� âûðàæåíè� "êîìïàê� ìåòðè÷åñêîã� ïðîñòðàíñòâà"í� âûðàæåíè� "çàìêíóòî� îãðàíè÷åííî� ìíîæåñòâ� åâêëèäîâ� ïðîñòðàíñòâà". 13 ÃËÀÂ� I.
ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈ� ÈÃÐ�1) Ôóíêöè� ìèíèìóì� W (x) = min F (x, y) íåïðåðûâí� í� X. y∈Y 2) Ïðåäïîëîæè� äîïîëíèòåëüíî, ÷ò� ïð� êàæäî� x ∈ X ìíîæåñòâ� Y (x) ñîñòîè� è� åäèíñòâåííîã� ýëåìåíò� y(x). Òîãä� ôóíêöè� y(x) íåïðåðûâí� í� X. Äîêàçàòåëüñòâî. 1) Âîçüìå� ïðîèçâîëüíó� ïîñëåäîâàòåëüíîñò� {xk }ýëåìåíòî� è� X, ñõîäÿùóþñ� � x0 . Ïîêàæåì, ÷ò� lim W (xk ) ñóùåñòâóå� k→∞� ðàâå� W (x0 ).
Ïðåäïîëîæè� ïðîòèâíîå. Òîãä� íàéäåòñ� òàêà� ïîäïîñëåäîâàòåëüíîñò� {kl }, ÷ò� lim W (xkl ) = A =6 W (x0 ). Âîçüìå� ïîñëåäîl→∞âàòåëüíîñò� {y kl ∈ Y (xkl )}. � ñèë� êîìïàêòíîñò� ìíîæåñòâ� Y ìîæí� ñ÷èòàòü, ÷òî2 lim y kl = y 0 . Ïîêàæåì, ÷ò� y 0 ∈ Y (x0 ). Äåéñòâèòåëüíî, ï� l→∞îïðåäåëåíè� y kl W (x kl ) = F (x kl , y kl ) ≤ F (x kl , y) ∀ y ∈ Y. Ïåðåõîä� � ýòî� íåðàâåíñòâ� � ïðåäåë� ïð� l → ∞ � èñïîëüçó� íåïðåðûâíîñò� ôóíêöè� F (x, y), ïîëó÷è� F (x 0 , y 0 ) ≤ F (x 0 , y) ∀ y ∈ Y ⇒ y 0 ∈ Y (x 0 ).
Íàêîíåö, A = lim F (xkl , y kl ) = F (x0 , y 0 ) = W (x0 ) (ïðîòèâîðå÷èå). l→∞ 2) Ïîêàæåì, ÷ò� ôóíêöè� y(x) íåïðåðûâí� í� X . Ïðåäïîëîæèì, ÷ò� îí� ðàçðûâí� � íåêîòîðî� òî÷ê� x0 ∈ X. Òîãä� íàéäåòñ� òàêà� ïîñëåäîâàòåëüíîñò� {xk } ýëåìåíòî� è� X, ñõîäÿùàÿñ� � x0 , ÷ò� ñîîòâåòñòâóþùà� ïîñëåäîâàòåëüíîñò� {y(xk )} í� ñõîäèòñ� � y(x0 ). Ïîýòîì� ñóùåñòâóå� îêðåñòíîñò� U òî÷ê� y(x0 ), âí� êîòîðî� íàõîäèòñ� áåñêîíå÷íî� ÷èñë� ÷ëåíî� ïîñëåäîâàòåëüíîñò� {y(xk )}.
� ñèë� êîìïàêòíîñò� ìíîæåñòâ� Y \U è� ýòî� ïîñëåäîâàòåëüíîñò� ìîæí� âûäåëèò� ïîäïîñëåäîâàòåëüíîñò� {y(xkl )} ⊂ Y \U, ñõîäÿùóþñ� � íåêîòîðîì� ýëåìåíò� y � =6 y(x0 ). � 0Íî, êà� � � ÷àñò� 1), íåòðóäí� äîêàçàòü, ÷ò� y ∈ Y (x ). Ïîëó÷èë� ïðîòèâîðå÷è� � òåì, ÷ò� ìíîæåñòâ� Y (x0 ) ñîñòîè� è� åäèíñòâåííîã� ýëåìåíòà. Çàìå÷àíèå. � ïðîöåññ� äîêàçàòåëüñòâ� òåîðåì� ì� òàêæ� óñòàíîâèë� çàìêíóòîñò� ìíîæåñòâ� {(x, y) | x ∈ X, y ∈ Y (x)}.
Îòìåòè� òàêæå, ÷ò� � òåîðåì� 2.2 êîìïàêòíîñò� ìíîæåñòâ� Y ñóùåñòâåííà. 2 Çäåñ� èñïîëüçîâàí� ñëåäóþùå� ñâîéñòâ� êîìïàêò� ìåòðè÷åñêîã� ïðîñòðàíñòâà: è� ëþáî� ïîñëåäîâàòåëüíîñò� ýëåìåíòî� êîìïàêò� Y ìîæí� âûäåëèò� ïîäïîñëåäîâàòåëüíîñòü, ñõîäÿùóþñ� � íåêîòîðîì� ýëåìåíò� è� Y. Ñ÷èòàåì, ÷ò� {y kl } � åñò� ñîîòâåòñòâóþùà� âûäåëåííà� ïîäïîñëåäîâàòåëüíîñòü. 14 2. Ñåäëîâû� òî÷ê� � àíòàãîíèñòè÷åñêè� èãð�Ïðèìå� 2.5. Ïóñò� X = [−1, 1], Y = (−∞, +∞), F (x, y) = (y 2 + 1)(xy − 1)2 .
Çäåñ� ìíîæåñòâ� Y í� ÿâëÿåòñ� êîìïàêòîì, � ôóíêöè� ((1/x , x 6= 0, 0, x 6= 0, y(x) = W (x) = min F (x, y) = y∈Y 0,x = 0, 1, x = 0, ðàçðûâíû. Îïðåäåëåíèå. Àíòàãîíèñòè÷åñêà� èãð� Γ íàçûâàåòñ� íåïðåðûâíîé, åñë� X, Y − ïàðàëëåëåïèïåä� åâêëèäîâû� ïðîñòðàíñòâ, � ôóíêöè� F (x, y) íåïðåðûâí� í� X × Y . � ÷àñòíîñòè, ïð� X = [a, b], Y = [c, d] áóäå� ãîâîðèò� � íåïðåðûâíî� èãð� í� ïðÿìîóãîëüíèêå. È� òåîðåì� 2.2 ñëåäóåò, ÷ò� � íåïðåðûâíî� èãð� Γ ñóùåñòâóþ� ìàêñèìèííû� � ìèíèìàêñíû� ñòðàòåãè� èãðîêîâ.
Òåïåð� çàéìåìñ� äîñòàòî÷íûì� óñëîâèÿì� ñóùåñòâîâàíè� ñåäëîâî� òî÷ê� ôóíêöè� äâó� ïåðåìåííûõ. È� ìîæí� ñôîðìóëèðîâàò� � òåðìèíà� âûïóêëîã� àíàëèçà. Íàïîìíè� íåêîòîðû� îïðåäåëåíèÿ. Îïðåäåëåíèå. Ìíîæåñòâ� Z åâêëèäîâ� ïðîñòðàíñòâ� íàçûâàåòñ� âûïóêëûì, åñë� äë� ëþáû� òî÷å� z � 6= z 0� è� Z � ëþáîã� ÷èñë� 0 < λ < 1 òî÷ê� λz � + (1 − λ)z 0� òàêæ� ïðèíàäëåæè� ìíîæåñòâ� Z. Îïðåäåëåíèå. Ôóíêöè� h(z), îïðåäåëåííà� í� âûïóêëî� ìíîæåñòâ� Z, íàçûâàåòñ� âûïóêëîé, åñë� äë� ëþáû� òî÷å� z � 6= z 0� è� Z � ëþáîã� ÷èñë� 0 < λ < 1 âûïîëíåí� íåðàâåíñòâ� h(λz � + (1 − λ)z 00 ) ≤ λh(z 0 ) + (1 − λ)h(z 00 ).
(2.4) Åñë� ïîñëåäíå� íåðàâåíñòâ� âûïîëíåí� êà� ñòðîãîå, ò� ôóíêöè� h(z) íàçûâàåòñ� ñòðîã� âûïóêëîé. Åñë� âìåñò� íåðàâåíñòâ� ≤ � (2.4) ôèãóðèðóå� íåðàâåíñòâ� ≥ (>), ò� ôóíêöè� h(z) íàçûâàåòñ� âîãíóòî� (ñòðîã� âîãíóòîé). mPÓïðàæíåíè� 2.5. Äîêàæèòå, ÷ò� ôóíêöè� zi 2 ñòðîã� âûïóêëà. i=1 Óïðàæíåíè� 2.6. Äîêàæèòå, ÷ò� ñòðîã� âûïóêëà� íåïðåðûâíà� ôóíêöè� í� âûïóêëî� êîìïàêòå� åâêëèäîâ� ïðîñòðàíñòâ� äîñòèãàå� ìèíèìóì� � åäèíñòâåííî� òî÷êå. 1 Çàìêíóòî� îãðàíè÷åííî� ìíîæåñòâå. 15 ÃËÀÂ� I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈ� ÈÃÐ�Òåîðåì� 2.3.
Ïóñò� X ⊂ E m � Y ⊂ E n − âûïóêëû� êîìïàêò� åâêëèäîâû� ïðîñòðàíñòâ, � ôóíêöè� F (x, y) íåïðåðûâí� í� X ×Y. Ïðåäïîëîæèì, ÷ò� ïð� ëþáî� y ∈ Y ôóíêöè� F (x, y) âîãíóò� ï� x � ïð� ëþáî� x ∈ X îí� âûïóêë� ï� y. Òîãä� ôóíêöè� F (x, y) èìåå� í� X ×Y ñåäëîâó� òî÷êó. Äîêàçàòåëüñòâî. Âíà÷àë� äîêàæå� ñóùåñòâîâàíè� ñåäëîâî� òî÷ê� � ñëó÷àå, êîãä� ôóíêöè� F (x, y) ñòðîã� âûïóêë� ï� y. Òîãä� äë� âñÿêîã� x ∈ X ôóíêöè� F (x, y) äîñòèãàå� ìèíèìóì� í� Y � åäèíñòâåííî� òî÷ê� y(x). Ï� òåîðåì� 2.2 ôóíêöè� W (x) = min F (x, y) � y(x) íåïðåðûâí� y∈Y í� X .
Âîçüìå� òî÷ê� x∗ , ìàêñèìèçèðóþùó� ôóíêöè� W (x) í� X, � äîêàæåì, ÷ò� ïàð� (x∗ , y(x∗ )) ÿâëÿåòñ� ñåäëîâî� òî÷êî� ôóíêöè� F (x, y). Äë� ëþáû� x � 0 < t < 1 ïîëîæè� ỹ = y((1−t)x∗ +tx). � ñèë� âîãíóòîñò� ï� x ôóíêöè� F (x, y) èìåå� W (x∗ ) ≥ W ((1 − t)x∗ + tx) = F ((1 − t)x∗ + tx, ỹ) ≥ ≥ (1 − t)F (x∗ , ỹ) + tF (x, ỹ) ≥ (1 − t)W (x∗ ) + tF (x, ỹ). Îòñþä� tF (x, ỹ) ≤ tW (x∗ ). Ñîêðàòè� í� ïîëîæèòåëüíî� t � óñòðåìè� t → 0+, ïîëó÷è� íåðàâåíñòâ� äë� ñåäëîâî� òî÷ê� F (x, y(x∗ )) ≤ W (x∗ ) = F (x∗ , y(x∗ )) ≤ F (x∗ , y) ∀ x ∈ X, ∀ y ∈ Y.
Äîêàæå� òåîðåì� � îáùå� ñëó÷àå. Ïð� ε > 0 ôóíêöè� n� def Fε (x, y) = F (x, y) + εyj 2 íåïðåðûâíà, âîãíóò� ï� x � ñòðîã� âûïóêë� j=1 ï� y. Ï� äîêàçàííîì� ôóíêöè� Fε (x, y) èìåå� ñåäëîâó� òî÷ê� (xε , y ε ) í� X × Y : Fε (x, y ε ) ≤ Fε (x ε , y ε ) ≤ Fε (x ε , y) ∀ x ∈ X, ∀ y ∈ Y. Âîçüìå� ïîñëåäîâàòåëüíîñò� ïîëîæèòåëüíû� ÷èñå� {εk }, ñõîäÿùóþñ� � íóëþ.
È� êîìïàêòíîñò� ìíîæåñò� X � Y ñëåäóåò, ÷ò� áå� ïîòåð� îáùíîñò� xεk → x0 , y εk → y 0 . Ïîëàãà� � ïîñëåäíè� íåðàâåíñòâà� ε = εk èïåðåõîä� � ïðåäåë� ïð� k → ∞, ïîëó÷è� íåðàâåíñòâ� (2.1) è� îïðåäåëåíè� ñåäëîâî� òî÷êè. Çàìåòèì, ÷ò� ïåðâà� ÷àñò� äîêàçàòåëüñòâ� òåîðåì� êîíñòðóêòèâíà: äë� ïîèñê� ñåäëîâî� òî÷ê� ôóíêöè� F (x, y), ñòðîã� âûïóêëî� ï� y, äîñòàòî÷í� íàéò� ìàêñèìèííó� ñòðàòåãè� x∗ � íàèëó÷øè� îòâå� í� íå� 16 3. Ñìåøàííû� ðàñøèðåíè� àíòàãîíèñòè÷åñêè� èã�y(x∗ ) âòîðîã� èãðîêà. Àíàëîãè÷íî, ïóñò� � óñëîâèÿ� òåîðåì� 2.3 ôóíêöè� F (x, y) ñòðîã� âîãíóò� ï� x, y ∗ − ìèíèìàêñíà� ñòðàòåãèÿ, � x(y ∗ ) ∈Arg max F (x, y ∗ ) − íàèëó÷øè� îòâå� í� íå� ïåðâîã� èãðîêà. Òîãä� x∈X (x(y ∗ ), y ∗ ) − ñåäëîâà� òî÷ê� ôóíêöè� F (x, y).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
