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

Ïåðåáèðàåìâñå íåâûðîæäåííûå k × k -ïîäìàòðèöû A ìàòðèöû A, íà÷èíàÿ ñ k = 2.48Ÿ 5. Ìåòîäû ðåøåíèÿ ìàòðè÷íûõ èãðÄëÿ êàæäîé ïîäìàòðèöû A ðåøàåì ñèñòåìû óðàâíåíèé (5.3) è (5.4). Åñëèðåøåíèÿ íå ñóùåñòâóåò èëè íåêîòîðûå êîìïîíåíòûp0il , l = 1, ..., k, qj0t , t = 1, ..., kîòðèöàòåëüíû, òî ïåðåõîäèì ê ñëåäóþùåé ïîäìàòðèöå A. Ïóñòü óêàçàííûå êîìïîíåíòû ðåøåíèé íåîòðèöàòåëüíû. Òîãäà îïðåäåëèì ñìåøàííûåñòðàòåãèè((0p,i=i,qj0t , j = jt ,lilp0 : p0i =q 0 : qj0 =0,i 6= il ;0,j 6= jt .Òåïåðü äëÿ òðîéêè (p0 , q 0 , v) íåîáõîäèìî ïðîâåðèòü óñëîâèå (∗) òåîðåìû 4.1 0 .

Åñëè îíî âûïîëíåíî, òî èñêîìîå ðåøåíèå (p0 , q 0 , v) íàéäåíî. Âïðîòèâíîì ñëó÷àå ïåðåõîäèì ê ñëåäóþùåé ïîäìàòðèöå A.Ïðèìåð 5.4. Ðàññìîòðèì ìàòðèöó âèäà1 1 1 01 0 0 1A=0 1 0 00 0 1 100.11Çäåñü íåò ñëàáî äîìèíèðóåìûõ ñòðîê (äàæå íèêàêèìè âûïóêëûìè êîìáèíàöèÿìè − äîêàæèòå!) è ñëàáî äîìèíèðóþùèõ ñòîëáöîâ . Åñëè ïðèìåíèòü óêàçàííûé âûøå àëãîðèòì, òî ïîäìàòðèöà a11 a151 0A==a41 a450 1äàñò ðåøåíèå â ñìåøàííûõ ñòðàòåãèÿõp0 = (1/2, 0, 0, 1/2), q 0 = (1/2, 0, 0, 0, 1/2), v = 1/2.V. Ìåòîä Áðàóíà. ýòîì ïàðàãðàôå ìû ðàññìîòðèì èòåðàöèîííûé ìåòîä ïðèáëèæåííîãî ðåøåíèÿ èãðû ñ ìàòðèöåé A. Ïóñòü çàäàíî ÷èñëî ε > 0.

Òðåáóåòñÿíàéòè çíà÷åíèå èãðû ñ òî÷íîñòüþ äî âåëè÷èíû ε, à òàêæå ε-ìàêñèìèííóþè ε-ìèíèìàêñíóþ ñìåøàííûå ñòðàòåãèè èãðîêîâ.Ìåòîä Áðàóíà ñîñòîèò â ìíîãîêðàòíîì ôèêòèâíîì ðàçûãðûâàíèè ìàòðè÷íîé èãðû, ïðè êîòîðîì èãðîêè ïî îïðåäåëåííûì ïðàâèëàì âûáèðàþò ñâîè ÷èñòûå ñòðàòåãèè. Ïóñòü çà k ïîâòîðåíèé èãðû ïåðâûé èãðîê ri49ÃËÀÂÀ I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛðàç âûáðàë ñòðàòåãèþ i, i = 1, ..., m, à âòîðîé lj ðàç âûáðàë ñòðàòåãèþj, j = 1, ..., n. Âåêòîðû ÷àñòîò âûáîðà ÷èñòûõ ñòðàòåãèé!!r1rml1lnp(k) =, ...,, q(k) =, ...,kkkkÿâëÿþòñÿ ñìåøàííûìè ñòðàòåãèÿìè èãðîêîâ.Îïðåäåëèì èòåðàöèîííûé ïðîöåññ Áðàóíà.Øàã 1.

Èãðîêè âûáèðàþò ïðîèçâîëüíî ñòðàòåãèè i1 è j1 .Ïóñòü çà k ïîâòîðåíèé èãðû ïåðâûé èãðîê âûáðàë ñòðàòåãèè i1 , ..., ik ,à âòîðîé − ñòðàòåãèè j1 , ..., jk . Ïðè ýòîì p(k) è q(k) − ñîîòâåòñòâóþùèåâåêòîðû ÷àñòîò.Øàã k + 1. Èãðîêè âûáèðàþò ñòðàòåãèè ik+1 è jk+1 èç óñëîâèéA(ik+1 , q(k)) = max A(i, q(k)) = v1 (k),1≤i≤mA(p(k), jk+1 ) = min A(p(k), j) = v2 (k).1≤j≤nÊàæäûé èãðîê âûáèðàåò ñâîþ ÷èñòóþ ñòðàòåãèþ êàê íàèëó÷øèé îòâåòíà ñîîòâåòñòâóþùèé âåêòîð ÷àñòîò ïàðòíåðà. Åñëè íàèëó÷øèõ îòâåòîâíåñêîëüêî, òî âûáèðàåòñÿ ëþáîé èç íèõ.Ïîêàæåì, ÷òî v1 (k) è v2 (k) − îöåíêè äëÿ çíà÷åíèÿ v ìàòðè÷íîé èãðû:v2 (k) ≤ v ≤ v1 (k),k = 1, 2, ....(5.7)Äåéñòâèòåëüíî, èñïîëüçóÿ ñëåäñòâèå òåîðåìû 4.2 0 , ïîëó÷èìv2 (k) = min A(p(k), j) ≤ max min A(p, j) = v =1≤j≤np∈P 1≤j≤n= min max A(i, q) ≤ max A(i, q(k)) = v1 (k).q∈Q 1≤i≤m1≤i≤mÄëÿ äîêàçàòåëüñòâà ñõîäèìîñòè ïîñëåäîâàòåëüíîñòåé {v1 (k)}, {v2 (k)}ê çíà÷åíèþ èãðû v íàì ïîòðåáóåòñÿ îáîáùåííûé èòåðàöèîííûé ïðîöåññ.Ïóñòü c(0) ∈ E m , d(0) ∈ E n − äâà âåêòîðà, óäîâëåòâîðÿþùèå óñëîâèþmax ci (0) = min dj (0).

Âîçüìåì1≤i≤m1≤j≤ni1 ∈ Arg max ci (0), j1 ∈ Arg min dj (0).1≤i≤m1≤j≤n50Ÿ 5. Ìåòîäû ðåøåíèÿ ìàòðè÷íûõ èãðÏóñòü îïðåäåëåíû ñòðàòåãèè i1 , ..., ik , j1 , ..., jk è âåêòîðûc(0), c(1), ..., c(k), d(0), d(1), ..., d(k). Âîçüìåìik+1 ∈ Arg max ci (k), jk+1 ∈ Arg min dj (k)1≤i≤m1≤j≤nè ïîëîæèì äëÿ âñåõ i = 1, ..., m, j = 1, ..., nci (k + 1) = ci (k) + aijk , dj (k + 1) = dj (k) + aik j .Òàêèì îáðàçîì, âåêòîð c(k + 1) åñòü ñóììà âåêòîðà c(0) è ñòîëáöîâ ìàòðèöû A ñ íîìåðàìè j1 , ..., jk .

Àíàëîãè÷íî, âåêòîð d(k + 1) åñòü ñóììàâåêòîðà d(0) è ñòðîê ìàòðèöû A ñ íîìåðàìè i1 , ..., ik . Íåòðóäíî âèäåòü,÷òîci (k) = ci (0) +kXaijt = ci (0) +t=1nXaij lj = ci (0) + kA(i, q(k)),j=1dj (k) = dj (0) + kA(p(k), j).Ïðè íóëåâûõ âåêòîðàõ c(0) è d(0) ïîñòðîåííûé èòåðàöèîííûé ïðîöåñññîâïàäàåò ñ ïðîöåññîì Áðàóíà. Ïîñêîëüêó ìíîæåñòâàArg max ci (k) è Arg min dj (k) ìîãóò ñîäåðæàòü áîëåå îäíîãî ýëåìåíòà,1≤i≤m1≤j≤nïîñëåäîâàòåëüíîñòè {c(k)}, {d(k)} îïðåäåëÿþòñÿ â õîäå èòåðàöèîííîãîïðîöåññà íå îäíîçíà÷íî.Îïðåäåëèì, êàê è ðàíåå, ïîñëåäîâàòåëüíîñòè âåëè÷èídj (k)ci (k), v2 (k) = min, k = 1, 2, ....1≤j≤n1≤i≤m kkv1 (k) = maxÄàëåå áóäåò äîêàçàíà èõ ñõîäèìîñòü ê çíà÷åíèþ èãðû v äëÿ ëþáûõ âåêòîðîâ c(0), d(0).Èç íåðàâåíñòâ (ñì.

äîêàçàòåëüñòâî íåðàâåíñòâà (5.7))max A(i, q(k)) ≥ v ≥ min A(p(k), j), k = 1, 2, ...,1≤i≤m1≤j≤nñëåäóåò, ÷òî"lim v1 (k) = lim maxk→∞k→∞ 1≤i≤m#ci (0)+ A(i, q(k)) ≥ v ≥k51ÃËÀÂÀ I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛ"≥ lim mink→∞ 1≤j≤n#dj (0)+ A(p(k), j) = lim v2 (k).k→∞kÎòñþäàlim (v1 (k) − v2 (k)) ≥ 0.(5.8)k→∞Ïîêàæåì, ÷òîlim (v1 (k) − v2 (k)) ≤ 0.k→∞(5.9)Áóäåì èñïîëüçîâàòü îáîçíà÷åíèå∆(k) = max ci (k) − min dj (k).1≤i≤m1≤j≤nÑ ïîìîùüþ íåãî óñëîâèå max ci (0) = min dj (0) ìîæíî çàïèñàòü â âèäå1≤i≤m1≤j≤n∆(0) = 0.Îïðåäåëåíèå.

Áóäåì ãîâîðèòü, ÷òî i-àÿ ñòðîêà (j -é ñòîëáåö) ìàòðèöû A ñóùåñòâåííà (ñóùåñòâåíåí) íà îòðåçêå øàãîâ [s, s + t], åñëè äëÿíåêîòîðîãî øàãà t0 ∈ [s, s + t] it0 = i (jt0 = j).Ëåììà 5.1. Ïóñòü âñå ñòðîêè è ñòîëáöû ìàòðèöû A ñóùåñòâåííû íàîòðåçêå øàãîâ [s, s + t]. Òîãäàmax ci (s + t) − min dj (s + t) ≤ 4at,1≤i≤m1≤j≤n(5.10)ãäå a = max max |aij |.1≤i≤m 1≤j≤nÄîêàçàòåëüñòâî. Ïîêàæåì ñíà÷àëà, ÷òî â óñëîâèÿõ ëåììû ñïðàâåäëèâû íåðàâåíñòâàmax ci (s + t) − min ci (s + t) ≤ 2at,(5.11)max dj (s + t) − min dj (s + t) ≤ 2at.(5.12)1≤i≤m1≤j≤n1≤i≤m1≤j≤nÄîêàæåì (5.11).

Ïóñòü äëÿ l-îé ñòðîêè âûïîëíåíî ðàâåíñòâîmin ci (s + t) = cl (s + t). Èç óñëîâèÿ ëåììû âûòåêàåò, ÷òî íàéäåòñÿ òàêîé1≤i≤míîìåð øàãà t0 ∈ [s, s + t], ÷òî max ci (t0 ) = cl (t0 ). Òîãäà1≤i≤mmax ci (s + t) − min ci (s + t) =1≤i≤m1≤i≤m52Ÿ 5. Ìåòîäû ðåøåíèÿ ìàòðè÷íûõ èãð= max ci (s + t) − max ci (t0 ) + cl (t0 ) − cl (s + t) ≤1≤i≤m1≤i≤m≤ max (ci (s + t) − ci (t0 )) + cl (t0 ) − cl (s + t) ≤ 2at,1≤i≤mïîñêîëüêó âñå ïîñëåäíèå ðàçíîñòè íà ïðåâîñõîäÿò at. Íåðàâåíñòâî (5.12)äîêàçûâàåòñÿ àíàëîãè÷íî. Ïîêàæåì òàêæå, ÷òî ñïðàâåäëèâî íåðàâåíñòâîmin ci (s + t) − max dj (s + t) ≤ 0.1≤i≤m1≤j≤n(5.13)Ïóñòü v T − çíà÷åíèå èãðû ñ ìàòðèöåé AT , òðàíñïîíèðîâàííîé ê A.

Òîãäàmin A(i, q(s + t)) ≤ max min A(i, q) = v T =1≤i≤mq∈Q 1≤i≤m= min max A(p, j) ≤ max A(p(s + t), j).p∈P 1≤j≤n1≤j≤nÎòñþäà"min1≤i≤m#ci (0)ci (0)+ A(i, q(s + t)) ≤ max+ min A(i, q(s + t)) ≤1≤i≤m s + t1≤i≤ms+t"#dj (0)dj (0)≤ min+ max A(p(s + t), j)) ≤ max+ A(p(s + t), j))1≤j≤n1≤j≤n s + t1≤j≤n s + tÄîìíîæàÿ ýòî íåðàâåíñòâî íà s + t, âûâîäèì (5.13). Íåðàâåíñòâî (5.10)ïîëó÷àåòñÿ ñëîæåíèåì íåðàâåíñòâ (5.11)−(5.13).Ëåììà 5.2. Äëÿ ïðîèçâîëüíîé ìàòðèöû A è ïðîèçâîëüíîãî ε > 0íàéäåòñÿ òàêîé íîìåð øàãà k0 , ÷òî äëÿ ëþáûõ ïîñëåäîâàòåëüíîñòåéc(k), d(k), k = 0, 1, ...

èòåðàöèîííîãî ïðîöåññà ∆(k) ≤ εk ïðè k ≥ k0 .Äîêàçàòåëüñòâî. Óòâåðæäåíèå ëåììû âåðíî äëÿ 1 × 1-ìàòðèö A, ïîñêîëüêó òîãäà c(k) = d(k) äëÿ âñåõ k ≥ 1. Ïðèìåì, ÷òî ëåììà âåðíà äëÿâñåõ ïîäìàòðèö ìàòðèöû A è äîêàæåì, ÷òî îíà âåðíà è äëÿ A. Âûáåðåìk1 òàêèì îáðàçîì, ÷òîáû äëÿ ëþáûõ ïîñëåäîâàòåëüíîñòåéc1 (k), d1 (k), k = 0, 1, ... èòåðàöèîííîãî ïðîöåññà, ñîîòâåòñòâóþùåãî ïîäìàòðèöå A1 = (aij )i∈Ij∈J , ïîëó÷åííîé èç A âû÷åðêèâàíèåì ñòðîêè èëèñòîëáöà, áûëî âûïîëíåíî íåðàâåíñòâî1def∆1 (k) = max c1i (k) − min d1j (k) ≤ εk, k ≥ k1 .i∈Ij∈J253ÃËÀÂÀ I.

ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛÄîêàæåì, ÷òî åñëè äëÿ ìàòðèöû A íåêîòîðàÿ ñòðîêà (ñòîëáåö) íåñóùåñòâåííà (íåñóùåñòâåíåí) íà îòðåçêå [s, s + k1 ], òî ñïðàâåäëèâî íåðàâåíñòâî1(5.14)∆(s + k1 ) ≤ ∆(s) + εk1 .2Ïðåäïîëîæèì, íàïðèìåð, ÷òî ïîäìàòðèöà A1 ïîëó÷àåòñÿ âû÷åðêèâàíèåìèç A íåñóùåñòâåííîé l-é ñòðîêè. Ïîëîæèì I = {1, ..., m}\{l},d1j (0) = dj (s) + ∆(s), j = 1, ..., n, c1i (0) = ci (s), i ∈ I.Ïîñêîëüêó l-àÿ ñòðîêà ìàòðèöû A íåñóùåñòâåííà, ∆1 (0) = 0 è â èòåðàöèîííîì ïðîöåññå ìîæíî âçÿòü i1k = is+k , jk1 = js+k , k = 1, ..., k1 . Ñëåäîâàòåëüíî, d1j (k) = dj (s + k) + ∆(s), j = 1, ..., n, c1 (k) = (ci (s + k), i ∈ I), k =1, ..., k1 . Èòåðàöèîííûé ïðîöåññ äëÿ ìàòðèöû A1 ìîæíî ïðîäîëæàòü èïðè k > k1 .Íà îñíîâàíèè âûáîðà k1 ∆1 (k1 ) ≤ 21 εk1 .

Ïîýòîìó1∆(s + k1 ) = ∆1 (k1 ) + ∆(s) ≤ ∆(s) + εk12è íåðàâåíñòâî (5.14) äîêàçàíî.Ìû ìîæåì òåïåðü ïîêàçàòü, ÷òî äëÿ ëþáûõ ïîñëåäîâàòåëüíîñòåéc(k), d(k), k = 0, 1, ..., èòåðàöèîííîãî ïðîöåññà ∆(k) ≤ εk ïðè k ≥ 8ak1 /ε.Ðàññìîòðèì öåëîå k > k1 è ïðåäñòàâèì åãî â âèäå k = (θ + t)k1 , ãäå0 ≤ θ < 1, à t > 0 − öåëîå (θk1 − îñòàòîê îò äåëåíèÿ k íà k1 ).Ñëó÷àé 1. Íàéäåòñÿ òàêîå öåëîå ïîëîæèòåëüíîå ÷èñëî h ≤ t, ÷òî âñåñòðîêè è ñòîëáöû ìàòðèöû A íà îòðåçêå [(θ + h − 1)k1 , (θ + h)k1 ] ñóùåñòâåííû. Áåðÿ íàèáîëüøåå èç òàêèõ h, èìååì1∆(k) ≤ ∆((θ + h)k1 ) + ε(t − h)k1 .2(5.15)Ýòî íåðàâåíñòâî ïîëó÷åíî ïîâòîðíûì ïðèìåíåíèåì íåðàâåíñòâà (5.14),ïîñêîëüêó íà êàæäîì èç îòðåçêîâ[(θ + r − 1)k1 , (θ + r)k1 ], r = h + 1, ..., t,íåêîòîðàÿ ñòðîêà èëè ñòîëáåö ìàòðèöû A íåñóùåñòâåííû.Èç ëåììû 5.1 íà îñíîâàíèè âûáîðà h èìååì∆((θ + h)k1 ) ≤ 4ak1 .54(5.16)Ÿ 5.