[учебник] Введение в теорию игр (с приложениями к экономике). Васин, Морозов (2003) ([учебник] Введение в теорию игр (с приложениями к экономике). Васин, Морозов (2003).pdf), страница 2

Ïàðà (x0 , y 0 ) ∈ X × Y íàçûâàåòñÿ ñåäëîâîé òî÷êîéôóíêöèè F (x, y) íà X × Y, åñëèF (x, y 0 ) ≤ F (x0 , y 0 ) ≤ F (x0 , y) ∀ x ∈ X, ∀ y ∈ Y(2.1)èëè, ýêâèâàëåíòíî,max F (x, y 0 ) = F (x0 , y 0 ) = min F (x0 , y).x∈Xy∈YÏîíÿòèå ñåäëîâîé òî÷êè èñïîëüçóåòñÿ â îïðåäåëåíèè ðåøåíèÿ àíòàãîíèñòè÷åñêîé èãðû.Îïèøåì àíòàãîíèñòè÷åñêóþ èãðó.  íåé ïðèíèìàþò ó÷àñòèå äâà èãðîêà 1 è 2 (ïåðâûé è âòîðîé). Èãðîê 1 âûáèðàåò ñòðàòåãèþ x èç ìíîæåñòâà ñòðàòåãèé X, èãðîê 2 âûáèðàåò ñòðàòåãèþ y èç ìíîæåñòâà ñòðàòåãèéY. Íîðìàëüíàÿ ôîðìà èãðû ïîäðàçóìåâàåò, ÷òî êàæäûé èãðîê âûáèðàåò ñâîþ ñòðàòåãèþ íåçàâèñèìî, íå çíàÿ âûáîðà ïàðòíåðà. Çàäàíà ôóíêöèÿ âûèãðûøà F (x, y) ïåðâîãî èãðîêà, îïðåäåëåííàÿ íà X × Y.

ÂûèãðûøF (x, y) ïåðâîãî èãðîêà ÿâëÿåòñÿ ïðîèãðûøåì äëÿ âòîðîãî. Öåëü ïåðâîãîèãðîêà ñîñòîèò â óâåëè÷åíèè ñâîåãî âûèãðûøà F (x, y), à öåëü âòîðîãî −â óìåíüøåíèè F (x, y).Òàêèìîáðàçîì, àíòàãîíèñòè÷åñêàÿèãðà çàäàåòñÿ íàáîðîìΓ = X, Y, F (x, y) . Òåðìèíû "âûèãðûø"è "èãðîê"ñëîæèëèñü èñòîðè÷åñêè, êîãäà àíàëèçèðîâàëèñü ïðåèìóùåñòâåííî àçàðòíûå èãðû. Ýòèòåðìèíû íå ñîâñåì òî÷íûå. Íàïðèìåð, åñëè çíà÷åíèå F (x, y) < 0, òî "âûèãðûø"ïåðâîãî èãðîêà ÿâëÿåòñÿ ôàêòè÷åñêè åãî ïðîèãðûøåì. Êðîìå òîãî, ðàññìàòðèâàþò èãðû, ãäå F (x, y) ÿâëÿåòñÿ íå äåíåæíûì âûèãðûøåì,à, ñêàæåì, âåðîÿòíîñòüþ ïîðàæåíèÿ öåëè. Èãðîê 2 ìîæåò íå áûòü èíòåëëåêòóàëüíûì ïðîòèâíèêîì.

×àñòî ðàññìàòðèâàþò èãðû ïðîòèâ "ïðèðîäû".Âåðíåìñÿ ê îïðåäåëåíèþ ñåäëîâîé òî÷êè, êîòîðîé ìîæíî ïðèäàòüñëåäóþùèé èãðîâîé ñìûñë. Åñëè èãðîêè âûáðàëè â êà÷åñòâå ñòðàòåãèéêîìïîíåíòû x0 , y 0 ñåäëîâîé òî÷êè, òî êàæäîìó èç íèõ íåâûãîäíî îòêëîíÿòüñÿ îò âûáðàííîé ñòðàòåãèè. Ïîýòîìó ñåäëîâàÿ òî÷êà ÿâëÿåòñÿ ôîðìàëèçàöèåé êîíöåïöèè ðàâíîâåñèÿ â èãðå.8Ÿ 2. Ñåäëîâûå òî÷êè è àíòàãîíèñòè÷åñêèå èãðûÎïðåäåëåíèå. Ãîâîðÿò, ÷òî àíòàãîíèñòè÷åñêàÿ èãðà Γ èìååò ðåøåíèå,åñëè ôóíêöèÿ F (x, y) èìååò íà X × Y ñåäëîâóþ òî÷êó. Ïóñòü (x0 , y 0 ) −ñåäëîâàÿ òî÷êà ôóíêöèè F (x, y).

