А.А. Васин, В.В. Морозов - Введение в теорию игр с приложениями к экономике (1184512), страница 10
Текст из файла (страница 10)
Äîêàæèòå, ÷ò� óñëîâè� (5.3) � (5.4) äîñòàòî÷í� äë� òîãî, ÷òîá� îïòèìàëüíû� ñìåøàííû� ñòðàòåãè� p0 � q 0 áûë� êðàéíèì� îïòèìàëüíûìè. 47 ÃËÀÂ� I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈ� ÈÃÐ�Ïîêàæåì, ÷ò� ñèñòåì� k + 1 ëèíåéíû� óðàâíåíè� (5.3) îòíîñèòåëüí� k + 1 íåèçâåñòíû� p0 il , l = 1, ..., k, v ëèá� í� èìåå� ðåøåíèÿ, ëèá� èìåå� åäèíñòâåííî� ðåøåíèå. Äåéñòâèòåëüíî, ðàñøèðåííà� ìàòðèö� ñèñòåì� (5.3) èìåå� âè� ⎛ ⎞ ai1 j1 · · · aik j1 −10⎜ · · · · · · · · · −1 0⎟ . ⎜ ai1 j · · · ai j −1 0⎠ k k k 1 · · · 10 1Íåòðóäí� âèäåòü, ÷ò� å� ðàí� ðàâå� k + 1. Åñë� ñèñòåì� (5.3) èìåå� ðåøåíèå, ò� ï� òåîðåì� Êðåíåêåðà-Êàïåëë� ðàí� ìàòðèö� ñèñòåì� òàêæ� ðàâå� k + 1 � îí� − íåâûðîæäåííàÿ.
Îòñþä� ñëåäóå� åäèíñòâåííîñò� ðåøåíè� ñèñòåì� (5.3). Âûïèøå� � ïîñëåäíå� ñëó÷à� ðåøåíè� ñèñòå� (5.3) � (5.4) � ÿâíî� âèäå. Äë� ýòîã� ââåäå� âåêòîð� p = (p0 il , l = 1, ..., k), q = (qj0 t , t = 1, ..., k), e = (1, ..., 1) ∈ E k � çàïèøå� ñèñòåì� (5.3) � ìàòðè÷íû� îáîçíà÷åíèÿ� pA = ve, p, e = 1. Óìíîæà� ïåðâî� ðàâåíñòâ� ñïðàâ� í� ìàòðèö� (A)−1 , âûðàçè� âåêòî� p −1 ÷åðå� v : p = ve(A) . Ïîäñòàâëÿ� ýò� âûðàæåíè� � óðàâíåíè� p, e = 1, ïîëó÷è� p = e(A)−1 1 , v = .
e(A)−1 , e e(A)−1 , e Àíàëîãè÷í� è� ñèñòåì� (5.4) íàõîäèòñ� q = (A)−1 e . (A)−1 e, e Óïðàæíåíè� 5.7. Ïðèâåäèò� ïðèìå� 2 × 2-ìàòðèö� A, äë� êîòîðî� ñèñòåì� (5.3) í� èìåå� ðåøåíèÿ. Ðàññìîòðè� òåïåð� àëãîðèò� ðåøåíè� ìàòðè÷íî� èãðû. Ïåðåáèðàå� âñ� íåâûðîæäåííû� k × k -ïîäìàòðèö� A ìàòðèö� A, íà÷èíà� � k = 2. 48 5. Ìåòîä� ðåøåíè� ìàòðè÷íû� èã�Äë� êàæäî� ïîäìàòðèö� A ðåøàå� ñèñòåì� óðàâíåíè� (5.3) � (5.4).
Åñë� ðåøåíè� í� ñóùåñòâóå� èë� íåêîòîðû� êîìïîíåíò� p0 il , l = 1, ..., k, qj0 t , t = 1, ..., k îòðèöàòåëüíû, ò� ïåðåõîäè� � ñëåäóþùå� ïîäìàòðèö� A. Ïóñò� óêàçàííû� êîìïîíåíò� ðåøåíè� íåîòðèöàòåëüíû. Òîãä� îïðåäåëè� ñìåøàííû� ñòðàòåãè� (� 0 p,i = i,qj0 t , j = jt , lilp0 : p0 i = q 0 : qj 0 = 6 jt .
0,i 6= il ; 0,j = Òåïåð� äë� òðîéê� (p0 , q 0 , v) íåîáõîäèì� ïðîâåðèò� óñëîâè� (∗) òåîðåì� 4.1 0 . Åñë� îí� âûïîëíåíî, ò� èñêîìî� ðåøåíè� (p0 , q 0 , v) íàéäåíî. � ïðîòèâíî� ñëó÷à� ïåðåõîäè� � ñëåäóþùå� ïîäìàòðèö� A. Ïðèìå� 5.4. Ðàññìîòðè� ìàòðèö� âèä� ⎛ 1 1 1 01 0 0 1A = ⎝0 1 0 00 0 1 100 .1⎠1Çäåñ� íå� ñëàá� äîìèíèðóåìû� ñòðî� (äàæ� íèêàêèì� âûïóêëûì� êîìáèíàöèÿì� − äîêàæèòå!) � ñëàá� äîìèíèðóþùè� ñòîëáöî� . Åñë� ïðèìåíèò� óêàçàííû� âûø� àëãîðèòì, ò� ïîäìàòðèö� a11 a15 1 0 A == a41 a45 0 1 äàñ� ðåøåíè� � ñìåøàííû� ñòðàòåãèÿ� p0 = (1/2, 0, 0, 1/2), q 0 = (1/2, 0, 0, 0, 1/2), v = 1/2.
V. Ìåòî� Áðàóíà. � ýòî� ïàðàãðàô� ì� ðàññìîòðè� èòåðàöèîííû� ìåòî� ïðèáëèæåííîã� ðåøåíè� èãð� � ìàòðèöå� A. Ïóñò� çàäàí� ÷èñë� ε > 0. Òðåáóåòñ� íàéò� çíà÷åíè� èãð� � òî÷íîñòü� ä� âåëè÷èí� ε, � òàêæ� ε-ìàêñèìèííó� � ε-ìèíèìàêñíó� ñìåøàííû� ñòðàòåãè� èãðîêîâ. Ìåòî� Áðàóí� ñîñòîè� � ìíîãîêðàòíî� ôèêòèâíî� ðàçûãðûâàíè� ìàòðè÷íî� èãðû, ïð� êîòîðî� èãðîê� ï� îïðåäåëåííû� ïðàâèëà� âûáèðàþ� ñâî� ÷èñòû� ñòðàòåãèè. Ïóñò� ç� k ïîâòîðåíè� èãð� ïåðâû� èãðî� ri 49ÃËÀÂ� I.
ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈ� ÈÃÐ�ðà� âûáðà� ñòðàòåãè� i, i = 1, ..., m, � âòîðî� lj ðà� âûáðà� ñòðàòåãè� j, j = 1, ..., n. Âåêòîð� ÷àñòî� âûáîð� ÷èñòû� ñòðàòåãè� � � � � r1 rm l1 ln p(k) = , ..., , q(k) = , ..., k k k k ÿâëÿþòñ� ñìåøàííûì� ñòðàòåãèÿì� èãðîêîâ. Îïðåäåëè� èòåðàöèîííû� ïðîöåñ� Áðàóíà. Øà� 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≤m A(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≤m 1≤i≤m Äë� äîêàçàòåëüñòâ� ñõîäèìîñò� ïîñëåäîâàòåëüíîñòå� {v1 (k)}, {v2 (k)}� çíà÷åíè� èãð� v íà� ïîòðåáóåòñ� îáîáùåííû� èòåðàöèîííû� ïðîöåññ.
Ïóñò� c(0) ∈ E m , d(0) ∈ E n − äâ� âåêòîðà, óäîâëåòâîðÿþùè� óñëîâè� max ci (0) = min dj (0). Âîçüìå� 1≤i≤m 1≤j≤n i1 ∈ Arg max ci (0), j1 ∈ Arg min dj (0). 1≤i≤m 1≤j≤n 50 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≤m 1≤j≤n � ïîëîæè� äë� âñå� i = 1, ..., m, j = 1, ..., n ci (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=1 nXaij lj = ci (0) + kA(i, q(k)), j=1 dj (k) = dj (0) + kA(p(k), j). Ïð� íóëåâû� âåêòîðà� c(0) � d(0) ïîñòðîåííû� èòåðàöèîííû� ïðîöåñ� ñîâïàäàå� � ïðîöåññî� Áðàóíà. Ïîñêîëüê� ìíîæåñòâ� Ar� max ci (k) � Ar� min dj (k) ìîãó� ñîäåðæàò� áîëå� îäíîã� ýëåìåíòà, 1≤i≤m 1≤j≤n ïîñëåäîâàòåëüíîñò� {c(k)}, {d(k)} îïðåäåëÿþòñ� � õîä� èòåðàöèîííîã� ïðîöåññ� í� îäíîçíà÷íî. Îïðåäåëèì, êà� � ðàíåå, ïîñëåäîâàòåëüíîñò� âåëè÷è� ci (k) dj (k) , v2 (k) = min , k = 1, 2, .... 1≤i≤m k 1≤j≤n k v1 (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≤m 1≤j≤n ñëåäóåò, ÷ò� "lim v1 (k) = lim max k→∞ k→∞ 1≤i≤m #ci (0) + A(i, q(k)) ≥ v ≥k 51ÃËÀÂ� I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈ� ÈÃÐ�"≥ lim min k→∞ 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≤m 1≤j≤n � ïîìîùü� íåã� óñëîâè� max ci (0) = min dj (0) ìîæí� çàïèñàò� � âèä� 1≤i≤m 1≤j≤n ∆(0) = 0.
Îïðåäåëåíèå. Áóäå� ãîâîðèòü, ÷ò� i-à� ñòðîê� (j -� ñòîëáåö) ìàòðèö� A ñóùåñòâåíí� (ñóùåñòâåíåí) í� îòðåçê� øàãî� [s, s + t], åñë� äë� íåêîòîðîã� øàã� t� ∈ [s, s + t] it� = i (jt� = j). Ëåìì� 5.1. Ïóñò� âñ� ñòðîê� � ñòîëáö� ìàòðèö� A ñóùåñòâåíí� í� îòðåçê� øàãî� [s, s + t]. Òîãä� max ci (s + t) − min dj (s + t) ≤ 4at, 1≤i≤m 1≤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≤m 1≤j≤n 1≤i≤m 1≤j≤n Äîêàæå� (5.11). Ïóñò� äë� l-î� ñòðîê� âûïîëíåí� ðàâåíñòâ� min ci (s + t) = cl (s + t).
È� óñëîâè� ëåìì� âûòåêàåò, ÷ò� íàéäåòñ� òàêî� 1≤i≤m íîìå� øàã� t� ∈ [s, s + t], ÷ò� max ci (t0 ) = cl (t0 ). Òîãä� 1≤i≤m max ci (s + t) − min ci (s + t) = 1≤i≤m 1≤i≤m 52 5. Ìåòîä� ðåøåíè� ìàòðè÷íû� èã�= max ci (s + t) − max ci (t0 ) + cl (t0 ) − cl (s + t) ≤1≤i≤m 1≤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≤m 1≤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≤n 1≤j≤n Îòñþä� "min 1≤i≤m #ci (0) ci (0) + A(i, q(s + t)) ≤ max + min A(i, q(s + t)) ≤1≤i≤m s + t 1≤i≤m s + t "#dj (0) dj (0) ≤ min + max A(p(s + t), j)) ≤ max + A(p(s + t), j))1≤j≤n s + t 1≤j≤n 1≤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 âû÷åðêèâàíèå� ñòðîê� èë� ñòîëáöà, áûë� âûïîëíåí� íåðàâåíñòâ� 1 def ∆1 (k) = max c1 i (k) − min d1 j (k) ≤ εk, k ≥ k1 . i∈Ij∈J 253 ÃËÀÂ� I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈ� ÈÃÐ�Äîêàæåì, ÷ò� åñë� äë� ìàòðèö� A íåêîòîðà� ñòðîê� (ñòîëáåö) íåñóùåñòâåíí� (íåñóùåñòâåíåí) í� îòðåçê� [s, s + k1 ], ò� ñïðàâåäëèâ� íåðàâåíñòâ� 1 ∆(s + k1 ) ≤ ∆(s) + εk1 . (5.14) 2 Ïðåäïîëîæèì, íàïðèìåð, ÷ò� ïîäìàòðèö� A1 ïîëó÷àåòñ� âû÷åðêèâàíèå� è� A íåñóùåñòâåííî� l-� ñòðîêè.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
