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

Òîãäà ïî òåîðåìå4.3 0nXA(i, q 0 ) = ai qi0 = v, i = 1, ..., n,qi0 = 1.i=1Ðåøàÿ ýòó ñèñòåìó îòíîñèòåëüíî n + 1 íåèçâåñòíûõ qi0 , i = 1, ..., n, v,nP1ïîëó÷èì qi0 = v/ai , i = 1, ..., n, ãäå v = 1/.akk=1Àíàëîãè÷íî ìîæíî íàéòè, ÷òî p0 = q 0 .Ïðèâåäåì îäíó èíòåðïðåòàöèþ ýòîé èãðû. Ïóñòü ìèëèöèîíåð (ïåðâûé èãðîê) èùåò ïðåñòóïíèêà (âòîðîãî èãðîêà) â îäíîì èç n áàðîâ. Åñëèìèëèöèîíåð ïðèõîäèò â áàð i, ãäå íàõîäèòñÿ ïðåñòóïíèê, òî âåðîÿòíîñòüåãî çàäåðæàíèÿ ðàâíà ai . Îïòèìàëüíûå ñìåøàííûå ñòðàòåãèè ïðåäïèñûâàþò èãðîêàì èäòè ñ áîëüøåé âåðîÿòíîñòüþ â òîò áàð, ãäå âåðîÿòíîñòüçàäåðæàíèÿ ìåíüøå.

Ïîýòîìó îïòèìàëüíàÿ ñòðàòåãèÿ ïðåñòóïíèêà åñòåñòâåííà, à ìèëèöèîíåðà − ïàðàäîêñàëüíà. Îòìåòèì òàêæå, ÷òî ìû îäíîâðåìåííî ðåøèëè ñëåäóþùóþ çàäà÷ó ïîèñêà ìàêñèìèíà:v = max min A(p, i) = max min ai pi .p∈P 1≤i≤nŸ 5.p∈P 1≤i≤nÌåòîäû ðåøåíèÿ ìàòðè÷íûõ èãð ýòîì ïàðàãðàôå èçëîæåíû íåêîòîðûå ìåòîäû ðåøåíèÿ ìàòðè÷íûõèãð â ñìåøàííûõ ñòðàòåãèÿõ. Ïðè ýòîì íàøà öåëü áóäåò ñîñòîÿòü â ïîèñêå õîòÿ áû îäíîãî ðåøåíèÿ èãðû.I. Äîìèíèðîâàíèå ñòðîê è ñòîëáöîâ.Åñëè ýëåìåíòû íåêîòîðîé ñòðîêè i1 ìàòðèöû A ìåíüøå ñîîòâåòñòâóþùèõ ýëåìåíòîâ äðóãîé ñòðîêè i2 , òî èíòóèòèâíî ÿñíî, ÷òî ñòðîêó i1ïåðâîìó èãðîêó ìîæíî íå èñïîëüçîâàòü.

Ñôîðìóëèðóåì óñëîâèÿ äîìèíèðîâàíèÿ ñòðîê è ñòîëáöîâ ìàòðèöû èãðû, ïîçâîëÿþùèå óìåíüøèòü ååðàçìåðû.37ÃËÀÂÀ I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛÎïðåäåëåíèå. Áóäåì ãîâîðèòü, ÷òî âåêòîð a = (a1 , ..., al ) ñëàáî äîìèíèðóåò âåêòîð b = (b1 , ..., bl ), åñëè ai ≥ bi , i = 1, ..., l. Áóäåì ãîâîðèòü îñòðîãîì äîìèíèðîâàíèè, åñëè âñå íåñòðîãèå íåðàâåíñòâà ≥ çàìåíåíû íàñòðîãèå >. Çàìåòèì, ÷òî ñëàáîå äîìèíèðîâàíèå âîçìîæíî äàæå â ñëó÷àåðàâåíñòâà âåêòîðîâ a è b.Îïðåäåëåíèå.

