А.А. Васин, В.В. Морозов - Введение в теорию игр с приложениями к экономике (1184512), страница 23
Текст из файла (страница 23)
Ñèòóàöè� ðàâíîâåñè� � áèìàòðè÷íû� èãðà�è� ìíîæåñòâ� Z ïîñëåäîâàòåëüíû� èñêëþ÷åíèå� ñëàá� äîìèíèðóåìû� ï� ñìåøàííîì� äîìèíèðîâàíè� ñòðàòåãèé, ò.å. Z = Zk ⊂ Zk−1 ⊂ · · · ⊂ Z1 = Z, Zl = Xl × Yl , l = 1, ..., k, � âûïîëíåí� óñëîâè� ∀ i ∈ Xl \Xl+1 ∃ p ∈ P : p � i í� Yl , ps = 0 ∀ s ∈ / Xl+1 ; ∀ j ∈ Yl \Yl+1 ∃ q ∈ Q : q � j í� Xl , qk = 0 ∀ k ∈ / Yl+1 . Êà� ñâÿçàí� ðàçëè÷íû� îòíîøåíè� äîìèíèðîâàíèÿ? ñòðîãî� äîìèíèðîâàíè� ñòðîãî� äîìèíèðîâàíè� ⇒ � ÷èñòû� ñòðàòåãèÿ� � ñìåøàííû� ñòðàòåãèÿ� ⇓ ⇓ ñëàáî� äîìèíèðîâàíè� ñëàáî� äîìèíèðîâàíè� ⇒ � ÷èñòû� ñòðàòåãèÿ� � ñìåøàííû� ñòðàòåãèÿ� Âåðí¼ìñ� � ïðèìåð� 10.4 � íàéä¼� äîìèíèðóþùè� ìíîæåñòâà.
Ïåðâó� ñòðîê� ì� âû÷åðêíóëè, òà� êà� îí� ñòðîã� äîìèíèðóåì� êîìáèíàöèå� âòîðî� � òðåòüå� ñòðîê. Ðàññìîòðè� âòîðó� ìàòðèöó. Ìîæí� çàìåòèòü, ÷ò� ïåðâû� ñòîëáå� ñòðîã� äîìèíèðóåòñÿ, íàïðèìåð, âòîðû� ñòîëáöîì. Ñëåäîâàòåëüíî, ïåðâû� ñòîëáå� ìîæí� âû÷åðêíóòü. Ïîëó÷àåì, ÷ò� {2, 3} × {2, 3} � Z. Òåïåð� ñôîðìóëèðóå� òåîðåì� � ñâÿç� èñêëþ÷åíè� äîìèíèðóåìû� ñòðàòåãè� � ïîèñê� ñìåøàííû� ðàâíîâåñè� ï� Íýøó. Òåîðåì� 10.4. 1) Ïóñò� ìíîæåñòâ� Z = X × Y ñòðîã� äîìèíèðóå� ìíîæåñòâ� Z = X × Y � ñìåøàííû� ñòðàòåãèÿõ. Òîãä� äë� ëþáî� ñèòóàöè� ðàâíîâåñè� (p0 , q 0 ) âûïîëíåí� óñëîâè� i ∈ / X ⇒ p0 i = 0; j ∈ / Y ⇒ qj 0 = 0.2) Ïóñò� ìíîæåñòâ� Z = X × Y ñëàá� äîìèíèðóå� ìíîæåñòâ� Z = X × Y � ñìåøàííû� ñòðàòåãèÿ� � (p, q) − ñèòóàöè� ðàâíîâåñè� � èãð� � ìàòðèöàì� A = (aij )i∈X j∈Y , B = (bij )i∈X j∈Y .
115 ÃËÀÂ� II. ÈÃÐ� ÄÂÓ� ËÈ�Îïðåäåëè� ñìåøàííû� ñòðàòåãè�((p,i ∈ X, qj ,iq 0 : qj 0 = p 0 : p0 i = 0, i ∈ X\X;0,j ∈ Y , j ∈ Y \Y . Òîãä� (p0 , q 0 ) − ñèòóàöè� ðàâíîâåñè� � èñõîäíî� èãð� Γ. Óïðàæíåíè� 10.2. Äîêàæèò� òåîðåì� 10.4. Îáñóäè� ñìûñ� òåîðåìû. Âòîðî� óòâåðæäåíè� ãîâîðè� � òîì, ÷ò� åñë� ðåäóöèðîâàííà� èãð� ïîëó÷åí� ïóòå� èñêëþ÷åíè� ñëàá� äîìèíèðóåìû� ñòðàòåãèé, ò� êàæäîì� ñìåøàííîì� ðàâíîâåñè� ï� Íýø� (p, q) � ýòî� ðåäóöèðîâàííî� èãð� áóäå� ñîîòâåòñòâîâàò� ñìåøàííî� ðàâíîâåñè� ï� Íýø� (p0 , q 0 ) � èñõîäíî� èãðå, îïðåäåëÿåìî� ï� óêàçàííîì� ïðàâèëó. Ïåðâî� óòâåðæäåíè� òåîðåì� ïîêàçûâàåò, ÷ò� ïð� âû÷¼ðêèâàíè� ñòðî� � ñòîëáöî� ï� ñòðîãîì� äîìèíèðîâàíè� ì� í� òåðÿå� ðàâíîâåñè� ï� Íýøó.
Òàêè� îáðàçîì, ïð� ïîèñê� âñå� ðàâíîâåñè� ï� Íýø� ìîæí� âû÷åðêíóò� âñ� ñòðîã� äîìèíèðóåìû� ñòðîê� � ñòîëáö� � èñêàò� ðàâíîâåñè� � ðåäóöèðîâàííî� èãðå. Äîïîëíè� íóëÿì� íàéäåííî� ðàâíîâåñèå, ì� ïîëó÷è� ðàâíîâåñè� ñìåøàííî� � èñõîäíî� èãðå. Åñë� íåîáõîäèì� íàéò� õîò� á� îäí� ñìåøàííî� ðàâíîâåñè� ï� Íýøó, òîãä� ìîæí� âû÷¼ðêèâàò� ñòðîê� � ñòîëáö� ï� íåñòðîãîì� äîìèíèðîâàíèþ. Èñêëþ÷åíè� ñòðî� � ñòîëáöî� ïîçâîëÿå� ñîêðàòèò� ïåðåáî� ïîäìàòðè� äë� ïîèñê� ðàâíîâåñè� ï� Íýøó. � ïðèìåð� 10.4 ïîñë� èñêëþ÷åíè� ñòðîã� äîìèíèðóåìû� ñòðàòåãè� ïîëó÷è� ðåäóöèðîâàííó� èãð� −1 7 3 1 A = , B = .
3 0 −2 1 � ýòî� èãð� ñèòóàöè� (p, q) = ((3/5, 2/5), (7/11, 4/11)) ÿâëÿåòñ� åäèíñòâåííû� ñìåøàííû� ðàâíîâåñèå� ï� Íýøó. Ñëåäîâàòåëüíî, ñèòóàöè� (p0 , q 0 ) = ((0, 3/5, 2/5), (0, 7/11, 4/11)) ÿâëÿåòñ� ñìåøàííû� ðàâíîâåñèå� ï� Íýø� � èñõîäíî� èãð� Γ. Ïðèìå� 10.5. Ðàññìîòðè� èãð� Γ � ìàòðèöàì� ⎛ 2 0 6 0 7 2 63 2 0 40 1 0A = ⎝0 3 7 0⎠ , B = ⎝0 2 21 1 3 1 5 3 4116 04 .3⎠3 10. Ñèòóàöè� ðàâíîâåñè� � áèìàòðè÷íû� èãðà�Èùå� ìàêñèìàëüíû� ýëåìåíò� � ñòîëáöà� ïåðâî� ìàòðèöû. � ÷èñòû� ñòðàòåãèÿ� äîìèíèðîâàíè� íåò.
Ðàññìîòðè� äîìèíèðîâàíè� � ñìåøàííû� ñòðàòåãèÿõ. Âèäíî, ÷ò� ÷åòâ¼ðòà� ñòðîê� ñòðîã� äîìèíèðóåòñ� êîìáèíàöèå� âòîðî� � òðåòüå� ñòðî� � âåñàì� 1/2. Ïîýòîì� å� ìîæí� âû÷åðêíóòü. Òåïåð� íàéä¼� ìàêñèìàëüíû� ýëåìåíò� � ñòðîêà� âòîðî� (ðåäóöèðîâàííîé) ìàòðèöû. Âòîðî� ñòîëáå� ñòðîã� äîìèíèðóåòñ� êîìáèíàöèå� ïåðâîã� � ÷åòâ¼ðòîã� ñòîëáöî� � âåñàì� 1/3 − ε � 2/3 + ε ïð� ìàëû� ε > 0. Ì� ìîæå� âû÷åðêíóò� âòîðî� ñòîëáåö. Ñëåäîâàòåëüíî, {1, 2, 3} × {1, 3, 4} � Z . � ðåçóëüòàò� èñêëþ÷åíè� ÷åòâåðòî� ñòðîê� � âòîðîã� ñòîëáö� ïîëó÷è� ñëåäóþùè� ðåäóöèðîâàííû� ìàòðèöû: ⎛ ⎞ ⎛ ⎞ 2 6 0 7 6 0 A = 3 0 4⎠ , B = 0 0 4 .
0 7 0 0 2 3 Ïîâòîðÿå� ïðîöåäóð� ïîñëåäîâàòåëüíîã� èñêëþ÷åíè� ñòðàòåãè� äë� ðåäóöèðîâàííû� ìàòðèö. Èùå� ìàêñèìàëüíû� ýëåìåíò� � ñòîëáöà� ïåðâî� ìàòðèöû. � ÷èñòû� ñòðàòåãèÿ� äîìèíèðîâàíè� íåò. Ðàññìîòðè� äîìèíèðîâàíè� � ñìåøàííû� ñòðàòåãèÿõ. Âòîðó� � òðåòü� ñòðîê� èñêëþ÷èò� íåâîçìîæíî, òà� êà� � íè� ñîäåðæàòñ� ìàêñèìàëüíû� ï� ñòîëáöà� ýëåìåíòû. Ïåðâà� ñòðîê� í� ñîäåðæè� í� îäíîã� ìàêñèìàëüíîã� ï� ñòîëáö� ýëåìåíòà, îäíàêî, å� òàêæ� íåâîçìîæí� èñêëþ÷èòü, òà� êà� îí� í� äîìèíèðóåòñ� í� îäíî� ëèíåéíî� êîìáèíàöèå� âòîðî� � òðåòüå� ñòðîêè. Àíàëîãè÷íî, íåâîçìîæí� èñêëþ÷èò� í� îäè� ñòîëáå� â� âòîðî� ìàòðèöå. Ñëåäîâàòåëüíî, ïðîöåäóð� èñêëþ÷åíè� ï� äîìèíèðîâàíè� ñìåøàííûì� ñòðàòåãèÿì� çàâåðøåí� � {1, 2, 3} × {1, 3, 4} = Z .
Ïîçèòèâíû� ïîäõî� � ïîíÿòè� ðàâíîâåñè� Ñëåäóå� îòìåòèòü, ÷ò� èñïîëüçîâàíè� ñìåøàííû� ñòðàòåãè� � ïîìîùü� ìåõàíèçì� áðîñàíè� ìîíå� èë� äðóãè� ïîäîáíû� ìåõàíèçìî� í� õàðàêòåðí� äë� ðåàëüíîã� ïîâåäåíè� ëþäåé. Äðóãà� èíòåðïðåòàöè� ñìåøàííû� ðàâíîâåñè� îòíîñÿòñ� � èãðàì, ñîîòâåòñòâóþùè� òèïè÷íû� êîíôëèêòíû� ñèòóàöèÿì, � êîòîðû� ïðèíèìàþ� ó÷àñòè� ìíîã� èíäèâèäóóìîâ.
Òàêè� ñèòóàöè� îïèñàí� � ïðèìåðà� 9.1-4: ìíîæåñòâ� ïîêóïàòåëå� ïðèõîäè� í� ðûíî� � ñòàëêèâàåòñ� � ìíîæåñòâî� ïðîäàâöîâ; ðàçëè÷íû� ïàð� âîäèòåëå� ñòàëêèâàþòñ� � ïåðåêðåñòêî� � ò.ï. Ïîçèòèâíû� ïîäõî� � ðàâíîâåñè� � ñìåøàííû� ñòðàòåãèÿ� ïðåäïîëàãàåò, ÷ò� êàæäà� òàêà� ñòðàòåãè� îïèñûâàå� ðàñïðåäåëåíè� èíäèâèäóóìî� � ñîîòâåòñòâóþùå� 117ÃËÀÂ� II. ÈÃÐ� ÄÂÓ� ËÈ�ðîëè.
Íàïðèìåð, åñë� (p0 , q 0 ) − ñèòóàöè� ðàâíîâåñè� � èãð� "ïðîäàâåöïîêóïàòåëü"(ïðèìå� 9.1), ò� í� ïðàêòèê� äîë� p0 1 ïðîäàâöî� âåäå� ñåá� ÷åñòíî, � äîë� p0 2 îáìàíûâàåò, äîë� q10 ïîêóïàòåëå� í� ïðîâåðÿå� êóïëåííû� òîâàð, � îñòàëüíû� ïðîâåðÿþò, � ò.ï. Î÷åâèäíî, ÷ò� ëèø� åñë� ðàñïðåäåëåíè� ï� ñòðàòåãèÿ� � êàæäî� ðîë� ñîîòâåòñòâóþ� ñìåøàííû� ðàâíîâåñèÿ� ï� Íýøó, ò� í� � êîã� í� áóäå� ñòèìóë� ïîìåíÿò� ñòðàòåãè� ïîâåäåíèÿ. Ôîðìàëüí� ýò� îòðàæåí� � ëåìì� 10.1 � òåîðåì� 10.1.
Ïîýòîì� ìîæí� îæèäàòü, ÷ò� ñòàáèëüíû� ðàñïðåäåëåíè� ï� ñòðàòåãèÿ� � ðåàëüíû� âçàèìîäåéñòâèÿ� áîëüøè� ãðóï� îòâå÷àþ� ñìåøàííû� ðàâíîâåñèÿ� ï� Íýøó. Òåîðåòè÷åñêî� îáîñíîâàíè� ýòîã� òåçèñ� äàþ� äèíàìè÷åñêè� ìîäåë� ïîâåäåíè� (ñì. 14.).
Ïðèìåðî� ìîäåë� ïîâåäåíè� èãðîêî� ìîæå� ñëóæèò� ìåòî� Áðàóí� ôèêòèâíîã� ðàçûãðûâàíè� ìàòðè÷íî� èãðû, èçëîæåííû� � 5. Àíàëîãè÷íû� ìåòî� ìîæí� ïðèìåíÿò� � äë� ïîèñê� ñèòóàöè� ðàâíîâåñè� � áèìàòðè÷íû� èãðà� ñïåöèàëüíîã� âèäà. Îïðåäåëåíèå. Èãð� Γ � ìàòðèöàì� A � B íàçîâå� ýêâèâàëåíòíî� àíòàãîíèñòè÷åñêîé, åñë� íàéäåòñ� òàêà� ìàòðèö� A� = (a0ij )m×n (àíòàãîíèñòè÷åñêî� èãðû) � íàéäóòñ� òàêè� ÷èñë� fj , j = 1, ..., n, gi , i = 1, ..., m, ÷ò� aij = a0ij + fj , bij = −a0ij + gi , i = 1, ..., m, j = 1, ..., n. (10.7) Çàìåòèì, ÷ò� ìàòðèö� A� � êîýôôèöèåíò� fj , gi çäåñ� îïðåäåëÿþòñ� í� îäíîçíà÷íî.
Äåéñòâèòåëüíî, åñë� îí� óäîâëåòâîðÿþ� ðàâåíñòâà� (10.7), ò� äë� ëþáîã� ÷èñë� c ìàòðèö� � ýëåìåíòàì� a0ij + c � êîýôôèöèåíò� fj − c, gi + c òàêæ� óäîâëåòâîðÿþ� (10.7). Åñë� èãð� Γ ýêâèâàëåíòí� àíòàãîíèñòè÷åñêîé, ò� ñóìì� å� ìàòðè� ïðåäñòàâèì� � âèä� A + B = (gi + fj )m×n . Îáðàòíî, åñë� òàêî� ïðåäñòàâëåíè� èìåå� ìåñòî, ò� Γ ýêâèâàëåíòí� àíòàãîíèñòè÷åñêî� èãð� � ìàòðèöå� A� = (aij − fj )m×n = (−bij + gi )m×n . Óïðàæíåíè� 10.3. Ïóñò� áèìàòðè÷íà� èãð� Γ ýêâèâàëåíòí� àíòàãîíèñòè÷åñêî� èãð� � ìàòðèöå� A0 , � f1 = 0.
Âûðàçèò� ýëåìåíò� ìàòðèö� A� ÷åðå� ýëåìåíò� ìàòðè� A � B . Óïðàæíåíè� 10.4. Ïóñò� áèìàòðè÷íà� èãð� Γ ýêâèâàëåíòí� àíòàãîíèñòè÷åñêî� èãð� Γ0 . Äë� òîã� ÷òîá� ïàð� (p0 , q 0 ) áûë� ñåäëîâî� òî÷êî� � ñìåøàííû� ñòðàòåãèÿ� èãð� Γ0 , íåîáõîäèì� � äîñòàòî÷íî, ÷òîá� (p0 , q 0 ) áûë� ñèòóàöèå� ðàâíîâåñè� èãð� Γ. Äîêàæèòå. 118 10. Ñèòóàöè� ðàâíîâåñè� � áèìàòðè÷íû� èãðà� 5. Îïðåäåëè� èòåðàöèîííû� ïðîöåññ, àíàëîãè÷íû� ïðîöåññ� Áðàóí� è� Øà� 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)), B(p(k), jk+1 ) = max B(p(k), j). 1≤i≤m 1≤j≤n Êàæäû� èãðî� âûáèðàå� ñâî� ÷èñòó� ñòðàòåãè� êà� íàèëó÷øè� îòâå� í� ñîîòâåòñòâóþùè� âåêòî� ÷àñòî� ïàðòíåðà. Åñë� íàèëó÷øè� îòâåòî� íåñêîëüêî, ò� âûáèðàåòñ� ëþáî� è� íèõ. Òåîðåì� 10.5. Ïóñò� áèìàòðè÷íà� èãð� Γ ýêâèâàëåíòí� àíòàãîíèñòè÷åñêîé. Òîãä� ëþáà� ïðåäåëüíà� òî÷ê� (p0 , q 0 ) ïîñëåäîâàòåëüíîñò� {(p(k), q(k))} èòåðàöèîííîã� ïðîöåññ� ÿâëÿåòñ� ñèòóàöèå� ðàâíîâåñè� èãð� Γ.
Óïðàæíåíè� 10.5. Äîêàæèò� òåîðåì� 10.5. Åñë� áèìàòðè÷íà� èãð� Γ í� ýêâèâàëåíòí� àíòàãîíèñòè÷åñêîé, ò� óòâåðæäåíè� òåîðåì� 10.5 ìîæå� áûò� íåâåðíûì. Âñ� îñòàâøàÿñ� ÷àñò� ïàðàãðàô� áóäå� ïîñâÿùåí� äîêàçàòåëüñòâ� ýòîã� ôàêòà. � êà÷åñòâ� ïðèìåð� ðàññìîòðè� èãð� Γ è� óïðàæíåíè� 10.1 c ìàòðèöàì� ⎛ ⎞ ⎛ ⎞ 2 0 1 1 0 2 A = 1 2 0⎠ , B = 2 1 0 , 0 1 2 0 2 1 � êîòîðî� ñóùåñòâóå� åäèíñòâåííî� ñìåøàííî� ðàâíîâåñè� ï� Íýø� (p0 , q 0 ) = ((1/3, 1/3, 1/3), (1/3, 1/3, 1/3)). Ïóñò� ei ∈ E 3 − âåêòîð, i-à� êîìïîíåíò� êîòîðîã� ðàâí� 1, � äâ� äðóãè� ðàâí� íóëþ. Ïóñò� � (k + 1)-ã� ï� (k + s)-û� øà� ïåðâû� èãðî� âûáèðà� ÷èñòó� ñòðàòåãè� i.
Òîãä� kp(k) + sei ks i = p(k) + e . k + sk + sk + s Íåòðóäí� âèäåòü, ÷ò� òî÷ê� p(k + t) ïð� èçìåíåíè� t = 0, 1, ..., s, ïåðåìåùàåòñ� âäîë� îòðåçê� [p(s), ei ] î� òî÷ê� p(s) ä� òî÷ê� p(k + s). Àíàëîãè÷íà� ôîðìóë� ìîæå� áûò� çàïèñàí� � äë� âåêòîðî� ÷àñòî� âòîðîã� èãðîêà. p(k + s) = 119 ÃËÀÂ� II. ÈÃÐ� ÄÂÓ� ËÈ�Ïóñò� í� íåêîòîðî� k -î� øàã� (k > 1) âîçíèêë� ïàð� (ik , jk ) = (1, 1).
Ýò� îçíà÷àåò, ÷ò� âûïîëíåí� íåðàâåíñòâ� A(1, q(k − 1)) ≥ A(i, q(k − 1)), i = 2, 3,B(p(k − 1), 1) ≥ B(p(k − 1), j), j = 2, 3.Òîãä� (k − 1)A(1, q(k − 1)) + A(1, e1 )A(1, q(k)) = = k (k − 1)A(1, q(k − 1)) + 2 (k − 1)A(2, q(k − 1)) + 1 > = A(2, q(k)). kk Àíàëîãè÷í� äîêàçûâàåòñÿ, ÷ò� A(1, q(k)) > A(3, q(k)). Ïîýòîì� íåîáõîäèì� ik+1 = 1. Äàëåå, =B(p(k), 1) = (k − 1)B(p(k − 1), 1) + B(e1 , 1)= k (k − 1)B(p(k − 1), 1) + 1 (k − 1)B(p(k − 1), 2) > = B(p(k), 2)kk è, ñëåäîâàòåëüíî, jk+1 =6 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
