[учебник] Введение в теорию игр (с приложениями к экономике). Васин, Морозов (2003) (1186146), страница 6
Текст из файла (страница 6)
Ñâîéñòâà ðåøåíèé â ñìåøàííûõ ñòðàòåãèÿõòðåõ ñòîðîí òðåóãîëüíèêà. Íà ðèñ. 4.1 èçîáðàæåíû ëèíèè x1 = y1 , x2 =y2 , x 3 = y3 .(A, 0, 0)x3 = y3Jx2 = y2JJJJ JJJ JJ y Jx1 = y1JJJJJJJJJJJJ(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 JJ y 0JJJJJJ J y1 a a J Jy J J JJJJÐèñ. 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 = y20 = A/3, y31 = 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 DB 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 ìîæíî ñ÷èòàòü, ÷òî q10 = q30 .Ñëåäîâàòåëüíî,2q10 + q20 = 1, q10 + aq20 = v, 2aq10 + q20 = v.Âûïèøåì ðåøåíèå ïîëó÷åííîé ñèñòåìû óðàâíåíèéq101−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.
ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛëîãè÷íóþ èãðó ñ ìàòðèöåé1aA=00a1a00a1a00 , 0 < a < 1.a1Òåîðåìà 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∈YYÎòñþäà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∈Q1≤j≤n2) max A(p, q) = max A(i, q) ∀ q ∈ Q.p∈P1≤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.Îïðåäåëåíèå. Áóäåì ãîâîðèòü, ÷òî òî÷êà x0 ∈ X = [a, b] ïðèíàäëåæèòñïåêòðó ñòðàòåãèè ϕ, åñëè äëÿ âñÿêîãî ε > 0 ñóùåñòâóåò òàêîé îòðåçîê[a0 , b0 ], ñîäåðæàùèé x0 , ÷òî b0 − a0 < ε è ϕ(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). Ïðåäïîëîæèì ïðîòèâíîå, ò.å. íàéäåòñÿ òàêàÿ òî÷êà x0 ∈ Sp(ϕ0 ), ÷òî F (x0 , ψ 0 ) 6= v. Òîãäà ïîñâîéñòâó (∗) òåîðåìû 4.1 áóäåò âûïîëíåíî íåðàâåíñòâî F (x0 , ψ 0 ) < v. Èçíåïðåðûâíîñòè ôóíêöèè F (x, ψ 0 ) è îïðåäåëåíèÿ ñïåêòðà ñòðàòåãèè ϕ035ÃËÀÂÀ I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛâûòåêàåò, ÷òî äëÿ âñÿêîãî ε > 0 íàéäåòñÿ òàêîé îòðåçîê [a0 , b0 ], ñîäåðæàùèé òî÷êó x0 , è òàêîå ÷èñëî v 0 < v , ÷òî äëÿ âñåõ x ∈ [a0 , b0 ]F (x, ψ 0 ) ≤ v 0 < v,b0 − a0 < ε, ϕ0 (b0 ) − ϕ0 (a0 ) > 0.Òåïåðü0Z0F (ϕ , ψ ) =F (x, ψ 0 )dϕ0 (x) =XZ=00ZF (x, ψ )dϕ (x) +(a0 ,b0 ]0Z0F (x, ψ )dϕ (x) ≤X\(a0 ,b0 ]Z+v 0 dϕ0 (x)+(a0 ,b0 ]vdϕ0 (x) < (ϕ0 (b0 ) − ϕ0 (a0 ))v +X\(a0 ,b0 ]Zvdϕ0 (x) = v,X\(a0 ,b0 ]÷òî ïðîòèâîðå÷èò îïðåäåëåíèþ çíà÷åíèÿ èãðû. Óòâåðæäåíèå 2) äîêàçûâàåòñÿ àíàëîãè÷íî.Ñëåäñòâèå. Ïóñòü (ϕ0 , ψ 0 , v) − ðåøåíèå â ñìåøàííûõ ñòðàòåãèÿõ íåïðåðûâíîé èãðû Γ.
Òîãäà1) F (x, ψ 0 ) < v ⇒ x ∈/ Sp(ϕ0 );2) F (ϕ0 , y) > v ⇒ y ∈/ Sp(ψ 0 ).Ñôîðìóëèðóåì àíàëîãè÷íóþ òåîðåìó äëÿ ìàòðè÷íûõ èãð.Òåîðåìà 4.3 0 (Ñâîéñòâî äîïîëíÿþùåé íåæåñòêîñòè). Ïóñòü(p , q 0 , v) − ðåøåíèå â ñìåøàííûõ ñòðàòåãèÿõ èãðû ñ ìàòðèöåé A. Òîãäà1) p0i > 0 ⇒ A(i, q 0 ) = v;2) qj0 > 0 ⇒ A(p0 , j) = v.0Óïðàæíåíèå 4.8. Äîêàæèòå òåîðåìó 4.3 0 .Ñëåäñòâèå. Ïóñòü (p0 , q 0 , v) − ðåøåíèå â ñìåøàííûõ ñòðàòåãèÿõ èãðûñ ìàòðèöåé A. Òîãäà1) A(i, q 0 ) < v ⇒ p0i = 0;2) A(p0 , j) > v ⇒ qj0 = 0.Ïîÿñíèì âûðàæåíèå "äîïîëíÿþùàÿ íåæåñòêîñòü", çàèìñòâîâàííîå èçòåîðèè äâîéñòâåííîñòè ëèíåéíîãî ïðîãðàììèðîâàíèÿ.
Ïîñòàâèì â ñîîòâåòñòâèå íåðàâåíñòâó A(i, q 0 ) ≤ v (A(p0 , j) ≥ v) èç óñëîâèÿ (∗) íåðàâåíñòâî p0i ≥ 0 (qj0 ≥ 0) ñ òåì æå íîìåðîì. Òîãäà åñëè îäíî èç ýòèõ íåðàâåíñòâ âûïîëíåíî ñòðîãî ("íåæåñòêî"), òî ïî òåîðåìå 4.3 0 è åå ñëåäñòâèþ36 5. Ìåòîäû ðåøåíèÿ ìàòðè÷íûõ èãðñîîòâåòñòâóþùåå íåðàâåíñòâî âûïîëíåíî êàê ðàâåíñòâî ("æåñòêî"). Âñåýòî ìîæíî çàïèñàòü â ñëåäóþùåé êðàòêîé ôîðìå: äëÿ ðåøåíèÿ (p0 , q 0 , v)â ñìåøàííûõ ñòðàòåãèÿõ èãðû ñ ìàòðèöåé A ñïðàâåäëèâû ðàâåíñòâàp0i (v − A(i, q 0 )) = qj0 (A(p0 , j) − v) = 0, i = 1, ..., m, j = 1, ..., n.Ïðèìåð 4.4. Ðåøèì èãðó ñ äèàãîíàëüíîé ìàòðèöåé A, â êîòîðîé äèàãîíàëüíûå ýëåìåíòû ai > 0. Ïðåäïîëîæèì, ÷òî âñå êîìïîíåíòû îïòèìàëüíûõ ñìåøàííûõ ñòðàòåãèé p0 , q 0 ïîëîæèòåëüíû.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