Äëÿ âåêòîðîâ a(i) , i = 1, ..., m, åâêëèäîâà ïðîñòðàíñòâàmmPPè ÷èñåë pi ≥ 0, i = 1, ..., m,pi = 1, ëèíåéíàÿ êîìáèíàöèÿpi a(i)i=1i=1íàçûâàåòñÿ âûïóêëîé êîìáèíàöèåé âåêòîðîâ a(i) ñ êîýôôèöèåíòàìè pi .Òåîðåìà 5.1 (Î äîìèíèðîâàíèè ñòðîê). Ïóñòü íåêîòîðàÿ ñòðîêàìàòðèöû A ñëàáî äîìèíèðóåòñÿ âûïóêëîé êîìáèíàöèåé îñòàëüíûõ ñòðîê.Òîãäà ýòà ñòðîêà âõîäèò ñ íóëåâîé âåðîÿòíîñòüþ â íåêîòîðóþ îïòèìàëüíóþ ñìåøàííóþ ñòðàòåãèþ ïåðâîãî èãðîêà. Åñëè óêàçàííîå äîìèíèðîâàíèå ñòðîãîå, òî ýòà ñòðîêà âõîäèò ñ íóëåâîé âåðîÿòíîñòüþ â ëþáóþ îïòèìàëüíóþ ñìåøàííóþ ñòðàòåãèþ ïåðâîãî èãðîêà. Äîìèíèðóåìûå ñòðîêèìîæíî âû÷åðêíóòü èç ìàòðèöû èãðû.Äîêàçàòåëüñòâî.

Ïóñòü ñòðîêà ìàòðèöû A ñ íîìåðîì i1 ñëàáî äîìèíèðóåòñÿ âûïóêëîé êîìáèíàöèåé îñòàëüíûõ ñòðîê ñ êîýôôèöèåíòàìèpi ≥ 0, i 6= i1 :XXai1 j ≤pi aij , j = 1, ..., n,pi = 1.(5.1)i6=i1i6=i1Ðàññìîòðèì ìàòðèöó Â, ïîëó÷åííóþ èç A âû÷åðêèâàíèåì (èñêëþ÷åíèåì) i1 -îé ñòðîêè. Ïóñòü (p̂, q 0 , v) − ðåøåíèå èãðû ñ ìàòðèöåé Â. Ïîëîæèìp0 = (p̂1 , ..., p̂i1 −1 , 0, p̂i1 +1 , ..., p̂m ) è äîêàæåì, ÷òî òðîéêà (p0 , q 0 , v) − ðåøåíèå èãðû ñ ìàòðèöåé A. Òåì ñàìûì áóäåò äîêàçàíî âòîðîå óòâåðæäåíèåòåîðåìû è îáîñíîâàíî âû÷åðêèâàíèå i1 -îé ñòðîêè.

Äåéñòâèòåëüíî, ðåøàÿèãðó ñ ìàòðèöåé Â, ìû íàõîäèì ðåøåíèå èñõîäíîé èãðû, äîáàâëÿÿ â p̂íóëåâóþ i1 -óþ êîìïîíåíòó.Ïðîâåðèì óñëîâèå (∗) äëÿ òðîéêè (p0 , q 0 , v) â èãðå ñ ìàòðèöåé A. ÈìååìA(p0 , j) = Â(p̂, j) ≥ v, j = 1, ..., n; A(i, q 0 ) = Â(i, q 0 ) ≤ v ∀ i 6= i1 .Ïóñòü i = i1 . Òîãäà, ïîëàãàÿ p0 = (pi , i 6= i1 ), ïîëó÷èìA(i1 , q 0 ) =nXj=1ai1 j qj0 ≤n XX(aij pi )qj0 = Â(p0 , q 0 ) ≤ v,j=1 i6=i138Ÿ 5. Ìåòîäû ðåøåíèÿ ìàòðè÷íûõ èãðïîñêîëüêó ñòðàòåãèÿ q 0 âòîðîãî èãðîêà îïòèìàëüíà â èãðå ñ ìàòðèöåé Â.Èòàê, (p0 , q 0 , v) − ðåøåíèå èãðû ñ ìàòðèöåé A.Ïðåäïîëîæèì, ÷òî íåðàâåíñòâà â (5.1) ñòðîãèå. Òîãäà â ïîñëåäíèõâûêëàäêàõ ïåðâîå íåðàâåíñòâî òàêæå ñòðîãîå è A(i1 , q 0 ) < v. Ïóñòü p∗ −ïðîèçâîëüíàÿ îïòèìàëüíàÿ ñìåøàííàÿ ñòðàòåãèÿ ïåðâîãî èãðîêà. Òîãäà(p∗ , q 0 , v) − ðåøåíèå èãðû ñ ìàòðèöåé A.

