[учебник] Введение в теорию игр (с приложениями к экономике). Васин, Морозов (2003) (1186146), страница 22
Текст из файла (страница 22)
Äåéñòâèòåëüíî, âòîðîé èãðîê,ïîëó÷èâ ñîîáùåíèå î f ε , âûáåðåò y = y ε , òàê êàê â ïðîòèâíîì ñëó÷àå îíïîëó÷èò âûèãðûø G(f í (y), y) = min G(x, y) ≤ G2 < G(xε , y ε ). Ïîñêîëüx∈Xêó âòîðîé èãðîê ìàêñèìèçèðóåò ñâîé âûèãðûø, îí âûáåðåò y = y ε , ò.å.Y ∗ (f ε ) = {y ε }.2) K ≤ M. Óêàæåì ñòðàòåãèþ f 0 , äëÿ êîòîðîé W (f 0 ) ≥ M. Ïîëîæèì(f ∗ (y), y ∈ E,f 0 (y) =f í (y), y ∈/ E,ãäå ñòðàòåãèÿ f ∗ áûëà îïðåäåëåíà âûøå ïåðåä ëåììîé 11.1.
Ïîëó÷èâ ñîîáùåíèå î f 0 , âòîðîé èãðîê âûáåðåò y ∈ E. Äåéñòâèòåëüíî, åñëè y ∈/ E,í0òî G(f (y), y) = min G(x, y) < G2 . Äàëåå, ïðè y ∈ E G(f (y), y) =x∈XG(f ∗ (y), y) ≥ min G(x, y) = G2 . Ôóíêöèÿ G(f ∗ (y), y) ïîëóíåïðåðûâíàx∈Xñâåðõó íà êîìïàêòå E, ïîýòîìó Y ∗ (f 0 ) =Argmax G(f ∗ (y), y) ⊆ E. Îòñþäày∈EW (f 0 ) =minF (f ∗ (y), y) ≥∗ 0y∈Y (f )≥ min F (f ∗ (y), y) = min max F (x, y) = M.y∈Ey∈E x∈XÂòîðàÿ ÷àñòü. Äîêàæåì, ÷òî äëÿ ïðîèçâîëüíîé ñòðàòåãèè f ∈ {f }W (f ) ≤ max[K, M ].
Èìååìsup G(f (y), y) ≥ max min G(x, y) = G2 .y∈Yy∈Y x∈XÐàññìîòðèì äâà ñëó÷àÿ.1) sup G(f (y), y) > G2 .  ýòîì ñëó÷àå íàéäåòñÿ òàêàÿ ñòðàòåãèÿ âòîðîy∈Yãî èãðîêà y 0 ∈ Y ∗ (f ), ÷òî G(f (y 0 ), y 0 ) > G2 , ò.å. (f (y 0 ), y 0 ) ∈ D. Äåéñòâèòåëüíî, åñëè sup äîñòèãàåòñÿ, òî Y (f ) 6= ∅ è y 0 âîçüìåì ðåàëèçóþùèìy∈Ysup . Åñëè sup íå äîñòèãàåòñÿ, òî Y ∗ (f ) = Y è ñòðàòåãèÿ y 0 íàéäåòñÿ ïîy∈Yy∈Y127ÃËÀÂÀ II. ÈÃÐÛ ÄÂÓÕ ËÈÖîïðåäåëåíèþ sup .
Îòñþäày∈YW (f ) =infy∈Y ∗ (f )F (f (y), y) ≤ F (f (y 0 ), y 0 ) ≤ K ≤ max[K, M ].2) sup G(f (y), y) = G2 . Ïîêàæåì, ÷òî E ⊂ Y ∗ (f ). Äåéñòâèòåëüíî,y∈Yïóñòü y ∈ E. ÒîãäàG2 = min G(x, y) ≤ G(f (y), y) ≤ sup G(f (y), y) = G2 .x∈Xy∈Y ýòîé öåïî÷êå íåðàâåíñòâà âûïîëíåíû êàê ðàâåíñòâà.
Îòñþäà y ∈ Y ∗ (f )è E ⊆ Y ∗ (f ). Èòàê,W (f ) = inf∗ F (f (y), y) ≤y∈Y (f )≤ inf F (f (y), y) ≤ min max F (x, y) = M ≤ max[K, M ].y∈Ey∈E x∈XÑôîðìóëèðóåì àíàëîãè÷íûé ðåçóëüòàò äëÿ èãðû Γ3 . Íàïîìíèì, ÷òîâ èãðå Γ3 âòîðîé èãðîê âûáèðàåò y, êîãäà âûáîð ñòðàòåãèè x ïåðâîãî åìóèçâåñòåí. Âòîðîé èãðîê èñïîëüçóåò ñòðàòåãèþ g : X → Y.
Îïðåäåëèìñëåäóþùèå âåëè÷èíû è ìíîæåñòâî:G3 = min max G(x, y) = max G(xí , y) − íàèëó÷øèé ãàðàíòèðîâàííûéx∈X y∈Yy∈Yðåçóëüòàò âòîðîãî èãðîêà, êîãäà ïåðâûé ïðèìåíÿåò ñòðàòåãèþ íàêàçàíèÿxí ;D0 = {(x, y) ∈ X × Y | G(x, y) > G3 }; sup F (x, y), D0 6= ∅,0K = (x,y)∈D0−∞,D0 = ∅.Òîãäà ìîæíî äîêàçàòü, ÷òî F3 = max[K 0 , F1 ] (ñì. óïðàæíåíèÿ 11.12). Åñëè F1 ≥ K 0 , òî ïåðâûé èãðîê ïðèìåíÿåò ε-îïòèìàëüíóþ ñòðàòåãèþèãðû Γ1 . Ïóñòü F1 < K 0 .  ýòîì ñëó÷àå íàéäåòñÿ òàêàÿ ïàðà (xε , y ε ) ∈ D0 ,÷òî F (xε , y ε ) ≥ K 0 − ε.Óïðàæíåíèå 11.1.
Äîêàæèòå, ÷òî äëÿ ñòðàòåãèè(xε , g(xε ) = y ε ,f1ε (g) =xí , g(xε ) =6 yε,îöåíêà ýôôåêòèâíîñòè W (f1ε ) ≥ K 0 − ε.Óïðàæíåíèå 11.2. Äîêàæèòå, ÷òî äëÿ ëþáîé ñòðàòåãèè f1 ïåðâîãîèãðîêà â èãðå Γ3 W (f1 ) ≤ max[K 0 , F1 ].128 11. Èåðàðõè÷åñêèå èãðû äâóõ ëèöÓïðàæíåíèå 11.3. Äîêàæèòå, ÷òî â èãðå Γ1 â íîðìàëüíîé ôîðìå âñåãäà ñóùåñòâóåò ñèòóàöèÿ ðàâíîâåñèÿ.Óïðàæíåíèå 11.4. Äîêàæèòå, ÷òî F1 ≤ F3 ≤ F2 .Ïðèìåð 11.1. Ðåøèì èãðû Γ1 , Γ2 , Γ3 äëÿ èãðû Γ ñ ìàòðèöàìè3 687 4 32 , B = 7 7 3 .A = 4 37 −5 −14 6 6Èãðà Γ1 .
F1 = max min aij = max W (i), Y (i) = Arg max bij , W (1) =1≤i≤3 j∈Y (i)1≤i≤31≤j≤3W (2) = 3, W (3) = −5 ⇒ F1 = 3 è i0 = 1, 2 − îïòèìàëüíûå ñòðàòåãèè.Èãðà Γ2 . G2 = max min bij = 4, E = {1, 2}, D = {(i, j) | bij > 4},1≤j≤3 1≤i≤3K = max aij = 4, M = min max aij = 6 ⇒ F2 = M = 61≤j≤2 1≤i≤3(i,j)∈D(3, j = 1,è f 0 (j) =− îïòèìàëüíàÿ ñòðàòåãèÿ.1, j = 2, 3,Èãðà Γ3 . G3 = min max bij = 6, D0 = {(i, j) | bij > 6},1≤i≤3 1≤j≤30K = max 0 aij = 4 > F1 = 3 ⇒ F3 = K 0 = 4(i,j)∈D(2, g(2) = 1,è f10 (g) =− îïòèìàëüíàÿ ñòðàòåãèÿ.3, g(2) 6= 1,Ïðèìåð 11.2. Ðåøèì èãðû Γ1 , Γ2 , Γ3 äëÿ èãðû Γ :X = Y = [0, 1], F (x, y) = 3x/4 + y/2, G(x, y) = (x − y)2 .Èãðà Γ1 .
F1 = sup min (3x/4 + y/2),0≤x≤1 y∈Y (x)0 ≤ x < 1/2,{1},Y (x) = Arg max (x − y)2 = {0, 1}, x = 1/2,0≤y≤1{0},1/2 < x ≤ 1.Ãðàôèê ôóíêöèè W (x) = min (3x/4 + y/2) ñì. íà ðèñ. 11.1.y∈Y (x)129ÃËÀÂÀ II. ÈÃÐÛ ÄÂÓÕ ËÈÖW (x) 67/8> 3/4- x1/21Ðèñ. 11.1Çäåñü F1 = 7/8, xε = 1/2 − 4ε/3 − ε-îïòèìàëüíàÿ ñòðàòåãèÿ. Îòìåòèì,÷òî âíåøíÿÿ âåðõíÿÿ ãðàíü â âûðàæåíèè äëÿ F1 íå äîñòèãàåòñÿ.Èãðà Γ2 . G2 = max min (x − y)2 = 0, D = {(x, y) | (x − y)2 > 0},0≤y≤1 0≤x≤1(xε , y = y ε ,ε εεK = 5/4 = F2 , (x , y ) = (1 − 4ε/3, 1), f (y) =y, y 6= y ε ,− ε-îïòèìàëüíàÿ ñòðàòåãèÿ.Èãðà Γ3 .
G3 = min max (x − y)2 = 1/4, xí = 1/2,0≤x≤1 0≤y≤1D0 = {(x, y) | |x − y| > 1/2}, K 0 = sup (3x/4 + y/2) = 1 >(x,y)∈D007/8 = F1(⇒ F3 = K , (x , y ) = (1, 1/2 − 2ε) ∈ K 0 ,f1ε (g) =εε1,g(1) = 1/2 − 2ε,− ε-îïòèìàëüíàÿ ñòðàòåãèÿ.1/2, g(1) =6 1/2 − 2ε,Ïðèìåð 11.3.
Èãðà ïåðåñòðàõîâàíèÿ. Ïåðåñòðàõîâùèê (èãðîê 1) èñòðàõîâùèê (èãðîê 2) çàêëþ÷àþò äîãîâîð ïåðåñòðàõîâàíèÿ. Ïóñòü Z −ñóììàðíîå âîçìåùåíèå ñòðàõîâùèêà êëèåíòàì, ïðåäñòàâëÿþùåå ñîáîéñëó÷àéíóþ âåëè÷èíó ñ ýêñïîíåíöèàëüíîé ïëîòíîñòüþ ðàñïðåäåëåíèÿe−z/m /m, z ≥ 0. Ïðè çàêëþ÷åíèè äîãîâîðà ñòðàõîâùèê âûáèðàåò ïðåäåëóáûòî÷íîñòè y ∈ Y = {y ∈ E 1 | y ≥ 0} : åñëè Z > y, òî ñóììó Z − y âîçìåùàåò ïåðåñòðàõîâùèê. Îòìåòèì, ÷òî ïðè y = 0 ñòðàõîâùèê ïîëíîñòüþïåðåäàåò îïëàòó èñêîâ ïåðåñòðàõîâùèêó.
Âåëè÷èíàZ∞1h(y) = E max[Z − y, 0] = (z − y) e−z/m dz = me−y/mmdefy130 11. Èåðàðõè÷åñêèå èãðû äâóõ ëèö− ñðåäíÿÿ âåëè÷èíà âûïëàò ïåðåñòðàõîâùèêà. Ñòîèìîñòü äîãîâîðà ïådefðåñòðàõîâàíèÿ ðàâíà d(x, y) = (1 + x)h(y), ãäå x ≥ 0 − êîýôôèöèåíò íàäáàâêè çà ðèñê, óñòàíàâëèâàåìûé ïåðåñòðàõîâùèêîì. Áóäåì ñ÷èòàòü, ÷òîîïëàòà äîãîâîðà îñóùåñòâëÿåòñÿ ñòðàõîâùèêîì èç ôîíäà ñòðàõîâûõ ïëàòåæåé âåëè÷èíû A > m. Äîãîâîð ìîæåò áûòü çàêëþ÷åí ëèøü ïðè âûïîëíåíèè íåðàâåíñòâà d(x, y) + y ≤ A. ÏîëîæèìŶ (x) = {y ∈ Y | d(x, y) + y ≤ A}, X = {x ∈ E 1 | x ≥ 0, Ŷ (x) 6= ∅}.Åñëè y ∈ Ŷ (x), òî äîãîâîð çàêëþ÷àåòñÿ, âûèãðûø ïåðåñòðàõîâùèêà ðàâåí åãî îæèäàåìîé ïðèáûëè F (x, y) = xh(y), à âûèãðûø ñòðàõîâùèêà −ãàðàíòèðîâàííîé âåëè÷èíå îñòàòêà ôîíäà ñòðàõîâûõ ïëàòåæåé G(x, y) =A − d(x, y) − y, ñîîòâåòñòâóþùåé ñëó÷àþ Z ≥ y.Ðåøèì èãðó Γ1 .
Íàïîìíèì, ÷òî ñíà÷àëà ïåðâûé èãðîê ñîîáùàåò âòîðîìó ñòðàòåãèþ x ∈ X. Çàòåì âòîðîé èãðîê âûáèðàåò ñòðàòåãèþy ∈ Y (x) = Arg max G(x, y). Ïóñòü x ∈ X. Ìàêñèìóìy∈Ŷ (x)max G(x, y) = max [A − (1 + x)me−y/m − y] = A − m − m ln(1 + x)y∈Ŷ (x)y∈Ŷ (x)äîñòèãàåòñÿ â åäèíñòâåííîé òî÷êå y(x) = m ln(1 + x). Îòñþäà âûòåêàåò,÷òî Ŷ (x) 6= ∅, åñëè A − m − m ln(1 + x) ≥ 0. Ñëåäîâàòåëüíî, X = [0, x0 ],defãäå x0 = e(A−m)/m − 1. ÎòñþäàF1 = max F (x, y(x)) = max 0x∈X0≤x≤xxmx0 m=1+x1 + x0è x0 − îïòèìàëüíàÿ ñòðàòåãèÿ ïåðâîãî èãðîêà.Óïðàæíåíèå 11.5.
Ðàññìîòðèòå èãðó äâóõ ôèðì èç ïðèìåðà 9.9 ïðèα = 1 è ðåøèòå èãðó Γ1 . Ñðàâíèòå íàèëó÷øèé ãàðàíòèðîâàííûé ðåçóëüòàò ïåðâîãî èãðîêà F1 ñ âûèãðûøåì, êîòîðûé îí ïîëó÷àåò â ñèòóàöèèðàâíîâåñèÿ.Ðàâíîâåñèå ïî ØòàêåëüáåðãóÎïðåäåëèì òåïåðü ðàâíîâåñèå ïî Øòàêåëüáåðãó èãðû Γ1 . ÏîëîæèìY ∗ (x) =Arg max F (x, y) ìíîæåñòâî íàèëó÷øèõ îòâåòîâ âòîðîãî èãðîêà,y∈Y (x)áëàãîæåëàòåëüíûõ ïî îòíîøåíèþ ê ïåðâîìó.Îïðåäåëåíèå. Ñèòóàöèÿ (x0 , y 0 ) íàçûâàåòñÿ ðàâíîâåñèåì ïî Øòàêåëüáåðãó, åñëèx0 ∈ Arg max max F (x, y), y 0 ∈ Y ∗ (x0 ).x∈X y∈Y (x)131ÃËÀÂÀ II. ÈÃÐÛ ÄÂÓÕ ËÈÖÇäåñü ïðåäïîëàãàåòñÿ, ÷òî âòîðîé èãðîê, ïîëó÷èâ èíôîðìàöèþ î x, èñïîëüçóåò ñâîé íàèëó÷øèé îòâåò, áëàãîæåëàòåëüíûé ïî îòíîøåíèþ ê ïåðâîìó èãðîêó.Ïîêàæåì, ÷òî â ñäåëàííûõ ïðåäïîëîæåíèÿõ ðàâíîâåñèå ïî Øòàêåëüáåðãó ñóùåñòâóåò. Äëÿ ýòîãî îïðåäåëèì ñòðàòåãèþ âòîðîãî èãðîêà g ∗ :g ∗ (x) ∈ Y ∗ (x) ∀x ∈ Y.
Ïî ëåììå 11.1 ôóíêöèÿ F (x, g ∗ (x)) ïîëóíåïðåðûâíà ñâåðõó íà X. Ñëåäîâàòåëüíî, îíà äîñòèãàåò íà êîìïàêòå X íàèáîëüøååçíà÷åíèå â íåêîòîðîé òî÷êå x0 . Òîãäà ïðè y 0 = g ∗ (x0 ) ñèòóàöèÿ (x0 , y 0 )áóäåò ðàâíîâåñèåì ïî Øòàêåëüáåðãó.Óïðàæíåíèå 11.6.  óñëîâèÿõ ïðèìåðîâ 11.1 è 11.2 íàéäèòå ðàâíîâåñèÿ ïî Øòàêåëüáåðãó.Îòìåòèì, ÷òî èñïîëüçîâàíèå ðàâíîâåñèÿ ïî Øòàêåëüáåðãó òðåáóåò îòèãðîêîâ ñîòðóäíè÷åñòâà, êîòîðîå, êàê ïîêàçûâàåò ñëåäóþùèé ïðèìåð, íåâñåãäà âîçìîæíî.  èãðå ñ ìàòðèöàìè5 75 6A=, B=4 81 1ñèòóàöèÿ (2,2) ÿâëÿåòñÿ åäèíñòâåííûì ðàâíîâåñèåì ïî Øòàêåëüáåðãó.Îäíàêî äîãîâîðèòüñÿ î íåé èãðîêàì áóäåò î÷åíü ñëîæíî, ïîñêîëüêó âñèòóàöèè (1,2) (âîçíèêàþùåé ïðè ðåøåíèè èãðû Γ1 ) âûèãðûø âòîðîãîèãðîêà ñóùåñòâåííî áîëüøå, ÷åì â (2,2), è îí åäâà ëè ñîãëàñèòñÿ íà ñèòóàöèþ (2,2).Êîììåíòàðèé è áèáëèîãðàôèÿ ê ãëàâå II 9.
Ïîíÿòèå ñèòóàöèè ðàâíîâåñèÿ â ÷àñòíîì ñëó÷àå, åùå â 19-ì âåêå,èñïîëüçîâàëîñü Î. Êóðíî ïðè àíàëèçå ìîäåëè äóîïîëèè [59]. Îïðåäåëåíèå ñèòóàöèè ðàâíîâåñèÿ äëÿ èãðû ìíîãèõ ëèö ïðèíàäëåæèò Äæ. Íýøó[76].  1999 ãîäó Äæîí Íýø ïîëó÷èë Íîáåëåâñêóþ ïðåìèþ ïî ýêîíîìèêå.Êðèòè÷åñêèé ðàçáîð ïîíÿòèÿ ñèòóàöèè ðàâíîâåñèÿ (â ÷àñòíîñòè, àíàëèçèãð "ñåìåéíûé ñïîð"è "äèëåììà çàêëþ÷åííîãî") ñäåëàí Ð.Ä. Ëüþñîì èÕ. Ðàéôîé [61].
Ïðèìåð 9.3 ÿâëÿåòñÿ ìîäèôèêàöèåé ïðèìåðà "ïåðåêðåñòîê"èç [71].Òåîðåìà 9.1 î íåïîäâèæíîé òî÷êå ïðèíàäëåæèò Ë. Áðàóýðó [18]. Êîìáèíàòîðíîå äîêàçàòåëüñòâî ýòîé òåîðåìû, èñïîëüçóþùåå ëåììó Ý. Øïåðíåðà [107], ïîëó÷åíî Á. Êíàñòåðîì, Ê. Êóðàòîâñêèì è Ñ. Ìàçóðêåâè÷åì[53] (äîêàçàòåëüñòâî òåîðåìû ñì. â Ïðèëîæåíèè è â [79]).132 11.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
