Введение в теорию игр (сторонняя методичка) (Введение в теорию игр (сторонняя методичка).PDF), страница 9

Ìåòîä Áðàóíà. ýòîì ïàðàãðàôå ìû ðàññìîòðèì èòåðàöèîííûé ìåòîä ïðèáëèæåííîãî ðåøåíèÿ èãðû ñ ìàòðèöåé 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. Ìåòîäû ðåøåíèÿ ìàòðè÷íûõ èãðÈç (5.15) è (5.16) ïîëó÷àåì11∆(k) ≤ 4ak1 + ε(t − h)k1 ≤ (4a + εt)k1 .22Ñëó÷àé 2.

 êàæäîì îòðåçêå [(θ + h − 1)k1 , (θ + h)k1 ], h = 1, ..., t,íåêîòîðàÿ ñòðîêà èëè ñòîëáåö íåñóùåñòâåííû. Ñëåäîâàòåëüíî, êàê è ïðèâûâîäå (5.15),11∆(k) ≤ ∆(θk1 ) + εtk1 ≤ (2aθ + εt)k1 .22 îáîèõ ñëó÷àÿõ, èñïîëüçóÿ íåðàâåíñòâî tk1 ≤ k, ïîëó÷èì∆(k) ≤ (4a + 12 εt)k1 ≤ 4ak1 + 12 εk ≤ εk ïðè k ≥ 8ak1 /ε.Èç ëåììû 5.2 âûòåêàåò íåðàâåíñòâî (5.9) è ñõîäèìîñòü ïîñëåäîâàòåëüíîñòåé v1 (k), v2 (k), k = 0, 1, ..., ê çíà÷åíèþ èãðû v.Âåðíåìñÿ ê ìåòîäó Áðàóíà.

Ñôîðìóëèðóåì ïðàâèëî îñòàíîâêè. Ïóñòüçàäàíî ÷èñëî ε > 0. Áóäåì îñòàíàâëèâàòüñÿ íà øàãå k0 , êîãäà âïåðâûåâûïîëíåíî íåðàâåíñòâîv1 (k0 ) − v2 (k0 ) ≤ ε.(5.17)Èç (5.7) è (5.17) ñëåäóåò, ÷òî âåëè÷èíû v1 (k0 ), v2 (k0 ) ïðèáëèæàþò çíà÷åíèå v ìàòðè÷íîé èãðû ñ òî÷íîñòüþ äî ε. Ïîêàæåì, ÷òî p(k0 ) − εìàêñèìèííàÿ ñòðàòåãèÿ ïåðâîãî èãðîêà.

Äåéñòâèòåëüíî,min A(p(k0 ), j) = v2 (k0 ) ≥ v − ε.1≤j≤nÀíàëîãè÷íî, q(k0 ) −ε-ìèíèìàêñíàÿ ñòðàòåãèÿ âòîðîãî èãðîêà.Òåîðåìà 5.3.  ìåòîäå Áðàóíà lim v1 (k) = lim v2 (k) = v, à ëþáûåk→∞k→∞ïðåäåëüíûå òî÷êè p0 , q 0 ïîñëåäîâàòåëüíîñòåé {p(k)}, {q(k)} ÿâëÿþòñÿ îïòèìàëüíûìè ñìåøàííûìè ñòðàòåãèÿìè èãðîêîâ.Äîêàçàòåëüñòâî. Ñõîäèìîñòü ïîñëåäîâàòåëüíîñòåé {v1 (k)} è {v2 (k)}ê çíà÷åíèþ èãðû v âûòåêàåò èç ëåììû 5.2.

Ïóñòü p0 − ëþáàÿ ïðåäåëüíàÿ òî÷êà ïîñëåäîâàòåëüíîñòè {p(k)}. Ïîêàæåì, ÷òî p0 − îïòèìàëüíàÿñìåøàííàÿ ñòðàòåãèÿ ïåðâîãî èãðîêà. Äåéñòâèòåëüíî, ïîñêîëüêó ïîñëåäîâàòåëüíîñòü {p(k)} ïðèíàäëåæèò êîìïàêòó P, áåç ïîòåðè îáùíîñòè(âûäåëÿÿ ñîîòâåòñòâóþùóþ ïîäïîñëåäîâàòåëüíîñòü) ìîæíî ñ÷èòàòü, ÷òîîíà ñõîäèòñÿ ê p0 .

Òîãäàmin A(p(k), j) ≥ v − εk , k = 1, 2, ...,1≤j≤m55ÃËÀÂÀ I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛãäå εk → 0 + . Ïåðåõîäÿ â ýòèõ íåðàâåíñòâàõ ê ïðåäåëó ïðè k → ∞, ïîëó÷èì íåðàâåíñòâî min A(p0 , j) ≥ v, ÷òî îçíà÷àåò îïòèìàëüíîñòü ñòðà1≤j≤mòåãèè p0 . Àíàëîãè÷íî äîêàçûâàåòñÿ îïòèìàëüíîñòü äëÿ âòîðîãî èãðîêàëþáîé ïðåäåëüíîé òî÷êè q 0 ïîñëåäîâàòåëüíîñòè {q(k)}.Îöåíèì ñêîðîñòü ñõîäèìîñòè ïîñëåäîâàòåëüíîñòåé {v1 (k)} è {v2 (k)}ê çíà÷åíèþ èãðû v.Ïóñòü Al , l ≥ 0 − ïîäìàòðèöà, ïîëó÷åííàÿ èç ìàòðèöû A âû÷åðêèâàíèåì êàêèõ-ëèáî l ñòðîê èëè ñòîëáöîâ, à {v1l (k)}, {v2l (k)} − ïîñëåäîâàòåëüíîñòè îáîáùåííîãî èòåðàöèîííîãî ïðîöåññà, ñîîòâåòñòâóþùåãî ïîäìàòðèöå Al . Îáîçíà÷èì ÷åðåç kl ÷èñëî ïîâòîðåíèé èãðû, ïðè êîòîðîì äëÿëþáîé ïîäìàòðèöû Al è ëþáûõ íà÷àëüíûõ âåêòîðîâ cl (0), dl (0) âûïîëíåíî íåðàâåíñòâî v1l (k) − v2l (k) ≤ 2−l ε ∀k ≥ kl .