Введение в теорию игр (сторонняя методичка) (1184510), страница 18
Текст из файла (страница 18)
Ïóñòü (p0 , q 0 ) − ñèòóàöèÿ ðàâíîâåñèÿ. Ïîëîæèì v1 = A(p0 , q 0 ), v2 = B(p0 , q 0 ),X 0 = {i ∈ X | p0i > 0}, Y 0 = {j ∈ Y | qj0 > 0}.Óñëîâèÿ (10.1) è (10.2) âûòåêàþò èç ëåììû 10.1 è òåîðåìû 10.1.Äîñòàòî÷íîñòü. Ïóñòü äëÿ ñèòóàöèè (p0 , q 0 ) âûïîëíåíû óñëîâèÿ (10.1)è (10.2).
Ïîêàæåì, ÷òî òîãäà íåîáõîäèìî A(p0 , q 0 ) = v1 . Äåéñòâèòåëüíî,èç (10.1)nXX0aij qj =aij qj0 = v1 ∀ i ∈ X 0 .j∈Y 0j=1Óìíîæàÿ ýòè ðàâåíñòâà íà p0i , i ∈ X 0 , è ñêëàäûâàÿ èõ, ïîëó÷èìA(p0 , q 0 ) = v1 . Àíàëîãè÷íî äîêàçûâàåòñÿ, ÷òî B(p0 , q 0 ) = v2 . Ïî ëåììå10.1 (p0 , q 0 ) ÿâëÿåòñÿ ñèòóàöèåé ðàâíîâåñèÿ.Óïðàæíåíèå 10.1. Äîêàæèòå, ÷òî â èãðå Γ2 0 11A= 1 2 0 , B= 20 1 20ñ ìàòðèöàìè0 21 02 1cóùåñòâóåò åäèíñòâåííîå ðàâíîâåñèå ïî Íýøó(p0 , q 0 ) = ((1/3, 1/3, 1/3), (1/3, 1/3, 1/3)).Ñôîðìóëèðóåì óñëîâèå, îáåñïå÷èâàþùåå ðàâåíñòâî |X 0 | = |Y 0 |1 . ýòîì ñëó÷àå ìàòðèöû ñèñòåì (9.7) è (9.8)A = (aij )i∈X 0 j∈Y 0 , B = (bij )i∈X 0 j∈Y 0ÿâëÿþòñÿ êâàäðàòíûìè.Îïðåäåëåíèå. Ãîâîðÿò, ÷òî ñèñòåìà âåêòîðîâ a(i) ∈ E m , i ∈ X 0 , |X 0 | ≥m + 1 èìååò ìàêñèìàëüíûé àôôèííûé ðàíã, åñëè íàéäóòñÿ òàêîé íîìåði0 ∈ X 0 è òàêîå ìíîæåñòâî X 1 ⊂ X 0 , i0 ∈/ X 1 , |X 1 | = m, ÷òî âåêòîðûa(i) − a(i0 ) , i ∈ X 1 ëèíåéíî íåçàâèñèìû.
Íàïðèìåð, ïðè m = 2 ñèñòåìàòî÷åê íà ïëîñêîñòè òîãäà è òîëüêî òîãäà èìååò ìàêñèìàëüíûé àôôèííûéðàíã, êîãäà òî÷êè íå ëåæàò íà îäíîé ïðÿìîé.Îïðåäåëåíèå. Ãîâîðÿò, ÷òî ìàòðèöà A (ìàòðèöà B ) íàõîäèòñÿ â îáùåìïîëîæåíèè, åñëè ñèñòåìà ñòðîê (ñòîëáöîâ) ëþáîé åå ïîäìàòðèöû A =1 ÌíîæåñòâàX 0 è Y 0 ñîäåðæàò ðàâíîå ÷èñëî ýëåìåíòîâ.105ÃËÀÂÀ II.
ÈÃÐÛ ÄÂÓÕ ËÈÖ(aij )i∈X 0 j∈Y 0 ñ |X 0 | > |Y 0 | (ïîäìàòðèöû B = (bij )i∈X 0 j∈Y 0 c |X 0 | < |Y 0 |)èìååò ìàêñèìàëüíûé àôôèííûé ðàíã.Îòìåòèì, ÷òî äëÿ ëþáûõ äâóõ ìàòðèö A è B íàéäóòñÿ ñêîëü óãîäíîïîýëåìåíòíî áëèçêèå ìàòðèöû A0 è B 0 , äëÿ êîòîðûõ âûïîëíåíî óñëîâèå îáùíîñòè ïîëîæåíèÿ. Ýòî óòâåðæäåíèå ìîæíî äîêàçàòü, èñïîëüçóÿíåïðåðûâíîñòü îïðåäåëèòåëÿ ìàòðèöû êàê ôóíêöèè åå ýëåìåíòîâ.Òåîðåìà 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 )qj0 = 0 ∀ i ∈ X 1 ,j∈Y 0èìåþùóþíóëåâîå ðåøåíèå qj0 = 0, j ∈ Y 0 , ÷òî ïðîòèâîðå÷èò ðàâåíñòâóP 0qj = 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 è ÷èñëà v1k , v2k , ÷òî |X k | = |Y k | è âûïîëíåíû óñëîâèÿX k kXkkaq=v∀i∈X,pki bkij = v2k∀ j ∈ Y k,ijj1 kkj∈Yi∈XPP kkkkaij qj ≤ v1∀i∈/X ,pi bij ≤ v2k∀j∈/ Y k,kj∈Y kP ki∈XP kkk pi = 1, pki ≥ 0 ∀ i ∈ X k .qj = 1, qj ≥ 0 ∀ j ∈ Y , i∈X kj∈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). Åñëè ðåøåíèÿ ýòèõ ñèñòåìp0i , i ∈ X 0 , v1 è qj0 , j ∈ Y 0 , v2 óäîâëåòâîðÿþò íåðàâåíñòâàì èç óñëîâèé10.1 è 10.2, òî, äîáàâëÿÿ êîìïîíåíòû pi = 0, i ∈/ X 0 , qj = 0, j ∈/ Y 0,0 00ïîëó÷èì ñèòóàöèþ ðàâíîâåñèÿ (p , q ). Èç òåîðåìû 10.3 âûòåêàåò, ÷òî÷åðåç êîíå÷íîå ÷èñëî øàãîâ àëãîðèòì ïðèâîäèò ê ñèòóàöèè ðàâíîâåñèÿ.Ïðîèëëþñòðèðóåì ðàáîòó àëãîðèòìà äëÿ èãð ñ ìàòðèöàìè ðàçìåðîâ2×n:a11 · · · a1nb11 · · · b1nA=, B=.a21 · · · a2nb21 · · · b2n äàííîì ñëó÷àå ñìåøàííàÿ ñòðàòåãèÿ ïåðâîãî èãðîêà èìååò âèä p =(p1 , 1 − p1 ), ãäå 0 ≤ p1 ≤ 1. Ïåðåáèðàòü íóæíî 2 × 2-ïîäìàòðèöû. Êàæäàÿèç íèõ çàäàåòñÿ íîìåðàìè äâóõ ñòîëáöîâ j1 , j2 .
Çàïèøåì ñèñòåìó (10.2)p01 b1j1 + (1 − p01 )b2j1 = v2 ,p01 b1j + (1 − p01 )b2j ≤ v2p01 b1j2 + (1 − p01 )b2j2 = v2 ,∀ j 6= j1 , j2 , 0 ≤ p01 ≤ 1.Åñëè ýòà ñèñòåìà íåñîâìåñòíà, òî ïåðåéäåì ê äðóãîé ïàðå j1 , j2 . Åñëèðåøåíèå p01 , v1 ñèñòåìû (10.2) ñóùåñòâóåò, òî ðàññìîòðèì ñèñòåìó (10.1)a1j1 q ∗ + a1j2 (1 − q ∗ ) = v1 ,a2j1 q ∗ + a2j2 (1 − q ∗ ) = v1 , 0 ≤ q ∗ ≤ 1.107ÃËÀÂÀ II. ÈÃÐÛ ÄÂÓÕ ËÈÖÏóñòü ñóùåñòâóåò åå ðåøåíèå1 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 ≤ p01 ≤ 1, êîãäà âûïîëíåíî íåðàâåíñòâî(ðèñ. 10.1)(b22 − b21 )(b11 − b12 ) ≥ 0.(10.3)6b22 PPPPPPb11b12lPP 1PP P P l2b21 0p01-p11Ðèñ. 10.1Åñëè ñòîëáöû ìàòðèöû B (è ñîîòâåòñòâóþùèå ïðÿìûå l1 è l2 ) íå ñîâïàäàþò, òî êîìïîíåíòû ñìåøàííîé ñòðàòåãèè p0 , óäîâëåòâîðÿþùåé ñèñòåìå (10.2), ìîæíî çàïèñàòü â ÿâíîì âèäåp01 =1Âb22 − b21b11 − b12, p02 =.b22 − b21 + b11 − b12b22 − 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 − a12a11 − a21, q20 =.a22 − a12 + a11 − a21a22 − 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. ÈÃÐÛ ÄÂÓÕ ËÈÖèçäåðæåê íà ÎÒÊ è âîçìîæíûõ âûïëàò ôèðìå.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
