[учебник] Введение в теорию игр (с приложениями к экономике). Васин, Морозов (2003) ([учебник] Введение в теорию игр (с приложениями к экономике). Васин, Морозов (2003).pdf), страница 16

Òàêèìîáðàçîì, â àíòàãîíèñòè÷åñêîé èãðå ïðèíöèï ðàâíîâåñèÿ ñîãëàñóåòñÿ ñïðèíöèïîì îïòèìèçàöèè èãðîêàìè ñâîèõ ãàðàíòèðîâàííûõ ðåçóëüòàòîâ.Êðîìå òîãî, âî âñåõ ñåäëîâûõ òî÷êàõ âûèãðûø ïåðâîãî èãðîêà îäèí èòîò æå è ðàâåí çíà÷åíèþ èãðû. Ê ñîæàëåíèþ, â îáùåì ñëó÷àå ñèòóàöèèðàâíîâåñèÿ íå îáëàäàþò óêàçàííûìè ñâîéñòâàìè.

Óáåäèìñÿ â ýòîì íàïðèìåðàõ. Ïðåäâàðèòåëüíî ââåäåì ïîíÿòèå áèìàòðè÷íîé èãðû.Îïðåäåëåíèå. Èãðà äâóõ ëèö Γ íàçûâàåòñÿ áèìàòðè÷íîé, åñëè ìíîæåñòâà ñòðàòåãèé èãðîêîâ êîíå÷íû:X = {1, ..., m}, Y = {1, ..., n}.Çäåñü i ∈ X, j ∈ Y − ñòðàòåãèè ïåðâîãî è âòîðîãî èãðîêîâ. Âûèãðûøèèãðîêîâ çàäàþòñÿ äâóìÿ ìàòðèöàìèA = (F (i, j))m×n = (aij )m×n , B = (G(i, j))m×n = (bij )m×n .Çàïèøåì îïðåäåëåíèå ñèòóàöèè ðàâíîâåñèÿ â îáîçíà÷åíèÿõ áèìàòðè÷íîé èãðû.Îïðåäåëåíèå. Ñèòóàöèÿ (i0 , j 0 ) áèìàòðè÷íîé èãðû Γ íàçûâàåòñÿ ñèòóàöèåé ðàâíîâåñèÿ (ðàâíîâåñèåì ïî Íýøó), åñëèaij 0 ≤ ai0 j 0 , i = 1, ..., m,bi0 j ≤ bi0 j 0 , j = 1, ..., n.Âñåãäà ëè â èãðå äâóõ ëèö ñóùåñòâóåò ñèòóàöèÿ ðàâíîâåñèÿ?  îáùåìñëó÷àå îòâåò − îòðèöàòåëüíûé, ïîñêîëüêó, íàïðèìåð, â àíòàãîíèñòè÷åñêîé èãðå íå âñåãäà ñóùåñòâóåò ñåäëîâàÿ òî÷êà.Ïðèâåäåì ïðèìåð íåàíòàãîíèñòè÷åñêîé èãðû, íå èìåþùåé ñèòóàöèèðàâíîâåñèÿ.92Ÿ 9.

Ñèòóàöèè ðàâíîâåñèÿ â èãðàõ äâóõ ëèöÏðèìåð 9.1. Ïîêóïàòåëü (èãðîê 2) ïðèõîäèò íà ðûíîê çà ÿáëîêàìè.Ïðîäàâåö, òîðãóþùèé ÿáëîêàìè (èãðîê 1), èñïîëüçóåò ïðóæèííûå âåñû.Ó íåãî åñòü äâå ñòðàòåãèè:1) ÷åñòíî âçâåñèòü 1 êã ÿáëîê;2) ïîäêðóòèòü ïðóæèíêó è îáâåñèòü ïîêóïàòåëÿ íà 200 ãðàìì.Íàçîâåì ýòè ñòðàòåãèè "÷åñòíîñòü"è "îáìàí"ñîîòâåòñòâåííî.Ïîêóïàòåëü òàêæå èìååò äâå ñòðàòåãèè:1) ïîâåðèâ ïðîäàâöó, çàïëàòèòü äåíüãè è óéòè;2) âçâåñèòü êóïëåííûå ÿáëîêè íà êîíòðîëüíûõ âåñàõ è â ñëó÷àå îáíàðóæåíèÿ îáìàíà çâàòü êîãî-òî è äîêàçûâàòü, ÷òî åãî îáâåñèëè.Íàçîâåì ýòè ñòðàòåãèè "ïîâåðèòü"è "ïðîâåðèòü"ñîîòâåòñòâåííî.Îïðåäåëèì âûèãðûøè ïðîäàâöà è ïîêóïàòåëÿ â êàæäîé ñèòóàöèè:à) Ïðîäàâåö ÷åñòíî âçâåñèë, à ïîêóïàòåëü åìó ïîâåðèë.

Ñîîòâåòñòâóþùèå âûèãðûøè îáîèõ, ðàâíûå 0, âûáåðåì â êà÷åñòâå íà÷àëà îòñ÷åòà.á) Ïðîäàâåö îáìàíóë, à ïîêóïàòåëü åìó ïîâåðèë. Âûèãðûø ïðîäàâöàðàâåí 1, òàê êàê îí ïîëó÷èë äîïîëíèòåëüíóþ ïðèáûëü. Âûèãðûø ïîêóïàòåëÿ ðàâåí −1, ïîñêîëüêó îí ïîëó÷èë ìåíüøå ÿáëîê.â) Ïðîäàâåö ÷åñòíî âçâåñèë, à ïîêóïàòåëü åãî ïðîâåðèë.

Âûèãðûøïðîäàâöà ðàâåí 0. Âûèãðûø ïîêóïàòåëÿ ðàâåí −1/2: îí, âî-ïåðâûõ, çðÿïîòðàòèë âðåìÿ, à, âî-âòîðûõ, ãëóïî ñåáÿ ÷óâñòâóåò.ã) Ïðîäàâåö îáìàíóë, à ïîêóïàòåëü åãî ïðîâåðèë. Âûèãðûø ïðîäàâöà ðàâåí −1, òàê êàê îáíàðóæåíèå îáìàíà ãðîçèò åìó îïðåäåëåííûìèíåïðèÿòíîñòÿìè (íàïðèìåð, åãî ìîãóò ëèøèòü ëèöåíçèè íà òîðãîâëþ íàýòîì ðûíêå). Âûèãðûø ïîêóïàòåëÿ ðàâåí 1/2, òàê êàê, âî-ïåðâûõ, åìóâîçìåñòèëè îáâåñ, à, âî-âòîðûõ, îí èñïûòûâàåò ìîðàëüíîå óäîâëåòâîðåíèå îò ðàçîáëà÷åíèÿ îáìàíùèêà.Ïîëó÷àåòñÿ ñëåäóþùàÿ áèìàòðè÷íàÿ èãðà:A=÷åñòíîáìàíïîâ01ïðîâ0,−1B=÷åñòíîáìàíïîâ0−1ïðîâ−1/2.1/2Ëåãêî ïðîâåðèòü, ÷òî çäåñü íåò ðàâíîâåñèé ïî Íýøó. ïðèâåäåííîì ïðèìåðå ýëåìåíòû ìàòðèö A è B óäîâëåòâîðÿþò ñëåäóþùèì íåðàâåíñòâàì:a11a12b11 > b12∧.∨ , a21a22b21 < b2293ÃËÀÂÀ II.

ÈÃÐÛ ÄÂÓÕ ËÈÖÓïðàæíåíèå 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.