Òîãäà òðîéêà(x0 , y 0 , v = F (x0 , y 0 )) íàçûâàåòñÿ ðåøåíèåì èãðû, x0 , y 0 − îïòèìàëüíûìè ñòðàòåãèÿìè èãðîêîâ, à v − çíà÷åíèåì èãðû.Ïîêàæåì, ÷òî çíà÷åíèå èãðû íå çàâèñèò îò âûáîðà ñåäëîâîé òî÷êè.Ëåììà 2.1. Åñëè (x0 , y 0 ), (x∗ , y ∗ ) − äâå ñåäëîâûå òî÷êè ôóíêöèèF (x, y) íà X × Y, òî F (x0 , y 0 ) = F (x∗ , y ∗ ).Äîêàçàòåëüñòâî. Íàðÿäó ñ (2.1), âûïèøåì àíàëîãè÷íûå íåðàâåíñòâàäëÿ ñåäëîâîé òî÷êè (x∗ , y ∗ )F (x, y ∗ ) ≤ F (x∗ , y ∗ ) ≤ F (x∗ , y) ∀ x ∈ X, ∀ y ∈ Y.(2.2)Èìååì(2.2)(2.1)(2.1)(2.2)F (x∗ , y ∗ ) ≤ F (x∗ , y 0 ) ≤ F (x0 , y 0 ) ≤ F (x0 , y ∗ ) ≤ F (x∗ , y ∗ ).Çäåñü âñå íåðàâåíñòâà âûïîëíåíû êàê ðàâåíñòâà.Âàæíåéøèé êëàññ àíòàãîíèñòè÷åñêèõ èãð îáðàçóþò ìàòðè÷íûå èãðû.Îïðåäåëåíèå.

Àíòàãîíèñòè÷åñêàÿ èãðà Γ íàçûâàåòñÿ ìàòðè÷íîé, åñëèìíîæåñòâà ñòðàòåãèé èãðîêîâ êîíå÷íû: X = {1, ..., m}, Y = {1, ..., n}.Ïðè ýòîì ïðèíÿòî îáîçíà÷àòü ñòðàòåãèþ ïåðâîãî èãðîêà ÷åðåç i, ñòðàòåãèþ âòîðîãî ÷åðåç j, à âûèãðûø ïåðâîãî F (i, j) ÷åðåç aij . ÌàòðèöàA = (aij )m×n íàçûâàåòñÿ ìàòðèöåé èãðû. Ïåðâûé èãðîê âûáèðàåò â íåéíîìåð ñòðîêè i, à âòîðîé − íîìåð ñòîëáöà j . îáîçíà÷åíèÿõ ìàòðè÷íîé èãðû (i0 , j 0 ) − ñåäëîâàÿ òî÷êà ìàòðèöûA, åñëèaij 0 ≤ ai0 j 0 ≤ ai0 j , i = 1, ...m, j = 1, ..., n.0 0Ïðèìåð 2.1.

A =.0 4Çäåñü (1,1) è (2,1) − äâå ñåäëîâûå òî÷êè è çíà÷åíèå èãðû v ðàâíî íóëþ. Çàìåòèì, ÷òî a12 = v , íî (1,2) íå ÿâëÿåòñÿ ñåäëîâîé òî÷êîé ìàòðèöû.Ïðèìåð 2.2. Èãðà "îðëÿíêà". Ïåðâûé èãðîê çàêëàäûâàåò ìîíåòó îðëîì (Î) èëè ðåøêîé (Ð), à âòîðîé ïûòàåòñÿ îòãàäàòü. Åñëè âòîðîé èãðîêîòãàäàåò, òî ïåðâûé ïëàòèò åìó åäèíèöó, åñëè íå îòãàäàåò, òî − íàîáîðîò.9ÃËÀÂÀ I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛOP−11. Íåòðóäíî âèäåòü, ÷òî ýòà ìàòðèöà íå èìååò1 −1OPñåäëîâîé òî÷êè.Âåðíåìñÿ ê îáùåìó îïðåäåëåíèþ ñåäëîâîé òî÷êè è àíòàãîíèñòè÷åñêîé èãðû.

