Введение в теорию игр (сторонняя методичка) (1184510), страница 14
Текст из файла (страница 14)
Íåòðóäíî ïîäñ÷èòàòü, ÷òî âåðîÿòíîñòèåãî âûèãðûøà ïðè ðàçìåùåíèÿõ ÌÊÊ, ÊÌÊ è ÊÊÌ ðàâíû 1/6, 1/3 è0 ñîîòâåòñòâåííî. Òàêèì îáðàçîì, äàííàÿ ÷èñòàÿ ñòðàòåãèÿ îáåñïå÷èâàåòâûèãðûø ïðèçà ñ âåðîÿòíîñòüþ 1/2. Åñëè íà âòîðîì øàãå ïåðâûé èãðîêóêàçûâàåò íå íà ïåðâóþ äâåðü, òî âûèãðûø ïðèçà (òîëüêî â ýòîì ñëó÷àå)óâåëè÷èâàåòñÿ äî 2/3.Îòìåòèì, ÷òî â ýòîì ïðèìåðå ìû îáîøëèñü áåç ïîëíîãî îïèñàíèÿìíîæåñòâ ñòðàòåãèé èãðîêîâ è ìàòðèöû èãðû. Ýòî ïðåäñòàâëÿåò ñîáîéâåñüìà íåïðîñòóþ çàäà÷ó, åñëè ðàññìîòðåòü îáîáùåíèå èãðû íà ñëó÷àé,êîãäà èìååòñÿ n äâåðåé, çà êîòîðûìè ðàñïîëàãàþòñÿ îäèí "Ìåðñåäåñ"èn − 1 êîçåë.
Èãðà ïðîèñõîäèò â òå÷åíèå n − 1 øàãîâ. Íà êàæäîì èç ïåðâûõ n − 2 øàãîâ ó÷àñòíèê ïîêàçûâàåò íà êàêóþ-ëèáî çàêðûòóþ äâåðü,à âåäóùèé îòêðûâàåò äðóãóþ äâåðü, çà êîòîðîé ñòîèò êîçåë. Íà øàãån − 1 âñå ïðîèñõîäèò òàê æå, êàê è ïðè n = 3. Çíà÷åíèå èãðû çäåñü ðàâíî(n − 1)/n. Äîêàæèòå îïòèìàëüíîñòü ñëåäóþùåé ñòðàòåãèè ïåðâîãî èãðîêà.
Ñ ðàâíîé âåðîÿòíîñòüþ 1/n îí âûáèðàåò îäíó èç äâåðåé, íà êîòîðóþïîêàçûâàåò â òå÷åíèå ïåðâûõ n − 2 øàãîâ. Íà ïîñëåäíåì (n − 1)-ì øàãå,êîãäà îñòàíóòñÿ äâå çàêðûòûå äâåðè, îí îòêðûâàåò äðóãóþ äâåðü.Ïóñòü ìíîãîøàãîâàÿ èãðà çàäàíà â ïîçèöèîííîé ôîðìå. Òîãäà èíôîðìèðîâàííîñòü èãðîêîâ çàäàåòñÿ ñ ïîìîùüþ èíôîðìàöèîííûõ ìíîæåñòâ.Îïðåäåëåíèå. Èíôîðìàöèîííûì ìíîæåñòâîì èãðîêà íàçûâàåòñÿ ìíîæåñòâî âåðøèí äåðåâà èãðû, â êîòîðûõ î÷åðåäü õîäà ïðèíàäëåæèò äàííîìó èãðîêó è èìååòñÿ îäèíàêîâîå ÷èñëî àëüòåðíàòèâ.
Èãðîê çíàåò, ÷òîïîçèöèÿ èãðû ñîîòâåòñòâóåò îäíîé èç âåðøèí èíôîðìàöèîííîãî ìíîæåñòâà, íî íå çíàåò êàêîé èìåííî. Íà èíôîðìàöèîííîå ìíîæåñòâî íàêëà84 8. Ìíîãîøàãîâûå àíòàãîíèñòè÷åñêèå èãðûäûâàåòñÿ ñëåäóþùåå îãðàíè÷åíèå: îíî íå ìîæåò ñîäåðæàòü äâóõ âåðøèíëåæàùèõ íà îäíîì ïóòè, âåäóùèì èç íà÷àëüíîé âåðøèíû â ôèíàëüíóþ.Áóäåì ñ÷èòàòü, ÷òî âñå èíôîðìàöèîííûå ìíîæåñòâà ïåðâîãî èãðîêàI1 , ..., Ik ïðîíóìåðîâàíû òàêèì îáðàçîì, ÷òî åñëè êàêàÿ-òî âåðøèíà ìíîæåñòâà Ii ðåàëèçóåòñÿ â èãðå ðàíüøå íåêîòîðîé âåðøèíû ìíîæåñòâà Ij ,òî i < j. Âñå èíôîðìàöèîííûå ìíîæåñòâà âòîðîãî èãðîêà J1 , ..., Jl ïðîíóìåðîâàíû àíàëîãè÷íûì îáðàçîì.Ñòðàòåãèåé ïåðâîãî èãðîêà ÿâëÿåòñÿ âåêòîð x = (x1 , ..., xk ) ∈ X, ãäå xi− ëèáî àëüòåðíàòèâà, âûáèðàåìàÿ èãðîêîì â ìíîæåñòâå Ii , ëèáî xi = ∗.Ïîñëåäíåå îçíà÷àåò, ÷òî âûáîð àëüòåðíàòèâ x1 , ..., xi−1 ãàðàíòèðóåò, ÷òîâ èãðå çàâåäîìî íå áóäåò ðåàëèçîâàíà íèêàêàÿ âåðøèíà èç ìíîæåñòâàIi .
Àíàëîãè÷íûì îáðàçîì îïðåäåëÿþòñÿ ñòðàòåãèè y = (y1 , ..., yl ) ∈ Yâòîðîãî èãðîêà.Îòìåòèì, ÷òî â èãðå ìîãóò âñòðå÷àòüñÿ ïîçèöèè ñëó÷àÿ. Ýòî îçíà÷àåò, ÷òî â íåêîòîðûõ âåðøèíàõ äåðåâà èãðû âûáîð àëüòåðíàòèâû íåïðèíàäëåæèò èãðîêàì, à îñóùåñòâëÿåòñÿ ñëó÷àéíûì îáðàçîì ñ èçâåñòíûì çàêîíîì ðàñïðåäåëåíèÿ (ñì. ïðèìåð íèæå). Òîãäà ïðè âûáðàííûõñòðàòåãèÿõ èãðîêîâ x è y âûèãðûø ïåðâîãî èãðîêà, îïðåäåëÿåìûé ïîôèíàëüíîé âåðøèíå, áóäåò ñëó÷àéíîé âåëè÷èíîé è çíà÷åíèå F (x, y) ñëåäóåò îïðåäåëèòü êàê ìàòåìàòè÷åñêîå îæèäàíèå ýòîãî âûèãðûøà.
Òàêèìîáðàçîì, ìû ñâåëè ïîçèöèîííóþ ôîðìó èãðû ê íîðìàëüíîé ôîðìå.Ïðèìåð 8.6. Èãðà "ïîêåð". Êîëîäà ñîñòîèò èç äâóõ êàðò: ñòàðøåé (ñ) èìëàäøåé (ì). Èãðîêàì ñäàåòñÿ ïî îäíîé êàðòå ðóáàøêîé ââåðõ. Ïåðâûéèãðîê áåðåò ñâîþ êàðòó è èìååò äâå àëüòåðíàòèâû: ëèáî ïàñîâàòü (ï),âûïëà÷èâàÿ âòîðîìó èãðîêó ñóììó a > 0, ëèáî óâåëè÷èâàòü ñòàâêó (ó)äî ñóììû b > a. Åñëè ïåðâûé èãðîê óâåëè÷èâàåò, òî âòîðîé èãðîê, íåçíàÿ ðàñêëàäà êàðò, ìîæåò ëèáî ïàñîâàòü, âûïëà÷èâàÿ ïåðâîìó a, ëèáîóâåëè÷èâàòü ñòàâêó äî b. Åñëè îáà èãðîêà óâåëè÷èâàþò ñòàâêó, òî êàðòûîòêðûâàþòñÿ è èãðîê ñî ñòàðøåé êàðòîé ïîëó÷àåò ñóììó b îò ïàðòíåðà.Íà ðèñ. 8.2 èçîáðàæåíî äåðåâî èãðû.85ÃËÀÂÀ I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛb@ñI1ïb@ ì@@ I2@bbï−ab−aób@ï@bbb@ó@@bba−bó@baóJ1ïÐèñ. 8.2Ïåðâûé èãðîê èìååò äâà èíôîðìàöèîííûõ ìíîæåñòâà, îòâå÷àþùèõäâóì ðàâíîâåðîÿòíûì ðàñêëàäàì êàðò.
Ïîýòîìó ó ïåðâîãî èãðîêà ÷åòûðåñòðàòåãèè: (ï,ï),(ï,ó),(ó,ï),(ó,ó). Âòîðîé èãðîê íå çíàåò ðàñêëàäà êàðò. Îíèìååò åäèíñòâåííîå èíôîðìàöèîííîå ìíîæåñòâî è äâå ñòðàòåãèè: ï è ó.Ìàòðèöà èãðû â íîðìàëüíîé ôîðìå èìååò âèäï(ï,ï)−a1(ï,ó) (−a)+ 12 a 12A=(ó,ï) 2 a + 12 (−a)1(ó,ó)a + 12 a2ó −a −a−a1 0 − a+b (−a) + 12 (−b) 2 2=11b−a . 0b+(−a)2221b + 12 (−b)a02Íåòðóäíî âèäåòü, ÷òî òðåòüÿ ñòðîêà ìàòðèöû äîìèíèðóåò ïåðâóþ è âòîðóþ ñòðîêè. Âû÷åðêèâàÿ èõ è ðåøàÿ èãðó ñ 2×2-ìàòðèöåé, ïîëó÷èì ðåøåíèå â ñìåøàííûõ ñòðàòåãèÿõp0 =!2a b − a0, 0,,, q0 =b+a b+a!b − a 2aa(b − a),, v=.b+a b+ab+aÌîæíî ñäåëàòü âûâîä, ÷òî ÷åì áîëüøå çíà÷åíèå b/a, òåì ñ áîëüøåé âåðîÿòíîñòüþ ïåðâûé èãðîê äîëæåí áëåôîâàòü (óâåëè÷èâàòü íà ìëàäøåéêàðòå), à âòîðîé − åìó íå âåðèòü (ïàñîâàòü).86 8.
Ìíîãîøàãîâûå àíòàãîíèñòè÷åñêèå èãðûÊîììåíòàðèé è áèáëèîãðàôèÿ ê ãëàâå I 2. Îñíîâíûå ïîíÿòèÿ òåîðèè àíòàãîíèñòè÷åñêèõ èãð áûëè ââåäåíûÝ.Áîðåëåì (ñì. àíãëèéñêèé ïåðåâîä [15] òðåõ åãî ðàáîò 1920-õ ãîäîâ).Òåðìèí "ôèçè÷åñêàÿ ñìåñü ñòðàòåãèé"èñïîëüçîâàëà Å.Ñ. Âåíòöåëü â [29].Ïðèìåð 3.2 âçÿò èç êíèãè Ã.Í. Äþáèíà è Â.Ã.
Ñóçäàëÿ [46]. Åùå îäèíïðèìåð 9.7 èñïîëüçîâàíèÿ "ôèçè÷åñêîé ñìåñè ñòðàòåãèé"â áèìàòðè÷íîéèãðå ñì. âî âòîðîé ãëàâå. Îñíîâû òåîðèè ïîëåçíîñòè çàëîæåíû â ôóíäàìåíòàëüíîì òðóäå Äæ. ôîí Íåéìàíà è Î. Ìîðãåíøòåðíà [72]. Î ìåòîäàõïîñòðîåíèÿ ôóíêöèé ïîëåçíîñòè ñì. [49].Èíòåðåñíî ïðîàíàëèçèðîâàòü ïîâåäåíèå ïåðâîãî èãðîêà, èñïîëüçóþùåãî îïòèìàëüíóþ ñìåøàííóþ(a/(1 + a), 1/(1 + a)) â èãðå ñ ñòðàòåãèþ1 0ìàòðèöåé ïîëåçíîñòåé A =ïðèìåðà 3.4, â çàâèñèìîñòè îò åãî0 aîòíîøåíèÿ ê ðèñêó.
×åì áîëåå îñòîðîæåí èãðîê (ñ ðîñòîì ïîëåçíîñòè a),òåì áëèæå åãî ñòðàòåãèÿ ê (1/2, 1/2). Àçàðòíûé èãðîê âûáèðàåò ÷èñòóþâòîðóþ ñòðàòåãèþ ñ òåì áîëüøåé âåðîÿòíîñòüþ, ÷åì ìåíüøå çíà÷åíèå a.Ñõîäíîå ïîâåäåíèå ìû íàáëþäàëè ó ìèëèöèîíåðà â ïðèìåðå 4.4.Òåîðåìà 2.1 äîêàçàíà â êíèãå Äæ. ôîí Íåéìàíà è Î. Ìîðãåíøòåðíà [72]. Òåîðåìà 2.2 ïîëó÷åíà Ì. Øèôìàíîì [104] â õîäå äîêàçàòåëüñòâàòåîðåìû 2.3.
Ïðèìåð 2.5 áûë ñîîáùåí àâòîðó Ñ.À. Àøìàíîâûì. Àíàëîãè÷íûé ïðèìåð ñì. â [6] (ñ.237). Òåîðåìà 2.3 äîêàçàíà Ñ. Êàêóòàíè [47]ñ èñïîëüçîâàíèåì îáîáùåíèÿ òåîðåìû Ë. Áðàóýðà î íåïîäâèæíîé òî÷êå.Îäíàêî îíà âûòåêàåò èç ïîëó÷åííîãî ÷åòûðüìÿ ãîäàìè ðàíüøå ñëåäóþùåãî ðåçóëüòàòà [74].Òåîðåìà (Äæ. ôîí Íåéìàí). Ïóñòü X ⊂ E m è Y ⊂ E n − âûïóêëûå êîìïàêòû åâêëèäîâûõ ïðîñòðàíñòâ, à êîìïàêòû U, V ⊂ X × Yóäîâëåòâîðÿþò ñëåäóþùåìó óñëîâèþ: äëÿ ëþáûõ x ∈ X è y ∈ Y ìíîæåñòâà Y (x) = {y ∈ Y | (x, y) ∈ V } è X(y) = {x ∈ X | (x, y) ∈ U } ÿâëÿþòñÿíåïóñòûìè âûïóêëûìè êîìïàêòàìè. Òîãäà U ∩ V 6= ∅.Äåéñòâèòåëüíî, ïîëàãàÿ â óñëîâèÿõ òåîðåìû 2.3X(y) = Arg max F (x, y), U = {(x, y) ∈ X × Y | x ∈ X(y)},x∈XY (x) = Arg min F (x, y), V = {(x, y) ∈ X × Y | y ∈ Y (x)},y∈Yïîëó÷èì, ÷òî ñóùåñòâóåò ïàðà (x0 , y 0 ) ∈ U ∩ V − ñåäëîâàÿ òî÷êà ôóíêöèè F (x, y).
Ïîýòîìó òåîðåìó 2.3 îáû÷íî ñâÿçûâàþò ñ èìåíåì Äæ. ôîíÍåéìàíà.87ÃËÀÂÀ I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛÄîêàçàòåëüñòâà Ñ. Êàêóòàíè è Ì. Øèôìàíà òåîðåìû 2.3 ìîæíî ïðî÷åñòü â êíèãå Ñ. Êàðëèíà [48]. 3. Ñ òåîðèåé èíòåãðàëà Ñòèëòüåñà ìîæíî îçíàêîìèòüñÿ ïî ó÷åáíèêóÀ.Í. Êîëìîãîðîâà è Ñ.Â. Ôîìèíà [50]. Îñíîâíàÿ òåîðåìà ìàòðè÷íûõ èãð(òåîðåìà 3.1) áûëà äîêàçàíà Äæ.ôîí Íåéìàíîì â 1928 ãîäó [73] ìåòîäîììàòåìàòè÷åñêîé èíäóêöèè ïî ðàçìåðàì ìàòðèöû èãðû.
Ðàíåå Ý. Áîðåëü[15] ïðîäåìîíñòðèðîâàë åå ñïðàâåäëèâîñòü äëÿ êîñîñèììåòðè÷åñêîé 3×3ìàòðèöû. Ïðèâåäåííîå äîêàçàòåëüñòâî òåîðåìû 3.1 ïðèíàäëåæèò Ñ. Êàêóòàíè [47]. Òåîðåìà 3.2 îáúåäèíÿåò äâå òåîðåìû Ý. Õåëëè ([50]). Îñíîâíàÿ òåîðåìà íåïðåðûâíûõ èãð (òåîðåìà 3.3) áûëà äîêàçàíà Æ. Âèëëåì[30]. 4. Ñâîéñòâà ðåøåíèé â ñìåøàííûõ ñòðàòåãèÿõ ìàòðè÷íûõ è íåïðåðûâíûõ èãð èçëàãàþòñÿ â áîëüøèíñòâå êíèã ïî òåîðèè èãð (ñì., íàïðèìåð, [45, 63]).
Ïðèìåð 4.2 ïðèíàäëåæèò Ý. Áîðåëþ [16]. Îí òàêæå ðàññìàòðèâàë äèñêðåòíûé âàðèàíò èãðû ñ A = 7, êîòîðîìó äàë ñëåäóþùóþèíòåðïðåòàöèþ. Èãðîêè íàáèðàþò ïî ñåìü êàðò. Êàæäàÿ êàðòà ìîæåòáûòü îäíîé èç òðåõ ìàñòåé (ñîäåðæàùèõ ïî 14 êàðò): òðåôû, áóáíû èëè÷åðâû. Ïåðâûé èãðîê ïîáåæäàåò, åñëè â êàæäîé èç êàêèõ-ëèáî äâóõ ìàñòåé îí èìååò áîëüøå êàðò, ÷åì ïðîòèâíèê. Î äðóãèõ ðåøåíèÿõ ýòîé èãðûñì. [78].Âûðàâíèâàþùèå ñòðàòåãèè âïåðâûå èñïîëüçîâàë Ý. Áîðåëü [15] äëÿäîêàçàòåëüñòâà ñóùåñòâîâàíèÿ ðåøåíèÿ â ñìåøàííûõ ñòðàòåãèÿõ èãðû ñêîñîñèììåòðè÷åñêîé 3×3-ìàòðèöåé. Èãðû ñ äèàãîíàëüíûìè è öèêëè÷åñêèìè ìàòðèöàìè, à òàêæå íåêîòîðûå èõ îáîáùåíèÿ ñì. â [48]. 5.
Ïîíÿòèÿ äîìèíèðîâàíèÿ ñòðîê è ñòîëáöîâ â ìàòðè÷íûõ èãðàõèñïîëüçîâàëèñü ìíîãèìè àâòîðàìè.  ôîðìå òåîðåì îíè, ïî-âèäèìîìó,âïåðâûå áûëè ñôîðìóëèðîâàíû Ì. Äðåøåðîì â 1951 ãîäó â îò÷åòå êîðïîðàöèè ÐÝÍÄ (ñì. åãî êíèãó [45]). Ãðàôè÷åñêèé ìåòîä ðåøåíèÿ èãð ñ2 × 2-ìàòðèöàìè èñïîëüçîâàë åùå Ý. Áîðåëü.
Áîëåå îáùèé ìåòîä "äâîéíîãî îïèñàíèÿ"ñì. â ðàáîòå [70]. Ýêâèâàëåíòíîñòü ðåøåíèÿ ìàòðè÷íîéèãðû çàäà÷å ëèíåéíîãî ïðîãðàììèðîâàíèÿ áûëà ïðîäåìîíñòðèðîâàíà Ã.Äàíöèãîì [43]. Òåîðåìà 5.2 î êðàéíèõ îïòèìàëüíûõ ñìåøàííûõ ñòðàòåãèÿõ äîêàçàíà Ë.Ñ. Øåïëè è Ð. Ñíîó [101].Èòåðàöèîííûé ìåòîä ðåøåíèÿ ìàòðè÷íîé èãðû áûë ñôîðìóëèðîâàíÃ. Áðàóíîì â [17]. Ñõîäèìîñòü ïðîöåññà Áðàóíà äîêàçàíà Äæóëèåé Ðîáèíñîí [84]. Îíà èñïîëüçîâàëà áîëåå îáùèé èòåðàöèîííûé ïðîöåññ ñ íåíóëåâûìè íà÷àëüíûìè âåêòîðàìè c(0) è d(0), íàçûâàåìûé â ëèòåðàòóðå88 8. Ìíîãîøàãîâûå àíòàãîíèñòè÷åñêèå èãðû1ïðîöåññîì Áðàóíà-Ðîáèíñîí. Îöåíêà ñêîðîñòè ñõîäèìîñòè O(k − m+n−2 )áûëà ïîëó÷åíà Ã.Í.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
