А.А. Васин, В.В. Морозов - Введение в теорию игр с приложениями к экономике (1184512), страница 16
Текст из файла (страница 16)
y. ˜ Èòàê, îïðåäåëåí� èãð� Γ = X, Ïðèìå� 8.3. Ïóñò� αt = βt = (xt−1 , y t−1 ), Ht 1 (αt ) = {αt }, Ht 2 (βt ) = {(xt , y t−1 ) | xt ∈ Ut (βt )}. Çäåñ� í� êàæäî� òåêóùå� øàã� èãðîê� í� çíàþ� âûáîð� äðó� äðóãà, í� îí� çíàþ� âñ� âûáîðû, ñäåëàííû� í� ïðåäûäóùè� øàãàõ. Ïð� ýòî� áóäå� ãîâîðèò� î� èãð� � ïîëíî� èíôîðìàöèå� � ïðåäûäóùè� øàãàõ. Êîíêðåòíû� ïðèìåðî� ìîæå� ñëóæèò� ïîâòîðÿþùàÿñ� èãð� "îðëÿíêà".
Óïðàæíåíè� 8.1. Ïîêàçàòü, ÷ò� � èãð� Γ � ïîëíî� èíôîðìàöèå� � ïðåäûäóùè� øàãà� (ïðèìå� 8.3) íèæíå� � âåðõíå� çíà÷åíè� èãð� çàäàþòñ� ñëåäóþùèì� âûðàæåíèÿìè: v = max min max min · · · v = min max min max · · · x1 ∈U1 y1 ∈V1 x2 ∈U2 (x1 ,y1 ) y2 ∈V2 (x1 ,y1 ) y1 ∈V1 x1 ∈U1 y2 ∈V2 (x1 ,y1 ) x2 ∈U2 (x1 ,y1 ) max min F (xT , y T ), min max F (xT , y T ).
xT ∈UT (αT ) yT ∈VT (βT ) yT ∈VT (βT ) xT ∈UT (αT ) Óïðàæíåíè� 8.2. Íàéò� âåðõíå� � íèæíå� çíà÷åíè� èãð� è� ïðèìåð� 8.2, ïðåäïîëàãà� ïîëíó� èíôîðìèðîâàííîñò� èãðîêî� � ïðåäûäóùè� øàãàõ. Åñë� � èãð� Γ v < v, ò� èãðîê� äîëæí� èñïîëüçîâàò� ñìåøàííû� ñòðàòåãèè. Îãðàíè÷èìñ� ïðèìåðàìè. Ïðèìå� 8.4.
Íàéäå� ðåøåíè� � ñìåøàííû� ñòðàòåãèÿ� èãð� è� ïðèìåð� 8.2, ïðåäïîëàãà� ïîëíó� èíôîðìèðîâàííîñò� èãðîêî� � ïðåäûäóùè� øàãàõ. Í� âòîðî� øàã� çíà÷åíè� α, β èãðîêà� èçâåñòí� � âîçíèêàå� ïîäûãð� � 2×2-ïîäìàòðèöå� (aij )i∈Mα j∈Nβ ìàòðèö� A. Ïóñò� (p0 (α, β), q 0 (α, β), v(α, β)) − ðåøåíè� � ñìåøàííû� ñòðàòåãèÿ� óêàçàííî� ïîäûãðû. � ñëåäóþùå� òàáëèö� ýò� ðåøåíè� ïðèâåäåí� ïð� âñå� çíà÷åíèÿ� α � β. 82 8. Ìíîãîøàãîâû� àíòàãîíèñòè÷åñêè� èãð�Òàáë. 8.1α 1 1 2 2 β 1 2 1 2 p0 (α, β) (5/7,2/7) (2/5,3/5) (1,0) (1,0) q 0 (α, β) (4/7,3/7) (4/5,1/5) (0,1) (1,0) v(α, β) 29/7 8/5 2 3 Í� ïåðâî� øàã� ïåðâû� èãðî� ñòðåìèòñ� óâåëè÷èò� ñâî� îæèäàåìû� âûèãðûø, ïîëó÷àåìû� í� âòîðî� øàãå, � âòîðî� èãðî� ñòðåìèòñ� ýòî� âûèãðû� óìåíüøèòü.
Ïîýòîì� í� ïåðâî� øàã� èãðîê� ó÷àñòâóþ� � èãð� � ìàòðèöå� � 29/7 8/5 (v(α, β))2×2 = . 23 Ðåøåíè� ýòî� èãð� � ñìåøàííû� ñòðàòåãèÿ� èìåå� âè� (p 0 , q 0 , v) = ((35/124, 89/124), (49/124, 75/124), 323/124). Èòàê, ïåðâû� èãðî� äîëæå� âûáèðàò� α = 1 � âåðîÿòíîñòü� 35/124, � âòîðî� èãðî� äîëæå� âûáèðàò� β = 1 � âåðîÿòíîñòü� 49/124.
Çíà÷åíè� èãð� Γ ðàâí� 323/124. Ïðèìå� 8.5. Âåäóùè� òåëåâèçèîííîã� øî� ïðåäëàãàå� ó÷àñòíèê� ïîêàçàò� í� îäí� è� òðå� çàêðûòû� äâåðåé, ç� êîòîðûì� ðàçìåùåí� "Ìåðñåäåñ"� äâ� êîçëà. Ïîñë� ýòîã� âåäóùè� îòêðûâàå� êàêóþ-ëèá� è� äâó� íåâûáðàííû� äâåðåé, ç� êîòîðî� íàõîäèòñ� êîçåë, � âòîðè÷í� (øà� 2) ïðåäëàãàå� ó÷àñòíèê� îòêðûò� îäí� è� îñòàâøèõñ� äâåðåé. Åñë� ç� äâåðü� ñòîè� "Ìåðñåäåñ", ò� ó÷àñòíè� ïîëó÷àå� åã� � êà÷åñòâ� ïðèçà, åñë� −êîçåë, ò� ó÷àñòíè� íè÷åã� í� ïîëó÷àåò.
Ïóñò� âûèãðû� ó÷àñòíèê� ðàâå� 1 èë� 0 � çàâèñèìîñò� î� òîãî, ïîëó÷å� è� ïðè� èë� íåò. Íàéäå� îïòèìàëüíû� ñòðàòåãè� ó÷àñòíèê� (ïåðâîã� èãðîêà) � âåäóùåã� øî� (âòîðîã� èãðîêà), � òàêæ� çíà÷åíè� èãðû. Åñë� í� ïåðâî� øàã� ïåðâû� èãðî� ïîêàçà� í� äâåðü, ç� êîòîðî� ñòîè� êîçåë, ò� ÿñíî, ÷ò� í� âòîðî� øàã� î� äîëæå� îòêðûò� äðóãó� äâåð� � íàâåðíÿê� ïîëó÷èò� ïðèç. Îòñþäà, èñïîëüçó� ñîîáðàæåíè� ñèììåòðèè, óêàæå� îïòèìàëüíû� ñìåøàííû� ñòðàòåãè� èãðîêîâ. Îïðåäåëè� ñòðàòåãè� p0 ïåðâîã� èãðîêà: í� ïåðâî� øàã� î� äîëæå� âûáðàò� îäí� è� òðå� äâåðå� � âåðîÿòíîñòü� 1/3, � í� âòîðî� øàã� îòêðûâàò� äðóãó� îñòàâøóþñ� äâåðü. Îïðåäåëè� ñòðàòåãè� q 0 âòîðîã� èãðîêà: î� äîëæå� ïîìåñòèò� "Ìåðñåäåñ"ç� îäíî� äâåðü� è� òðå� � âåðîÿòíîñòü� 1/3.
Åñë� ïåðâû� èãðî� 83ÃËÀÂ� I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈ� ÈÃÐ�ïîêàçà� í� äâåð� � "Ìåðñåäåñîì", ò� âòîðî� èãðî� äîëæå� îòêðûò� îäí� è� äâó� äðóãè� äâåðå� � âåðîÿòíîñòü� 1/2. Çíà÷åíè� èãð� ðàâí� 2/3. Äë� äîêàçàòåëüñòâ� îïòèìàëüíîñò� óêàçàííû� ñòðàòåãè� ïðîâåðè� óñëîâè� (∗). Ïð� ëþáî� ÷èñòî� ñòðàòåãè� âòîðîã� èãðîê� ïåðâû� èãðîê, ïðèìåíÿ� p0 , ïîêàçûâàå� í� äâåð� � êîçëî� � âåðîÿòíîñòü� 2/3. Í� âòîðî� øàã� î� óêàçûâàå� í� äðóãó� äâåð� � âûèãðûâàå� ïðèç.
� äðóãî� ñòîðîíû, ïóñò� âòîðî� èãðî� ïðèìåíÿå� ñòðàòåãè� q 0 . Ïîêàæåì, ÷ò� ïåðâû� èãðî� í� ìîæå� âûèãðàò� ïðè� � âåðîÿòíîñòüþ, áîëüøåé, ÷å� 2/3. Ðàññìîòðè� òèïè÷íó� ÷èñòó� ñòðàòåãè� ïåðâîã� èãðîêà: ñíà÷àë� î� âûáèðàå� ïåðâó� äâåðü, í� âòîðî� øàã� î� îòêðûâàå� âòîðó� äâåðü, åñë� âòîðî� èãðî� îòêðû� òðåòü� � îòêðûâàå� ïåðâó� äâåðü, åñë� âòîðî� èãðî� îòêðû� âòîðóþ. Íåòðóäí� ïîäñ÷èòàòü, ÷ò� âåðîÿòíîñò� åã� âûèãðûø� ïð� ðàçìåùåíèÿ� ÌÊÊ, ÊÌ� � ÊÊ� ðàâí� 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@� � @@ I2� �� I1 � � � b� −a � −a � � � b� a � @ó@� J1 @bbb@ó@@ � ba −b � � Ðèñ. 8.2 Ïåðâû� èãðî� èìåå� äâ� èíôîðìàöèîííû� ìíîæåñòâà, îòâå÷àþùè� äâó� ðàâíîâåðîÿòíû� ðàñêëàäà� êàðò. Ïîýòîì� � ïåðâîã� èãðîê� ÷åòûð� ñòðàòåãèè: (ï,ï),(ï,ó),(ó,ï),(ó,ó). Âòîðî� èãðî� í� çíàå� ðàñêëàä� êàðò. Î� èìåå� åäèíñòâåííî� èíôîðìàöèîííî� ìíîæåñòâ� � äâ� ñòðàòåãèè: � � ó.