Введение в теорию игр (сторонняя методичка) (1184510), страница 16
Текст из файла (страница 16)
ÈÃÐÛ ÄÂÓÕ ËÈÖÓïðàæíåíèå 9.2. Ïðîâåðèòü, ÷òî åñëè ýëåìåíòû â ìàòðèöàõ âûèãðûøåé èãðîêîâ ñâÿçàíû òàêèìè ñîîòíîøåíèÿìè, òî â èãðå íå ñóùåñòâóåòðàâíîâåñèé ïî Íýøó.Èãðû, ïîäîáíûå ïðèìåðó 9.1, ðàñïðîñòðàíåíû â ìîäåëÿõ, îïèñûâàþùèõ ýêîíîìè÷åñêèå è ýêîëîãè÷åñêèå âçàèìîäåéñòâèÿ. Ðàññìîòðèì ïðèìåð èãðû, èìåþùåé äâå ñèòóàöèè ðàâíîâåñèÿ.Ïðèìåð 9.2. Èãðà "ñåìåéíûé ñïîð":A=ôòô ò1 0,0 2B=ôòô ò2 0.0 1Èíòåðïðåòàöèÿ. Æåíà è ìóæ (ïåðâûé è âòîðîé èãðîêè) îáñóæäàþò âîïðîñ, êóäà ïîéòè ðàçâëå÷üñÿ: íà ôóòáîë (ñòðàòåãèÿ 1 ) èëè â òåàòð (ñòðàòåãèÿ 2). Åñëè èäóò íà ôóòáîë, òî æåíà ïîëó÷àåò 1 åäèíèöó, à ìóæ −2 åäèíèöû "óäîâîëüñòâèÿ."Åñëè èäóò â òåàòð, òî âûèãðûø æåíû − 2,à ìóæà − 1.
Åñëè îáà èäóò â ðàçíûå ìåñòà, òî âûèãðûøè èãðîêîâ −íóëåâûå. èãðå ñóùåñòâóåò äâå ñèòóàöèè ðàâíîâåñèÿ: (1,1) è (2,2). Ïåðâàÿ èçíèõ ïðåäïî÷òèòåëüíåé âòîðîìó èãðîêó, à âòîðàÿ − ïåðâîìó. Åñëè èãðîêèáóäóò äåéñòâîâàòü íåçàâèñèìî, òî ïåðâûé âûáåðåò ñòðàòåãèþ 2, à âòîðîé− ñòðàòåãèþ 1.  ðåçóëüòàòå îáà ïîëó÷àò ïî íóëþ. Ïðèìåð 9.2 ïîêàçûâàåò, ÷òî íåîáõîäèì êàêîé-òî ìåõàíèçì êîîðäèíàöèè ïðè âûáîðå ñòðàòåãèè,åñëè ñóùåñòâóåò íåñêîëüêî ðàâíîâåñèé ïî Íýøó. Ïîýòîìó èãðû, ïîäîáíûåïðèìåðó 9.2, íàçûâàþò òàêæå "èãðàìè íà êîîðäèíàöèþ".Èñïîëüçîâàíèå ñèòóàöèé ðàâíîâåñèÿ íà ïðàêòèêå ÷àñòî ñâÿçûâàåòñÿñî ñëåäóþùèì ñöåíàðèåì ïîâåäåíèÿ èãðîêîâ. Îíè ñíà÷àëà äîëæíû äîãîâîðèòüñÿ î ñèòóàöèè ðàâíîâåñèÿ, çàòåì âñÿêèå ïåðåãîâîðû çàïðåùàþòñÿè èãðîêè íåçàâèñèìî âûáèðàþò ñâîè ñòðàòåãèè, âîçìîæíî íàðóøàÿ ïðèíÿòîå ñîãëàøåíèå. Çàìåòèì, ÷òî îäíîìó èãðîêó áóäåò íåâûãîäíî îòêëîíÿòüñÿ îò ñâîåé ðàâíîâåñíîé ñòðàòåãèè.
Åñëè èãðîêè ïðèäåðæèâàþòñÿ âèãðå òàêîãî ñöåíàðèÿ ïîâåäåíèÿ, òî èãðà Γ íàçûâàåòñÿ áåñêîàëèöèîííîé.Ïðèâåäåì åùå îäèí ïðèìåð "èãðû íà êîîðäèíàöèþ".Ïðèìåð 9.3. Èãðîêàìè ÿâëÿþòñÿ äâà âîäèòåëÿ, êîòîðûì íàäî ïðîåõàòü ÷åðåç ïåðåêðåñòîê, ê êîòîðîìó îíè ïîäúåõàëè îäíîâðåìåííî.
Åñòüäâå ñòðàòåãèè ïåðåñå÷åíèÿ ïåðåêðåñòêà: èñïîëüçîâàòü "ïðàâèëî ïðàâîéðóêè", ñîãëàñíî êîòîðîìó âîäèòåëü äîëæåí ïðîïóñòèòü ïîìåõó ñïðàâà94 9. Ñèòóàöèè ðàâíîâåñèÿ â èãðàõ äâóõ ëèö(ñòðàòåãèÿ 1), èëè "ïðàâèëî ëåâîé ðóêè", ñîãëàñíî êîòîðîìó âîäèòåëüäîëæåí ïðîïóñòèòü ïîìåõó ñëåâà (ñòðàòåãèÿ 2). Åñëè îáà âîäèòåëÿ ïðèäåðæèâàþòñÿ îäíîãî ïðàâèëà, òî îíè óñïåøíî ðàçúåäóòñÿ, íî åñëè îäèíèç íèõ èñïîëüçóåò "ïðàâèëî ïðàâîé ðóêè", à äðóãîé "ïðàâèëî ëåâîé ðóêè", òî ìîæåò âîçíèêíóòü àâàðèÿ.
Ñëåäîâàòåëüíî, äëÿ áëàãîïðèÿòíîãîèñõîäà â òàêèõ èãðàõ ó âñåõ èãðîêîâ äîëæåí áûòü îäèíàêîâûé ïîäõîä êâûáîðó ïðàâèë ïîâåäåíèÿ.Óïðàæíåíèå 9.3. Îáúÿñíèòü (ñì. ðèñ. 9.1), ïî÷åìó âûèãðûøè èãðîêîââ ïîñëåäíåì ïðèìåðå ìîæíî çàäàòü ñëåäóþùèìè ìàòðèöàìè:A=ïð.ðëåâ.ðïð.ð1−1ëåâ.ð−10,0B=ïð.ðëåâ.ðïð.ð0−1ëåâ.ð−10.12 61Ðèñ. 9.1Ðàññìîòðåííûå â ïðèìåðàõ 9.2 è 9.3 èãðû õàðàêòåðèçóþòñÿ ñëåäóþùèìè ñîîòíîøåíèÿìè ýëåìåíòîâ ìàòðèö âûèãðûøà:a11a12b11 > b12∨.∧ , a21a22b21 < b22Óïðàæíåíèå 9.4. Ïðîâåðèòü, ÷òî ïðè âûïîëíåíèè òàêèõ ñîîòíîøåíèéâ èãðå âñåãäà ñóùåñòâóåò äâà ðàâíîâåñèÿ ïî Íýøó.Ïðèâåäåì ïðèìåð, êîòîðûé ïîêàçûâàåò, ÷òî ðàâíîâåñèå ïî Íýøó ìîæåò áûòü íåýôôåêòèâíûì ñ òî÷êè çðåíèÿ èíòåðåñîâ èãðîêîâ.Ïðèìåð 9.4. Èãðà "äèëåììà çàêëþ÷åííîãî":A=ïðíåòïð íåò−80,−10 −1B=95ïðíåòïð−80íåò−10.−1ÃËÀÂÀ II.
ÈÃÐÛ ÄÂÓÕ ËÈÖÈíòåðïðåòàöèÿ. Äâà áàíäèòà (èãðîêè 1 è 2), ïîäîçðåâàåìûå â ñîâåðøåíèè òÿæêîãî ïðåñòóïëåíèÿ, íàõîäÿòñÿ èçîëèðîâàííî äðóã îò äðóãà âïðåäâàðèòåëüíîì çàêëþ÷åíèè. Ââèäó îòñóòñòâèÿ ïðÿìûõ óëèê óñïåõ èëèíåóñïåõ îáâèíåíèÿ çàâèñèò îò ïðèçíàíèÿ (ñòðàòåãèÿ 1) èëè íåïðèçíàíèÿ(ñòðàòåãèÿ 2) ñàìèõ áàíäèòîâ. Åñëè îáà áàíäèòà ïðèçíàþòñÿ (ñèòóàöèÿ(1,1)), òî îíè áóäóò ïðèçíàíû âèíîâíûìè è ïðèãîâîðåíû ê 8 ãîäàì òþðüìû.
Åñëè íè îäèí èç íèõ íå ïðèçíàåòñÿ (ñèòóàöèÿ (2,2)), òî ïî îáâèíåíèþâ ãëàâíîì ïðåñòóïëåíèè îíè áóäóò îïðàâäàíû, íî îáâèíèòåëþ âñå-òàêèóäàñòñÿ äîêàçàòü èõ âèíîâíîñòü â íåêîòîðîì ñîïóòñòâóþùåì ìåíåå òÿæêîì ïðåñòóïëåíèè, íàïðèìåð, â íîøåíèè îðóæèÿ, â ðåçóëüòàòå ÷åãî îíèáóäóò ïðèãîâîðåíû ê 1 ãîäó òþðüìû. Åñëè, íàêîíåö, ïðèçíàåòñÿ òîëüêîîäèí èç íèõ (ñèòóàöèè (2,1) è (1,2)), òî ïðèçíàâøèéñÿ áóäåò îñâîáîæäåí(çà ïîìîùü ñëåäñòâèþ), à íåïðèçíàâøèéñÿ áóäåò ïðèãîâîðåí ê îòáûòèþìàêñèìàëüíîãî ñðîêà − 10 ëåò. ýòîé èãðå èìååòñÿ åäèíñòâåííàÿ ñèòóàöèÿ ðàâíîâåñèÿ (1,1): îáîèìïðèçíàòüñÿ. Îäíàêî åñòü ñèòóàöèÿ (2,2), áîëåå âûãîäíàÿ îáîèì èãðîêàì,íî íå ÿâëÿþùàÿñÿ ñèòóàöèåé ðàâíîâåñèÿ. Ñëåäîâàòåëüíî, ðàâíîâåñèÿ ïîÍýøó ìîãóò áûòü íåýôôåêòèâíû â òîì ñìûñëå, ÷òî çà ñ÷åò îòêëîíåíèÿîáîèõ èãðîêîâ îò ñèòóàöèè ðàâíîâåñèÿ ìîæíî óëó÷øèòü âûèãðûøè êàæäîãî èç íèõ.Îïèñàííàÿ â ïðèìåðå 9.4 èãðà èìååò ñëåäóþùóþ ñòðóêòóðó:a11a12b11 > b12∨.∨ , a21a22b21 > b22Óïðàæíåíèå 9.5.
Ïðîâåðèòü, ÷òî ïðè âûïîëíåíèè òàêèõ ñîîòíîøåíèéâ èãðå âñåãäà ñóùåñòâóåò åäèíñòâåííîå ðàâíîâåñèå ïî Íýøó. ñâÿçè ñ ïîñëåäíèì ïðèìåðîì äàäèì îïðåäåëåíèå ñèòóàöèè, îïòèìàëüíîé ïî Ïàðåòî.Îïðåäåëåíèå. Ñèòóàöèÿ (x0 , y 0 ) èãðû Γ íàçûâàåòñÿ îïòèìàëüíîé ïîÏàðåòî, åñëè íå ñóùåñòâóåò òàêîé ñèòóàöèè (x, y) ÷òî âûïîëíåíû íåðàâåíñòâàF (x, y) ≥ F (x0 , y 0 ), G(x, y) ≥ G(x0 , y 0 )è ïðè ýòîì õîòÿ áû îäíî èç íèõ − ñòðîãîå. ïðèìåðå 9.4 â ñèòóàöèè (2,2) îáà èãðîêà ïîëó÷àþò ïî −1, ÷òî áîëüøå, ÷åì èõ âûèãðûø −8 â ñèòóàöèè ðàâíîâåñèÿ (1,1).
Ñëåäîâàòåëüíî,ñèòóàöèÿ ðàâíîâåñèÿ íå ÿâëÿåòñÿ îïòèìàëüíîé ïî Ïàðåòî.96 9. Ñèòóàöèè ðàâíîâåñèÿ â èãðàõ äâóõ ëèöÓïðàæíåíèå 9.6. Äîêàæèòå, ÷òî â àíòàãîíèñòè÷åñêîé èãðå ëþáàÿ ñèòóàöèÿ îïòèìàëüíà ïî Ïàðåòî.Ñëåäóþùèé ïðèìåð ïîêàçûâàåò, ÷òî íå âñåãäà ðàâíîâåñíûå ñòðàòåãèèÿâëÿþòñÿ ìàêñèìèííûìè.Ïðèìåð 9.5. ÏóñòüA=2 0 5,2 2 3B=2 2 1.0 7 8Çäåñü (1,1) − åäèíñòâåííàÿ ñèòóàöèÿ ðàâíîâåñèÿ, íî ñòðàòåãèÿ 1 ïåðâîãîèãðîêà íå ÿâëÿåòñÿ ìàêñèìèííîé. Äåéñòâèòåëüíî,W (1) = min a1j = 0,W (2) = min a2j = 2.1≤j≤31≤j≤3Ñòðàòåãèÿ 1 âòîðîãî èãðîêà òàêæå íå ÿâëÿåòñÿ ìàêñèìèííîé. Åñëè èãðîê íåáëàãîæåëàòåëüíî íàñòðîåí ïî îòíîøåíèþ ê ïàðòíåðó, òî îí ìîæåòíàðóøèòü ñîãëàøåíèå è âìåñòî ðàâíîâåñíîé ñòðàòåãèè âûáðàòü ìàêñèìèííóþ.
 ðåçóëüòàòå îí ïîëó÷èò òîò æå âûèãðûø 2, ÷òî è â ñèòóàöèèðàâíîâåñèÿ, à ïàðòíåð ïîëó÷èò 0.Ìû îòìåòèëè òðè íåäîñòàòêà ïîíÿòèÿ ðàâíîâåñèÿ ïî Íýøó:1) ðàâíîâåñèé ïî Íýøó â èãðå ìîæåò íå ñóùåñòâîâàòü;2) ðàâíîâåñèå ïî Íýøó ìîæåò áûòü íå åäèíñòâåííî;3) ðàâíîâåñèå ïî Íýøó ìîæåò áûòü íåýôôåêòèâíî.Íî, íåñìîòðÿ íà ýòè íåäîñòàòêè, óêàçàííîå ïîíÿòèå èãðàåò öåíòðàëüíóþ ðîëü â òåîðèè ïðèíÿòèÿ ðåøåíèé â êîíôëèêòíûõ ñèòóàöèÿõ.Ïðèâåäåì òåîðåìó ñóùåñòâîâàíèÿ ñèòóàöèè ðàâíîâåñèÿ â èãðå äâóõëèö, êîòîðàÿ ÿâëÿåòñÿ îáîáùåíèåì òåîðåìû 2.3.
