[учебник] Введение в теорию игр (с приложениями к экономике). Васин, Морозов (2003) (1186146), страница 19
Текст из файла (страница 19)
Ñòîèìîñòü ïðîâåðêè àâòîìîáèëÿ äëÿ ôèðìû ñîñòàâëÿåò 0.12 åä. Åñëè ÎÒÊ çàâîäîì íå ïðîâîäèòñÿ, òî àâòîìîáèëü íåèñïðàâåí ñ âåðîÿòíîñòüþ 4/5.  ñëó÷àå îáíàðóæåíèÿ íåèñïðàâíîñòåé çàâîäîáÿçàí èõ óñòðàíèòü, çàòðàòèâ 0.3 åä., è çàïëàòèòü äîïîëíèòåëüíî ôèðìå0.2 åä. èç ñâîèõ ïðåìèàëüíûõ. Ôèðìà (èãðîê 2) ìîæåò ëèáî ïðîâåðèòüïàðòèþ (ñòðàòåãèÿ 1), ëèáî îòêàçàòüñÿ îò åå ïðîâåðêè (ñòðàòåãèÿ 2).Âûèãðûøåì ïåðâîãî èãðîêà ÿâëÿåòñÿ îæèäàåìàÿ ñóììà ïðåìèàëüíûõ, ïîëó÷åííàÿ çàâîäîì îò êîíöåðíà çà ïàðòèþ àâòîìîáèëåé ñ ó÷åòîì109ÃËÀÂÀ II. ÈÃÐÛ ÄÂÓÕ ËÈÖèçäåðæåê íà ÎÒÊ è âîçìîæíûõ âûïëàò ôèðìå. Âûèãðûøåì âòîðîãî èãðîêà ÿâëÿåòñÿ îæèäàåìàÿ ñóììà âûïëàò, ïîëó÷åííûõ îò çàâîäà ïðè ïðîâåðêå ïàðòèè àâòîìîáèëåé ñ ó÷åòîì çàòðàò íà ýòó ïðîâåðêó. Âûïèøåììàòðèöû èãðû100 100−12 0A=, B=.90 1304 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 àâòîìîáèëåéêàæäîé ïàðòèè.Ïðèìåð 10.2. ÏóñòüA=2 4 53 2 0, B=.4 2 10 2 36 l1Q bbl2Q2QQQQQQ l3QQ3 QQ01323-p11Ðèñ.
10.2Çäåñü l1 (p1 ) = 3p1 , l2 (p1 ) ≡ 2, l3 (p1 ) = 3(1 − p1 ). Ïåðâàÿ òî÷êà âåðõíåéîãèáàþùåé ( ïåðåñå÷åíèå ïðÿìûõ l2 è l3 íà ðèñ. 10.2) èìååò àáñöèññó110 10. Ñèòóàöèè ðàâíîâåñèÿ â áèìàòðè÷íûõ èãðàõp01 = 1/3. Ðàññìîòðèì ñèñòåìó óðàâíåíèé èç 10.14q ∗ + 5(1 − q ∗ ) = v1 ,2q ∗ + (1 − q ∗ ) = v1 .Èç íåå íàõîäèì q ∗ = 2 > 1, ÷òî íåâîçìîæíî. Ïåðåõîäèì êî âòîðîé òî÷êåîãèáàþùåé, ëåæàùåé íà ïåðåñå÷åíèè ïðÿìûõ l1 è l2 . Îíà èìååò àáñöèññóp01 = 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 12 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, p0 B = v2 e, p0 , e = 1,ãäå e = (1, ..., 1) ∈ E m .Àíàëîãè÷íûå ñèñòåìû (5.3) è (5.4) ñïðàâåäëèâû äëÿ êðàéíèõ îïòèìàëüíûõ ñìåøàííûõ ñòðàòåãèé èç 5. (Òàì æå ñì.
è ñïîñîá íàõîæäåíèÿðåøåíèÿ ýòèõ ñèñòåì.) Ïóñòü ìàòðèöû A è B − íåâûðîæäåííûå. Òîãäàq0 = p0 = 1A−1 e , v1 = ,A−1 e, eA−1 e, eeB −11 , v2 = .−1−1eB , eeB , 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 244 43 1 .A = 4 −1 7 , B = −1−53 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.
Ñèòóàöèè ðàâíîâåñèÿ â áèìàòðè÷íûõ èãðàõèç ìíîæåñòâà 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 è íàéä¼ì äîìèíèðóþùèå ìíîæåñòâà. Ïåðâóþ ñòðîêó ìû âû÷åðêíóëè, òàê êàê îíà ñòðîãî äîìèíèðóåìà êîìáèíàöèåé âòîðîé è òðåòüåé ñòðîê.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
