[учебник] Введение в теорию игр (с приложениями к экономике). Васин, Морозов (2003) (1186146), страница 27
Текст из файла (страница 27)
Òàêèì îáðàçîì, äëÿ ëþáîé ñèòóàöèèµ äëÿ êàæäîãî èãðîêà a ∈ A îïðåäåëåíî ñðåäíåå çíà÷åíèå ôóíêöèè âûèãðûøàXua (µ) = E(ua (x)|µ) =p(x|µ)ua (x).x∈TÎïðåäåëåíèå. Ñìåøàííîé ñòðàòåãèåé π a èãðîêà a ∈ A íàçûâàåòñÿâåðîÿòíîñòíîå ðàñïðåäåëåíèå íà ìíîæåñòâå {µa } åãî ÷èñòûõ ñòðàòåãèé,154 14. Ïîçèöèîííûå èãðû îáùåãî âèäàñòàâÿùåå â ñîîòâåòñòâèå êàæäîé ñòðàòåãèè µa âåðîÿòíîñòü πµaa åå âûáîðà.Ñèòóàöèÿ π = (π a , a ∈ A) â ñìåøàííûõ ñòðàòåãèÿõ îïðåäåëÿåò âåðîÿòíîñòíîå ðàñïðåäåëåíèå íà ìíîæåñòâå T ôèíàëüíûõ ïîçèöèé:X Yπµa p(x|µ) ∀ x ∈ T.p(x|π) =µa∈AÎæèäàåìûé âûèãðûø èãðîêà a â ñèòóàöèè π îïðåäåëÿåòñÿ êàê ìàòåìàòè÷åñêîå îæèäàíèåXua (π) = E(ua (x)|µ) =p(x|π)ua (x).x∈TÓêàçàííûé ñïîñîá ââåäåíèÿ ñìåøàííûõ ñòðàòåãèé àíàëîãè÷åí ñëó÷àþèãð â íîðìàëüíîé ôîðìå.
Îäíàêî â äàííîì êëàññå èãð îí, êàê ïðàâèëî,íåýôôåêòèâåí, ïîñêîëüêó äàæå äëÿ íåáîëüøèõ äåðåâüåâ ÷èñëî âîçìîæíûõ ÷èñòûõ ñòðàòåãèé ìîæåò áûòü î÷åíü âåëèêî. Áîëåå ýôôåêòèâíûìÿâëÿåòñÿ ñëåäóþùèé ïîäõîä, ñâÿçàííûé ñ ïîíÿòèåì ñòðàòåãèè ïîâåäåíèÿ.Ðàññìîòðèì ñèòóàöèþ, êîãäà èãðîê âûáèðàåò âåðîÿòíîñòíîå ðàñïðåäåëåíèå íà àëüòåðíàòèâàõ äëÿ êàæäîãî ñâîåãî èíôîðìàöèîííîãî ìíîæåñòâà è, â ñëó÷àå ñâîåãî âûáîðà, ïðîâîäèò ðàíäîìèçàöèþ, ïîëüçóÿñüýòèì ðàñïðåäåëåíèåì. Ïðè ýòîì ïðåäïîëàãàåòñÿ, ÷òî ñëó÷àéíûé âûáîðàëüòåðíàòèâ â ðàçëè÷íûõ èíôîðìàöèîííûõ ìíîæåñòâàõ ïðîèçâîäèòñÿíåçàâèñèìî.Îïðåäåëåíèå. Ñòðàòåãèåé ïîâåäåíèÿ β a èãðîêà a íàçûâàåòñÿ îòîáðàæåíèå, êîòîðîå êàæäîìó èíôîðìàöèîííîìó ìíîæåñòâó Z aj , j ∈ J a ,ñîïîñòàâëÿåò íàáîð(pajk ,k = 1, ..., k(j)) :k(j)Xajpajk = 1, pk ≥ 0, k = 1, ..., k(j),k=1ajïðè÷åì pajâ ëþáîé ïîçèk − âåðîÿòíîñòü âûáîðà àëüòåðíàòèâû k ∈ Alajöèè ìíîæåñòâà Z .Ëþáàÿ ñèòóàöèÿ β = (β a , a ∈ A) â ñòðàòåãèÿõ ïîâåäåíèÿ îïðåäåëÿåòâåðîÿòíîñòíîå ðàñïðåäåëåíèå íà ìíîæåñòâå ïîçèöèé ñëåäóþùèì îáðàçîì:σ(x) ∈ Z aj , x = ξ(σ(x), k), k ∈ Alaj ⇒ p(x|β) = p(σ(x)|β)pajk ;155ÃËÀÂÀ III.
ÈÃÐÛ ÌÍÎÃÈÕ ËÈÖσ(x) ∈ X 0 ⇒ p(x|β) = p(σ(x)|β)p(x|σ(x)).Îæèäàåìûé âûèãðûø ua (β) èãðîêà a â ñèòóàöèèPβ = (β a , a ∈ A) îïðåäåëÿåòñÿ êàê ìàòåìàòè÷åñêîå îæèäàíèå ua (β) =p(x|β)ua (x).x∈TÒàêèì îáðàçîì, ìû îïðåäåëèëè äâà ñìåøàííûõ ðàñøèðåíèÿ èãðûΓ(G):Γ(G) = A, {π a }, ua (π), a ∈ A è Γ̂(G) = A, {β a }, ua (β), a ∈ A .Êàê îíè ìåæäó ñîáîé ñîîòíîñÿòñÿ? Èçó÷èì ýòîò âîïðîñ, èñïîëüçóÿñëåäóþùèå ïîíÿòèÿ.Îïðåäåëåíèå. Ïîçèöèÿ x ∈ X a èãðîêà a íàçûâàåòñÿ âîçìîæíîé äëÿñìåøàííîé ñòðàòåãèè π a (÷èñòîé ñòðàòåãèè µa ), åñëè ñóùåñòâóåò òàêàÿñèòóàöèÿ π (µ), ñîäåðæàùàÿ π a (µa ), ÷òî p(x|π) > 0 (p(x|µ) > 0).Îïðåäåëåíèå.
Èíôîðìàöèîííîå ìíîæåñòâî Z aj èãðîêà a íàçûâàåòñÿñóùåñòâåííûì äëÿ ñìåøàííîé ñòðàòåãèè π a (÷èñòîé ñòðàòåãèè µa ), åñëèíåêîòîðàÿ ïîçèöèÿ x ∈ Z aj âîçìîæíà äëÿ π a (µa ).Îáîçíà÷èì ìíîæåñòâî ïîçèöèé, âîçìîæíûõ äëÿ ñòðàòåãèè µa , ÷åðåçPoss µa , à ñåìåéñòâî èíôîðìàöèîííûõ ìíîæåñòâ, ñóùåñòâåííûõ äëÿ µa ,÷åðåç Rel µa . Àíàëîãè÷íî ââîäÿòñÿ ìíîæåñòâî Poss π a è ñåìåéñòâî Rel π a .Îáîçíà÷èì ÷åðåç [x0 , x] ïóòü, âåäóùèé èç íà÷àëüíîé âåðøèíû x0 äåðåâà â âåðøèíó x.Óïðàæíåíèå 14.1. Ïóñòü µa − ÷èñòàÿ ñòðàòåãèÿ èãðîêà a ∈ A. Ïîêàæèòå, ÷òî x ∈ Poss µa òîãäà è òîëüêî òîãäà, êîãäà ñòðàòåãèÿ µa â ëþáîéâåðøèíå x0 ∈ [x0 , x] ∩ X a , x0 6= x, âûáèðàåò àëüòåðíàòèâó, ïðèíàäëåæàùóþ ïóòè [x0 , x].
 ÷àñòíîñòè, åñëè x ∈ X a ∩ Z aj − ïåðâàÿ ïîçèöèÿ, ãäåèãðîê a äåëàåò õîä, òî x ∈ Poss µa è Z aj ∈ Rel µa äëÿ ëþáîé ÷èñòîéñòðàòåãèè µa .Äëÿ ñìåøàííîé ñòðàòåãèè π a , èíôîðìàöèîííîãî ìíîæåñòâà Z aj è àëüòåðíàòèâû k ∈ Alaj ïîëîæèìP (π a , j) =Xπµaa , Pk (π a , j) =Xπµaa .µa :Z aj ∈Rel µa , µa (Z aj )=kµa :Z aj ∈Rel µaÇäåñü 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 ,ajPpk =(14.1)πµaa ,åñëè Z aj ∈/ Rel π a .µa :µa (Z aj )=kÈç ïîñëåäíèõ ôîðìóë âûòåêàåò, ÷òî êàæäàÿ ñìåøàííàÿ ñòðàòåãèÿ îäíîçíà÷íî îïðåäåëÿåò ñîîòâåòñòâóþùóþ ñòðàòåãèþ ïîâåäåíèÿ. Îáðàòíî,êàæäîé ñòðàòåãèè ïîâåäåíèÿ ñîîòâåòñòâóåò ìíîãî ñìåøàííûõ ñòðàòåãèé.Íî îäíó èç íèõ âñåãäà ìîæíî çàäàòü ñëåäóþùèì îáðàçîì.Ëåììà 14.1.
