[учебник] Введение в теорию игр (с приложениями к экономике). Васин, Морозов (2003) ([учебник] Введение в теорию игр (с приложениями к экономике). Васин, Морозов (2003).pdf), страница 17
Описание файла
PDF-файл из архива "[учебник] Введение в теорию игр (с приложениями к экономике). Васин, Морозов (2003).pdf", который расположен в категории "". Всё это находится в предмете "теория игр и исследование операций" из 11 семестр (3 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 17 страницы из PDF
Òîãäà â èãðå Γ ñóùåñòâóåò ñèòóàöèÿ ðàâíîâåñèÿ.Äîêàçàòåëüñòâî. Âíà÷àëå ïðåäïîëîæèì, ÷òî ôóíêöèè F (x, y) è G(x, y)íåïðåðûâíû íà X × Y è ñòðîãî âîãíóòû ïî "ñâîèì"ïåðåìåííûì x è y ñîîòâåòñòâåííî. Òîãäà äëÿ ëþáûõ ñòðàòåãèé y è x ìíîæåñòâà íàèëó÷øèõîòâåòîâ èãðîêîâdefdefX(y) = Arg max F (x, y) = {x(y)}, Y (x) = Arg max G(x, y) = {y(x)}x∈Xy∈Yñîäåðæàò ïî îäíîìó ýëåìåíòó x(y) è y(x). Ñîãëàñíî òåîðåìå 2.2, ôóíêöèè x(y) è y(x) íåïðåðûâíû.
Áóäåì íàçûâàòü èõ ôóíêöèÿìè íàèëó÷øåãîîòâåòà ïåðâîãî è âòîðîãî èãðîêîâ ñîîòâåòñòâåííî.Ïîëîæèì Z = X × Y è ðàññìîòðèì îòîáðàæåíèå f : Z → Z,f (x, y) = (x(y), y(x)). Ïî òåîðåìå 9.1 îòîáðàæåíèå f èìååò íåïîäâèæíóþòî÷êó z 0 = (x0 , y 0 ) : f (z 0 ) = z 0 èëè x(y 0 ) = x0 , y(x0 ) = y 0 . Ñëåäîâàòåëüíî, (x0 , y 0 ) − ñèòóàöèÿ ðàâíîâåñèÿ.Òåïåðü ïðåäïîëîæèì, ÷òî ôóíêöèè F (x, y) è G(x, y) âîãíóòû ïî "ñâîèì"ïåðåìåííûì x è y , íî íåîáÿçàòåëüíî ñòðîãî. ÏîëîæèìFε (x, y) = F (x, y) − εmXx2i ,Gε (x, y) = G(x, y) − εi=1mXyj2 ,j=1ãäå ε > 0. Ôóíêöèè Fε (x, y) è Gε (x, y) íåïðåðûâíû íà X × Y , Fε (x, y)ñòðîãî âîãíóòàïî x, à Gε (x, y) ñòðîãî âîãíóòà ïî y. Ïî äîêàçàííîìó â èãεðå Γ = X, Y, Fε (x, y), Gε (x, y) ñóùåñòâóåò ñèòóàöèÿ ðàâíîâåñèÿ (xε , y ε ).Ïóñòü {εh } − òàêàÿ ïîñëåäîâàòåëüíîñòü ÷èñåë, ÷òî εh → 0+ è ñîîòâåòñòâóþùàÿ ïîñëåäîâàòåëüíîñòü ñèòóàöèé ðàâíîâåñèÿ {(xεh , y εh )} ñõîäèòñÿê íåêîòîðîé ñèòóàöèè (x0 , y 0 ).
Ïî îïðåäåëåíèþ (xεh , y εh )Fεh (x, y εh ) ≤ Fεh (xεh , y εh ) ∀ x ∈ X,98 9. Ñèòóàöèè ðàâíîâåñèÿ â èãðàõ äâóõ ëèöGεh (xεh , y) ≤ Gεh (xεh , y εh ) ∀ y ∈ Y.Ïåðåõîäÿ â ýòèõ íåðàâåíñòâàõ ïðè ôèêñèðîâàííûõ x è y ê ïðåäåëó ïðèh → ∞, ïîëó÷èìF (x, y 0 ) ≤ F (x0 , y 0 ) ∀ x ∈ X, G(x0 , y) ≤ G(x0 , y 0 ) ∀ y ∈ Y,Ýòî îçíà÷àåò, ÷òî (x0 , y 0 ) − ñèòóàöèÿ ðàâíîâåñèÿ èãðû Γ.Ðàññìîòðèì ìåòîä ïîèñêà ñèòóàöèè ðàâíîâåñèÿ ñ èñïîëüçîâàíèåì ìíîæåñòâ íàèëó÷øèõ îòâåòîâ X(y) = Arg max F (x, y) è Y (x) = Arg max G(x, y).x∈XÎí ñîñòîèò â ðåøåíèè ñèñòåìû âêëþ÷åíèéx0 ∈ X(y 0 ), y 0 ∈ Y (x0 ).y∈Y(9.1) ñëó÷àå, êîãäà ó èãðîêîâ ñóùåñòâóþò íåïðåðûâíûå ôóíêöèè íàèëó÷øåãî îòâåòà x(y) è y(x) (ñì. ïåðâóþ ÷àñòü äîêàçàòåëüñòâà òåîðåìû 9.2),ñèñòåìà âêëþ÷åíèé (9.1) ýêâèâàëåíòíà ñèñòåìå óðàâíåíèéx(y 0 ) = x0 , y(x0 ) = y 0 .Ïðèìåð 9.6. Íàéäåì âñå23 4 −2A= 21−12ñèòóàöèè ðàâíîâåñèÿ èãðû Γ :5 −17 5 4 73 4 , B = 4 5 5 4 .−3 6 6 25 45 38 7 3 6 ìàòðèöå A ïîä÷åðêíóòû íàèáîëüøèå ýëåìåíòû â ñòîëáöàõ, à â ìàòðèöå B − íàèáîëüøèå ýëåìåíòû â ñòðîêàõ.
Îáùèé ïîä÷åðêíóòûé ýëåìåíòñîîòâåòñòâóåò (3,3) − åäèíñòâåííîé ñèòóàöèè ðàâíîâåñèÿ.Ïðèìåð9.7. Ðàññìîòðèì èãðó äâóõ ëèöΓ = X, Y, F (x, y), G(x, y) , ãäå X, Y è F (x, y), G(x, y) − ìíîæåñòâà ñòðàòåãèé è ôóíêöèè âûèãðûøà ïåðâîãî è âòîðîãî èãðîêîâ. ÏóñòüX = Y = [0, 1], F (x, y) = −3x2 + 2y 2 + 7xy, G(x, y) = −(x + y − 1)2 .Ôóíêöèè F (x, y) è G(x, y) ñòðîãî âîãíóòû ïî ïåðåìåííûì x è y ñîîòâåòñòâåííî. Ôóíêöèè íàèëó÷øåãî îòâåòà −(7y/6, 0 ≤ y ≤ 6/7,x(y) =y(x) = 1 − x.1,6/7 < y ≤ 1,99ÃËÀÂÀ II. ÈÃÐÛ ÄÂÓÕ ËÈÖÐåøàÿ ñèñòåìó x(y) = x, y(x) = y, íàõîäèì x0 = 7/13, y 0 = 6/13.Äëÿ ÷èñëåííîãî ðåøåíèÿ ñèñòåìû âêëþ÷åíèé (9.1) ÷àñòî ïðèìåíÿåòñÿ ïðîöåäóðà íàùóïûâàíèÿ ïî Êóðíî. Îíà çàêëþ÷àåòñÿ â ïîñòðîåíèèïîñëåäîâàòåëüíîñòè ñòðàòåãèé:x1 ∈ X, y 1 ∈ Y (x1 ), x2 ∈ X(y 1 ), y 2 ∈ Y (x2 ) è ò.ä.Ïóñòü ïîñëåäîâàòåëüíîñòè ñòðàòåãèé {xk }, {y k } ñõîäÿòñÿ ñîîòâåòñòâåííî ê x0 è y 0 . Òîãäà (x0 , y 0 ) − ñèòóàöèÿ ðàâíîâåñèÿ, ïîñêîëüêó äëÿ(x0 , y 0 ) ñïðàâåäëèâà ñèñòåìà âêëþ÷åíèé (9.1) (ñì.
äîêàçàòåëüñòâî òåîðåìû 2.2). Îäíàêî ïîñëåäîâàòåëüíîñòè {xk }, {y k } ñõîäÿòñÿ íå âñåãäà.Ïðèìåð9.8. Ðàññìîòðèìàíòàãîíèñòè÷åñêóþ èãðóΓ = X, Y, F (x, y) , â êîòîðîéX = Y = [−1, 1], F (x, y) = −x2 + 2axy + y 2 ,ãäå a ∈ (0, 1] − ïàðàìåòð.
Ôóíêöèÿ F (x, y) ñòðîãî âîãíóòà ïî x, ñòðîãî âûïóêëà ïî y è èìååò åäèíñòâåííóþ ñåäëîâóþ òî÷êó (0, 0). Ôóíêöèèíàèëó÷øåãî îòâåòà èãðîêîâ ðàâíû x(y) = ay, y(x) = −ax. Ïóñòü x1 6= 0.Òîãäà ïðîöåäóðà íàùóïûâàíèÿ ïî Êóðíî ïîðîæäàåò ïîñëåäîâàòåëüíîñòè{xk = (−a)k−1 x1 }, {y k = (−a)k x1 }, ñõîäÿùèåñÿ ïðè 0 < a < 1 è ðàñõîäÿùèåñÿ ïðè a = 1.Ñëåäóþùèé ïðèìåð ïîêàçûâàåò, ÷òî äëÿ ïîèñêà ðàâíîâåñèÿ ïî Íýøó ìîæíî èñïîëüçîâàòü íåîáõîäèìûå óñëîâèÿ îïòèìàëüíîñòè ïåðâîãîïîðÿäêà.Ïðèìåð 9.9. Ìîäåëü äóîïîëèè.
Äâå ôèðìû âûïóñêàþò áåñêîíå÷íîäåëèìûé òîâàð äëÿ ïðîäàæè íà ðûíêå. Ïóñòü x è y − êîëè÷åñòâà òîâàðà,âûïóñêàåìîãî ïåðâîé è âòîðîé ôèðìàìè, à 0 < c1 ≤ c2 − çàòðàòû íà åãîïðîèçâîäñòâî, ò.å. ñåáåñòîèìîñòè åäèíèöû òîâàðà äëÿ îáåèõ ôèðì. Öåíàòîâàðà p(x + y) çàâèñèò îò îáùåãî âûïóñêà x + y.
Ôóíêöèè âûèãðûøàôèðì F (x, y) = (p(x + y) − c1 )x è G(x, y) = (p(x + y) − c2 )y − ïðèáûëè,ïîëó÷åííûå îò ðåàëèçàöèè ïðîèçâåäåííîé ïðîäóêöèè.Ïóñòü öåíà íà ïðîäóêöèþ îïðåäåëÿåòñÿ ïî ñëåäóþùåé ôîðìóëåp(x + y) = K/(x + y)α , ãäå 1 ≥ α > 0. Òîãäà ìîæíî ñ÷èòàòü, ÷òîX = [0, (K/c1 )1/α ], ïîñêîëüêó ïðè x > (K/c1 )1/α ïåðâàÿ ôèðìà òåðïèòóáûòêè. Àíàëîãè÷íî Y = [0, (K/c2 )1/α ].Çàìåòèì, ÷òî äëÿ ïîëó÷åííîé èãðû âûïîëíåíû óñëîâèÿ òåîðåìû 9.2è ñèòóàöèÿ ðàâíîâåñèÿ (x0 , y 0 ) ñóùåñòâóåò. Ïóñòü x0 > 0, y 0 > 0. Òîãäà100 9. Ñèòóàöèè ðàâíîâåñèÿ â èãðàõ äâóõ ëèöðàâíîâåñíûå ñòðàòåãèè x0 , y 0 íàõîäÿòñÿ èç ñèñòåìû óðàâíåíèéFx0 (x0 , y 0 ) =KαKx0−c−= 0,1(x0 + y 0 )α(x0 + y 0 )α+1G0y (x0 , y 0 ) =αKy 0K−c−= 0.2(x0 + y 0 )α(x0 + y 0 )α+1Ñêëàäûâàÿ óðàâíåíèÿ, íàõîäèì ñíà÷àëà ñóììó (2 − α)K 1/α, à çàòåìc1 + c2 (2 − α)K (α+1)/α 1(x0 , y 0 ) =c2 + (α − 1)c1 , c1 + (α − 1)c2 .α(2 − α)K c1 + c2x0 + y 0 =Ïîñêîëüêó y 0 > 0, òî íåîáõîäèìî c1 + (α − 1)c2 > 0.
Åñëè âûïîëíåíîíåðàâåíñòâî c1 + (α − 1)c2 ≤ 0, òî ïåðâàÿ ôèðìà ÿâëÿåòñÿ íà ðûíêåìîíîïîëèñòîì è ðàâíîâåñíûå ñòðàòåãèè èìåþò âèä (1 − α)K 1/α, y 0 = 0.x0 =c1Áàéåñîâñêîå ðàâíîâåñèåÏóñòü â èãðå äâóõ ëèö Γ = X, Y, F (x, y, c), F (x, y, c) ôóíêöèèâûèãðûøà èãðîêîâ F (x, y, c) è G(x, y, c) çàâèñÿò íå òîëüêî îò ñèòóàöèè(x, y), íî è îò ñëó÷àéíîãî âåêòîðà ïàðàìåòðîâ c = (c1 , c2 ) ∈ C. Ïðåäïîëîæèì, ÷òî ìíîæåñòâî C êîíå÷íî è p(c), c ∈ C − âåðîÿòíîñòíîå ðàñïðåäåëåíèå íà C, èçâåñòíîå âñåì èãðîêàì.
Ïóñòü Ck − ìíîæåñòâî çíà÷åíèé,ïðèíèìàåìûõ ïàðàìåòðîì ck , êîãäà âåêòîð c ïðîáåãàåò ìíîæåñòâî C. Èãðîêó k ïåðåä âûáîðîì ñòðàòåãèè ñòàíîâèòñÿ èçâåñòíûì çíà÷åíèå "ñâîåãî"ïàðàìåòðà ck , k = 1, 2. Ïîýòîìó ñòðàòåãèåé ïåðâîãî èãðîêà ÿâëÿåòñÿôóíêöèÿ x̃ : C1 → X, à âòîðîãî − ôóíêöèÿ ỹ : C2 → Y, Ìíîæåñòâî âñåõòàêèõ ôóíêöèé x̃ îáîçíà÷èì ÷åðåç X̃, à ôóíêöèé ỹ − ÷åðåç Ỹ .Îïðåäåëèì îñðåäíåííûå ôóíêöèè âûèãðûøà èãðîêîâXXp(c)F (x̃(c), ỹ(c), c), G̃(x̃, ỹ) =p(c)G(x̃(c), ỹ(c), c).F̃ (x̃, ỹ) =c∈Cc∈CÎïðåäåëåíèå. Èãðà Γ̃ = X̃, Ỹ , F̃ (x̃, ỹ), G̃(x̃, ỹ) è ñèòóàöèè ðàâíîâåñèÿ â íåé íàçûâàþòñÿ áàéåñîâñêèìè.101ÃËÀÂÀ II.
ÈÃÐÛ ÄÂÓÕ ËÈÖÏðèìåð 9.10.  ïðîäîëæåíèå ïðèìåðà 9.9 ðàññìîòðèì ìîäåëü äóîïîëèè c ôóíêöèÿìè âûèãðûøà èãðîêîâ F (x, y, c1 ) = (p(x + y) − c1 )x,G(x, y, c2 ) = (p(x+y)−c2 )y è ëèíåéíîé ôóíêöèåé öåíû p(x+y) = a−x−y.Ïóñòü ñåáåñòîèìîñòü c1 èçâåñòíà îáîèì èãðîêàì, à ñåáåñòîèìîñòü c2 ïðåäñòàâëÿåò ñîáîé ñëó÷àéíóþ âåëè÷èíó, ïðèíèìàþùóþ çíà÷åíèÿ c12 è c22 ñâåðîÿòíîñòüþ 1/2.  ýòèõ ïðåäïîëîæåíèÿõ ñòðàòåãèÿ x̃ èãðîêà 1 ÿâëÿåòñÿ ôóíêöèåé-êîíñòàíòîé è ñîâïàäàåò ñ x. Ïîëîæèì y i = ỹ(ci2 ), i = 1, 2.Òîãäà â áàéåñîâñêîé èãðå ôóíêöèè âûèãðûøà èãðîêîâ èìåþò âèäF̃ (x̃, ỹ) = a − x − y1 + y2 2− c1 x,11G̃(x̃, ỹ) = (a − x − y 1 − c12 )y 1 + (a − x − y 2 − c22 )y 2 .22Íàéäåì áàéåñîâñêóþ ñèòóàöèþ ðàâíîâåñèÿ (x0 , (y 01 , y 02 )) ïðèa > 2 max[c1 , c12 , c22 ].
Ôóíêöèè íàèëó÷øåãî îòâåòà èãðîêîâ èìåþò âèä"x̃∗ (y 1 , y 2 ) = max12#a − c1 y + y−,0 ,24"#ia−cx2− , 0 , i = 1, 2.ỹ ∗ (ci2 , x) = max22Ðåøàÿ ñèñòåìó óðàâíåíèéx̃∗ (y 1 , y 2 ) = x, ỹ ∗ (ci2 , x) = y i , i = 1, 2,íàõîäèì ñèòóàöèþ ðàâíîâåñèÿ!121c+c2x0 =a − 2c1 + 2,32y01!!17 1 1 217 2 1 102=a + c1 − c2 − c2 , y =a + c1 − c2 − c2 .344344102 10. Ñèòóàöèè ðàâíîâåñèÿ â áèìàòðè÷íûõ èãðàõ 10.Ñèòóàöèè ðàâíîâåñèÿ â áèìàòðè÷íûõ èãðàõÏåðåéäåì ê ñìåøàííûì ðàñøèðåíèÿì áèìàòðè÷íûõ èãð Γ, çàäàâàåìûõ ìàòðèöàìèA = (aij )m×n , B = (bij )m×n .Ñìåøàííûå ñòðàòåãèè èãðîêîâ çäåñü òàêèå æå, êàê è â ìàòðè÷íîé èãðå:p ∈ P, q ∈ Q. Îæèäàåìûå âûèãðûøè èãðîêîâ −A(p, q) =m XnXpi aij qj , B(p, q) =i=1 j=1m XnXpi bij qj .i=1 j=1 ðåçóëüòàòå ïîëó÷èëè ñìåøàííîå ðàñøèðåíèå áèìàòðè÷íîé èãðûΓ = P, Q, A(p, q), B(p, q) .Ñèòóàöèè ðàâíîâåñèÿ èãðû Γ áóäåì íàçûâàòü ñèòóàöèÿìè ðàâíîâåñèÿ âñìåøàííûõ ñòðàòåãèÿõ (èëè ñìåøàííûìè ðàâíîâåñèÿìè ïî Íýøó) èñõîäíîé èãðû Γ.Ìíîæåñòâà ñìåøàííûõ ñòðàòåãèé P è Q − âûïóêëûå êîìïàêòû åâêëèäîâûõ ïðîñòðàíñòâ, à ôóíêöèè A(p, q) è B(p, q) áèëèíåéíû.
Ïî òåîðåìå 9.2 â èãðå Γ ñóùåñòâóåò ñèòóàöèÿ ðàâíîâåñèÿ ñ ñìåøàííûõ ñòðàòåãèÿõ(p0 , q 0 ). Äëÿ íåå ïî îïðåäåëåíèþ âûïîëíåíû íåðàâåíñòâàA(p, q 0 ) ≤ A(p0 , q 0 ) ∀ p ∈ P,B(p0 , q) ≤ B(p0 , q 0 ) ∀ q ∈ Q.Ðàññìîòðèì ñâîéñòâà ñèòóàöèé ðàâíîâåñèÿ â ñìåøàííûõ ñòðàòåãèÿõ, àíàëîãè÷íûå ñâîéñòâàì ðåøåíèé ìàòðè÷íûõ èãð.Ëåììà 10.1. Äëÿ òîãî ÷òîáû ñèòóàöèÿ (p0 , q 0 ) áûëà ñèòóàöèåé ðàâíîâåñèÿ â ñìåøàííûõ ñòðàòåãèÿõ áèìàòðè÷íîé èãðû Γ, íåîáõîäèìî èäîñòàòî÷íî, ÷òîáû áûëî âûïîëíåíî óñëîâèå(A(i, q 0 ) ≤ A(p0 , q 0 ), i = 1, ..., m,(∗)B(p0 , j) ≤ B(p0 , q 0 ), j = 1, ..., n.Äîêàçàòåëüñòâî.