А.А. Васин, В.В. Морозов - Введение в теорию игр с приложениями к экономике (1184512), страница 17
Текст из файла (страница 17)
Ìàòðèö� èãð� � íîðìàëüíî� ôîðì� èìåå� âè� ï(ï,ï)−a 1 (ï,ó) (−a) + 12 a 21 A =(ó,ï) ⎝ 2 a + 1 2 (−a)1(ó,ó)a + 1 2 a2⎛�⎞ −a −a −a1 0 − a+b (−a) + 12 (−b) 2 2=1 1b−a ⎠ .⎠ ⎝ 0b +(−a) 2221b + 12 (−b) a 0 2Íåòðóäí� âèäåòü, ÷ò� òðåòü� ñòðîê� ìàòðèö� äîìèíèðóå� ïåðâó� � âòîðó� ñòðîêè. Âû÷åðêèâà� è� � ðåøà� èãð� � 2×2-ìàòðèöåé, ïîëó÷è� ðåøåíè� � ñìåøàííû� ñòðàòåãèÿ� p 0 =!2a b − a 0, 0,, , q 0 =b + a b + a!b − a 2a a(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.3 X(y) = Arg max F (x, y), U = {(x, y) ∈ X × Y | x ∈ X(y)}, x∈X Y (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 ) áûë� ïîëó÷åí� Ã.Í. Øàïèð� � [100].
Ìîäèôèêàöè� óñëîâè� îñòàíîâê� ï� ìåòîä� Áðàóí� áûë� ïðåäëîæåí� Þ.Á. Ãåðìåéåðî� � [36]. � äðóãè� èãðîâû� ïðîöåññà� òèï� Áðàóíà-Ðîáèíñî� ñì. [8]. 6. Òåîðåì� 6.1 � ïåðåñå÷åíè� âûïóêëû� êîìïàêòî� åâêëèäîâ� ïðîñòðàíñòâ� áûë� îòêðûò� Ý. Õåëë� � 1913 ãîä� � ñîîáùåí� È. Ðàäîíó, îïóáëèêîâàâøåì� å� äîêàçàòåëüñòâ� � [83] êà� ñëåäñòâè� ñîáñòâåííû� ðåçóëüòàòîâ. Ãåîìåòðè÷åñêî� (� áîëå� íàãëÿäíîå) äîêàçàòåëüñòâ� ìåòîäî� ìàòåìàòè÷åñêî� èíäóêöè� ï� ðàçìåðíîñò� ïðîñòðàíñòâ� áûë� îïóáëèêîâàí� Ý.
Õåëë� � [94]. Ìíîãî÷èñëåííû� îáîáùåíè� � ïðèëîæåíè� òåîðåì� Õåëë� ñì. � [42]. Ñòðóêòóð� ðåøåíè� � ñìåøàííû� ñòðàòåãèÿ� èã� � âîãíóòûì� � âûïóêëûì� âûèãðûøàì� óñòàíîâëåí� Õ.Ô. Áîíåíáëàñòîì, Ñ. Êàðëèíî� � Ë.Ñ. Øåïë� � [12]. Ïðèâîäèìû� çäåñ� êîíñòðóêòèâíû� äîêàçàòåëüñòâ� òåîðå� 6.2 � 6.3 ïðèíàäëåæà� Ý.Ã. Äàâûäîâ� [41], êîòîðû� îïèðàëñ� í� ðåçóëüòà� 1938 ãîä� Ë.Ã. Øíèðåëüìàí� [106], ïðèäà� åì� ñîâðåìåííû� âè� � . Îñíîâ� òåîðè� ñòàòèñòè÷åñêè� ðåøåíè� áûë� çàëîæåí� À.
Âàëüäî� [21] (ñì. òàêæ� [11, 20]), ãäå, � ÷àñòíîñòè, ââåäåí� ôóíêöè� ðèñêà. � ïðèëîæåíèÿì� òåîðè� ñòàòèñòè÷åñêè� èã� ìîæí� îçíàêîìèòüñ� � [40]. Ìèíèìàêñíà� îöåíê� ïàðàìåòð� áèíîìèàëüíîã� ðàñïðåäåëåíè� ïîëó÷åí� Äæ. Õîäæåñî� � Å. Ëåìàíî� [96], � àíàëîãè÷íà� îöåíê� ìàòåìàòè÷åñêîã� îæèäàíè� íîðìàëüíîã� ðàñïðåäåëåíè� ïð� èçâåñòíî� äèñïåðñè� ïîëó÷åí� È. Âîëüôîâèöå� [33]. 7.
Ìîäåë� "íàïàäåíèå-îáîðîíà"îïðåäåëåí� � èçó÷åí� Þ.Á. Ãåðìåéåðî� [36]. Îí� ÿâëÿåòñ� ìîäèôèêàöèå� ìîäåë� Î. Ãðîññà, � êîòîðî� ôóíênPöè� âûèãðûø� íàïàäåíè� èìåå� âè� F (x, y) = ki max[xi − yi , 0], � ki i=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) . � àíòàãîíèñòè÷åñêî� èãð� ïîíÿòè� ðåøåíè� ì� ñâÿçûâàë� � ñåäëîâî� òî÷êî� ôóíêöè� âûèãðûø� ïåðâîã� èãðîêà. � ïðîèçâîëüíî� èãð� äâó� ëè� àíàëîãî� ñåäëîâî� òî÷ê� ÿâëÿåòñ� ïîíÿòè� ñèòóàöè� ðàâíîâåñèÿ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