Èç ïîñëåäíåãî íåðàâåíñòâà ïîñâîéñòâó äîïîëíÿþùåé íåæåñòêîñòè ïîëó÷àåì p∗i1 = 0.Îòìåòèì, ÷òî ïðè èñêëþ÷åíèè ñòðîãî äîìèíèðóåìûõ ñòðîê îïòèìàëüíûå ñìåøàííûå ñòðàòåãèè ïåðâîãî èãðîêà ñîõðàíÿþòñÿ. Ïðè ñëàáîì äîìèíèðîâàíèè îïòèìàëüíûå ñòðàòåãèè ìîãóò òåðÿòüñÿ.  êà÷åñòâå ïðèìåðà äîñòàòî÷íî ðàññìîòðåòü ìàòðèöó èãðû ñ ðàâíûìè ýëåìåíòàìè.Ñëåäóþùóþ òåîðåìó äîêàæèòå ñàìîñòîÿòåëüíî.Òåîðåìà 5.1 0 (Î äîìèíèðîâàíèè ñòîëáöîâ).

Ïóñòü íåêîòîðûéñòîëáåö ìàòðèöû A ñëàáî äîìèíèðóåò âûïóêëóþ êîìáèíàöèþ îñòàëüíûõñòîëáöîâ ýòîé ìàòðèöû. Òîãäà ýòîò ñòîëáåö âõîäèò ñ íóëåâîé âåðîÿòíîñòüþ â íåêîòîðóþ îïòèìàëüíóþ ñìåøàííóþ ñòðàòåãèþ âòîðîãî èãðîêà.Åñëè óêàçàííîå äîìèíèðîâàíèå ñòðîãîå, òî ýòîò ñòîëáåö âõîäèò ñ íóëåâîé âåðîÿòíîñòüþ â ëþáóþ îïòèìàëüíóþ ñìåøàííóþ ñòðàòåãèþ âòîðîãîèãðîêà. Äîìèíèðóþùèå ñòîëáöû ìîæíî âû÷åðêíóòü èç ìàòðèöû èãðû.Ïðèìåð 5.1. Ðåøèòü èãðó ñ ìàòðèöåé3 1 5A = 1 3 3 .2 2 1Çäåñü ïîëóñóììà ïåðâûõ äâóõ ñòðîê ñëàáî äîìèíèðóåò òðåòüþ ñòðîêó èåå ìîæíî âû÷åðêíóòü.  ïîëó÷åííîé ìàòðèöå òðåòèé ñòîëáåö ñëàáî äîìèíèðóåòÏîñëå åãî âû÷åðêèâàíèÿ ïîëó÷èì öèêëè÷åñêóþ ìàòðèöó âòîðîé.3 1 =ñ ðåøåíèåì (p̂, q̂, v) = ((1/2, 1/2), (1/2, 1/2), 2).

Ïîýòîìó èñ1 3õîäíàÿ èãðà èìååò ðåøåíèå(p0 , q 0 , v) = ((1/2, 1/2, 0), (1/2, 1/2, 0), 2).Óïðàæíåíèå 5.1. Ïóñòü ìàòðèöà A èìååò ñåäëîâóþ òî÷êó. Ïîêàçàòü,÷òî ïîñëå èñêëþ÷åíèÿ ñëàáî äîìèíèðóåìûõ ñòðîê è ñëàáî äîìèíèðóþùèõ ñòîëáöîâ áåç èñïîëüçîâàíèÿ âûïóêëûõ êîìáèíàöèé ðåäóöèðîâàííàÿìàòðèöà èìååò ñåäëîâóþ òî÷êó ìàòðèöû A.39ÃËÀÂÀ I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛÓïðàæíåíèå 5.2. Ïîëêîâíèêó Áëîòòî1 (ïåðâîìó èãðîêó) ïîñòàâëåíà çàäà÷à ïðîðûâà òðåìÿ ïîëêàìè ÷åðåç äâà ãîðíûõ ïåðåâàëà, îõðàíÿåìûõ äâóìÿ ïîëêàìè ïðîòèâíèêà (âòîðîãî èãðîêà).

Ñòðàòåãèÿ Áëîòòî(k1 , k2 ) ∈ X = {(3, 0), (2, 1), (1, 2), (0, 3)} ñîñòîèò â òîì, ÷òî k1 ïîëêîâíàïðàâëÿþòñÿ íà ïåðâûé ïåðåâàë, à k2 − íà âòîðîé. Ïðîòèâíèê ðàñïîëàãàåò àíàëîãè÷íûìè ñòðàòåãèÿìè (l1 , l2 ) ∈ Y = {(2, 0), (1, 1), (0, 2)}.

