А.А. Васин, В.В. Морозов - Введение в теорию игр с приложениями к экономике (1184512), страница 32
Текст из файла (страница 32)
Äë� ñìåøàííî� ñòðàòåãè� π a , èíôîðìàöèîííîã� ìíîæåñòâ� Z aj � àëüòåðíàòèâ� k ∈ Alaj ïîëîæè� P (π a , j) = Xπµa a , Pk (π a , j) = µa :Z aj ∈Rel µa Xπµa a . µa :Z aj ∈Rel µa , µa (Z aj )=k Çäåñ� P (π a , j) − âåðîÿòíîñò� âûáîð� ÷èñòî� ñòðàòåãè� µa , äë� êîòîðî� ìíîæåñòâ� Z aj âîçìîæíî, � Pk (π a , j) − âåðîÿòíîñò� âûáîð� àíàëîãè÷íî� ñòðàòåãè� µa � äîïîëíèòåëüíû� óñëîâèå� µa (Z aj ) = k . Íåòðóäí� âèäåòü, 156 14. Ïîçèöèîííû� èãð� îáùåã� âèä�÷ò� aP (π , j) = k(j)XPk (π a , j). k=1 Îïðåäåëåíèå. Ñòðàòåãèå� ïîâåäåíè� β a , ñîîòâåòñòâóþùå� ñìåøàííî� ñòðàòåãè� π a èãðîê� a, íàçûâàåòñ� ñòðàòåãè� ïîâåäåíèÿ, îïðåäåëÿåìà� ñëåäóþùè� îáðàçîì: ⎧ Pk (π a , j)/P (π a , j), åñë� Z aj ∈ Rel π a , aj� pk = (14.1) πµa a , åñë� Z aj ∈/ Rel π a .
µa :µa (Z aj )=k È� ïîñëåäíè� ôîðìó� âûòåêàåò, ÷ò� êàæäà� ñìåøàííà� ñòðàòåãè� îäíîçíà÷í� îïðåäåëÿå� ñîîòâåòñòâóþùó� ñòðàòåãè� ïîâåäåíèÿ. Îáðàòíî, êàæäî� ñòðàòåãè� ïîâåäåíè� ñîîòâåòñòâóå� ìíîã� ñìåøàííû� ñòðàòåãèé. Í� îäí� è� íè� âñåãä� ìîæí� çàäàò� ñëåäóþùè� îáðàçîì. Ëåìì� 14.1. Åñë� äàí� ñòðàòåãè� ïîâåäåíè� β a èãðîê� a � ñìåøàííà� ñòðàòåãè� π a îïðåäåëåí� ï� ôîðìóë� Y aj πµa a = pij , j∈J a ãä� µa (Z aj ) = ij ∈ Alaj ∀ j ∈ J a , ò� β a åñò� ñòðàòåãè� ïîâåäåíèÿ, ñîîòâåòñòâóþùà� π a . Äîêàçàòåëüñòâî.
Ëþáà� ÷èñòà� ñòðàòåãè� µa èãðîê� a îïðåäåëÿåòñ� íàáîðî� çíà÷åíè� ia = (ij | µ a (Z aj ) = ij ∈ Alaj , j ∈ J a ). Ïîýòîì� � µa πµa a = X � paj ij k(j)Y � = ia j∈J a paj ij = 1.j∈J a ij =1 Ïóñò� Z aj ∈ Rel π a . Òîãä� äë� k ∈ Alaj Pk (π a , j) = Xµa :Z aj ∈Rel µa , µa (Z aj )=k 157 πµa a = ÃËÀÂ� III. ÈÃÐ� ÌÍÎÃÈ� ËÈ�X= Y ajajpal µa (Z al ) pk = dk pk .aµa :Z aj ∈Rel µa , µa (Z aj )=k l∈J \{j} Âåëè÷èí� dk î� k ∈ Alaj í� çàâèñèò, ïîñêîëüê� îí� ïðåäñòàâëÿå� ñîáî� ñóìì� îäèíàêîâîã� ÷èñë� ñëàãàåìûõ, í� çàâèñÿùè� î� k.
Îòñþä� aP (π , j) = k(j)XaPk (π , j) = k=1 k(j)Xaj aadk paj k = dk ⇒ pk = Pk (π , j)/P (π , j).k=1 Ïóñò� Z aj ∈/ Rel π a . Òîãä� � πµa a = µa :µa (Z aj )=k= YX� � ajpal µa (Z al ) pk = µa :µa (Z aj )=k l∈J a \{j} Xajajpal µa (Z al ) pk = pk . l∈J a \{j} µa :µa (Z aj )=k Ïðèâåäåííà� ëåìì� óòâåðæäàåò, ÷ò� ì� ìîæå� ïîëó÷èò� êàæäó� ñòðàòåãè� ïîâåäåíè� è� íåêîòîðî� ñìåøàííî� ñòðàòåãèè. Ïðèìå� 14.1. Èãð� � ïàðòíåðîì. � ýòî� àíòàãîíèñòè÷åñêî� èãð� èãðî� 1 ñîñòîè� è� äâó� àãåíòîâ, íàçûâàåìû� Èãðàþùè� � Ïàðòíåð. Äâ� êàðòû, "ñòàðøàÿ"� "ìëàäøàÿ", ñäàþòñ� Èãðàþùåì� � èãðîê� 2.
Îá� âîçìîæíû� ðàñêëàä� êàð� ñ÷èòàþòñ� ðàâíîâåðîÿòíûìè. Èãðî� ñ� ñòàðøå� êàðòî� ïîëó÷àå� äîëëà� î� èãðîê� � ìëàäøå� êàðòî� � èìåå� àëüòåðíàòèâ� ëèá� çàêîí÷èòü, ëèá� ïðîäîëæèò� ïàðòèþ. Åñë� ïàðòè� ïðîäîëæàåòñÿ, Ïàðòíåð, í� çíà� ðàñêëàä� (� ïîëó÷åííî� ñóììû), ìîæå� ïîñîâåòîâàò� Èãðàþùåì� ïîìåíÿòüñ� êàðòî� � èãðîêî� 2 èë� ñîõðàíèò� ñâî� êàðòó.
Ñíîâ� èìåþùè� ñòàðøó� êàðò� ïîëó÷àå� äîëëà� î� àãåíòà, èìåþùåã� ìëàäøó� (ñì. ðèñ. 14.1, ãä� � êàæäî� ôèíàëüíî� ïîçèöè� çàïèñà� âûèãðû� èãðîê� 1). 158 14. Ïîçèöèîííû� èãð� îáùåã� âèä�b@1/2Z 11b z � 1 1/2 @@21� Z@bb−1 Z 12 � b w 2� x@@@b0 y � � b@@@ � −20 Ðèñ. 14.1 Çäåñ� X 1 = Z 11 ∪ Z 12 , X 2 = Z 21 . Ïîýòîì� µ1 = (µ1 (Z 11 ), µ1 (Z 12 )) � µ2 = (µ2 (Z 21 )). Ìàòðèö� îæèäàåìû� âûèãðûøå� u1 (µ1 , µ2 ) ïåðâîã� èãðîê� åñò� (1) (2) çàêîí÷èò� ïðîäîëæèò�⎛⎞(çàêîí÷èòü, îñòàâèòü) (1, 1) 0−1/2(çàêîí÷èòü, ìåíÿòüñÿ) (1, 2) 01/2.⎠(ïðîäîëæèòü, îñòàâèòü) (2, 1) ⎝1/20(ïðîäîëæèòü, ìåíÿòüñÿ) (2, 2) −1/20 u1 ((1, 1), 1) = 1/2 · 1 + 1/2 · (−1) = 0; u1 ((1, 1), 2) = 1/2 · 1 + 1/2 · (−2) = −1/2;u1 ((1, 2), 1) = 1/2 · 1 + 1/2 · (−1) = 0; u1 ((1, 2), 2) = 1/2 · 1 + 1/2 · 0 = 1/2;1u ((2, 1), 1) = 1/2 · 2 + 1/2 · (−1) = 1/2;u1 ((2, 1), 2) = 1/2 · 2 + 1/2 · (−2) = 0; u1 ((2, 2), 1) = 1/2 · 0 + 1/2 · (−1) = −1/2;u1 ((2, 2), 2) = 1/2 · 0 + 1/2 · 0 = 0.Ðåøåíè� ìàòðè÷íî� èãð� (π 1 , π 2 , v) = ((0, 1/2, 1/2, 0), (1/2, 1/2), 1/4) îáåñïå÷èâàå� èãðîê� 1 îæèäàåìû� âûèãðû� 1/4, � èãðîê� 2 − îæèäàåìó� ïîòåðþ, í� ïðåâûøàþùó� 1/4.
� äðóãî� ñòîðîíû, åñë� âçÿò� ñòðà111212òåãè� ïîâåäåíè� èãðîê� 1 s = p111 , 1 − s = p2 � r = p1 , 1 − r = p2 , ò� ïîëó÷èì, ÷ò� îæèäàåìû� âûèãðû� èãðîê� 1 ðàâå� 159ÃËÀÂ� III. ÈÃÐ� ÌÍÎÃÈ� ËÈ�(s/2 + 2((1 − s)r/2) + 0 − 1/2 = (s − 1)(1/2 − r), åñë� µ2 = (1), s/2 + 2((1 − s)r/2) + 0 + (−2)r/2 + 0 = s(1/2 − r), åñë� µ2 = (2). Äë� ëþáû� s � r èãðîê� 1 ãàðàíòèðîâà� òîëüê� ìèíèìó� è� ýòè� äâó� çíà÷åíèé.
Ñëåäîâàòåëüíî, ìàêñèìàëüíà� ñóììà, êîòîðó� èãðî� 1 ìîæå� ñåá� îáåñïå÷èòü, ðàâí� max min[(s − 1)(1/2 − r), s(1/2 − r)] = 0 0≤s,r≤1 � äîñòèãàåòñ� ïð� r = 1/2. Òàêè� îáðàçîì, ñòðàòåãè� ïîâåäåíè� ìîãó� äàò� õóäøè� ðåçóëüòàò, ÷å� ñìåøàííû� ñòðàòåãèè. Çàìåòèì, ÷ò� ñìåøàí1 1 1 1 íà� ñòðàòåãè� π 1 = (π(1,1), π(1,2), π(2,1), π(2,2)) èìåå� ñîîòâåòñòâóþùó� ñòðà1 1 1 1 1 òåãè� ïîâåäåíè� β = (s, r) = (π(1,1) + π(1,2) , π(1,1) + π(2,1)).
Ñëåäîâàòåëüíî, åñë� ì� ðàññìîòðè� îïòèìàëüíó� ñìåøàííó� ñòðàòåãè� (0, 1/2, 1/2, 0) èãðîê� 1, ñîîòâåòñòâóþùå� ñòðàòåãèå� ïîâåäåíè� áóäå� s = r = 1/2, è, � ò� âðåì� êà� îïòèìàëüíà� ñìåøàííà� ñòðàòåãè� îáåñïå÷èâàå� ïåðâîì� èãðîê� âûèãðû� 1/4, äàæ� ñîîòâåòñòâóþùà� ñòðàòåãè� ïîâåäåíè� äàå� åì� òîëüê� 0. Ýò� ðàñõîæäåíè� îáúÿñíÿåòñÿ, êîíå÷íî, íåçàâèñèìîñòüþ, ñîäåðæàùåéñ� � ïðèðîä� ñòðàòåãè� ïîâåäåíèÿ. ×òîá� ïîëó÷èò� ïîëîæèòåëüíû� ðåçóëüòàò� ïð� èñïîëüçîâàíè� ñòðàòåãè� ïîâåäåíèÿ, íàä� íàëîæèò� îãðàíè÷åíè� í� èíôîðìàöèîííî� ðàçáèåíèå.
Îïðåäåëåíèå. Èãð� G íàçûâàåòñ� èãðî� � ïîëíî� ïàìÿòü� äë� èãðîê� a, åñë� è� Z aj ∈ Rel µa � x ∈ Z aj ñëåäóå� x ∈ Poss µa äë� âñå� Z aj , x � µa . È� îïðåäåëåíè� âûòåêàåò, ÷ò� � èãð� � ïîëíî� ïàìÿòü� äë� èãðîê� a ëþáà� ïîçèöè� è� ñóùåñòâåííîã� èíôîðìàöèîííîã� ìíîæåñòâ� ÿâëÿåòñ� âîçìîæíîé. Òåðìè� "ïîëíà� ïàìÿòü"îçíà÷àåò, ÷ò� èãðî� ìîæå� òî÷í� âîññòàíîâèòü, êàêè� àëüòåðíàòèâ� î� âûáèðà� â� âñå� ñâîè� ïðåäûäóùè� õîäà� (ñì.
óïðàæíåíè� 14.1). � ïðèìåð� 14.1 èãð� G í� ÿâëÿåòñ� èãðî� � ïîëíî� ïàìÿòü� äë� èãðîê� 1. Äåéñòâèòåëüíî, èíôîðìàöèîííî� ìíîæåñòâ� Z 12 ñóùåñòâåíí� äë� ñòðàòåãè� µ1 = (1, 2), ïîñêîëüêó, åñë� èãðî� 2 èñïîëüçóå� ñòðàòåãè� µ2 = (2), ò� ïîçèöè� y ∈ Z 12 ðåàëèçóåòñ� � âåðîÿòíîñòü� 1/2.
Îäíàê� äðóãà� ïîçèöè� x ∈ Z 12 í� ÿâëÿåòñ� âîçìîæíî� äë� ñòðàòåãè� µ1 , òà� êà� Èãðàþùèé, ïîëó÷è� ñòàðøó� êàðòó, çàêàí÷èâàå� èãðó. 160 14. Ïîçèöèîííû� èãð� îáùåã� âèä�Èãð� � ïîëíî� ïàìÿòü� äë� âñå� èãðîêî� ïðåâðàùàåòñ� � èãð� � ïîëíî� èíôîðìàöèåé, åñë� âñ� å� èíôîðìàöèîííû� ìíîæåñòâ� ñîäåðæà� ï� îäíî� âåðøèíå.
Ïóñò� w ∈ T − ôèíàëüíà� ïîçèöèÿ, � èãðîê� a ïðèíàäëåæè� íåêîòîðà� ïîçèöè� ïóò� [x0 , w]. Ïðåäïîëîæèì, ÷ò� åã� ïîñëåäíÿ� ïîçèöè� x ∈ Z aj ∩ [x0 , w] èìåå� àëüòåðíàòèâ� � íîìåðî� t ∈ Alaj , òàêæ� ïðèíàäëåæàùó� ïóò� [x0 , w]. Ïîëîæè� S a (w) = {µ a | Z aj ∈ Rel µ a , µ a (Z aj ) = t}. Íàêîíåö, ïóñò� âåëè÷èí� c(w) ðàâí� èë� ïðîèçâåäåíè� âåðîÿòíîñòå� àëüòåðíàòè� ñëó÷àÿ, ïðèíàäëåæàùè� ïóò� [x0 , w], èë� 1, åñë� òàêîâû� íåò. Í� ðèñ. 14.1 äë� ôèíàëüíî� âåðøèí� w c(w) = 1/2, S 1 (w) = {(1, 1), (2, 1)}. Ëåìì� 14.2. Ïóñò� G − èãð� � ïîëíî� ïàìÿòü� äë� âñå� èãðîêîâ. Òîãä� äë� ëþáî� ñèòóàöè� µ = (µa , a ∈ A) � äë� âñå� w ∈ T (c(w), åñë� µa ∈ S a (w) ∀ a ∈ A, p(w|µ) = 0 � ïðîòèâíî� ñëó÷àå.
Äîêàçàòåëüñòâî. Î÷åâèäíî, äîñòàòî÷í� ïîêàçàòü, ÷ò� åñë� µa ∈ S a (w), a ∈ A, ò� êàæäà� ñòðàòåãè� µa âûáèðàå� àëüòåðíàòèâ� èãðîê� a, ïðèíàäëåæàùè� ïóò� [x0 , w] (åñë� òàêîâû� ñóùåñòâóþò). Í� åñë� µa ∈ S a (w), ò� Z aj ∈ Rel µa è, òà� êà� G − èãð� � ïîëíî� ïàìÿòüþ, ò� x ∈ Poss µa . Ïîýòîì� µa âûáèðàå� âñ� àëüòåðíàòèâ� èãðîê� a, ïðèíàäëåæàùè� ïóò� [x0 , w] (ñì.
óïðàæíåíè� 14.1). Ñëåäñòâèå. Ïóñò� G − èãð� � ïîëíî� ïàìÿòü� äë� âñå� èãðîêîâ. Òîãä� äë� ëþáî� ñèòóàöè� � ñìåøàííû� ñòðàòåãèÿ� π = (π a , a ∈ A) ïîçèöè� w ∈ T âîçíèêàå� � âåðîÿòíîñòü� XYXYp(w|π) = πµa a p(w|µ) = πµa a c(w). (14.2) µa∈Aµ:µa ∈S a (w),a∈A a∈A Ëåìì� 14.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
