А.А. Васин, В.В. Морозов - Введение в теорию игр с приложениями к экономике (1184512), страница 22
Текст из файла (страница 22)
Ïðèìå� 10.2. Ïóñò� 2 4 5 3 2 0 A = , B = . 4 2 1 0 2 3 63 QQQQ� 2 Q� � l1 l2QQ0 13QQQ l3 QQ2 3 � p1 1 Ðèñ. 10.2 Çäåñ� l1 (p1 ) = 3p1 , l2 (p1 ) ≡ 2, l3 (p1 ) = 3(1 − p1 ). Ïåðâà� òî÷ê� âåðõíå� îãèáàþùå� ( ïåðåñå÷åíè� ïðÿìû� l2 � l3 í� ðèñ. 10.2) èìåå� àáñöèññ� 110 10. Ñèòóàöè� ðàâíîâåñè� � áèìàòðè÷íû� èãðà�p01 = 1/3. Ðàññìîòðè� ñèñòåì� óðàâíåíè� è� 10.1 4q ∗ + 5(1 − q ∗ ) = v1 , 2q ∗ + (1 − q ∗ ) = v1 .
È� íå� íàõîäè� q ∗ = 2 > 1, ÷ò� íåâîçìîæíî. Ïåðåõîäè� ê� âòîðî� òî÷ê� îãèáàþùåé, ëåæàùå� í� ïåðåñå÷åíè� ïðÿìû� l1 � l2 . Îí� èìåå� àáñöèññ� p0 1 = 2/3. Ñèñòåì� 2q ∗ + 4(1 − q ∗ ) = v1 , 4q ∗ + 2(1 − q ∗ ) = v1 èìåå� ðåøåíè� q ∗ = 1/2, v1 = 3. Ïîýòîì� (p0 , q 0 ) = ((2/3, 1/3), (1/2, 1/2, 0)) − èñêîìà� ñèòóàöè� ðàâíîâåñè� � ñìåøàííû� ñòðàòåãèÿõ. Îòìåòèì, ÷ò� ðàññìàòðèâàåìû� àëãîðèò� í� âñåãä� ïðèâîäè� � íàõîæäåíè� âñå� ñèòóàöè� ðàâíîâåñèÿ. Ïðèìå� 10.3.
Ïóñò� A = 0 1 2 2 , B = . 1 0 −1 3 Çäåñ� ïåðåñå÷åíè� ïðÿìû� l1 � l2 äàå� ñòðàòåãè� p0 = (1, 0) � íóëåâî� êîìïîíåíòî� (âûðîæäåííû� ñëó÷àé). Ðåøà� ñèñòåì� óðàâíåíè� è� (10.1), íàõîäè� q 0 = (1/2, 1/2). Ïîëó÷åííà� ñèòóàöè� ðàâíîâåñè� í� åäèíñòâåííà. Äåéñòâèòåëüíî, çàïèøå� óñëîâè� (10.1) äë� ñòðàòåãè� (q ∗ , 1 − q ∗ ) âòîðîã� èãðîê� � ó÷åòî� ñâîéñòâ� äîïîëíÿþùå� íåæåñòêîñò� 1 − q ∗ = v1 , q ∗ ≤ v1 , 0 ≤ q ∗ ≤ 1.
Îòñþä� 0 ≤ q ∗ ≤ 1/2. Òàêè� îáðàçîì, � äàííî� ïðèìåð� ïîëó÷èë� öåëû� îòðåçî� ñèòóàöè� ðàâíîâåñè� {((1, 0), (q ∗ , 1 − q ∗ )) | 0 ≤ q ∗ ≤ 1/2}. Äë� èãð� � ìàòðèöàì� ðàçìåðî� 3 × 3 ïîèñ� ñìåøàííû� ðàâíîâåñè� ï� Íýø� óæ� òðåáóå� äîñòàòî÷í� áîëüøîã� ïåðåáîð� âñåâîçìîæíû� ïîäìàòðè� èñõîäíû� ìàòðè� A � B . Îäíàê� � íåêîòîðû� ñëó÷àÿõ, îáñóæäàåìû� � ñëåäóþùè� äâó� ïàðàãðàôàõ, ýòî� ïåðåáî� ìîæí� çíà÷èòåëüí� ñîêðàòèòü.
Âïîëí� ñìåøàííî� ðàâíîâåñè� Îïðåäåëåíèå. Ñèòóàöè� ðàâíîâåñè� íàçûâàåòñ� âïîëí� ñìåøàííîé, åñë� âñ� ÷èñòû� ñòðàòåãè� èñïîëüçóþòñ� � ïîëîæèòåëüíûì� âåðîÿòíîñòÿìè. 111 ÃËÀÂ� II. ÈÃÐ� ÄÂÓ� ËÈ�� îáùè� ïðåäïîëîæåíèÿ� (äë� "ïî÷ò� ëþáî� áèìàòðè÷íî� èãðû") âïîëí� ñìåøàííî� ðàâíîâåñè� ìîæå� ñóùåñòâîâàòü, òîëüê� åñë� m = n. Ýò� èíòóèòèâí� ïîíÿòíî: äë� íàõîæäåíè� ñìåøàííî� ñòðàòåãè� âòîðîã� èãðîêà, � êîòîðî� âñ� êîìïîíåíò� îòëè÷í� î� íóëÿ, òðåáóåòñ� ðåøèò� ñèñòåì� óðàâíåíè� è� (10.1), ñîäåðæàùó� m + 1 óðàâíåíè� � n + 1 íåèçâåñòíû� (÷èñë� ýëåìåíòî� â� ìíîæåñòâ� Y ïëþ� åù� îäí� íåèçâåñòíî� v1 ). Ñëåäîâàòåëüíî, äë� ñóùåñòâîâàíè� ðåøåíè� äîëæí� âûïîëíÿòüñ� óñëîâè� n ≥ m. Àíàëîãè÷íî, ñìåøàííà� ñòðàòåãè� ïåðâîã� èãðîê� óäîâëåòâîðÿå� ñèñòåì� óðàâíåíè� è� (10.2), ñîäåðæàùå� n + 1 óðàâíåíè� � m + 1 íåèçâåñòíûì, � äë� ñóùåñòâîâàíè� ðåøåíè� äîëæí� áûò� m ≥ n.
� ðåçóëüòàò� ïîëó÷àåì, ÷ò� äë� ñóùåñòâîâàíè� ðåøåíè� îáåè� ñèñòå� äîëæí� áûò� m = n, åñë� îá� ñèñòåì� íåâûðîæäåííûå. Âûïèøå� äë� âïîëí� ñìåøàííîã� ðàâíîâåñè� (p0 , q 0 ) ñèñòåì� óðàâíåíè� è� (10.1) � (10.2) � ìàòðè÷íî� âèä� Aq 0 = v1 e, q 0 , e = 1, p 0 B = v2 e, p 0 , e = 1, ãä� e = (1, ..., 1) ∈ E m .
Àíàëîãè÷íû� ñèñòåì� (5.3) � (5.4) ñïðàâåäëèâ� äë� êðàéíè� îïòèìàëüíû� ñìåøàííû� ñòðàòåãè� è� 5. (Òà� æ� ñì. � ñïîñî� íàõîæäåíè� ðåøåíè� ýòè� ñèñòåì.) Ïóñò� ìàòðèö� A � B − íåâûðîæäåííûå. Òîãä� q 0 = p 0 = A−1 e 1 , v1 = , A−1 e, e A−1 e, e eB −1 1 , v2 = . −1−1eB , e eB , e Äîìèíèðîâàíè� � áèìàòðè÷íû� èãðà� Ïð� ïîèñê� ñèòóàöè� ðàâíîâåñè� � áèìàòðè÷íû� èãðà� ìîæí� èñïîëüçîâàò� äîìèíèðîâàíè� ñòðî� ìàòðèö� A � ñòîëáöî� ìàòðèö� B. Îïðåäåëåíèå.
Áóäå� ãîâîðèòü, ÷ò� � áèìàòðè÷íî� èãð� Γ ñòðàòåãè� ïåðâîã� èãðîê� i1 ñòðîã� äîìèíèðóå� ñòðàòåãè� i2 (i1 � i2 ) í� ìíîæåñòâ� Y ⊆ Y, åñë� ai1 j > ai2 j ∀ j ∈ Y . Áóäå� ãîâîðèò� � ñëàáî� äîìèíèðîâàíè� (i1 � i2 ), åñë� ai1 j ≥ ai2 j ∀ j ∈ Y . Ï� ñìûñë� ïð� ñòðîãî� äîìèíèðîâàíè� ñòðàòåãè� i1 ïðèíîñè� ïåðâîì� èãðîê� áîëüøè� âûèãðûø, ÷å� ñòðàòåãè� i2 , êà� á� í� èãðà� âòîðî� 112 10.
Ñèòóàöè� ðàâíîâåñè� � áèìàòðè÷íû� èãðà�èãðîê, èñïîëüçó� ñòðàòåãè� è� ìíîæåñòâ� Y . Àíàëîãè÷í� ââîäÿòñ� ïîíÿòè� ñòðîãîã� � ñëàáîã� äîìèíèðîâàíè� äë� ñòðàòåãè� âòîðîã� èãðîêà. Îïðåäåëåíèå. Áóäå� ãîâîðèòü, ÷ò� � áèìàòðè÷íî� èãð� Γ ñòðàòåãè� âòîðîã� èãðîê� j1 ñòðîã� äîìèíèðóå� ñòðàòåãè� j2 (j1 � j2 ) í� ìíîæåñòâ� X ⊆ X, åñë� bij1 > bij2 ∀ i ∈ X . Áóäå� ãîâîðèò� � ñëàáî� äîìèíèðîâàíè� (j1 � j2 ), åñë� bij1 ≥ bij2 ∀ i ∈ X . Îïðåäåëè� ïðîöåäóð� ïîñëåäîâàòåëüíîã� èñêëþ÷åíè� ñòðîã� äîìèíèðóåìû� ñòðàòåãèé. Ýò� ïðîöåäóð� ñîñòîè� � ïîñòðîåíè� äâó� ïîñëåäîâàòåëüíîñòå� âëîæåííû� ìíîæåñò� X = X1 ⊇ X2 ⊇ · · · ⊇ Xk èY = Y1 ⊇ Y2 ⊇ · · · ⊇ Yk .
Ïð� ýòî� äë� l = 1, ..., k − 1 âûïîëíåí� ñëåäóþùè� óñëîâèÿ: ∀ i2 ∈ Xl \Xl+1 ∃ i1 ∈ Xl+1 : i1 � i2 í� Yl ;∀ j2 ∈ Yl \Yl+1 ∃ j1 ∈ Yl+1 : j1 � j2 í� Xl .Ì� îïèñàë� ïðîöåäóð� ïîñëåäîâàòåëüíîã� èñêëþ÷åíè� ñòðàòåãè� ôîðìàëüíî. Ïîñìîòðèì, êà� ýò� ïðîöåäóð� îñóùåñòâëÿåòñ� í� ïðàêòèêå. Øà� 1. È� ìíîæåñò� X = X1 � Y = Y1 ñòðîè� ìíîæåñòâ� X2 � Y2 . Äë� ýòîã� âûêèäûâàå� è� ìíîæåñòâ� X1 âñ� ñòðîã� äîìèíèðóåìû� í� ìíîæåñòâ� Y1 ñòðàòåãèè, ò.å.
ì� èùå� òàêè� ïàð� ñòðàòåãè� i1 , i2 , ÷ò� ñòðîê� i1 ïîýëåìåíòí� áîëüø� ñòðîê� i2 � ìàòðèö� A : ai1 j > ai2 j , j = 1, ..., n. Âû÷åðêèâàå� âñ� òàêè� íàéäåííû� ñòðîê� i2 � îáåè� ìàòðèöàõ. Àíàëîãè÷í� èùå� ñòîëáö� j2 � ìàòðèö� B âòîðîã� èãðîêà, êîòîðû� ñòðîã� äîìèíèðóþòñ� äðóãèì� ñòîëáöàì� j1 : bij1 > bij2 , i = 1, ..., m. Âû÷åðêèâàå� âñ� òàêè� äîìèíèðóåìû� ñòîëáö� j2 è� îáåè� ìàòðèö. Ïðåäïîëîæèì, ÷ò� íà� óäàëîñ� âû÷åðêíóò� õîò� á� îäí� ñòðîê� èë� ñòîëáåö. Òîãä� ïåðåõîäè� � øàã� 2. Øà� 2.
Ïîñë� âû÷åðêèâàíè� ñòðî� � ñòîëáöî� í� ïåðâî� øàã� ì� ïîëó÷èë� ðåäóöèðîâàííû� ìàòðèöû, � êîòîðû� ìíîæåñòâ� ñòðî� − X2 , � ìíîæåñòâ� ñòîëáöî� − Y2 . Ïð� ýòî� ëèá� X2 =6 X1 , ëèá� Y2 =6 Y1 , ëèá� îá� ìíîæåñòâ� í� ñîâïàäàþ� � ïðåäûäóùèìè. Ìîæå� ïîëó÷èòüñ� òàê, ÷ò� � ðåäóöèðîâàííû� ìàòðèöà� îêàæóòñ� íîâû� äîìèíèðóåìû� ñòðîê� � ñòîëáöû. Âû÷åðêèâàå� è� � ïåðåõîäè� � ñëåäóþùåì� øàãó.
� òà� äàëåå. Ïðîäîëæàå� ïðîöåäóð� ä� òå� ïîð, ïîê� í� âû÷åðêíå� âñå, ÷ò� ìîæíî. Íèæ� äîêàçàíî, ÷ò� ïð� ýòî� ñîõðàíÿþòñ� âñ� ñìåøàííû� ðàâíîâåñè� ï� Íýøó. Îïðåäåëåíèå. Áóäå� ãîâîðèòü, ÷ò� ìíîæåñòâ� Z = X ×Y ñòðîã� äîìèíèðóå� ìíîæåñòâ� Z = X × Y (Z � Z ), åñë� îí� ïîëó÷åí� è� ìíîæåñòâ� 113 ÃËÀÂ� II. ÈÃÐ� ÄÂÓ� ËÈ�Z ïîñëåäîâàòåëüíû� èñêëþ÷åíèå� ñòðîã� äîìèíèðóåìû� ñòðàòåãèé, ò.å. � îïèñàííî� âûø� ïðîöåäóð� X = Xk , Y = Yk . Áóäå� ãîâîðèò� � ñëàáî� äîìèíèðîâàíè� (Z � Z ), åñë� ìíîæåñòâ� Z ïîëó÷åí� è� ìíîæåñòâ� Z ïîñëåäîâàòåëüíû� èñêëþ÷åíèå� ñëàá� äîìèíèðóåìû� ñòðàòåãèé. Ðàññìîòðè� ïîíÿòè� äîìèíèðîâàíè� � ñìåøàííû� ñòðàòåãèÿõ. Îïðåäåëåíèå. Áóäå� ãîâîðèòü, ÷ò� ñìåøàííà� ñòðàòåãè� p ñòðîã� äîìèíèðóå� ÷èñòó� ñòðàòåãè� i í� ìíîæåñòâ� Y ⊆ Y (p � i), åñë� A(p, j) > aij ∀ j ∈ Y .
Áóäå� ãîâîðèò� � ñëàáî� äîìèíèðîâàíè� í� ìíîæåñòâ� Y ⊆ Y (p � i), åñë� A(p, j) ≥ aij ∀ j ∈ Y . Àíàëîãè÷í� îïðåäåëÿåòñ� äîìèíèðîâàíè� � ñìåøàííû� ñòðàòåãèÿ� âòîðîã� èãðîêà. Êà� èñêàò� ñòðîã� äîìèíèðóåìó� ñòðàòåãèþ? Ïðèìå� 10.4. Ðàññìîòðè� èãð� Γ � ìàòðèöàì� ⎛ ⎛ ⎞ −40 2 44 4 3 1⎠ . A = 4 −1 7⎠ , B = −1 −5 3 0 −4 −2 1 Íàéä¼� � êàæäî� ñòîëáö� ïåðâî� ìàòðèö� ìàêñèìàëüíû� ýëåìåíò.
Åñë� ìàêñèìó� åäèíñòâåííû� � ñòîè� � íåêîòîðî� ñòðîêå, ò� îí� í� ìîæå� áûò� ñòðîã� äîìèíèðóåìîé. Ñëåäîâàòåëüíî, ñòðîã� äîìèíèðóåìî� ìîæå� áûò� òîëüê� ïåðâà� ñòðîêà. � ÷èñòû� ñòðàòåãèÿ� äîìèíèðîâàíè� íåò. Èññëåäóå� äîìèíèðîâàíè� � ñìåøàííû� ñòðàòåãèÿõ. Âîçüì¼� âòîðó� � òðåòü� ñòðîê� � êîýôôèöèåíòàì� 1/2. Âèäíî, ÷ò� ýò� êîìáèíàöè� ñòðîã� äîìèíèðóå� ïåðâó� ñòðîêó.
Ââåä¼� ïîíÿòè� äîìèíèðóþùè� ìíîæåñò� äë� ñìåøàííû� ñòðàòåãèé. Îïðåäåëåíèå. Áóäå� ãîâîðèòü, ÷ò� ìíîæåñòâ� Z = X × Y ñòðîã� äîìèíèðóå� ìíîæåñòâ� Z = X × Y � ñìåøàííû� ñòðàòåãèÿ� (Z � Z ), åñë� îí� ïîëó÷åí� è� ìíîæåñòâ� 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 . Áóäå� ãîâîðèòü, ÷ò� ìíîæåñòâ� Z = X × Y ñëàá� äîìèíèðóå� ìíîæåñòâ� Z = X × Y � ñìåøàííû� ñòðàòåãèÿ� (Z � Z ), åñë� îí� ïîëó÷åí� 114 10.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