ÏîëêèÁëîòòî è ïðîòèâíèêà, âñòðåòèâøèñü íà ïåðåâàëå, âçàèìíî óíè÷òîæàþòäðóã äðóãà. Âûèãðûøåì Áëîòòî ÿâëÿåòñÿ îáùåå ÷èñëî åãî ïîëêîâ, ïðîðâàâøèõñÿ ÷åðåç äâà ïåðåâàëà, ò.å. âåëè÷èíà max[k1 −l1 , 0]+max[k2 −l2 , 0].Ðåøèòü ìàòðè÷íóþ èãðó è íàéòè îïòèìàëüíóþ ñòðàòåãèþ Áëîòòî.II. Ãðàôè÷åñêèé ìåòîä ðåøåíèÿ èãð ñ ìàòðèöàìè ðàçìåðîâ 2 × n èm × 2.Ðàññìîòðèì èãðó ñ 2 × n-ìàòðèöåé A. Ñìåøàííàÿ ñòðàòåãèÿ ïåðâîãîèãðîêà p = (p1 , 1 − p1 ) îïðåäåëÿåòñÿ âåëè÷èíîé p1 ∈ [0, 1]. Çíà÷åíèå èãðû,ñîãëàñíî ñëåäñòâèþ òåîðåìû 4.2 0 , ïðåäñòàâèìî â âèäåv = max min A(p, j) = max min [a1j p1 + a2j (1 − p1 )].0≤p1 ≤1 1≤j≤np∈P 1≤j≤nÄëÿ íàõîæäåíèÿ çíà÷åíèÿ èãðû è îïòèìàëüíîé ñìåøàííîé ñòðàòåãèèïåðâîãî èãðîêà äîñòàòî÷íî íà îòðåçêå [0,1] ïîñòðîèòü ãðàôèêè ñåìåéñòâàëèíåéíûõ ôóíêöèé lj (p1 ) = a1j p1 + a2j (1 − p1 ) ñ óãëîâûìè êîýôôèöèåíòàìè kj = a1j − a2j , j = 1, ..., n, è íàéòè òî÷êó ìàêñèìóìà p01 ôóíêöèèmin lj (p1 ) − íèæíåé îãèáàþùåé ñåìåéñòâà (ðèñ.

5.1).1≤j≤n6SSlj1SSQQQ SvQ SQ SQQSQSQ lS Q j2SQS01p01- p1Ðèñ. 5.11 ÏîëêîâíèêÁëîòòî − àíåêäîòè÷åñêèé ïåðñîíàæ, äåéñòâóþùåå ëèöî ìíîãèõ èëëþñòðàòèâíûõ ïðèìåðîâ èç îáëàñòè àíòàãîíèñòè÷åñêèõ èãð.40Ÿ 5. Ìåòîäû ðåøåíèÿ ìàòðè÷íûõ èãðÍàéäåì îïòèìàëüíóþ ñìåøàííóþ ñòðàòåãèþ âòîðîãî èãðîêà. Ðàçáåðåì ñëåäóþùèå âîçìîæíîñòè.à) 0 < p01 < 1.Ýòîò ñëó÷àé ïðåäñòàâëåí íà ðèñ.

5.1. Âîçüìåì äâå ïðÿìûå lj1 è lj2 ,ïðîõîäÿùèå ÷åðåç òî÷êó (p01 , v) è èìåþùèå óãëîâûå êîýôôèöèåíòû kj1 ≥0, kj2 ≤ 0. Ðàññìîòðèì óðàâíåíèåkj1 q ∗ + kj2 (1 − q ∗ ) = 0.(5.2)Îíî èìååò ðåøåíèå q ∗ , ïðèíàäëåæàùåå îòðåçêó [0,1]. Èç (5.2) ñëåäóåò,÷òî óãëîâîé êîýôôèöèåíò ïðÿìîé lj1 (p1 )q ∗ + lj2 (p1 )(1 − q ∗ ) ðàâåí íóëþ.Ñìåøàííàÿ ñòðàòåãèÿ âòîðîãî èãðîêà∗j = j1 ,q ,00∗q : qj = 1 − q , j = j2 ,0,j 6= j1 , j2 ,îïòèìàëüíà, ïîñêîëüêó ïðè âñåõ p1 ∈ [0, 1]A(p, q 0 ) = lj1 (p1 )q ∗ + lj2 (p1 )(1 − q ∗ ) = v.á) p01 = 0. ýòîì ñëó÷àå ÷èñòàÿ ñòðàòåãèÿ 2 ïåðâîãî èãðîêà ÿâëÿåòñÿ îïòèìàëüíîé.

