Введение в теорию игр (сторонняя методичка) (1184510), страница 15
Текст из файла (страница 15)
Øàïèðî â [100]. Ìîäèôèêàöèÿ óñëîâèÿ îñòàíîâêèïî ìåòîäó Áðàóíà áûëà ïðåäëîæåíà Þ.Á. Ãåðìåéåðîì â [36]. Î äðóãèõèãðîâûõ ïðîöåññàõ òèïà Áðàóíà-Ðîáèíñîí ñì. [8]. 6. Òåîðåìà 6.1 î ïåðåñå÷åíèè âûïóêëûõ êîìïàêòîâ åâêëèäîâà ïðîñòðàíñòâà áûëà îòêðûòà Ý. Õåëëè â 1913 ãîäó è ñîîáùåíà È. Ðàäîíó,îïóáëèêîâàâøåìó åå äîêàçàòåëüñòâî â [83] êàê ñëåäñòâèå ñîáñòâåííûõ ðåçóëüòàòîâ.
Ãåîìåòðè÷åñêîå (è áîëåå íàãëÿäíîå) äîêàçàòåëüñòâî ìåòîäîììàòåìàòè÷åñêîé èíäóêöèè ïî ðàçìåðíîñòè ïðîñòðàíñòâà áûëî îïóáëèêîâàíî Ý. Õåëëè â [94]. Ìíîãî÷èñëåííûå îáîáùåíèÿ è ïðèëîæåíèÿ òåîðåìûÕåëëè ñì. â [42].Ñòðóêòóðà ðåøåíèé â ñìåøàííûõ ñòðàòåãèÿõ èãð ñ âîãíóòûìè è âûïóêëûìè âûèãðûøàìè óñòàíîâëåíà Õ.Ô. Áîíåíáëàñòîì, Ñ. Êàðëèíîì èË.Ñ. Øåïëè â [12]. Ïðèâîäèìûå çäåñü êîíñòðóêòèâíûå äîêàçàòåëüñòâàòåîðåì 6.2 è 6.3 ïðèíàäëåæàò Ý.Ã.
Äàâûäîâó [41], êîòîðûé îïèðàëñÿ íàðåçóëüòàò 1938 ãîäà Ë.Ã. Øíèðåëüìàíà [106], ïðèäàâ åìó ñîâðåìåííûéâèä 1 .Îñíîâû òåîðèè ñòàòèñòè÷åñêèõ ðåøåíèé áûëè çàëîæåíû À. Âàëüäîì[21] (ñì. òàêæå [11, 20]), ãäå, â ÷àñòíîñòè, ââåäåíà ôóíêöèÿ ðèñêà. Ñïðèëîæåíèÿìè òåîðèè ñòàòèñòè÷åñêèõ èãð ìîæíî îçíàêîìèòüñÿ â [40].Ìèíèìàêñíàÿ îöåíêà ïàðàìåòðà áèíîìèàëüíîãî ðàñïðåäåëåíèÿ ïîëó÷åíà Äæ. Õîäæåñîì è Å. Ëåìàíîì [96], à àíàëîãè÷íàÿ îöåíêà ìàòåìàòè÷åñêîãî îæèäàíèÿ íîðìàëüíîãî ðàñïðåäåëåíèÿ ïðè èçâåñòíîé äèñïåðñèèïîëó÷åíà È. Âîëüôîâèöåì [33]. 7. Ìîäåëü "íàïàäåíèå-îáîðîíà"îïðåäåëåíà è èçó÷åíà Þ.Á. Ãåðìåéåðîì [36].
Îíà ÿâëÿåòñÿ ìîäèôèêàöèåé ìîäåëè Î. Ãðîññà, â êîòîðîé ôóíênPöèÿ âûèãðûøà íàïàäåíèÿ èìååò âèä F (x, y) =ki max[xi − yi , 0], à kii=1èíòåðïðåòèðóþòñÿ êàê êîýôôèöèåíòû âàæíîñòè ïóíêòîâ. Â.À. Ãîðåëèêïðåäëîæèë ñõîäíóþ èãðîâóþ ìîäåëü ïðîèçâîäñòâà áåíçèíà [39].Ïðèâîäèìûå çäåñü øóìíàÿ è áåñøóìíàÿ ìîäåëè äóýëåé èññëåäîâàíûÞ.Á. Ãåðìåéåðîì [36].
 êëàññè÷åñêèõ ìîäåëÿõ [48] F (x, y) ïîëó÷àåòñÿîñðåäíåíèåì ôóíêöèè, ïðèíèìàþùåé çíà÷åíèå 1, åñëè óáèò âòîðîé äóýëÿíò, à ïåðâûé îñòàëñÿ æèâ, çíà÷åíèå −1, åñëè óáèò ïåðâûé äóýëÿíò,à âòîðîé îñòàëñÿ æèâ è çíà÷åíèå 0 â îñòàëüíûõ ñëó÷àÿõ (îáà äóýëÿíòà1 Øíèðåëüìàíäîêàçàë òåîðåìó 6.2 â òåðìèíàõ âûïóêëûõ ìíîæåñòâ, íå èñïîëüçóÿïîíÿòèå âîãíóòîé ôóíêöèè.89ÃËÀÂÀ I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛæèâû èëè îáà óáèòû). Ìåòîäû ðåøåíèÿ èãð ñ âûáîðîì ìîìåíòà âðåìåíè (äóýëüíîãî òèïà), îñíîâàííûå íà èñïîëüçîâàíèè èíòåãðàëüíûõ èäèôôåðåíöèàëüíûõ óðàâíåíèé, ñì. â [9, 48]. 8. Òåîðåìà ñóùåñòâîâàíèÿ ðåøåíèÿ ìíîãîøàãîâîé èãðû ñ ïîëíîé èíôîðìàöèåé ñ öåëüþ ïðèìåíåíèÿ ê øàõìàòíîé èãðå äîêàçàíà Ý.Öåðìåëîâ 1912 ãîäó [97].
