[учебник] Введение в теорию игр (с приложениями к экономике). Васин, Морозов (2003) (1186146), страница 20
Текст из файла (страница 20)
Ðàññìîòðèì âòîðóþ ìàòðèöó. Ìîæíîçàìåòèòü, ÷òî ïåðâûé ñòîëáåö ñòðîãî äîìèíèðóåòñÿ, íàïðèìåð, âòîðûìñòîëáöîì. Ñëåäîâàòåëüíî, ïåðâûé ñòîëáåö ìîæíî âû÷åðêíóòü. Ïîëó÷àåì, ÷òî{2, 3} × {2, 3} Z.Òåïåðü ñôîðìóëèðóåì òåîðåìó î ñâÿçè èñêëþ÷åíèÿ äîìèíèðóåìûõñòðàòåãèé è ïîèñêà ñìåøàííûõ ðàâíîâåñèé ïî Íýøó.Òåîðåìà 10.4. 1) Ïóñòü ìíîæåñòâî Z = X × Y ñòðîãî äîìèíèðó-åò ìíîæåñòâî Z = X × Y â ñìåøàííûõ ñòðàòåãèÿõ. Òîãäà äëÿ ëþáîéñèòóàöèè ðàâíîâåñèÿ (p0 , q 0 ) âûïîëíåíû óñëîâèÿi∈/ X ⇒ p0i = 0;j∈/ Y ⇒ qj0 = 0.2) Ïóñòü ìíîæåñòâî Z = X × Y ñëàáî äîìèíèðóåò ìíîæåñòâîZ = X × Y â ñìåøàííûõ ñòðàòåãèÿõ è (p, q) − ñèòóàöèÿ ðàâíîâåñèÿ âèãðå ñ ìàòðèöàìèA = (aij )i∈X j∈Y , B = (bij )i∈X j∈Y .115ÃËÀÂÀ II.
ÈÃÐÛ ÄÂÓÕ ËÈÖÎïðåäåëèì ñìåøàííûå ñòðàòåãèè((qj ,X,p,i∈iq 0 : qj0 =p0 : p0i =0,0, i ∈ X\X;j ∈Y,j ∈ Y \Y .Òîãäà (p0 , q 0 ) − ñèòóàöèÿ ðàâíîâåñèÿ â èñõîäíîé èãðå Γ.Óïðàæíåíèå 10.2. Äîêàæèòå òåîðåìó 10.4.Îáñóäèì ñìûñë òåîðåìû. Âòîðîå óòâåðæäåíèå ãîâîðèò î òîì, ÷òî åñëè ðåäóöèðîâàííàÿ èãðà ïîëó÷åíà ïóòåì èñêëþ÷åíèÿ ñëàáî äîìèíèðóåìûõ ñòðàòåãèé, òî êàæäîìó ñìåøàííîìó ðàâíîâåñèþ ïî Íýøó (p, q) âýòîé ðåäóöèðîâàííîé èãðå áóäåò ñîîòâåòñòâîâàòü ñìåøàííîå ðàâíîâåñèåïî Íýøó (p0 , q 0 ) â èñõîäíîé èãðå, îïðåäåëÿåìîå ïî óêàçàííîìó ïðàâèëó.Ïåðâîå óòâåðæäåíèå òåîðåìû ïîêàçûâàåò, ÷òî ïðè âû÷¼ðêèâàíèè ñòðîê èñòîëáöîâ ïî ñòðîãîìó äîìèíèðîâàíèþ ìû íå òåðÿåì ðàâíîâåñèé ïî Íýøó.Òàêèì îáðàçîì, ïðè ïîèñêå âñåõ ðàâíîâåñèé ïî Íýøó ìîæíî âû÷åðêíóòü âñå ñòðîãî äîìèíèðóåìûå ñòðîêè è ñòîëáöû è èñêàòü ðàâíîâåñèå âðåäóöèðîâàííîé èãðå.
Äîïîëíèâ íóëÿìè íàéäåííîå ðàâíîâåñèå, ìû ïîëó÷èì ðàâíîâåñèå ñìåøàííîå â èñõîäíîé èãðå. Åñëè íåîáõîäèìî íàéòèõîòÿ áû îäíî ñìåøàííîå ðàâíîâåñèå ïî Íýøó, òîãäà ìîæíî âû÷¼ðêèâàòüñòðîêè è ñòîëáöû ïî íåñòðîãîìó äîìèíèðîâàíèþ. Èñêëþ÷åíèå ñòðîê èñòîëáöîâ ïîçâîëÿåò ñîêðàòèòü ïåðåáîð ïîäìàòðèö äëÿ ïîèñêà ðàâíîâåñèé ïî Íýøó.  ïðèìåðå 10.4 ïîñëå èñêëþ÷åíèÿ ñòðîãî äîìèíèðóåìûõñòðàòåãèé ïîëó÷èì ðåäóöèðîâàííóþ èãðó−1 73 1A=, 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 07 2 63 2 0 40 1 0A=0 3 7 0 , B = 0 2 21 1 3 15 3 411604.33 10. Ñèòóàöèè ðàâíîâåñèÿ â áèìàòðè÷íûõ èãðàõÈùåì ìàêñèìàëüíûå ýëåìåíòû â ñòîëáöàõ ïåðâîé ìàòðèöû.  ÷èñòûõ ñòðàòåãèÿõ äîìèíèðîâàíèÿ íåò.
Ðàññìîòðèì äîìèíèðîâàíèå â ñìåøàííûõ ñòðàòåãèÿõ. Âèäíî, ÷òî ÷åòâ¼ðòàÿ ñòðîêà ñòðîãî äîìèíèðóåòñÿêîìáèíàöèåé âòîðîé è òðåòüåé ñòðîê ñ âåñàìè 1/2. Ïîýòîìó åå ìîæíîâû÷åðêíóòü.Òåïåðü íàéä¼ì ìàêñèìàëüíûå ýëåìåíòû â ñòðîêàõ âòîðîé (ðåäóöèðîâàííîé) ìàòðèöû. Âòîðîé ñòîëáåö ñòðîãî äîìèíèðóåòñÿ êîìáèíàöèåéïåðâîãî è ÷åòâ¼ðòîãî ñòîëáöîâ ñ âåñàìè 1/3 − ε è 2/3 + ε ïðè ìàëûõε > 0.
Ìû ìîæåì âû÷åðêíóòü âòîðîé ñòîëáåö. Ñëåäîâàòåëüíî, {1, 2, 3} ×{1, 3, 4} Z .  ðåçóëüòàòå èñêëþ÷åíèÿ ÷åòâåðòîé ñòðîêè è âòîðîãî ñòîëáöà ïîëó÷èì ñëåäóþùèå ðåäóöèðîâàííûå ìàòðèöû:2 6 07 6 0A = 3 0 4 , B = 0 0 4 .0 7 00 2 3Ïîâòîðÿåì ïðîöåäóðó ïîñëåäîâàòåëüíîãî èñêëþ÷åíèÿ ñòðàòåãèé äëÿðåäóöèðîâàííûõ ìàòðèö. Èùåì ìàêñèìàëüíûå ýëåìåíòû â ñòîëáöàõ ïåðâîé ìàòðèöû.  ÷èñòûõ ñòðàòåãèÿõ äîìèíèðîâàíèÿ íåò. Ðàññìîòðèì äîìèíèðîâàíèå â ñìåøàííûõ ñòðàòåãèÿõ. Âòîðóþ è òðåòüþ ñòðîêó èñêëþ÷èòü íåâîçìîæíî, òàê êàê â íèõ ñîäåðæàòñÿ ìàêñèìàëüíûå ïî ñòîëáöàìýëåìåíòû. Ïåðâàÿ ñòðîêà íå ñîäåðæèò íè îäíîãî ìàêñèìàëüíîãî ïî ñòîëáöó ýëåìåíòà, îäíàêî, åå òàêæå íåâîçìîæíî èñêëþ÷èòü, òàê êàê îíà íåäîìèíèðóåòñÿ íè îäíîé ëèíåéíîé êîìáèíàöèåé âòîðîé è òðåòüåé ñòðîêè.Àíàëîãè÷íî, íåâîçìîæíî èñêëþ÷èòü íè îäèí ñòîëáåö âî âòîðîé ìàòðèöå.Ñëåäîâàòåëüíî, ïðîöåäóðà èñêëþ÷åíèÿ ïî äîìèíèðîâàíèþ ñìåøàííûìèñòðàòåãèÿìè çàâåðøåíà è {1, 2, 3} × {1, 3, 4} = Z .Ïîçèòèâíûé ïîäõîä ê ïîíÿòèþ ðàâíîâåñèÿÑëåäóåò îòìåòèòü, ÷òî èñïîëüçîâàíèå ñìåøàííûõ ñòðàòåãèé ñ ïîìîùüþ ìåõàíèçìà áðîñàíèÿ ìîíåò èëè äðóãèõ ïîäîáíûõ ìåõàíèçìîâ íåõàðàêòåðíî äëÿ ðåàëüíîãî ïîâåäåíèÿ ëþäåé.
Äðóãàÿ èíòåðïðåòàöèÿ ñìåøàííûõ ðàâíîâåñèé îòíîñÿòñÿ ê èãðàì, ñîîòâåòñòâóþùèì òèïè÷íûì êîíôëèêòíûì ñèòóàöèÿì, â êîòîðûõ ïðèíèìàþò ó÷àñòèå ìíîãî èíäèâèäóóìîâ. Òàêèå ñèòóàöèè îïèñàíû â ïðèìåðàõ 9.1-4: ìíîæåñòâî ïîêóïàòåëåéïðèõîäèò íà ðûíîê è ñòàëêèâàåòñÿ ñ ìíîæåñòâîì ïðîäàâöîâ; ðàçëè÷íûåïàðû âîäèòåëåé ñòàëêèâàþòñÿ ó ïåðåêðåñòêîâ è ò.ï. Ïîçèòèâíûé ïîäõîäê ðàâíîâåñèþ â ñìåøàííûõ ñòðàòåãèÿõ ïðåäïîëàãàåò, ÷òî êàæäàÿ òàêàÿñòðàòåãèÿ îïèñûâàåò ðàñïðåäåëåíèå èíäèâèäóóìîâ â ñîîòâåòñòâóþùåé117ÃËÀÂÀ II. ÈÃÐÛ ÄÂÓÕ ËÈÖðîëè. Íàïðèìåð, åñëè (p0 , q 0 ) − ñèòóàöèÿ ðàâíîâåñèÿ â èãðå "ïðîäàâåöïîêóïàòåëü"(ïðèìåð 9.1), òî íà ïðàêòèêå äîëÿ p01 ïðîäàâöîâ âåäåò ñåáÿ÷åñòíî, à äîëÿ p02 îáìàíûâàåò, äîëÿ q10 ïîêóïàòåëåé íå ïðîâåðÿåò êóïëåííûé òîâàð, à îñòàëüíûå ïðîâåðÿþò, è ò.ï.
Î÷åâèäíî, ÷òî ëèøü åñëèðàñïðåäåëåíèÿ ïî ñòðàòåãèÿì â êàæäîé ðîëè ñîîòâåòñòâóþò ñìåøàííûìðàâíîâåñèÿì ïî Íýøó, òî íè ó êîãî íå áóäåò ñòèìóëà ïîìåíÿòü ñòðàòåãèþ ïîâåäåíèÿ. Ôîðìàëüíî ýòî îòðàæåíî â ëåììå 10.1 è òåîðåìå 10.1.Ïîýòîìó ìîæíî îæèäàòü, ÷òî ñòàáèëüíûå ðàñïðåäåëåíèÿ ïî ñòðàòåãèÿì â ðåàëüíûõ âçàèìîäåéñòâèÿõ áîëüøèõ ãðóïï îòâå÷àþò ñìåøàííûìðàâíîâåñèÿì ïî Íýøó.
Òåîðåòè÷åñêîå îáîñíîâàíèå ýòîãî òåçèñà äàþò äèíàìè÷åñêèå ìîäåëè ïîâåäåíèÿ (ñì. 14.). Ïðèìåðîì ìîäåëè ïîâåäåíèÿèãðîêîâ ìîæåò ñëóæèòü ìåòîä Áðàóíà ôèêòèâíîãî ðàçûãðûâàíèÿ ìàòðè÷íîé èãðû, èçëîæåííûé â 5. Àíàëîãè÷íûé ìåòîä ìîæíî ïðèìåíÿòüè äëÿ ïîèñêà ñèòóàöèé ðàâíîâåñèÿ â áèìàòðè÷íûõ èãðàõ ñïåöèàëüíîãîâèäà.Îïðåäåëåíèå. Èãðó Γ ñ ìàòðèöàìè A è B íàçîâåì ýêâèâàëåíòíîé àíòàãîíèñòè÷åñêîé, åñëè íàéäåòñÿ òàêàÿ ìàòðèöà A0 = (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)Çàìåòèì, ÷òî ìàòðèöà A0 è êîýôôèöèåíòû fj , gi çäåñü îïðåäåëÿþòñÿ íåîäíîçíà÷íî.
Äåéñòâèòåëüíî, åñëè îíè óäîâëåòâîðÿþò ðàâåíñòâàì (10.7),òî äëÿ ëþáîãî ÷èñëà c ìàòðèöà ñ ýëåìåíòàìè a0ij + c è êîýôôèöèåíòûfj − c, gi + c òàêæå óäîâëåòâîðÿþò (10.7).Åñëè èãðà Γ ýêâèâàëåíòíà àíòàãîíèñòè÷åñêîé, òî ñóììà åå ìàòðèöïðåäñòàâèìà â âèäå A + B = (gi + fj )m×n . Îáðàòíî, åñëè òàêîå ïðåäñòàâëåíèå èìååò ìåñòî, òî Γ ýêâèâàëåíòíà àíòàãîíèñòè÷åñêîé èãðå ñ ìàòðèöåéA0 = (aij − fj )m×n = (−bij + gi )m×n .Óïðàæíåíèå 10.3. Ïóñòü áèìàòðè÷íàÿ èãðà Γ ýêâèâàëåíòíà àíòàãîíèñòè÷åñêîé èãðå ñ ìàòðèöåé A0 , à f1 = 0. Âûðàçèòå ýëåìåíòû ìàòðèöûA0 ÷åðåç ýëåìåíòû ìàòðèö 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≤m1≤j≤nÊàæäûé èãðîê âûáèðàåò ñâîþ ÷èñòóþ ñòðàòåãèþ êàê íàèëó÷øèé îòâåòíà ñîîòâåòñòâóþùèé âåêòîð ÷àñòîò ïàðòíåðà. Åñëè íàèëó÷øèõ îòâåòîâíåñêîëüêî, òî âûáèðàåòñÿ ëþáîé èç íèõ.Òåîðåìà 10.5. Ïóñòü áèìàòðè÷íàÿ èãðà Γ ýêâèâàëåíòíà àíòàãîíè-ñòè÷åñêîé. Òîãäà ëþáàÿ ïðåäåëüíàÿ òî÷êà (p0 , q 0 ) ïîñëåäîâàòåëüíîñòè{(p(k), q(k))} èòåðàöèîííîãî ïðîöåññà ÿâëÿåòñÿ ñèòóàöèåé ðàâíîâåñèÿ èãðû Γ.Óïðàæíåíèå 10.5.
Äîêàæèòå òåîðåìó 10.5.Åñëè áèìàòðè÷íàÿ èãðà Γ íå ýêâèâàëåíòíà àíòàãîíèñòè÷åñêîé, òîóòâåðæäåíèå òåîðåìû 10.5 ìîæåò áûòü íåâåðíûì. Âñÿ îñòàâøàÿñÿ ÷àñòüïàðàãðàôà áóäåò ïîñâÿùåíà äîêàçàòåëüñòâó ýòîãî ôàêòà.  êà÷åñòâå ïðèìåðà ðàññìîòðèì èãðó Γ èç óïðàæíåíèÿ 10.1 c ìàòðèöàìè2 0 11 0 2A = 1 2 0 , B = 2 1 0 ,0 1 20 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. Òîãäàks ikp(k) + sei=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.Òàêèì îáðàçîì, íà (k + 1)-ì øàãå âîçíèêíåò ïàðà (1,1) èëè (1,3). Ïðè÷åì ïîñëå íåñêîëüêèõ âîçìîæíûõ ïîâòîðåíèé ïàðà (1,1) îáÿçàòåëüíî ïåðåéäåò â ïàðó (1,3). Àíàëîãè÷íî äîêàçûâàåòñÿ, ÷òî ïîñëå ïàðû (1,3) ïðîöåññ îáÿçàòåëüíî ïåðåéäåò â ïàðó (3,3) è ò.ä. ïî ñõåìå(1, 1) → (1, 3) → (3, 3) → (3, 2) → (2, 2) → (2, 1) → (1, 1).Ïóñòü íà (k + 1)-ì øàãå ïðîöåññ ïåðåøåë ñ ïàðû (2,1) íà ïàðó (1,1)(ò.å.
ik = 2, jk = 1, ik+1 = jk+1 = 1), íà (k + s + 1)-ì øàãå − ñ ïàðû (1,1)íà ïàðó (1,3), à íà (k + s + t + 1)-ì øàãå − ñ ïàðû (1,3) íà ïàðó (3,3):=kk+sk+s+t..., (2, 1), (1, 1), ..., (1, 1), (1, 3), ..., (1, 3), (3, 3), ...Òîãäà A(1, q(k)) ≥ A(3, q(k)) èA(3, q(k + s + t)) =kA(3, q(k)) + sa31 + ta33≥ A(1, q(k + s + t)) =k+s+tkA(1, q(k)) + sa11 + ta13kA(3, q(k)) + sa11 + ta13≥.k+s+tk+s+tÎòñþäà ïîëó÷àåì íåðàâåíñòâî sa31 + ta33 ≥ sa11 + ta13 èëè t ≥ 2s.=120 10. Ñèòóàöèè ðàâíîâåñèÿ â áèìàòðè÷íûõ èãðàõÈòàê, "ïðåáûâàíèå"ïðîöåññà â åãî îñòàíîâêå íà ïàðå (1,3) áóäåò ïîêðàéíåé ìåðå â äâà ðàçà ïðîäîëæèòåëüíåå, ÷åì íà íåïîñðåäñòâåííî ïðåäøåñòâîâàâøåé îñòàíîâêå íà ïàðå (1,1). Òî÷íî òàê æå ïîñëåäóþùàÿ îñòàíîâêà íà ïàðå (3,3) ïî êðàéíåé ìåðå â äâà ðàçà ïðîäîëæèòåëüíåå, ÷åì íàïàðå (1,3) è ò.ä.Òåïåðü ðàññìîòðèì, êàê ìåíÿþòñÿ ñòðàòåãèè èãðîêîâ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