Âîçíèêàþò äâà âîïðîñà. Êîãäà àíòàãîíèñòè÷åñêàÿ èãðà èìååòðåøåíèå, ò.å. êîãäà ôóíêöèÿ F (x, y) èìååò ñåäëîâóþ òî÷êó íà X × Y ?Êàê èñêàòü ñåäëîâûå òî÷êè, åñëè èçâåñòíî, ÷òî îíè ñóùåñòâóþò?Ðàññìîòðèì èãðó Γ ñ òî÷êè çðåíèÿ ïåðâîãî èãðîêà. Ïóñòü îí âûáðàëñòðàòåãèþ x. ßñíî, ÷òî åãî âûèãðûø áóäåò íå ìåíüøå, ÷åì inf F (x, y).Çäåñü A =y∈YÂåëè÷èíó inf F (x, y) íàçîâåì ãàðàíòèðîâàííûì ðåçóëüòàòîì (âûèãðûy∈Yøåì) äëÿ ïåðâîãî èãðîêà. Íàèëó÷øèé ãàðàíòèðîâàííûé ðåçóëüòàò äëÿïåðâîãî èãðîêà v = sup inf F (x, y) íàçûâàåòñÿ íèæíèì çíà÷åíèåì èãðû.x∈X y∈YÎïðåäåëåíèå. Ñòðàòåãèÿ x0 ïåðâîãî èãðîêà íàçûâàåòñÿ ìàêñèìèííîé,åñëè inf F (x0 , y) = v.y∈YÐàññìîòðèì èãðó Γ ñ òî÷êè çðåíèÿ âòîðîãî èãðîêà. Åñëè îí âûáðàëñòðàòåãèþ y, òî äëÿ íåãî åñòåñòâåííî ñ÷èòàòü ãàðàíòèðîâàííûì ðåçóëüòàòîì âåëè÷èíó sup F (x, y).

Ïðîèãðûø âòîðîãî èãðîêà áóäåò íå áîëüùå,x∈X÷åì ýòà âåëè÷èíà. Íàèëó÷øèé ãàðàíòèðîâàííûé ðåçóëüòàò äëÿ âòîðîãîèãðîêà v = inf sup F (x, y) íàçûâàåòñÿ âåðõíèì çíà÷åíèåì èãðû.y∈Y x∈XÎïðåäåëåíèå. Ñòðàòåãèÿ y 0 âòîðîãî èãðîêà íàçûâàåòñÿ ìèíèìàêñíîé,åñëè sup F (x, y 0 ) = v.x∈XËåììà 2.2.  ëþáîé àíòàãîíèñòè÷åñêîé èãðå Γ ñïðàâåäëèâî íåðàâåíñòâî v ≤ v.1Äîêàçàòåëüñòâî. Âîçüìåì ïðîèçâîëüíûå ñòðàòåãèè èãðîêîâ x è y.Òîãäàinf F (x, y) ≤ F (x, y) ≤ sup F (x, y) ⇒ inf F (x, y) ≤ sup F (x, y).y∈Yy∈Yx∈Xx∈XËåâàÿ ÷àñòü ïîñëåäíåãî íåðàâåíñòâà çàâèñèò îò x, à ïðàâàÿ ÷àñòü − íåò.1 Ýòîìóíåðàâåíñòâó ìîæíî äàòü ñëåäóþùóþ èíòåðïðåòàöèþ: "ëó÷øå áûòü ïëîõèìñðåäè õîðîøèõ, ÷åì õîðîøèì ñðåäè ïëîõèõ".10Ÿ 2. Ñåäëîâûå òî÷êè è àíòàãîíèñòè÷åñêèå èãðûÏîýòîìósup inf F (x, y) ≤ sup F (x, y) ∀ y ∈ Yx∈X y∈Y⇒ v ≤ v.x∈XÒåïåðü ñôîðìóëèðóåì íåîáõîäèìîå è äîñòàòî÷íîå óñëîâèå ñóùåñòâîâàíèÿ ñåäëîâîé òî÷êè äëÿ ôóíêöèè äâóõ ïåðåìåííûõ.Òåîðåìà 2.1.

1) Äëÿ òîãî ÷òîáû ôóíêöèÿ F (x, y) íà X × Y èìåëàñåäëîâóþ òî÷êó, íåîáõîäèìî è äîñòàòî÷íî, ÷òîáû áûëî âûïîëíåíî ðàâåíñòâîmax inf F (x, y) = min sup F (x, y).(2.3)x∈X y∈Yy∈Y x∈X2) Ïóñòü âûïîëíåíî ðàâåíñòâî (2.3). Ïàðà (x0 , y 0 ) òîãäà è òîëüêî òîãäàÿâëÿåòñÿ ñåäëîâîé òî÷êîé, êîãäà x0 − ìàêñèìèííàÿ, à y 0 − ìèíèìàêñíàÿñòðàòåãèè èãðîêîâ.Äîêàçàòåëüñòâî.