Îñíîâíûå ïîíÿòèÿ òåîðèè ïîçèöèîííûõ èãð îïðåäåëåíûÄæ. ôîí Íåéìàíîì è Î. Ìîðãåíøòåðíîì â [72]. Ïîëíàÿ ôîðìàëèçàöèÿýòèõ èãð ïðîâåäåíà Ã.Ó. Êóíîì [58]. Ïðèìåð 8.5 áûë ñîîáùåí àâòîðóÍ.Ì. Íîâèêîâîé. Ïðèìåð 8.6 ïðîñòåéøåé ìîäåëè ïîêåðà ïðèíàäëåæèòÝ. Áîðåëþ [16].90ÃËÀÂÀ II. ÈÃÐÛ ÄÂÓÕ ËÈÖ 9.Ñèòóàöèè ðàâíîâåñèÿ â èãðàõ äâóõ ëèöÏîíÿòèå àíòàãîíèñòè÷åñêîé èãðû ìîæíî çíà÷èòåëüíî ðàñøèðèòü. Âèãðå äâóõ ëèö èíòåðåñû èãðîêîâ íåîáÿçàòåëüíî áûâàþò ïðîòèâîïîëîæíûìè. Ðàññìàòðèâàþò è èãðû ìíîãèõ ëèö. Èì ïîñâÿùåíà òðåòüÿ ãëàâà.Îïðåäåëèì èãðó äâóõ ëèö.
Ïóñòü ïåðâûé èãðîê èìååò â ñâîåì ðàñïîðÿæåíèè ñòðàòåãèè x èç ìíîæåñòâà ñòðàòåãèé X, à âòîðîé èãðîê −ñòðàòåãèè y èç ìíîæåñòâà ñòðàòåãèé Y. Áóäåì ðàññìàòðèâàòü èãðó â íîðìàëüíîé ôîðìå. Ýòî îçíà÷àåò, ÷òî êàæäûé èç èãðîêîâ âûáèðàåò ñòðàòåãèþ, íå çíàÿ âûáîðà ïàðòíåðà. Ïàðó ñòðàòåãèé (x, y) áóäåì íàçûâàòüñèòóàöèåé. Ó ïåðâîãî èãðîêà èìååòñÿ ôóíêöèÿ âûèãðûøà F (x, y), à óâòîðîãî − ôóíêöèÿ âûèãðûøà G(x, y), îïðåäåëåííûå íà ìíîæåñòâå âñåõñèòóàöèé X × Y. Êàæäûé èãðîê ñòðåìèòñÿ, ïî âîçìîæíîñòè, ìàêñèìèçèðîâàòü ñâîþ ôóíêöèþ âûèãðûøà.
Òàêèì îáðàçîì, èãðà äâóõ ëèö âíîðìàëüíîé ôîðìå çàäàåòñÿ íàáîðîì Γ = X, Y, F (x, y), G(x, y) . àíòàãîíèñòè÷åñêîé èãðå ïîíÿòèå ðåøåíèÿ ìû ñâÿçûâàëè ñ ñåäëîâîéòî÷êîé ôóíêöèè âûèãðûøà ïåðâîãî èãðîêà.  ïðîèçâîëüíîé èãðå äâóõëèö àíàëîãîì ñåäëîâîé òî÷êè ÿâëÿåòñÿ ïîíÿòèå ñèòóàöèè ðàâíîâåñèÿ.Îïðåäåëåíèå. Ñèòóàöèÿ (x0 , y 0 ) íàçûâàåòñÿ ñèòóàöèåé ðàâíîâåñèÿ (ðàâíîâåñèåì ïî Íýøó) èãðû Γ, åñëèmax F (x, y 0 ) = F (x0 , y 0 ), max G(x0 , y) = G(x0 , y 0 ).x∈Xy∈YÑòðàòåãèè x0 è y 0 , ñîñòàâëÿþùèå ñèòóàöèþ ðàâíîâåñèÿ, áóäåì íàçûâàòüðàâíîâåñíûìè. Åñëè îáà èãðîêà ïðèäåðæèâàþòñÿ ñèòóàöèè ðàâíîâåñèÿ,òî îäíîìó èãðîêó îò íåå íåâûãîäíî îòêëîíÿòüñÿ.Óïðàæíåíèå 9.1.
Åñëè F (x, y) ≡ −G(x, y), òî èãðà Γ − àíòàãîíèñòè÷åñêàÿ. Äîêàæèòå, ÷òî â àíòàãîíèñòè÷åñêîé èãðå ñèòóàöèè ðàâíîâåñèÿ −ýòî ñåäëîâûå òî÷êè ôóíêöèè F (x, y) íà X × Y.Îáñóäèì, êàê ìîæíî èñïîëüçîâàòü ïîíÿòèå ðàâíîâåñèÿ ïî Íýøó ñ òî÷êè çðåíèÿ ïðèíÿòèÿ ðåøåíèé.  òåîðèè èãð, êàê è âî ìíîãèõ äðóãèõòåîðèÿõ, ìîæíî âûäåëèòü äâà ïîäõîäà: íîðìàòèâíûé è ïîçèòèâíûé.Íîðìàòèâíûé ïîäõîä ñîñòîèò â òîì, ÷òî òåîðèÿ äàåò ðåêîìåíäàöèè, êàêñëåäóåò äåéñòâîâàòü â òîé èëè èíîé êîíôëèêòíîé ñèòóàöèè. À ïðè ïîçèòèâíîì ïîäõîäå òåîðèÿ ïûòàåòñÿ îïèñàòü, êàê íà ñàìîì äåëå ïðîèñõîäèò91ÃËÀÂÀ II. ÈÃÐÛ ÄÂÓÕ ËÈÖâçàèìîäåéñòâèå ìåæäó èãðîêàìè.
Èçíà÷àëüíî òåîðèÿ èãð ðàçâèâàëàñüêàê íîðìàòèâíàÿ. È ñåé÷àñ ìû îáñóäèì ïîíÿòèå ðàâíîâåñèÿ ïî Íýøóèìåííî ñ òàêîé òî÷êè çðåíèÿ.  ýòîì ñëó÷àå ïðàâèëî ïðèíÿòèÿ ðåøåíèÿìîæíî ñôîðìóëèðîâàòü ñëåäóþùèì îáðàçîì: â êîíôëèêòíîé ñèòóàöèè,îïèñûâàåìîé èãðîé â íîðìàëüíîé ôîðìå, êàæäîìó ó÷àñòíèêó ñëåäóåòèñïîëüçîâàòü ñòðàòåãèþ, êîòîðàÿ âõîäèò â ðàâíîâåñèå ïî Íýøó. Ïîçèòèâíûé ïîäõîä îáñóæäàåòñÿ â êîíöå 10.Ñèòóàöèÿ ðàâíîâåñèÿ â ïðîèçâîëüíîé èãðå äâóõ ëèö ìîæåò íå îáëàäàòü òåìè ñâîéñòâàìè, êîòîðûå õàðàêòåðíû äëÿ ñåäëîâîé òî÷êè àíòàãîíèñòè÷åñêîé èãðû. àíòàãîíèñòè÷åñêîé èãðå, èìåþùåé ðåøåíèå, êîìïîíåíòû ñåäëîâîéòî÷êè ÿâëÿþòñÿ ìàêñèìèííîé è ìèíèìàêñíîé ñòðàòåãèÿìè èãðîêîâ è,íàîáîðîò, ëþáàÿ ïàðà òàêèõ ñòðàòåãèé îáðàçóåò ñåäëîâóþ òî÷êó. Òàêèìîáðàçîì, â àíòàãîíèñòè÷åñêîé èãðå ïðèíöèï ðàâíîâåñèÿ ñîãëàñóåòñÿ ñïðèíöèïîì îïòèìèçàöèè èãðîêàìè ñâîèõ ãàðàíòèðîâàííûõ ðåçóëüòàòîâ.Êðîìå òîãî, âî âñåõ ñåäëîâûõ òî÷êàõ âûèãðûø ïåðâîãî èãðîêà îäèí èòîò æå è ðàâåí çíà÷åíèþ èãðû.
Ê ñîæàëåíèþ, â îáùåì ñëó÷àå ñèòóàöèèðàâíîâåñèÿ íå îáëàäàþò óêàçàííûìè ñâîéñòâàìè. Óáåäèìñÿ â ýòîì íàïðèìåðàõ. Ïðåäâàðèòåëüíî ââåäåì ïîíÿòèå áèìàòðè÷íîé èãðû.Îïðåäåëåíèå. Èãðà äâóõ ëèö Γ íàçûâàåòñÿ áèìàòðè÷íîé, åñëè ìíîæåñòâà ñòðàòåãèé èãðîêîâ êîíå÷íû: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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
