А.А. Васин, В.В. Морозов - Введение в теорию игр с приложениями к экономике (1184512), страница 21
Текст из файла (страница 21)
Òåîðåì� 10.3. Ïóñò� ìàòðèö� A � B èãð� Γ íàõîäÿòñ� � îáùå� ïîëîæåíèè. Òîãä� äë� ëþáî� ñèòóàöè� ðàâíîâåñè� (p0 , q 0 ) � ñìåøàííû� ñòðàòåãèÿ� íàéäóòñ� òàêè� ìíîæåñòâ� X 0 ⊆ X, Y 0 ⊆ Y � òàêè� ÷èñë� v1 , v2 , ÷ò� âûïîëíåí� óñëîâè� (10.1), (10.2) � |X 0 | = |Y 0 |. Äîêàçàòåëüñòâî. Ïóñò� (p0 , q 0 ) − ïðîèçâîëüíà� ñèòóàöè� ðàâíîâåñè� � ñìåøàííû� ñòðàòåãèÿõ. Òîãä� ï� òåîðåì� 10.2 íàéäóòñ� òàêè� ìíîæåñòâ� X 0 ⊆ X, Y 0 ⊆ Y � òàêè� ÷èñë� v1 , v2 , ÷ò� âûïîëíåí� óñëîâè� (10.1) � (10.2). Äîêàæåì, ÷ò� |X 0 | = |Y 0 |. Ïðåäïîëîæèì, ÷ò� |X 0 | > |Y 0 |. Ðàññìîòðè� ïîäìàòðèö� A = (aij )i∈X 0 j∈Y 0 , îòâå÷àþùó� ñèñòåì� óðàâíåíè� (10.1).
È� óñëîâè� îáùíîñò� ïîëîæåíè� íàéäóòñ� òàêî� íîìå� i0 ∈ X 0 � òàêî� ìíîæåñòâ� X 1 ⊂ X 0 , i0 ∈/ X 1 , |X 1 | = |Y 0 |, ÷ò� ìàòðèö� (aij − ai0 j )i∈X 1 j∈Y 0 − íåâûðîæäåííàÿ. È� (10.1) ïîëó÷àå� ñèñòåì� óðàâíåíè� X(aij − ai0 j )qj 0 = 0 ∀ i ∈ X 1 , j∈Y 0 èìåþùó� íóëåâî� ðåøåíè� qj 0 = 0, j ∈ Y 0 , ÷ò� ïðîòèâîðå÷è� ðàâåíñòâ� P 0 qj = 1. j∈Y 0 Àíàëîãè÷í� ïðèõîäè� � ïðîòèâîðå÷èþ, ïðåäïîëàãàÿ, ÷ò� |X 0 | < |Y 0 |.
Óñëîâè� îáùíîñò� ïîëîæåíè� äë� ìàòðè� A � B òðóäí� ïðîâåðèòü. Îòêàçàâøèñ� î� íåãî, ìîæí� ïîëó÷èò� óòâåðæäåíèå, áîëå� ñëàáîå, ÷å� òåîðåì� 10.3. Òåîðåì� 10.3 0 . � ëþáî� áèìàòðè÷íî� èãð� Γ äë� íåêîòîðî� ñèòóàöè� ðàâíîâåñè� (p0 , q 0 ) � ñìåøàííû� ñòðàòåãèÿ� íàéäóòñ� òàêè� ìíîæåñòâ� X 0 ⊆ X, Y 0 ⊆ Y � òàêè� ÷èñë� v1 , v2 , ÷ò� âûïîëíåí� óñëîâè� (10.1), (10.2) � |X 0 | = |Y 0 |.
Äîêàçàòåëüñòâî. Äë� ìàòðè� A � B íàéäóòñ� òàêè� ïîñëåäîâàòåëüíîñò� ìàòðè� {Ak }, {B k }, óäîâëåòâîðÿþùè� óñëîâè� îáùíîñò� ïîëîæåíèÿ, ÷ò� ïîýëåìåíòí� Ak → A, B k → B. 106 10. Ñèòóàöè� ðàâíîâåñè� � áèìàòðè÷íû� èãðà�Âîçüìå� ïîñëåäîâàòåëüíîñò� ñèòóàöè� ðàâíîâåñè� {(pk , q k )} èã� Γk � ìàòðèöàì� Ak , B k . Ï� òåîðåì� 10.3 íàéäóòñ� òàêè� ìíîæåñòâ� X k ⊆ X, Y k ⊆ Y � ÷èñë� v1 k , v2 k , ÷ò� |X k | = |Y k | � âûïîëíåí� óñëîâè� � k k �k k a q= v ∀ i ∈ X, pki bkij = v 2 k∀ j ∈ Y k ,ijj 1 kk j∈Y i∈XPP kk k k aij qj ≤ v1 ∀ i ∈ /X ,∀ j ∈ / Y k , pi bij ≤ v2 k k j∈Y k P ki∈XP k k k pi = 1, pki ≥ 0 ∀ i ∈ X k .
qj = 1, qj ≥ 0 ∀ j ∈ Y , ⎩ ⎩ i∈X k j∈Y k Áå� ïîòåð� îáùíîñò� (âûäåëÿ� ñîîòâåòñòâóþùè� ïîäïîñëåäîâàòåëüíîñòè) ìîæí� ñ÷èòàòü, ÷ò� pk → p0 , q k → q 0 � X k = X 0 , Y k = Y 0 ïðèâñå� k. Ïåðåõîä� � ïîñëåäíè� óðàâíåíèÿ� � íåðàâåíñòâà� � ïðåäåë� ïð� k → ∞, ïîëó÷è� óñëîâè� (10.1),(10.2) äë� ñìåøàííû� ñòðàòåãè� p0 , q 0 . Ï� òåîðåì� 10.2 ñèòóàöè� (p0 , q 0 ) áóäå� ðàâíîâåñèå� ï� Íýøó. Ðàññìîòðè� àëãîðèò� ïîèñê� ñèòóàöè� ðàâíîâåñè� � ñìåøàííû� ñòðàòåãèÿõ.
Ïåðåáèðàå� êâàäðàòíû� ïîäìàòðèö� A = (aij )i∈X 0 j∈Y 0 , B = (bij )i∈X 0 j∈Y 0 � ðåøàå� ñèñòåì� óðàâíåíè� è� (10.1),(10.2). Åñë� ðåøåíè� ýòè� ñèñòå� p0 i , i ∈ X 0 , v1 � qj 0 , j ∈ Y 0 , v2 óäîâëåòâîðÿþ� íåðàâåíñòâà� è� óñëîâè� 10.1 � 10.2, òî, äîáàâëÿ� êîìïîíåíò� pi = 0, i ∈ / X 0 , qj = 0, j ∈ / Y 0 , 0 0� ïîëó÷è� ñèòóàöè� ðàâíîâåñè� (p , q ).
È� òåîðåì� 10.3 âûòåêàåò, ÷ò� ÷åðå� êîíå÷íî� ÷èñë� øàãî� àëãîðèò� ïðèâîäè� � ñèòóàöè� ðàâíîâåñèÿ. Ïðîèëëþñòðèðóå� ðàáîò� àëãîðèòì� äë� èã� � ìàòðèöàì� ðàçìåðî� 2 × n : � � a11 · · · a1n b11 · · · b1n A =, B = . a21 · · · a2n b21 · · · b2n� äàííî� ñëó÷à� ñìåøàííà� ñòðàòåãè� ïåðâîã� èãðîê� èìåå� âè� p = (p1 , 1 − p1 ), ãä� 0 ≤ p1 ≤ 1. Ïåðåáèðàò� íóæí� 2 × 2-ïîäìàòðèöû. Êàæäà� è� íè� çàäàåòñ� íîìåðàì� äâó� ñòîëáöî� j1 , j2 . Çàïèøå� ñèñòåì� (10.2) p 01 b1j1 + (1 − p 01 )b2j1 = v2 ,p01 b1j + (1 − p01 )b2j ≤ v2 p 01 b1j2 + (1 − p 01 )b2j2 = v2 , ∀ j =6 j1 , j2 , 0 ≤ p0 1 ≤ 1.
Åñë� ýò� ñèñòåì� íåñîâìåñòíà, ò� ïåðåéäå� � äðóãî� ïàð� j1 , j2 . Åñë� ðåøåíè� p0 1 , v1 ñèñòåì� (10.2) ñóùåñòâóåò, ò� ðàññìîòðè� ñèñòåì� (10.1) a1j1 q ∗ + a1j2 (1 − q ∗ ) = v1 ,a2j1 q ∗ + a2j2 (1 − q ∗ ) = v1 , 0 ≤ q ∗ ≤ 1. 107 ÃËÀÂ� II. ÈÃÐ� ÄÂÓ� ËÈ�Ïóñò� ñóùåñòâóå� å� ðåøåíèå� q ∗ , v1 . Îïðåäåëè� ñòðàòåãè� ⎧ ∗j = j1 , ⎨ q ,00 ∗q : qj = 1 − q , j = j2 ,⎩0,j = 6 j1 , j2 , � ñèòóàöè� (p0 , q 0 ) áóäå� ñìåøàííû� ðàâíîâåñèå� ï� Íýøó. Çäåñ� àëãîðèòì� ìîæí� äàò� ãåîìåòðè÷åñêó� èíòåðïðåòàöèþ. Í� îòðåçê� 0 ≤ p1 ≤ 1 ñòðîè� ïðÿìû� lj (p1 ) = b1j p1 + b2j (1 − p1 ), j = 1, ..., n.
Òî÷ê� èçëîì� âåðõíå� îãèáàþùå� ñåìåéñòâ� ïðÿìû� lj ñîîòâåòñòâóþ� ïàðà� j1 , j2 , äë� êîòîðû� ñóùåñòâóå� ðåøåíè� p01 , v2 ñèñòåì� (10.2). Ïîýòîì� ïîñëåäîâàòåëüí� ïåðåáèðàå� òî÷ê� âåðõíå� îãèáàþùå� � ðåøàå� ñèñòåì� óðàâíåíè� è� (10.1) � ïðîâåðêî� íåðàâåíñò� 0 ≤ q ∗ ≤ 1. Ïð� n = 2 îá� ìàòðèö� A � B èìåþ� ðàçìåð� 2 × 2. � ýòî� ñëó÷à� ïðÿìû� l1 (p1 ) = b11 p1 +b21 (1−p1 ) � l2 (p1 ) = b12 p1 +b22 (1−p1 ) òîãä� � òîëüê� òîãä� ïåðåñåêàþòñ� � òî÷ê� 0 ≤ p0 1 ≤ 1, êîãä� âûïîëíåí� íåðàâåíñòâ� (ðèñ.
10.1) (b22 − b21 )(b11 − b12 ) ≥ 0. (10.3) 6b22 � PPPPlPP � 1 PP � l2 PPb11 b12 b21 0 p0 1 � p1 1 Ðèñ. 10.1 Åñë� ñòîëáö� ìàòðèö� B (� ñîîòâåòñòâóþùè� ïðÿìû� l1 � l2 ) í� ñîâïàäàþò, ò� êîìïîíåíò� ñìåøàííî� ñòðàòåãè� p0 , óäîâëåòâîðÿþùå� ñèñòåì� (10.2), ìîæí� çàïèñàò� � ÿâíî� âèä� p0 1 = 1 � b22 − b21 b11 − b12 , p0 2 = . b22 − b21 + b11 − b12 b22 − b21 + b11 − b12 ïðîòèâíî� ñëó÷à� ïåðåõîäè� � äðóãî� ïàð� j1 , j2 .
108 (10.4) 10. Ñèòóàöè� ðàâíîâåñè� � áèìàòðè÷íû� èãðà�Äë� ñèñòåì� (10.1), è� êîòîðî� âû÷èñëÿåòñ� ñìåøàííà� ñòðàòåãè� âòîðîã� èãðîêà, âñ� ðàññóæäåíè� ïðîâîäÿòñ� àíàëîãè÷íû� îáðàçîì. � ðåçóëüòàò� ì� ïîëó÷è� ñëåäóþùå� óñëîâè� í� ìàòðèö� ïåðâîã� èãðîêà, îáåñïå÷èâàþùå� ñóùåñòâîâàíè� ðåøåíè� ñèñòåì� (10.1): (a22 − a12 )(a11 − a21 ) ≥ 0. (10.5) Ýò� óñëîâè� ìîæí� âûïèñàò� � ñðàçó, èñõîä� è� ñëåäóþùè� ñîîáðàæåíèé: íàä� çàìåíèò� âòîðîã� èãðîê� ïåðâû� � ó÷åñòü, ÷ò� âòîðî� èãðî� âûáèðà� ñâî� ñòðàòåãè� ï� ñòîëáöàì, � ïåðâû� âûáèðàå� è� ï� ñòðîêàì.
Ïîýòîìó, ÷òîá� âûïèñàò� óñëîâè� ñóùåñòâîâàíè� ðåøåíèÿ, íàä� âûïèñàò� óñëîâè� (10.3), çàìåíè� îäí� ìàòðèö� í� äðóãóþ, � ñòðîê� í� ñòîëáöû. Åñë� ñòðîê� ìàòðèö� A í� ñîâïàäàþò, ò� êîìïîíåíò� ñìåøàííî� ñòðàòåãè� q 0 , óäîâëåòâîðÿþùå� ñèñòåì� (10.1), ìîæí� çàïèñàò� � ÿâíî� âèä� q10 = a22 − a12 a11 − a21 , q20 = . a22 − a12 + a11 − a21 a22 − a12 + a11 − a21 (10.6) Ïðèìå� 10.1. Ìîäåë� òåõíè÷åñêîã� êîíòðîë� ç� êà÷åñòâî� ïðîäóêöèè. Çàâî� âûïóñêàå� àâòîìîáèë� ïàðòèÿì� ï� 100 øòóê. Ç� êàæäó� àâòîìàøèí� çàâî� ïîëó÷àå� î� êîíöåðí� 1.3 åä. îïëàòû, è� êîòîðû� 1 åä. ñîñòàâëÿþ� ïðåìèàëüíûå, � 0.3 åä. ïðåäíàçíà÷åí� äë� îïåðàöè� òåõíè÷åñêîã� êîíòðîë� (ÎÒÊ).
Çàâî� (èãðî� 1) ìîæå� âûïóñêàò� ïàðòè� àâòîìîáèëå� ëèá� � ÎÒ� (ñòðàòåãè� 1), ëèá� áå� ÎÒ� (ñòðàòåãè� 2), óâåëè÷èâà� ñóìì� ïðåìèàëüíûõ. Ïð� èñïîëüçîâàíè� ïåðâî� ñòðàòåãè� èòîãîâà� ñóìì� ïðåìèàëüíûõ, ïîëó÷åííà� çàâîäî� ç� ïàðòèþ, ñîñòàâëÿå� 100 åä., ïð� èñïîëüçîâàíè� âòîðî� ñòðàòåãè� − 130 åä. � öåëü� óìåíüøåíè� ïðîèçâîäñòâåííîã� áðàê� êîíöåð� ðåøè� ïðèâëå÷� íåçàâèñèìó� ôèðìó, îñóùåñòâëÿþùó� òåõíè÷åñêè� êîíòðîë� ç� êà÷åñòâî� ïðîäóêöèè. Ñòîèìîñò� ïðîâåðê� àâòîìîáèë� äë� ôèðì� ñîñòàâëÿå� 0.12 åä.
Åñë� ÎÒ� çàâîäî� í� ïðîâîäèòñÿ, ò� àâòîìîáèë� íåèñïðàâå� � âåðîÿòíîñòü� 4/5. � ñëó÷à� îáíàðóæåíè� íåèñïðàâíîñòå� çàâî� îáÿçà� è� óñòðàíèòü, çàòðàòè� 0.3 åä., � çàïëàòèò� äîïîëíèòåëüí� ôèðì� 0.2 åä. è� ñâîè� ïðåìèàëüíûõ. Ôèðì� (èãðî� 2) ìîæå� ëèá� ïðîâåðèò� ïàðòè� (ñòðàòåãè� 1), ëèá� îòêàçàòüñ� î� å� ïðîâåðê� (ñòðàòåãè� 2). Âûèãðûøå� ïåðâîã� èãðîê� ÿâëÿåòñ� îæèäàåìà� ñóìì� ïðåìèàëüíûõ, ïîëó÷åííà� çàâîäî� î� êîíöåðí� ç� ïàðòè� àâòîìîáèëå� � ó÷åòî� 109ÃËÀÂ� II. ÈÃÐ� ÄÂÓ� ËÈ�èçäåðæå� í� ÎÒ� � âîçìîæíû� âûïëà� ôèðìå. Âûèãðûøå� âòîðîã� èãðîê� ÿâëÿåòñ� îæèäàåìà� ñóìì� âûïëàò, ïîëó÷åííû� î� çàâîä� ïð� ïðîâåðê� ïàðòè� àâòîìîáèëå� � ó÷åòî� çàòðà� í� ýò� ïðîâåðêó.
Âûïèøå� ìàòðèö� èãð� 100 100 −12 0 A = , B = . 90 130 4 0 Íàïðèìåð, åñë� çàâî� í� ïðîâîäè� ÒÊ, � ôèðì� ïðîâåðÿå� ïàðòèþ, ò� ñðåäíè� ïðåìèàëüíû� ðàâí� 100(0.8(4/5) + 1.3(1/4)) = 90 åä., � îæèäàåìà� ïðèáûë� ôèðì� ñîñòàâè� 100(0.08(4/5)−0.12(1/5)) = 4 åä.
Íåòðóäí� âèäåòü, ÷ò� � äàííî� èãð� í� ñóùåñòâóå� ñèòóàöè� ðàâíîâåñè� � ÷èñòû� ñòðàòåãèÿõ. Óñëîâè� (10.3) � (10.5) âûïîëíåí� � ñèòóàöè� ðàâíîâåñè� íàõîäè� ï� ôîðìóëà� (10.4) � (10.6) (p0 , q 0 ) = ((1/4, 3/4), (3/4, 1/4)). Ðàâíîâåñíû� ñòðàòåãè� p0 � q 0 ìîãó� áûò� ðåàëèçîâàí� � âèä� "ôèçè÷åñêè� ñìåñåé": ïåðâû� èãðî� "äîëæåí"25 àâòîìîáèëå� êàæäî� ïàðòè� âûïóñêàò� c ÎÒÊ, âòîðî� èãðî� äîëæå� ïðîâåðÿò� ï� 75 àâòîìîáèëå� êàæäî� ïàðòèè.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
