А.А. Васин, В.В. Морозов - Введение в теорию игр с приложениями к экономике (1184512), страница 8
Текст из файла (страница 8)
Òåïåð� 0� 0F (ϕ , ψ ) = F (x, ψ 0 )dϕ0 (x) = X Z= 00ZF (x, ψ )dϕ (x) + (a0 ,b0 ] 0Z0F (x, ψ )dϕ (x) ≤ X\(a0 ,b0 ]Z+ v 0 dϕ0 (x)+ (a0 ,b0 ] vdϕ0 (x) < (ϕ0 (b0 ) − ϕ0 (a0 ))v + X\(a0 ,b0 ] Zvdϕ0 (x) = v, X\(a0 ,b0 ] ÷ò� ïðîòèâîðå÷è� îïðåäåëåíè� çíà÷åíè� èãðû. Óòâåðæäåíè� 2) äîêàçûâàåòñ� àíàëîãè÷íî. Ñëåäñòâèå. Ïóñò� (ϕ0 , ψ 0 , v) − ðåøåíè� � ñìåøàííû� ñòðàòåãèÿ� íåïðåðûâíî� èãð� Γ. Òîãä� 1) F (x, ψ 0 ) < v ⇒ x ∈ / Sp(ϕ0 ); 2) F (ϕ0 , y) > v ⇒ y ∈ / Sp(ψ 0 ). Ñôîðìóëèðóå� àíàëîãè÷íó� òåîðåì� äë� ìàòðè÷íû� èãð. Òåîðåì� 4.3 � (Ñâîéñòâ� äîïîëíÿþùå� íåæåñòêîñòè). Ïóñò� (p , q 0 , v) − ðåøåíè� � ñìåøàííû� ñòðàòåãèÿ� èãð� � ìàòðèöå� A.
Òîãä� 1) p0 i > 0 ⇒ A(i, q 0 ) = v;2) qj 0 > 0 ⇒ A(p0 , j) = v.0Óïðàæíåíè� 4.8. Äîêàæèò� òåîðåì� 4.3 0 . Ñëåäñòâèå. Ïóñò� (p0 , q 0 , v) − ðåøåíè� � ñìåøàííû� ñòðàòåãèÿ� èãð� � ìàòðèöå� A. Òîãä� 1) A(i, q 0 ) < v ⇒ p0 i = 0; 2) A(p0 , j) > v ⇒ qj 0 = 0.Ïîÿñíè� âûðàæåíè� "äîïîëíÿþùà� íåæåñòêîñòü", çàèìñòâîâàííî� è� òåîðè� äâîéñòâåííîñò� ëèíåéíîã� ïðîãðàììèðîâàíèÿ. Ïîñòàâè� � ñîîòâåòñòâè� íåðàâåíñòâ� A(i, q 0 ) ≤ v (A(p0 , j) ≥ v) è� óñëîâè� (∗) íåðàâåíñòâ� p0 i ≥ 0 (qj 0 ≥ 0) � òå� æ� íîìåðîì. Òîãä� åñë� îäí� è� ýòè� íåðàâåíñò� âûïîëíåí� ñòðîã� ("íåæåñòêî"), ò� ï� òåîðåì� 4.3 � � å� ñëåäñòâè� 36 5.
Ìåòîä� ðåøåíè� ìàòðè÷íû� èã�ñîîòâåòñòâóþùå� íåðàâåíñòâ� âûïîëíåí� êà� ðàâåíñòâ� ("æåñòêî"). Âñ� ýò� ìîæí� çàïèñàò� � ñëåäóþùå� êðàòêî� ôîðìå: äë� ðåøåíè� (p0 , q 0 , v) � ñìåøàííû� ñòðàòåãèÿ� èãð� � ìàòðèöå� A ñïðàâåäëèâ� ðàâåíñòâ� p 0 i (v − A(i, q 0 )) = qj 0 (A(p 0 , j) − v) = 0, i = 1, ..., m, j = 1, ..., n. Ïðèìå� 4.4.
Ðåøè� èãð� � äèàãîíàëüíî� ìàòðèöå� A, � êîòîðî� äèàãîíàëüíû� ýëåìåíò� ai > 0. Ïðåäïîëîæèì, ÷ò� âñ� êîìïîíåíò� îïòèìàëüíû� ñìåøàííû� ñòðàòåãè� p0 , q 0 ïîëîæèòåëüíû. Òîãä� ï� òåîðåì� 4.3 � nXA(i, q 0 ) = ai qi 0 = v, i = 1, ..., n, qi 0 = 1.
i=1 Ðåøà� ýò� ñèñòåì� îòíîñèòåëüí� n + 1 íåèçâåñòíû� qi 0 , i = 1, ..., n, v, nP1 ïîëó÷è� qi 0 = v/ai , i = 1, ..., n, ãä� v = 1/ . ak k=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=1 i=1 íàçûâàåòñ� âûïóêëî� êîìáèíàöèå� âåêòîðî� a(i) � êîýôôèöèåíòàì� pi . Òåîðåì� 5.1 (� äîìèíèðîâàíè� ñòðîê). Ïóñò� íåêîòîðà� ñòðîê� ìàòðèö� A ñëàá� äîìèíèðóåòñ� âûïóêëî� êîìáèíàöèå� îñòàëüíû� ñòðîê.
Òîãä� ýò� ñòðîê� âõîäè� � íóëåâî� âåðîÿòíîñòü� � íåêîòîðó� îïòèìàëüíó� ñìåøàííó� ñòðàòåãè� ïåðâîã� èãðîêà. Åñë� óêàçàííî� äîìèíèðîâàíè� ñòðîãîå, ò� ýò� ñòðîê� âõîäè� � íóëåâî� âåðîÿòíîñòü� � ëþáó� îïòèìàëüíó� ñìåøàííó� ñòðàòåãè� ïåðâîã� èãðîêà. Äîìèíèðóåìû� ñòðîê� ìîæí� âû÷åðêíóò� è� ìàòðèö� èãðû. Äîêàçàòåëüñòâî. Ïóñò� ñòðîê� ìàòðèö� A � íîìåðî� i1 ñëàá� äîìèíèðóåòñ� âûïóêëî� êîìáèíàöèå� îñòàëüíû� ñòðî� � êîýôôèöèåíòàì� 6 i1 : pi ≥ 0, i = XXai1 j ≤ pi aij , j = 1, ..., n, pi = 1. (5.1) i=i6 1 i=i6 1 Ðàññìîòðè� ìàòðèö� Â, ïîëó÷åííó� è� A âû÷åðêèâàíèå� (èñêëþ÷åíèˆ Ïîëîæè� åì) i1 -î� ñòðîêè. Ïóñò� (p̂, q 0 , v) − ðåøåíè� èãð� � ìàòðèöå� A.
0 00 p = (p̂1 , ..., p̂i1 −1 , 0, p̂i1 +1 , ..., p̂m ) � äîêàæåì, ÷ò� òðîéê� (p , q , v) − ðåøåíè� èãð� � ìàòðèöå� A. Òå� ñàìû� áóäå� äîêàçàí� âòîðî� óòâåðæäåíè� òåîðåì� � îáîñíîâàí� âû÷åðêèâàíè� i1 -î� ñòðîêè. Äåéñòâèòåëüíî, ðåøà� ˆ ì� íàõîäè� ðåøåíè� èñõîäíî� èãðû, äîáàâëÿ� � pˆèãð� � ìàòðèöå� A, íóëåâó� i1 -ó� êîìïîíåíòó. Ïðîâåðè� óñëîâè� (∗) äë� òðîéê� (p0 , q 0 , v) � èãð� � ìàòðèöå� A. Èìåå� A(p 0 , j) = Â(p̂, j) ≥ v, j = 1, ..., n; A(i, q 0 ) = Â(i, q 0 ) ≤ v ∀ i =6 i1 . Ïóñò� i = i1 . Òîãäà, ïîëàãà� p� = (pi , i = 6 i1 ), ïîëó÷è� A(i1 , q 0 ) = nXj=1 ai1 j qj 0 ≤ n XX( aij pi )q j 0 = Â(p0 , q 0 ) ≤ v, j=1 i=i6 1 38 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 � (� äîìèíèðîâàíè� ñòîëáöîâ). Ïóñò� íåêîòîðû� ñòîëáå� ìàòðèö� A ñëàá� äîìèíèðóå� âûïóêëó� êîìáèíàöè� îñòàëüíû� ñòîëáöî� ýòî� ìàòðèöû. Òîãä� ýòî� ñòîëáå� âõîäè� � íóëåâî� âåðîÿòíîñòü� � íåêîòîðó� îïòèìàëüíó� ñìåøàííó� ñòðàòåãè� âòîðîã� èãðîêà. Åñë� óêàçàííî� äîìèíèðîâàíè� ñòðîãîå, ò� ýòî� ñòîëáå� âõîäè� � íóëåâî� âåðîÿòíîñòü� � ëþáó� îïòèìàëüíó� ñìåøàííó� ñòðàòåãè� âòîðîã� èãðîêà.
Äîìèíèðóþùè� ñòîëáö� ìîæí� âû÷åðêíóò� è� ìàòðèö� èãðû. Ïðèìå� 5.1. Ðåøèò� èãð� � ìàòðèöå� ⎛ ⎞ 3 1 5 A = 1 3 3⎠ . 2 2 1 Çäåñ� ïîëóñóìì� ïåðâû� äâó� ñòðî� ñëàá� äîìèíèðóå� òðåòü� ñòðîê� � å� ìîæí� âû÷åðêíóòü. � ïîëó÷åííî� ìàòðèö� òðåòè� ñòîëáå� ñëàá� äîìèíèðóå� Ïîñë� åã� âû÷åðêèâàíè� ïîëó÷è� öèêëè÷åñêó� ìàòðèö� âòîðîé. 31 A ˆ = � ðåøåíèå� (ˆ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. Ïîëêîâíèê� Áëîòòî� (ïåðâîì� èãðîêó) ïîñòàâëåí� çàäà÷� ïðîðûâ� òðåì� ïîëêàì� ÷åðå� äâ� ãîðíû� ïåðåâàëà, îõðàíÿåìû� äâóì� ïîëêàì� ïðîòèâíèê� (âòîðîã� èãðîêà).
Ñòðàòåãè� Áëîòò� (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≤n p∈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≤n 6S� lj1 SSQQv 0 SQSQ SQQSQSQ lS Q j2 SQSQ1 p0 1� p1 Ðèñ.
5.1 1 Ïîëêîâíè� Áëîòò� − àíåêäîòè÷åñêè� ïåðñîíàæ, äåéñòâóþùå� ëèö� ìíîãè� èëëþñòðàòèâíû� ïðèìåðî� è� îáëàñò� àíòàãîíèñòè÷åñêè� èãð. 40 5. Ìåòîä� ðåøåíè� ìàòðè÷íû� èã�Íàéäå� îïòèìàëüíó� ñìåøàííó� ñòðàòåãè� âòîðîã� èãðîêà. Ðàçáåðå� ñëåäóþùè� âîçìîæíîñòè. à) 0 < p01 < 1. Ýòî� ñëó÷à� ïðåäñòàâëå� í� ðèñ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