Ïîêàæåì, ÷òî ó âòîðîãî èãðîêà òàêæå èìååòñÿ ÷èñòàÿ îïòèìàëüíàÿñòðàòåãèÿ. Äåéñòâèòåëüíî, íàéäåòñÿ ïðÿìàÿ lj1 , ïðîõîäÿùàÿ ÷åðåç òî÷êó(0, v) è èìåþùàÿ óãëîâîé êîýôôèöèåíò kj1 ≤ 0. Âûáèðàÿ ÷èñòóþ ñòðàòåãèþ j1 , âòîðîé èãðîê íå ïîçâîëèò ïåðâîìó âûèãðàòü áîëüøå, ÷åì v,ïîñêîëüêó A(p, j1 ) = lj1 (p1 ) ≤ v ïðè âñåõ p1 ∈ [0, 1]. Èòàê, ìàòðèöà èãðûèìååò ñåäëîâóþ òî÷êó (2, j1 ).â) p01 = 1. ýòîì ñëó÷àå, àíàëîãè÷íîì á), ìàòðèöà èãðû òàêæå èìååò ñåäëîâóþòî÷êó.−1 −2 3Ïðèìåð 5.2. Ðåøèì èãðó ñ ìàòðèöåé A =.24 1Ïîñòðîèâ òðè ïðÿìûå (ðèñ.

5.2)l1 (p1 ) = (−1)p1 + 2(1 − p1 ) = 2 − 3p1 ,l2 (p1 ) = (−2)p1 + 4(1 − p1 ) = 4 − 6p1 ,l3 (p1 ) = 3p1 + 1(1 − p1 ) = 1 + 2p1 ,íàéäåì, ÷òî ìàêñèìóì íèæíåé îãèáàþùåé äîñòèãàåòñÿ â p01 = 1/5 − òî÷êåïåðåñå÷åíèÿ ïðÿìûõ l1 è l3 .41ÃËÀÂÀ I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛ46J2v10J l2JJl3JZJZJZ Z JZJZJZJZl1011p1 = 5Jp1Ðèñ. 5.2Çíà÷åíèå èãðû v = l1 (p01 ) = 7/5 è p0 = (1/5, 4/5). Çäåñü j1 = 3, k3 =2, j2 = 1, k1 = −3. Èç óðàâíåíèÿ 2q ∗ + (−3)(1 − q ∗ ) = 0 íàõîäèì q ∗ =3/5. Îòñþäà q 0 = (2/5, 0, 3/5) − îïòèìàëüíàÿ ñòðàòåãèÿ âòîðîãî èãðîêà.Ñäåëàéòå ïðîâåðêó óñëîâèÿ (∗) òåîðåìû 4.1 0 äëÿ íàéäåííîãî ðåøåíèÿ(p0 , q 0 , v).Óïðàæíåíèå 5.3.

Íàéäèòå âñå îïòèìàëüíûå ñòðàòåãèè èãðîêîâ â èãðå3 1 0ñ ìàòðèöåé A =.0 1 3Òåïåðü ðàññìîòðèì èãðó ñ m × 2-ìàòðèöåé A. Ñìåøàííàÿ ñòðàòåãèÿq = (q1 , 1 − q1 ) âòîðîãî èãðîêà îïðåäåëÿåòñÿ âåëè÷èíîé q1 ∈ [0, 1]. Çíà÷åíèå èãðû, ñîãëàñíî ñëåäñòâèþ òåîðåìû 4.2 0 , ïðåäñòàâèìî â âèäåv = min max A(i, q) = min max [ai1 q1 + ai2 (1 − q1 )].q∈Q 1≤i≤m0≤q1 ≤1 1≤i≤mÏîýòîìó íåîáõîäèìî ïîñòðîèòü âåðõíþþ îãèáàþùóþ max li (q1 ) ñåìåé1≤i≤mñòâà ïðÿìûõ li (q1 ) = ai1 q1 +ai2 (1−q1 ), i = 1, ..., m, è íàéòè íà îòðåçêå [0,1]òî÷êó q10 åå ìèíèìóìà.