Введение в теорию игр (сторонняя методичка) (Введение в теорию игр (сторонняя методичка).PDF), страница 6

Êàìåíü ìîæíî ïîìåñòèòüâ ìåøîê, ïîýòîìó ìåøîê âûèãðûâàåò ó êàìíÿ 1, à êàìåíü ïðîèãðûâàåòìåøêó 1. Íîæíèöû ðåæóò ìåøîê, ïîýòîìó îíè âûèãðûâàþò ó ìåøêà 1,à ìåøîê ïðîèãðûâàåò íîæíèöàì 1.Óïðàæíåíèå 4.2. Ïóñòü B − ìàòðèöà, ïîëó÷åííàÿ ïðèáàâëåíèåì êîíñòàíòû c êî âñåì ýëåìåíòàì ìàòðèöû A. Ïîêàçàòü, ÷òî çíà÷åíèÿ ñîîòâåòñòâóþùèõ ìàòðè÷íûõ èãð ñâÿçàíû ñîîòíîøåíèåì v(B) = v(A) + c, àîïòèìàëüíûå ñìåøàííûå ñòðàòåãèè èãðîêîâ ñîâïàäàþò.Ïðèìåð 4.2.

Ïðîäàâåö âûñòàâëÿåò íà ïðîäàæó òðè ïðåäìåòà, íå ïðåäñòàâëÿþùèå äëÿ íåãî îñîáîé öåííîñòè (ñòàðûå òåëåâèçîðû è ò.ï.). Îí ãîòîâ èõ ïðîäàòü äàæå çà íåçíà÷èòåëüíóþ öåíó. Èìåþòñÿ äâà ïîêóïàòåëÿ(èãðîêà), ðàñïîëàãàþùèå îäèíàêîâûìè ñóììàìè äåíåã A. Èãðîê ñòàíîâèòñÿ îáëàäàòåëåì ïðåäìåòà, åñëè ïðåäëàãàåò çà íåãî ñóììó, áóëüøóþ,÷åì ïàðòíåð. Öåëü ïåðâîãî èãðîêà ñîñòîèò â ïîêóïêå äâóõ êàêèõ-ëèáîïðåäìåòîâ èç òðåõ. Öåëü âòîðîãî èãðîêà − âîñïðåïÿòñòâîâàòü ýòîìó.3PÏóñòü x = (x1 , x2 , x3 ) ∈ X = {x |xi = A, x1 , x2 , x3 ≥ 0} −i=1ñòðàòåãèÿ ïåðâîãî èãðîêà, ñîñòîÿùàÿ â ïðåäëîæåíèè ñóììû xi çà i-ûéïðåäìåò.

Àíàëîãè÷íóþ ñòðàòåãèþ y = (y1 , y2 , y3 ) ∈ Y = X èñïîëüçóåòâòîðîé èãðîê.Áóäåì ïèñàòü x  y, åñëè êàêèå-ëèáî äâå êîìïîíåíòû âåêòîðà x áîëüøå ñîîòâåòñòâóþùèõ êîìïîíåíò âåêòîðà y . Îïðåäåëèì ôóíêöèþ âûèãðûøà ïåðâîãî èãðîêà(1, x  y,F (x, y) =0, â ïðîòèâíîì ñëó÷àå.Çàìåòèì, ÷òî∀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 , 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 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 ìîæíî ñ÷èòàòü, ÷òî 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. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛëîãè÷íóþ èãðó ñ ìàòðèöåé1aA=00a1a00a1a00 , 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∈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.