Óòâåðæäåíèÿ 1) è 2) áóäåì äîêàçûâàòü îäíîâðåìåííî.Íåîáõîäèìîñòü. Ïóñòü (x0 , y 0 ) − ñåäëîâàÿ òî÷êà ôóíêöèè F (x, y). Ïîêàæåì, ÷òî âûïîëíåíî ðàâåíñòâî (2. 3), à x0 , y 0 − ìàêñèìèííàÿ è ìèíèìàêñíûå ñòðàòåãèè. Èìååìv ≤ sup F (x, y 0 ) = F (x0 , y 0 ) = v = inf F (x0 , y) ≤ v ⇒ v ≤ v.y∈Yx∈XÍî íåðàâåíñòâî v ≤ v âåðíî â ñèëó ëåììû 2.2. Ïîýòîìó v = v è â ïîñëåäíèõ íåðàâåíñòâàõ âñþäó ìîæíî ïîñòàâèòü çíàêè ðàâåíñòâ.

Èç ïîëó÷åííûõ ðàâåíñòâ ñëåäóåò, ÷òî x0 − ìàêñèìèííàÿ, à y 0 − ìèíèìàêñíàÿñòðàòåãèè èãðîêîâ.Äîñòàòî÷íîñòü. Ïóñòü ðàâåíñòâî (2.3) âûïîëíåíî. Âîçüìåì x0 , y 0 −ìàêñèìèííóþ è ìèíèìàêñíóþ ñòðàòåãèè è ïîêàæåì, ÷òî îíè îáðàçóþòñåäëîâóþ òî÷êó. Èìååì(2.3)F (x0 , y 0 ) ≥ inf F (x0 , y) = v = v = sup F (x, y 0 ) ≥ F (x0 , y 0 ).y∈Yx∈XÂî âñåõ íåðàâåíñòâàõ ìîæíî ïîñòàâèòü çíàêè ðàâåíñòâ è ïîëó÷àåì, ÷òî(x0 , y 0 ) − ñåäëîâàÿ òî÷êà ôóíêöèè F (x, y).Çàìå÷àíèå. Åñëè âûïîëíåíî ðàâåíñòâî (2.3), òî ìíîæåñòâî âñåõ ñåäëîâûõ òî÷åê ïðÿìîóãîëüíî è ñîâïàäàåò ñ X 0 ×Y 0 , ãäå X 0 è Y 0 − ìíîæåñòâàâñåõ ìàêñèìèííûõ è ìèíèìàêñíûõ ñòðàòåãèé èãðîêîâ.11ÃËÀÂÀ I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛÓïðàæíåíèå 2.1.

Äîêàæèòå, ÷òî 3×3-ìàòðèöà íå ìîæåò èìåòü ðîâíî7 ñåäëîâûõ òî÷åê.Ïðèìåð 2.3. Íàéäåì âñå ñåäëîâûå òî÷êè ìàòðèöû7 −1 −4 14232.A=22524 −3 7 −2Çäåñü ( min aij ) = (−4, 2, 2, −3) è ( max aij ) = (7, 2, 7, 2). Îòñþäà v =1≤j≤41≤i≤4v = 2, X 0 = {2, 3},ìíîæåñòâî X 0 × Y 0 .Y 0 = {2, 4}. ×åòûðå ñåäëîâûå òî÷êè îáðàçóþòÏðèìåð 2.4. Ïóñòü X = Y = [0, 1], F (x, y) = 2x2 − 3xy + 2y 2 . Íàéäåìâåëè÷èíû v è v. Ïðè ôèêñèðîâàííîì x ìèíèìóì ïî y ôóíêöèè F (x, y)äîñòèãàåòñÿ â òî÷êå y(x) = 3x/4 ∈ Y. Ïîýòîìó ôóíêöèÿ ìèíèìóìà −W (x) = min F (x, y) = 7x2 /8. Îòñþäà v = 7/8 è x0 = 1 − ìàêñèìèííàÿ0≤y≤1ñòðàòåãèÿ. Çàôèêñèðóåì y.

Ìàêñèìóì ôóíêöèè F (x, y) ïî x äîñòèãàåòñÿâ êîíöàõ îòðåçêà [0, 1] è ðàâåídefM (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) = −x2 + 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∈X12(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ε-ìèíèìàêñíîé ñòðàòåãèÿìè.