Ïðåäâàðèòåëüíî ñôîðìóëèðóåì òîïîëîãè÷åñêóþ òåîðåìó î íåïîäâèæíîé òî÷êå.Òåîðåìà 9.1 (Áðàóýð). Ïóñòü f : Z → Z − íåïðåðûâíîå îòîáðàæå-íèå â ñåáÿ âûïóêëîãî êîìïàêòà Z êîíå÷íîìåðíîãî åâêëèäîâà ïðîñòðàíñòâà. Òîãäà ó íåãî ñóùåñòâóåò íåïîäâèæíàÿ òî÷êà z 0 : f (z 0 ) = z 0 .Äîêàçàòåëüñòâî òåîðåìû ñì. â Ïðèëîæåíèè (Ï3,Ï4).Óïðàæíåíèå 9.7. Äîêàæèòå òåîðåìó äëÿ X = [0, 1].Îòìåòèì, ÷òî âñå óñëîâèÿ òåîðåìû ñóùåñòâåííû. Íàïðèìåð, åñëè ìíîæåñòâî Z − íåâûïóêëîå, òî óòâåðæäåíèå òåîðåìû ìîæåò áûòü íåâåðíûì.Äåéñòâèòåëüíî, åñëè Z − îêðóæíîñòü, à f − åå ïîâîðîò íà óãîë α < 2π,òî f íåïîäâèæíîé òî÷êè íå èìååò.97ÃËÀÂÀ II. ÈÃÐÛ ÄÂÓÕ ËÈÖÓïðàæíåíèå 9.8. Ïîñòðîéòå êîíòðïðèìåðû ê óòâåðæäåíèþ òåîðåìû,åñëè1) Z = [0, ∞);2) Z = (0, 1];3) Z = [0, 1], íî ôóíêöèÿ f ðàçðûâíà.Òåîðåìà 9.2. Ïóñòü â èãðå äâóõ ëèö Γ ìíîæåñòâà X è Y − âûïóêëûåêîìïàêòû åâêëèäîâûõ ïðîñòðàíñòâ E m è E n .
Ïðåäïîëîæèì, ÷òî ôóíêöèè F (x, y) è G(x, y) íåïðåðûâíû íà X × Y, ôóíêöèÿ F (x, y) âîãíóòà ïî xïðè ëþáîì ôèêñèðîâàííîì y, à ôóíêöèÿ G(x, y) âîãíóòà ïî y ïðè ëþáîìôèêñèðîâàííîì x. Òîãäà â èãðå Γ ñóùåñòâóåò ñèòóàöèÿ ðàâíîâåñèÿ.Äîêàçàòåëüñòâî. Âíà÷àëå ïðåäïîëîæèì, ÷òî ôóíêöèè F (x, y) è G(x, y)íåïðåðûâíû íà X × Y è ñòðîãî âîãíóòû ïî "ñâîèì"ïåðåìåííûì x è y ñîîòâåòñòâåííî.
Òîãäà äëÿ ëþáûõ ñòðàòåãèé y è x ìíîæåñòâà íàèëó÷øèõîòâåòîâ èãðîêîâdefdefX(y) = Arg max F (x, y) = {x(y)}, Y (x) = Arg max G(x, y) = {y(x)}x∈Xy∈Yñîäåðæàò ïî îäíîìó ýëåìåíòó x(y) è y(x). Ñîãëàñíî òåîðåìå 2.2, ôóíêöèè x(y) è y(x) íåïðåðûâíû. Áóäåì íàçûâàòü èõ ôóíêöèÿìè íàèëó÷øåãîîòâåòà ïåðâîãî è âòîðîãî èãðîêîâ ñîîòâåòñòâåííî.Ïîëîæèì Z = X × Y è ðàññìîòðèì îòîáðàæåíèå f : Z → Z,f (x, y) = (x(y), y(x)). Ïî òåîðåìå 9.1 îòîáðàæåíèå f èìååò íåïîäâèæíóþòî÷êó z 0 = (x0 , y 0 ) : f (z 0 ) = z 0 èëè x(y 0 ) = x0 , y(x0 ) = y 0 . Ñëåäîâàòåëüíî, (x0 , y 0 ) − ñèòóàöèÿ ðàâíîâåñèÿ.Òåïåðü ïðåäïîëîæèì, ÷òî ôóíêöèè F (x, y) è G(x, y) âîãíóòû ïî "ñâîèì"ïåðåìåííûì x è y , íî íåîáÿçàòåëüíî ñòðîãî.
ÏîëîæèìFε (x, y) = F (x, y) − εmXx2i ,Gε (x, y) = G(x, y) − εi=1mXyj2 ,j=1ãäå ε > 0. Ôóíêöèè Fε (x, y) è Gε (x, y) íåïðåðûâíû íà X × Y , Fε (x, y)ñòðîãî âîãíóòàïî x, à Gε (x, y) ñòðîãî âîãíóòà ïî y. Ïî äîêàçàííîìó â èãεðå Γ = X, Y, Fε (x, y), Gε (x, y) ñóùåñòâóåò ñèòóàöèÿ ðàâíîâåñèÿ (xε , y ε ).Ïóñòü {εh } − òàêàÿ ïîñëåäîâàòåëüíîñòü ÷èñåë, ÷òî εh → 0+ è ñîîòâåòñòâóþùàÿ ïîñëåäîâàòåëüíîñòü ñèòóàöèé ðàâíîâåñèÿ {(xεh , y εh )} ñõîäèòñÿê íåêîòîðîé ñèòóàöèè (x0 , y 0 ). Ïî îïðåäåëåíèþ (xεh , y εh )Fεh (x, y εh ) ≤ Fεh (xεh , y εh ) ∀ x ∈ X,98 9. Ñèòóàöèè ðàâíîâåñèÿ â èãðàõ äâóõ ëèöGεh (xεh , y) ≤ Gεh (xεh , y εh ) ∀ y ∈ Y.Ïåðåõîäÿ â ýòèõ íåðàâåíñòâàõ ïðè ôèêñèðîâàííûõ x è y ê ïðåäåëó ïðèh → ∞, ïîëó÷èìF (x, y 0 ) ≤ F (x0 , y 0 ) ∀ x ∈ X, G(x0 , y) ≤ G(x0 , y 0 ) ∀ y ∈ Y,Ýòî îçíà÷àåò, ÷òî (x0 , y 0 ) − ñèòóàöèÿ ðàâíîâåñèÿ èãðû Γ.Ðàññìîòðèì ìåòîä ïîèñêà ñèòóàöèè ðàâíîâåñèÿ ñ èñïîëüçîâàíèåì ìíîæåñòâ íàèëó÷øèõ îòâåòîâ X(y) = Arg max F (x, y) è Y (x) = Arg max G(x, y).x∈XÎí ñîñòîèò â ðåøåíèè ñèñòåìû âêëþ÷åíèéx0 ∈ X(y 0 ), y 0 ∈ Y (x0 ).y∈Y(9.1) ñëó÷àå, êîãäà ó èãðîêîâ ñóùåñòâóþò íåïðåðûâíûå ôóíêöèè íàèëó÷øåãî îòâåòà x(y) è y(x) (ñì.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
