Введение в теорию игр (сторонняя методичка) (1184510), страница 20
Текст из файла (страница 20)
Ñèòóàöèè ðàâíîâåñèÿ â áèìàòðè÷íûõ èãðàõÈùåì ìàêñèìàëüíûå ýëåìåíòû â ñòîëáöàõ ïåðâîé ìàòðèöû.  ÷èñòûõ ñòðàòåãèÿõ äîìèíèðîâàíèÿ íåò. Ðàññìîòðèì äîìèíèðîâàíèå â ñìåøàííûõ ñòðàòåãèÿõ. Âèäíî, ÷òî ÷åòâ¼ðòàÿ ñòðîêà ñòðîãî äîìèíèðóåòñÿêîìáèíàöèåé âòîðîé è òðåòüåé ñòðîê ñ âåñàìè 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) è ò.ä.Òåïåðü ðàññìîòðèì, êàê ìåíÿþòñÿ ñòðàòåãèè èãðîêîâ.
Åñëè ïåðâûéèãðîê íà íåêîòîðîì øàãå èñïîëüçóåò ñòðàòåãèþ 1, òî â äàëüíåéøåì îíåå ñìåíèò íà ñòðàòåãèþ 3, ïîòîì ñòðàòåãèþ 3 íà ñòðàòåãèþ 2 è ò.ä. ïîñëåäóþùåìó öèêëó: 1 → 3 → 2 → 1. Ðàçîáüåì ðàññìàòðèâàåìûé ïðîöåññíà îòðåçêè øàãîâ ïîñòîÿííîãî èñïîëüçîâàíèÿ ïåðâûì èãðîêîì ñâîèõ ÷èñòûõ ñòðàòåãèé. Äëèíà òàêîãî îòðåçêà − ýòî ÷èñëî ñîäåðæàùèõñÿ â íåìøàãîâ.Ëåììà 10.1.
Äëèíà îòðåçêà ïîñòîÿííîãî èñïîëüçîâàíèÿ ïåðâûì èãðîêîì ëþáîé ÷èñòîé ñòðàòåãèè áîëåå, ÷åì â òðè ðàçà ïðåâûøàåò ÷èñëîøàãîâ ïðîöåññà, ïðåäøåñòâîâàâøèõ äàííîìó îòðåçêó.Äîêàçàòåëüñòâî. Áåç ïîòåðè îáùíîñòè áóäåì ñ÷èòàòü, ÷òî ïðîöåññíà÷èíàåòñÿ ñ ïàðû ñòðàòåãèé (i1 , j1 ) = (1, 1). Ïóñòü ïåðâûé èãðîê l1 =1 + s ðàç ïîäðÿä, íà÷èíàÿ ñ ïåðâîãî øàãà, âûáèðàë ñòðàòåãèþ 1 ( îäèíðàç ïðè ïàðå (1,1) è s ðàç ïðè ïàðå (1,3)). Äàëåå, ïóñòü îí l3 = t + hðàç âûáèðàë ñòðàòåãèþ 3 ( t ðàç ïðè ïàðå (3,3) è h ðàç ïðè ïàðå (3,2)).Çàòåì îí l2 ðàçà ïîäðÿä âûáèðàë ñòðàòåãèþ 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
