Введение в теорию игр (сторонняя методичка) (1184510), страница 3
Текст из файла (страница 3)
Îáðàòíî, ε-ìàêñèìèííàÿ è ε-ìèíèìàêñíàÿ ñòðàòåãèè îáðàçóþò2ε-ñåäëîâóþ òî÷êó.Óïðàæíåíèå 2.4. Äîêàæèòå òåîðåìó 2.10 .Ïðåäñòàâëÿþò èíòåðåñ óñëîâèÿ òîïîëîãè÷åñêîãî õàðàêòåðà, ïðè êîòîðûõ ñóùåñòâóþò ìàêñèìèííûå è ìèíèìàêñíûå ñòðàòåãèè.Òåîðåìà 2.2. Ïóñòü ôóíêöèÿ F (x, y) íåïðåðûâíà íà X × Y, ãäåX, Y − êîìïàêòû ìåòðè÷åñêèõ ïðîñòðàíñòâ1 . ÏîëîæèìdefY (x) = Argmin F (x, y). Òîãäày∈Y1 Íåäîñòàòî÷íîïîäãîòîâëåííûé ÷èòàòåëü çäåñü è äàëåå ìîæåò çàìåíèòü âûðàæåíèå "êîìïàêò ìåòðè÷åñêîãî ïðîñòðàíñòâà"íà âûðàæåíèå "çàìêíóòîå îãðàíè÷åííîåìíîæåñòâî åâêëèäîâà ïðîñòðàíñòâà".13ÃËÀÂÀ I.
ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛ1) Ôóíêöèÿ ìèíèìóìà W (x) = min F (x, y) íåïðåðûâíà íà X.y∈Y2) Ïðåäïîëîæèì äîïîëíèòåëüíî, ÷òî ïðè êàæäîì 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 klW (xkl ) = F (xkl , y kl ) ≤ F (xkl , y) ∀ y ∈ Y.Ïåðåõîäÿ â ýòîì íåðàâåíñòâå ê ïðåäåëó ïðè l → ∞ è èñïîëüçóÿ íåïðåðûâíîñòü ôóíêöèè F (x, y), ïîëó÷èìF (x0 , y 0 ) ≤ F (x0 , y) ∀ y ∈ Y⇒ y 0 ∈ Y (x0 ).Íàêîíåö, 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 0 6= y(x0 ).Íî, êàê è â ÷àñòè 1), íåòðóäíî äîêàçàòü, ÷òî y 0 ∈ Y (x0 ). Ïîëó÷èëè ïðîòèâîðå÷èå ñ òåì, ÷òî ìíîæåñòâî 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,y(x) =W (x) = min F (x, y) =y∈Y0,x = 0,1,x 6= 0,x = 0,ðàçðûâíû.Îïðåäåëåíèå.
Àíòàãîíèñòè÷åñêàÿ èãðà Γ íàçûâàåòñÿ íåïðåðûâíîé, åñëè X, Y − ïàðàëëåëåïèïåäû åâêëèäîâûõ ïðîñòðàíñòâ, à ôóíêöèÿ F (x, y)íåïðåðûâíà íà X × Y .  ÷àñòíîñòè, ïðèX = [a, b], Y = [c, d] áóäåì ãîâîðèòü î íåïðåðûâíîé èãðå íà ïðÿìîóãîëüíèêå.Èç òåîðåìû 2.2 ñëåäóåò, ÷òî â íåïðåðûâíîé èãðå Γ ñóùåñòâóþò ìàêñèìèííûå è ìèíèìàêñíûå ñòðàòåãèè èãðîêîâ.Òåïåðü çàéìåìñÿ äîñòàòî÷íûìè óñëîâèÿìè ñóùåñòâîâàíèÿ ñåäëîâîéòî÷êè ôóíêöèè äâóõ ïåðåìåííûõ. Èõ ìîæíî ñôîðìóëèðîâàòü â òåðìèíàõâûïóêëîãî àíàëèçà. Íàïîìíèì íåêîòîðûå îïðåäåëåíèÿ.Îïðåäåëåíèå. Ìíîæåñòâî Z åâêëèäîâà ïðîñòðàíñòâà íàçûâàåòñÿ âûïóêëûì, åñëè äëÿ ëþáûõ òî÷åê z 0 6= z 00 èç Z è ëþáîãî ÷èñëà 0 < λ < 1òî÷êà λz 0 + (1 − λ)z 00 òàêæå ïðèíàäëåæèò ìíîæåñòâó Z.Îïðåäåëåíèå.
Ôóíêöèÿ h(z), îïðåäåëåííàÿ íà âûïóêëîì ìíîæåñòâåZ, íàçûâàåòñÿ âûïóêëîé, åñëè äëÿ ëþáûõ òî÷åê z 0 6= z 00 èç Z è ëþáîãî÷èñëà 0 < λ < 1 âûïîëíåíî íåðàâåíñòâîh(λz 0 + (1 − λ)z 00 ) ≤ λh(z 0 ) + (1 − λ)h(z 00 ).(2.4)Åñëè ïîñëåäíåå íåðàâåíñòâî âûïîëíåíî êàê ñòðîãîå, òî ôóíêöèÿ h(z) íàçûâàåòñÿ ñòðîãî âûïóêëîé. Åñëè âìåñòî íåðàâåíñòâà ≤ â (2.4) ôèãóðèðóåò íåðàâåíñòâî ≥ (>), òî ôóíêöèÿ h(z) íàçûâàåòñÿ âîãíóòîé (ñòðîãîâîãíóòîé).mPÓïðàæíåíèå 2.5.
Äîêàæèòå, ÷òî ôóíêöèÿzi2 ñòðîãî âûïóêëà.i=1Óïðàæíåíèå 2.6. Äîêàæèòå, ÷òî ñòðîãî âûïóêëàÿ íåïðåðûâíàÿ ôóíêöèÿ íà âûïóêëîì êîìïàêòå1 åâêëèäîâà ïðîñòðàíñòâà äîñòèãàåò ìèíèìóìà â åäèíñòâåííîé òî÷êå.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 ôóíêöèÿnPdefFε (x, y) = F (x, y) + εyj2 íåïðåðûâíà, âîãíóòà ïî 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).Èç ïåðâîé ÷àñòè äîêàçàòåëüñòâà âûòåêàåò, ÷òî äëÿ ñóùåñòâîâàíèÿñåäëîâîé òî÷êè âìåñòî ñòðîãîé âûïóêëîñòè ôóíêöèè F (x, y) ïî ïåðåìåííîé y äîñòàòî÷íî ïîòðåáîâàòü ïðè ëþáîì x ∈ X åäèíñòâåííîñòü íàèëó÷øåãî îòâåòà y(x) âòîðîãî èãðîêà.
Åñëè ïîñëåäíåå óñëîâèå íå âûïîëíåíî, òî ïàðà (x∗ , y ∗ ), ãäå y ∗ ∈ Y (x∗ ), ìîæåò íå áûòü ñåäëîâîé òî÷êîé.Íàïðèìåð, äëÿ ôóíêöèè F (x, y) = xy íà X × Y = [0, 1] × [0, 1] ïàðà(x∗ , y ∗ ) = (0, 1) ñåäëîâîé òî÷êîé íå ÿâëÿåòñÿ.Ïðèìåð 2.6. X = Y = [0, 1], F (x, y) = −x2 +y 3 +xy 2 −4y.
Çäåñü ôóíêöèÿ F (x, y) âûïóêëà ïî y è ñòðîãî âîãíóòà ïî x. Ôóíêöèÿ íàèëó÷øåãîîòâåòà ïåðâîãî èãðîêà − x(y) = y 2 /2 èM (y) = max F (x, y) = F (x(y), y) = y 4 /4 + y 3 − 4y.0≤x≤1Ïðîèçâîäíàÿ M 0 (y) = y 3 + 3y 2 − 4 îáðàùàåòñÿ â íóëü â òî÷êàõ 1,−2.Îòñþäà y 0 = 1 − ìèíèìàêñíàÿ ñòðàòåãèÿ è x(y 0 ) = 1/2. Ñëåäîâàòåëüíî,(1/2, 1) − ñåäëîâàÿ òî÷êà ôóíêöèè F (x, y). 3.Ñìåøàííûå ðàñøèðåíèÿ àíòàãîíèñòè÷åñêèõ èãð ïðåäûäóùåì ïàðàãðàôå ïðèâîäèëñÿ ïðèìåð àíòàãîíèñòè÷åñêîé èãðû, íå èìåþùåé ðåøåíèÿ ("îðëÿíêà").
Èãðàòü â ïîäîáíûå èãðû âåñüìàíåïðîñòî. Ïðîèãðàâøåìó èãðîêó êàæäûé ðàç õî÷åòñÿ ñìåíèòü ñâîþ ñòðàòåãèþ, íî îí áóäåò áîÿòüñÿ ýòî ñäåëàòü (à âäðóã ïàðòíåð äîãàäàåòñÿ?).Òåîðèÿ èãð ïðåäëàãàåò èãðîêàì èñïîëüçîâàòü ñìåøàííûå ñòðàòåãèè.Îïðåäåëåíèå. Ñìåøàííîé ñòðàòåãèåé ïåðâîãî èãðîêà â èãðå Γ íàçûâàåòñÿ âåðîÿòíîñòíîå ðàñïðåäåëåíèå ϕ íà ìíîæåñòâå ñòðàòåãèé X.Äëÿ ïåðâîãî èãðîêà ïðèìåíèòü ñìåøàííóþ ñòðàòåãèþ ϕ − ýòî âûáðàòü ñòðàòåãèþ x ∈ X êàê ðåàëèçàöèþ ñëó÷àéíîé âåëè÷èíû, èìåþùåéçàêîí ðàñïðåäåëåíèÿ ϕ. Äàëåå ðàññìàòðèâàþòñÿ òðè âèäà ñìåøàííûõñòðàòåãèé.1) Ïóñòü X = {1, ..., m}, êàê ýòî èìååò ìåñòî â ìàòðè÷íîé èãðå.
Òîãäà âìåñòî ϕ äëÿ îáîçíà÷åíèÿ ñìåøàííîé ñòðàòåãèè áóäåì èñïîëüçîâàòü"âåðîÿòíîñòíûé"âåêòîð p = (p1 , ..., pm ), óäîâëåòâîðÿþùèé îãðàíè÷åíèÿì17ÃËÀÂÀ I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛmPpi = 1, pi ≥ 0, i = 1, ..., m. Åñëè ïðèìåíÿåòñÿ p, òî ñòðàòåãèÿ i âûáè-i=1ðàåòñÿ ñ âåðîÿòíîñòüþ pi . Íàïðèìåð, â èãðå "îðëÿíêà"îïûòíûå èãðîêèèñïîëüçóþò ñìåøàííóþ ñòðàòåãèþ p0 = (1/2, 1/2), ïîäáðàñûâàÿ ìîíåòóè âûáèðàÿ "îðåë"èëè "ðåøêó"â çàâèñèìîñòè ðåçóëüòàòà áðîñàíèÿ.Âîîáùå, îäíà èç âîçìîæíûõ ðåàëèçàöèé ñìåøàííîé ñòðàòåãèè − ýòîáðîñàíèå ìîíåò.
Ñ ïîìîùüþ îäíîãî áðîñàíèÿ îäíîé ìîíåòû ìîæíî îñóùåñòâèòü òîëüêî âåðîÿòíîñòü 1/2. Ñ ïîìîùüþ äâóõ ìîíåò èëè äâóêðàòíîãî áðîñàíèÿ îäíîé ìîíåòû ìîæíî óæå ðåàëèçîâàòü âåðîÿòíîñòè 1/2,1/4 è 3/4. ßñíî, ÷òî áðîñàíèåì íåñêîëüêèõ ìîíåò èëè ìíîãîêðàòíûì áðîñàíèåì îäíîé ìîíåòû ìîæíî ðåàëèçîâàòü øèðîêèé ñïåêòð âåðîÿòíîñòåé.Äðóãîé âîçìîæíûé è áîëåå óäîáíûé ñïîñîá ðåàëèçàöèè ñìåøàííîé ñòðàòåãèè − èñïîëüçîâàòü ðóëåòêó. Äåëèì êðóã ðóëåòêè íà ñåêòîðà ñ ïëîùàäÿìè, ïðîïîðöèîíàëüíûìè çàäàííûì âåðîÿòíîñòÿì èñïîëüçîâàíèÿ ÷èñòûõ ñòðàòåãèé. Çàòåì âðàùàåì ñòðåëêó è èñïîëüçóåì òó ñòðàòåãèþ, âñåêòîðå êîòîðîé îíà îñòàíîâèòñÿ.2) Ïóñòü X = [a, b], êàê ýòî èìååò ìåñòî â íåïðåðûâíîé èãðå íà ïðÿìîóãîëüíèêå. Çäåñü ñìåøàííàÿ ñòðàòåãèÿ − ôóíêöèÿ ðàñïðåäåëåíèÿ ϕíà îòðåçêå [a, b].Ïðèìåð 3.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