Åñëè äàíà ñòðàòåãèÿ ïîâåäåíèÿ β a èãðîêà a è ñìåøàííàÿñòðàòåãèÿ π a îïðåäåëåíà ïî ôîðìóëåY ajπµaa =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 ).ÏîýòîìóXµaπµaa=XYpajijk(j)YX=ia j∈J apajij = 1.j∈J a ij =1Ïóñòü Z aj ∈ Rel π a .
Òîãäà äëÿ k ∈ AlajPk (π a , j) =Xµa :Z aj ∈Rel µa , µa (Z aj )=k157πµaa =ÃËÀÂÀ 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=1k(j)Xajaadk pajk = dk ⇒ pk = Pk (π , j)/P (π , j).k=1Ïóñòü Z aj ∈/ Rel π a . ÒîãäàXπµaa =µa :µa (Z aj )=k=YXYajpalµ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 zb11/2@@21@Z@bb−1Z 12bw2bx@@@b0yb@@@bb−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/20u1 ((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)] = 00≤s,r≤1è äîñòèãàåòñÿ ïðè r = 1/2. Òàêèì îáðàçîì, ñòðàòåãèè ïîâåäåíèÿ ìîãóòäàòü õóäøèé ðåçóëüòàò, ÷åì ñìåøàííûå ñòðàòåãèè.
Çàìåòèì, ÷òî ñìåøàí1111íàÿ ñòðàòåãèÿ π 1 = (π(1,1), π(1,2), π(2,1), π(2,2)) èìååò ñîîòâåòñòâóþùóþ ñòðà11111òåãèþ ïîâåäåíèÿ β = (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, åñëè òàêîâûõíåò.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
