А.А. Васин, В.В. Морозов - Введение в теорию игр с приложениями к экономике (1184512), страница 7
Текст из файла (страница 7)
Çàìåòèì, ÷ò� ∀x ∈ X ∃ y ∈ Y : ¬(x � y) ⇒ v = 0; ∀y ∈ Y ∃ x ∈ X : x � y ⇒ v = 1.Îòñþä� ñëåäóåò, ÷ò� èãð� í� èìåå� ðåøåíè� � ÷èñòû� ñòðàòåãèÿõ. Íàéäå� å� ðåøåíè� � ñìåøàííû� ñòðàòåãèÿõ. Ìíîæåñòâ� ñòðàòåãè� X (ñîâïàäàþùå� � Y ) èçîáðàçè� í� ïëîñêîñò� � âèä� ðàâíîñòîðîííåã� òðåóãîëüíèê� âûñîò� A. Òî÷ê� y èìåå� áàðèöåíòðè÷åñêè� êîîðäèíàò� y1 , y2 , y3 , îïðåäåëÿþùè� å� ðàññòîÿíè� î� 30 4.
Ñâîéñòâ� ðåøåíè� � ñìåøàííû� ñòðàòåãèÿ�òðå� ñòîðî� òðåóãîëüíèêà. Í� ðèñ. 4.1 èçîáðàæåí� ëèíè� x1 = y1 , x2 = y2 , x3 = y3 . (A, 0, 0) x3 = y3 Jx2 = y2 � JJ� J� JJ JJJ y Jx1 = y1 J� JJJJJJJJJJ(0, A, 0) (0, 0, A) Ðèñ. 4.1 Ìíîæåñòâ� ñòðàòåãè� âí� ýòè� ëèíè� ðàçîáüå� í� äâ� ïîäìíîæåñòâ� X1 (y) = {x ∈ X | x � y},X2 (y) = {x ∈ X | y � x}. Çàìåòèì, ÷ò� X1 (y) ÿâëÿåòñ� îáúåäèíåíèå� òðå� òðåóãîëüíèêîâ. Íàïðèìåð, íèæíè� òðåóãîëüíè� í� ðèñ. 4.1 ñîñòîè� è� òàêè� âåêòîðî� x, äë� êîòîðû� x2 > y2 , x3 > y3 . Ìíîæåñòâ� C = {x ∈ X | 0 ≤ xi ≤ 2A/3, i = 1, 2, 3}ïðåäñòàâëÿå� ñîáî� ïðàâèëüíû� øåñòèóãîëüíè� � öåíòðî� y 0 , ñîâïàäàþùè� � öåíòðî� òðåóãîëüíèê� X (ðèñ.
4.2). J JJJJJ J J� J � y 0 �� J� �JJJJ � y 1 a a � �y J � � J � � JJJÐèñ. 4.2 Ïóñò� ϕ0 − ðàâíîìåðíî� ðàñïðåäåëåíè� í� C. Äîêàæåì, ÷ò� òðîéê� 31 ÃËÀÂ� I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈ� ÈÃÐ�(ϕ0 , ϕ0 , 1/2) − ðåøåíè� èãð� � ñìåøàííû� ñòðàòåãèÿõ. Äë� ýòîã� äîñòàòî÷í� ïðîâåðèò� óñëîâè� (∗) òåîðåì� 4.1. Îáîçíà÷è� ÷åðå� mes(S) ïëîùàä� ôèãóð� S ⊂ X.
Òîãä� F (ϕ0 , y) = mes(X1 (y) ∩ C) ∀y ∈ Y. mes(C) Íåòðóäí� ïîêàçàòü, ÷ò� mes(X1 (y) ∩ C) = 0.5mes(C) äë� âñå� y ∈ C. Äåéñòâèòåëüíî, äë� öåíòð� øåñòèóãîëüíèê� y 0 ýò� óòâåðæäåíè� î÷åâèäíî. Ïóñò� y 6= y 0 . Îïðåäåëè� âåêòî� y 1 ∈ C :y11 = y1 , y21 = y2 0 = A/3, y3 1 = 2A/3 − y1 .Ñðàâíèâà� ôèãóð� X1 (y) ∩ C, X1 (y 1 ) ∩ C � X1 (y 0 ) ∩ C, óáåæäàåìñÿ, ÷ò� è� ïëîùàä� ðàâíû. Ñëåäîâàòåëüíî, ïð� y ∈ C F (ϕ0 , y) = 1/2. Ìåòîäî� ñðàâíåíè� ïëîùàäå� ìîæí� òàêæ� ïîêàçàòü, ÷ò� mes(X1 (y) ∩ C) > 0.5mes(C), åñë� y ∈ / C.
Èòàê, äîêàçàíî, ÷ò� F (ϕ0 , y) ≥ 1/2 ∀y ∈ Y. Ïîñêîëüê� mes(X2 (x) ∩ C)F (x, ϕ0 ) = ∀x ∈ X, mes(C) äë� äîêàçàòåëüñòâ� íåðàâåíñòâ� F (x, ϕ0 ) ≤ 1/2 ∀x ∈ X äîñòàòî÷í� çàìåòèòü, ÷ò� mes(X1 (x) ∩ C) + mes(X2 (x) ∩ C) = mes(C) ∀x ∈ X. Ïóñò� Γ − ñìåøàííî� ðàñøèðåíè� ïðîèçâîëüíî� àíòàãîíèñòè÷åñêî� èãð� Γ. Îïðåäåëåíèå.
Ñìåøàííà� ñòðàòåãè� ψ 0 âòîðîã� èãðîê� íàçûâàåòñ� âûðàâíèâàþùåé, åñë� F (x, ψ 0 ) ≡ const í� ìíîæåñòâ� X. Àíàëîãè÷í� îïðåäåëÿåòñ� âûðàâíèâàþùà� ñòðàòåãè� ïåðâîã� èãðîêà. Óòâåðæäåíè� 4.1. Åñë� � èãð� Γ � îáîè� èãðîêî� ñóùåñòâóþ� âûðàâíèâàþùè� ñòðàòåãè� ϕ0 , ψ 0 , ò� îí� îïòèìàëüíû. Äîêàçàòåëüñòâî. Äåéñòâèòåëüíî, ï� îïðåäåëåíè� F (ϕ0 , y) = c1 ∀y ∈ Y, F (x, ψ 0 ) = c2 ∀x ∈ X. Èíòåãðèðó� ýò� ðàâåíñòâ� ï� ψ 0 � ϕ0 ñîîòâåòñòâåííî, ïîëó÷è� F (ϕ0 , ψ 0 ) = c1 = c2 .
Ïð� v = F (ϕ0 , ψ 0 ) íåðàâåíñòâ� è� óñëîâè� (∗) òåîðåì� 4.1 äë� òðîéê� (ϕ0 , ψ 0 , v) âûïîëíåí� êà� ðàâåíñòâà. Äîêàçàííî� óòâåðæäåíè� ìîæí� óñèëèòü. 32 4. Ñâîéñòâ� ðåøåíè� � ñìåøàííû� ñòðàòåãèÿ�Óïðàæíåíè� 4.3. Ïóñò� � èãð� Γ ψ 0 − âûðàâíèâàþùà� ñòðàòåãè� âòîðîã� èãðîê� � íàéäåòñ� òàêà� ñìåøàííà� ñòðàòåãè� ϕ0 ïåðâîã� èãðîêà, ÷ò� F (ϕ0 , ψ 0 ) = min F (ϕ0 , ψ).
Äîêàæèòå, ÷ò� ϕ0 , ψ 0 − îïòèìàëüíû� ψ∈{ψ}ñìåøàííû� ñòðàòåãè� èãðîêîâ. Óïðàæíåíè� 4.4. Ïðèâåäèò� ïðèìå� èãð� � ìàòðèöå� ðàçìåðî� 2 ×3, � êîòîðî� âòîðî� èãðî� èìåå� âûðàâíèâàþùóþ, í� í� îïòèìàëüíó� ñìåøàííó� ñòðàòåãèþ. Ïðèìå� 4.3. Ïåðâû� èãðî� âåäå� ñòðåëüá� ï� öåëè, êîòîðà� ìîæå� íàõîäèòüñ� � îäíî� è� òðå� òî÷åê: ëèá� � êîíöà� îòðåçê� [B, C] äëèí� 2, ëèá� � åã� ñåðåäèí� D.
Ïåðâû� èãðî� âûáèðàå� òî÷ê� ïðèöåë� B, C èë� D. Ïóñò� d − ðàññòîÿíè� î� òî÷ê� ïðèöåë� ä� ïîëîæåíè� öåëè, � âåðîÿòíîñò� å� ïîðàæåíè� ðàâí� 1, a, 0 äë� ðàññòîÿíè� d = 0, 1, 2 ñîîòâåòñòâåííî. Âûèãðû� ïåðâîã� èãðîê� − âåðîÿòíîñò� ïîðàæåíè� öåëè. Òðåáóåòñ� îïðåäåëèò� îïòèìàëüíó� ñòðàòåãè� ñòðåëüá� � çàâèñèìîñò� î� çíà÷åíè� ïàðàìåòð� a ∈ (0, 1).
B C D ⎛ ⎞ B 1 a 0 Ñîñòàâè� ìàòðèö� èãð� A = C a 1 a . D 0 a 1Ïóñò� q 0 = (q10 , q20 , q30 ) − âûðàâíèâàþùà� ñòðàòåãè� âòîðîã� èãðîêà. Ìàòðèö� A ñèììåòðè÷í� � ñìåøàííà� ñòðàòåãè� p0 = q 0 ïåðâîã� èãð�ê� òàêæ� ÿâëÿåòñ� âûðàâíèâàþùåé. È� óòâåðæäåíè� 4.1 âûòåêàåò, ÷ò�ñòðàòåãè� p0 � q 0 îïòèìàëüíû. Íàéäå� q 0 . � ñèë� ñèììåòðè� êîíöî� î�ðåçê� [B, C] ï� îòíîøåíè� � åã� ñåðåäèí� D ìîæí� ñ÷èòàòü, ÷ò� q1 0 = q30 .Ñëåäîâàòåëüíî,2q10 + q20 = 1, q10 + aq2 0 = v, 2aq10 + q2 0 = v.Âûïèøå� ðåøåíè� ïîëó÷åííî� ñèñòåì� óðàâíåíè�q1 01 − a1 − 2a1 − 2a20=, q =, v =.3 − 4a 2 3 − 4a3 − 4a È� óñëîâè� íåîòðèöàòåëüíîñò� q10 , q20 íàõîäèì, ÷ò� a ≤ 1/2. Ïð� a >1/2 ïîêàæèòå, ÷ò� òðîéê� (p0 , q 0 , v) = ((0, 1, 0), (1/2, 0, 1/2), a) − ðåøåíè� èãð� � ñìåøàííû� ñòðàòåãèÿõ.
Óïðàæíåíè� 4.5. Èñïîëüçó� âûðàâíèâàþùè� ñòðàòåãèè, ðåøèò� àíà33 ÃËÀÂ� I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈ� ÈÃÐ�ëîãè÷íó� èãð� � ìàòðèöå�⎛ 1 a A = ⎝0 0 a 1 a 0 0 a 1 a 0 0 , 0 < a < 1.a ⎠1 Òåîðåì� 4.2. Äë� íåïðåðûâíî� èãð� Γ ñïðàâåäëèâ� ñëåäóþùè� äâ� óòâåðæäåíèÿ: 1) inf F (ϕ, ψ) = min F (ϕ, y) ∀ ϕ ∈ {ϕ}; y∈Y ψ∈{ψ} 2) sup F (ϕ, ψ) = max F (x, ψ) ∀ ψ ∈ {ψ}. x∈X ϕ∈{ϕ} Äîêàçàòåëüñòâî. Äîêàæå� 1). Âîçüìå� ëþáó� ñòðàòåãè� ϕ. Çàìåòèì, ÷ò� min F (ϕ, y) äîñòèãàåòñÿ, ïîñêîëüê� ôóíêöè� F (ϕ, y) íåïðåðûâí� y∈Y ï� y. Äàëåå, inf F (ϕ, ψ) ≤ min F (ϕ, y) (4.1) y∈Y ψ∈{ψ} � äë� ëþáîã� ψ ∈ {ψ} ZZF (ϕ, ψ) = F (ϕ, y)dψ(y) ≥ min F (ϕ, y)dψ(y) = min F (ϕ, y).
y∈YYy∈Y Y Îòñþä� inf F (ϕ, ψ) ≥ min F (ϕ, y). y∈Y ψ∈{ψ} (4.2) È� (4.1) � (4.2) ñëåäóå� ïåðâî� óòâåðæäåíè� òåîðåìû. Óòâåðæäåíè� 2) äîêàçûâàåòñ� àíàëîãè÷íî. Ñëåäñòâèå. Çíà÷åíè� v íåïðåðûâíî� èãð� Γ ìîæå� áûò� ïðåäñòàâëåí� � âèä� ñëåäóþùè� äâó� ôîðìóë: v = max min F (ϕ, y) = min max F (x, ψ). ϕ∈{ϕ} y∈Yψ∈{ψ} x∈X Äîêàçàòåëüñòâî. Ï� òåîðåìà� 2.1,3.2 � 4.2 ïîëó÷àå� v = max inf F (ϕ, y) ⇒ v = max inf F (ϕ, y). ϕ∈{ϕ} y∈Y ϕ∈{ϕ} ψ∈{ψ} Âòîðà� ôîðìóë� âûâîäèòñ� àíàëîãè÷íî. 34 4. Ñâîéñòâ� ðåøåíè� � ñìåøàííû� ñòðàòåãèÿ�Óïðàæíåíè� 4.6.
Äîêàæèòå, ÷ò� çíà÷åíè� v íåïðåðûâíî� èãð� Γ óäîâëåòâîðÿå� íåðàâåíñòâà� v = max min F (x, y) ≤ v ≤ min max F (x, y) = v. x∈X y∈Yy∈Y x∈X Òåîðåì� 4.2 0 . Äë� èãð� � ìàòðèöå� A ñïðàâåäëèâ� ñëåäóþùè� äâ� óòâåðæäåíèÿ: 1) min A(p, q) = min A(p, j) ∀ p ∈ P ; q∈Q 1≤j≤n 2) max A(p, q) = max A(i, q) ∀ q ∈ Q. p∈P 1≤i≤m Äîêàæèò� ñàìîñòîÿòåëüíî. Ñëåäñòâèå.
Çíà÷åíè� v èãð� � ìàòðèöå� A ìîæå� áûò� ïðåäñòàâëåí� � âèä� ñëåäóþùè� äâó� ôîðìóë: v = max min A(p, j) = min max A(i, q). p∈P 1≤j≤nq∈Q 1≤i≤m Òåïåð� îáñóäè� òà� íàçûâàåìî� ñâîéñòâ� äîïîëíÿþùå� íåæåñòêîñòè. Îïðåäåëè� ìíîæåñòâ� Sp(ϕ) ⊂ X − ñïåêò� ñìåøàííî� ñòðàòåãè� ϕ, çàäàííî� í� îòðåçê� X. Îïðåäåëåíèå. Áóäå� ãîâîðèòü, ÷ò� òî÷ê� x� ∈ X = [a, b] ïðèíàäëåæè� ñïåêòð� ñòðàòåãè� ϕ, åñë� äë� âñÿêîã� ε > 0 ñóùåñòâóå� òàêî� îòðåçî� [a0 , b0 ], ñîäåðæàùè� x0 , ÷ò� b� − a� < ε � ϕ(b0 ) − ϕ(a0 ) > 0. Ìíîæåñòâ� âñå� òî÷å� ñïåêòð� îáîçíà÷è� ÷åðå� Sp(ϕ).
Óïðàæíåíè� 4.7. Äîêàæèòå, ÷ò� òî÷ê� ñêà÷ê� ôóíêöè� ðàñïðåäåëåíè� ϕ � òî÷êè, ãä� å� ïðîèçâîäíà� ñóùåñòâóå� � ïîëîæèòåëüíà, ïðèíàäëåæà� ñïåêòð� Sp(ϕ). Òåîðåì� 4.3 (Ñâîéñòâ� äîïîëíÿþùå� íåæåñòêîñòè). Ïóñò� (ϕ0 , ψ 0 , v) − ðåøåíè� � ñìåøàííû� ñòðàòåãèÿ� íåïðåðûâíî� èãð� Γ. Òîãä� 1) x ∈ Sp(ϕ0 ) ⇒ F (x, ψ 0 ) = v;2) y ∈ Sp(ψ 0 ) ⇒ F (ϕ0 , y) = v.Äîêàçàòåëüñòâî. Äîêàæå� óòâåðæäåíè� 1). Ïðåäïîëîæè� ïðîòèâíîå, ò.å. íàéäåòñ� òàêà� òî÷ê� x� ∈ Sp(ϕ0 ), ÷ò� F (x0 , ψ 0 ) =6 v.
Òîãä� ï� ñâîéñòâ� (∗) òåîðåì� 4.1 áóäå� âûïîëíåí� íåðàâåíñòâ� F (x0 , ψ 0 ) < v. È� íåïðåðûâíîñò� ôóíêöè� F (x, ψ 0 ) � îïðåäåëåíè� ñïåêòð� ñòðàòåãè� ϕ0 35ÃËÀÂ� I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈ� ÈÃÐ�âûòåêàåò, ÷ò� äë� âñÿêîã� ε > 0 íàéäåòñ� òàêî� îòðåçî� [a0 , b0 ], ñîäåðæàùè� òî÷ê� x0 , � òàêî� ÷èñë� v � < v , ÷ò� äë� âñå� x ∈ [a0 , b0 ] F (x, ψ 0 ) ≤ v � < v, b� − a� < ε, ϕ0 (b0 ) − ϕ0 (a0 ) > 0.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
