А.А. Васин, В.В. Морозов - Введение в теорию игр с приложениями к экономике (1184512), страница 11
Текст из файла (страница 11)
Ïîëîæè� I = {1, ..., m}\{l}, d1j (0) = dj (s) + ∆(s), j = 1, ..., n, c 1i (0) = ci (s), i ∈ I. Ïîñêîëüê� l-à� ñòðîê� ìàòðèö� A íåñóùåñòâåííà, ∆1 (0) = 0 � � èòåðàöèîííî� ïðîöåññ� ìîæí� âçÿò� i1 k = is+k , jk 1 = 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 ) ≤ 1 2 ε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 + 1 2 εt)k1 ≤ 4ak1 + 1 2 ε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≤m 55 ÃËÀÂ� 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 . Ïðîñìàòðèâà� äîêàçàòåëüñòâ� ëåìì� 5.2, çàìå÷àåì, ÷ò� km+n−1 = 1 � k0 ≥ 8ak1 ε−1 .
Àíàëîãè÷íû� íåðàâåíñòâî� ñâÿçàí� kl � kl+1 : kl ≥ 2l 8akl+1 ε−1 , l = 0, 1, ..., m + n − 2. Îòñþä� !!8a k0 ≥ k1 ≥ ε≥ 8a ε 2 8a ε 2k2 ≥ 8a ε !m+n−1 1+2+...+m+n−223 8a ε km+n−1 =2 · 22 k3 ≥ ... !m+n−1 2 (m+n−2)(m+n−1) 2. Òàêè� îáðàçîì, ïð� ëþáî� k ≥ k0 âûïîëíåí� íåðàâåíñòâ� def v1 (k) − v2 (k) ≤ ε = 2 m+n−2 2 1 8ak 1 ! m+n−1 . Èòàê, ïîëó÷åííà� îöåíê� ñêîðîñò� ñõîäèìîñò� ïðîöåññ� Áðàóí� ìàëîýôôåêòèâí� ïð� áîëüøè� ðàçìåðà� ìàòðèö� A. Ïðàêòè÷åñê� íàáëþäàåìà� ñêîðîñò� ñõîäèìîñò� ñóùåñòâåíí� âûøå. � çàêëþ÷åíè� ðàññìîòðè� ìîäèôèêàöè� ïðàâèë� îñòàíîâê� ï� ìåòîä� Áðàóíà.
Ïîëîæè� v1∗ (k) = min v1 (t), v2∗ (k) = max v2 (t), k = 1, 2, ... 1≤t≤k 1≤t≤k È� íåðàâåíñò� (5.7) ñëåäóåò, ÷ò� v2∗ (k) ≤ v ≤ v1∗ (k), k = 1, 2, .... 56 (5.18) 5. Ìåòîä� ðåøåíè� ìàòðè÷íû� èã�Òàêè� îáðàçîì, v2∗ (k), v1∗ (k) − íàèëó÷øè� îöåíê� ñíèç� � ñâåðõ� äë� çíà÷åíè� èãð� v ç� k å� ïîâòîðåíèé. Ïð� çàäàííî� ε > 0 áóäå� îñòàíàâëèâàò� ïðîöåñ� í� øàã� k0 , êîãä� âïåðâû� âûïîëíåí� íåðàâåíñòâ� v1∗ (k0 ) − v2∗ (k0 ) ≤ ε. Ïð� ýòî� âåëè÷èí� v1∗ (k0 ), v2∗ (k0 ) ïðèáëèæàþ� çíà÷åíè� èãð� v � òî÷íîñòü� ä� ε. Ïóñò� v1∗ (k0 ) = v1 (t1 ), v2∗ (k0 ) = v2 (t2 ). Ïîêàæåì, ÷ò� p(t2 ) − ε-ìàêñèìèííà� ñòðàòåãè� ïåðâîã� èãðîêà.
Äåéñòâèòåëüíî, èñïîëüçó� íåðàâåíñòâ� (5.18) ïð� k = k0 , ïîëó÷è� min A(p(t2 ), j) = v2 (t2 ) = v2∗ (k0 ) ≥ v − ε.1≤j≤n Àíàëîãè÷íî, q(t1 ) − ε-ìèíèìàêñíà� ñòðàòåãè� âòîðîã� èãðîêà. Ïðèìå� 5.5. Ïóñò� ε = 1/5, � ìàòðèö� èãð� −⎛ ⎞ 2 1 0 A = ⎝ 2 0 3 . −1 3 −3 Îòìåòèì, ÷ò� ðåøåíè� èãð� � ñìåøàííû� ñòðàòåãèÿ� èìåå� âè� p 0 = q 0 = (0, 2/3, 1/3), v = 1. Ïðèìåíÿ� ìåòî� Áðàóíà, íàéäå� ïðèáëèæåííî� çíà÷åíè� èãðû, � òàêæ� ε-ìàêñèìèííó� � ε-ìèíèìàêñíó� ñìåøàííû� ñòðàòåãè� èãðîêîâ. Âû÷èñëåíè� óäîáí� ïðîèçâîäèò� � ôîðì� òàáëèöû. � êàæäî� å� k -î� ñòðîê� ïîä÷åðêíóò� íàèáîëüøè� çíà÷åíè� âåëè÷è� ci (k), i = 1, 2, 3 � íàèìåíüøè� çíà÷åíè� âåëè÷è� dj (k), j = 1, 2, 3.
Òàáë. 5.1 k 1 2 3 4 5 6 7 8 9 10 ik 1 1 2 2 2 2 2 2 3 3 c1 (·) 2 2 2 3 4 5 6 7 8 9 c2 (·) 2 5 8 8 8 8 8 8 8 8 c3 (·) -1 -4 -7 -4 -1 2 5 8 11 14 v1 (·) 2 5/2 8/3 2 8/5 4/3 8/7 1 11/9 7/5 57jk 1 3 3 2 2 2 2 2 2 2 d1 (·) 2 4 6 8 10 12 14 16 15 14 d2 (·) 1 2 2 2 2 2 2 2 5 8 d3 (·) 0 0 3 6 9 12 15 18 15 12 v2 (·) 0 0 2/3 1/2 2/5 1/3 2/7 1/4 5/9 4/5 ÃËÀÂ� I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈ� ÈÃÐ�v1∗ (10) = 1, v2∗ (10) = 4/5, t1 = 8, t2 = 10, p(10) = (1/5, 3/5, 1/5), q(8) = (1/8, 5/8, 1/4). Óïðàæíåíè� 5.8. Ïðîâåðèò� 1/5-îïòèìàëüíîñò� ïîëó÷åííû� ñòðàòåãèé. Ñäåëàò� åù� 8 øàãî� ï� àëãîðèòì� � óëó÷øèò� òî÷íîñò� ä� ε = 1/18.
6. Èãð� � âîãíóòî� ôóíêöèå� âûèãðûø� Îïðåäåëåíèå. Àíòàãîíèñòè÷åñêà� èãð� Γ = X, Y, F (x, y) íàçûâàåòñ� èãðî� � âîãíóòî� ôóíêöèå� âûèãðûøà, åñë� X ⊂ E m , Y ⊂ E n − âûïóêëû� êîìïàêò� åâêëèäîâû� ïðîñòðàíñòâ, ôóíêöè� F (x, y) íåïðåðûâí� í� X × Y � ïð� ëþáî� y ∈ Y îí� âîãíóò� ï� x.
Èãð� Γ íàçûâàåòñ� èãðî� � âûïóêëî� ôóíêöèå� âûèãðûøà, åñë� (âìåñò� òðåáîâàíè� âîãíóòîñòè) ïð� ëþáî� x ∈ X ôóíêöè� F (x, y) âûïóêë� ï� y. Òåîðåì� 6.1 (Õåëëè). � åâêëèäîâî� ïðîñòðàíñòâ� E m èìååòñ� ñåìåéñòâ� Dα , α ∈ {α} âûïóêëû� êîìïàêòîâ, îáëàäàþùå� ñëåäóþùè� mT+1ñâîéñòâîì: äë� ëþáû� α1 , ..., αm+1 Dαj 6= ∅. Òîãä� j=1 � Dα =6 ∅. α∈{α}Äîêàçàòåëüñòâ� òåîðåì� ñì.
� Ïðèëîæåíè� Ï2. Óïðàæíåíè� 6.1. Äîêàæèò� òåîðåì� ïð� m = 1. Òåîðåì� 6.2. Äë� èãð� Γ � âîãíóòî� ôóíêöèå� âûèãðûø� ñïðàâåäëèâ� ðàâåíñòâ� v = max min F (x, y) = x∈X y∈Y min j y ∈Y j=1,...,m+1 max min x∈X 1≤j≤m+1 F (x, y j ). Äîêàçàòåëüñòâî. Îáîçíà÷è� ïîñëåäíþ� âåëè÷èí� ÷åðå� w. Äë� ëþáû� y 1 , ..., y m+1 ∈ Y ñïðàâåäëèâ� íåðàâåíñòâ� max min x∈X 1≤j≤m+1 F (x, y j ) ≥ max min F (x, y) = v. x∈X y∈Y Ñëåäîâàòåëüíî, w ≥ v.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
