Введение в теорию игр (сторонняя методичка) (1184510), страница 17
Текст из файла (страница 17)
ïåðâóþ ÷àñòü äîêàçàòåëüñòâà òåîðåìû 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.Äîêàçàòåëüñòâî. Íåîáõîäèìîñòü.
Ïóñòü (p0 , q 0 ) − ñèòóàöèÿ ðàâíîâåñèÿ. Òîãäà A(p, q 0 ) ≤ A(p0 , q 0 ) ∀ p ∈ P. Ïîëàãàÿ p = (0, ...0, 1, 0, ..., 0),ïîëó÷èì íåðàâåíñòâà óñëîâèÿ (∗) äëÿ ìàòðèöû A. Àíàëîãè÷íî âûâîäÿòñÿíåðàâåíñòâà äëÿ ìàòðèöû B.103ÃËÀÂÀ II. ÈÃÐÛ ÄÂÓÕ ËÈÖÄîñòàòî÷íîñòü. Ïóñòü ñèòóàöèÿ (p0 , q 0 ) óäîâëåòâîðÿåò óñëîâèþ (∗).Âîçüìåì ïðîèçâîëüíóþ ñìåøàííóþ ñòðàòåãèþ p ïåðâîãî èãðîêà, äîìíîæèì íåðàâåíñòâà A(i, q 0 ) ≤ A(p0 , q 0 ) íà pi è ñëîæèì èõ.  ðåçóëüòàòåïîëó÷èì íåðàâåíñòâî A(p, q 0 ) ≤ A(p0 , q 0 ). Àíàëîãè÷íî, äëÿ ëþáîé ñìåøàííîé ñòðàòåãèè q âòîðîãî èãðîêà ñïðàâåäëèâî íåðàâåíñòâîB(p0 , q) ≤ B(p0 , q 0 ).Òåîðåìà 10.1 (ñâîéñòâî äîïîëíÿþùåé íåæåñòêîñòè).
Ïóñòü(p0 , q 0 ) − ñèòóàöèÿ ðàâíîâåñèÿ â ñìåøàííûõ ñòðàòåãèÿõ áèìàòðè÷íîéèãðû Γ. Òîãäà1) p0i > 0 ⇒ A(i, q 0 ) = A(p0 , q 0 );2) qj0 > 0 ⇒ B(p0 , j) = B(p0 , q 0 ).Äîêàçàòåëüñòâî. Äîêàæåì óòâåðæäåíèå 1). Ïðåäïîëîæèì, ÷òî äëÿíåêîòîðîãî i1p0i1 > 0 è A(i1 , q 0 ) < A(p0 , q 0 ).  óñëîâèè (∗) êàæäîåíåðàâåíñòâî A(i, q 0 ) ≤ A(p0 , q 0 ), i = 1, ..., m óìíîæèì íà p0i è ñëîæèìèõ. Ïîñêîëüêó i1 -å íåðàâåíñòâî ñîõðàíèòñÿ ñòðîãèì, ïîëó÷èì A(p0 , q 0 ) <A(p0 , q 0 ) (ïðîòèâîðå÷èå). Óòâåðæäåíèå 2) äîêàçûâàåòñÿ àíàëîãè÷íî.Ñëåäñòâèå.
Ïóñòü (p0 , q 0 ) − ñèòóàöèÿ ðàâíîâåñèÿ â ñìåøàííûõ ñòðàòåãèÿõ áèìàòðè÷íîé èãðû Γ. Òîãäà1) A(i, q 0 ) < A(p0 , q 0 ) ⇒ p0i = 0;2) B(p0 , j) < B(p0 , q 0 ) ⇒ qj0 = 0.Òåîðåìà 10.2. Äëÿ òîãî ÷òîáû ñèòóàöèÿ (p0 , q 0 ) áûëà ñèòóàöèåé ðàâ-íîâåñèÿ â ñìåøàííûõ ñòðàòåãèÿõ áèìàòðè÷íîé èãðû Γ, íåîáõîäèìî è äîñòàòî÷íî, ÷òîáû íàøëèñü ìíîæåñòâà X 0 ⊆ X, Y 0 ⊆ Y è ÷èñëà v1 , v2 , äëÿêîòîðûõ âûïîëíåíû óñëîâèÿXaij qj0 = v1∀ i ∈ X 0,0j∈YPaij qj0 ≤ v1∀i∈/ X 0,(10.1)j∈Y 0 P q 0 = 1, q 0 ≥ 0 ∀ j ∈ Y 0 ,jjj∈Y 0X∀ j ∈ Y 0,p0i bij = v20i∈XP 0pi bij ≤ v2∀j∈/ Y 0,0i∈XP 0pi = 1, p0i ≥ 0 ∀ i ∈ X 0 .i∈X 0104(10.2) 10. Ñèòóàöèè ðàâíîâåñèÿ â áèìàòðè÷íûõ èãðàõÄîêàçàòåëüñòâî. Íåîáõîäèìîñòü.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
