[учебник] Введение в теорию игр (с приложениями к экономике). Васин, Морозов (2003) (1186146), страница 28
Текст из файла (страница 28)
Íà ðèñ. 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|π) =πµaa p(w|µ) =πµaa c(w).(14.2)µa∈Aµ:µa ∈S a (w),a∈A a∈AËåììà 14.3. Ïóñòü G − èãðà ñ ïîëíîé ïàìÿòüþ äëÿ èãðîêà a. Ïîçèöèèz ∈ Z al , ξ(z, k) è x ∈ Z al ïðèíàäëåæàò ïóòè [x0 , w], w ∈ T, ïðè÷åì xñëåäóåò çà z.1 Òîãäà ìíîæåñòâà S1 = {µa | Z al ∈ Rel µa , µa (Z al ) = k} èS2 = {µa | Z aj ∈ Rel µa } ñîâïàäàþò.1Â÷àñòíîñòè, x ìîæåò ñîâïàñòü ñ ξ(z, k).161ÃËÀÂÀ III. ÈÃÐÛ ÌÍÎÃÈÕ ËÈÖÄîêàçàòåëüñòâî. Ïóñòü µa ∈ S1 . Òîãäà Z al ∈ Rel µa , è, òàê êàê G− èãðà ñ ïîëíîé ïàìÿòüþ äëÿ èãðîêà a, òî z ∈ Poss µa .
Ñëåäîâàòåëüíî, ñòðàòåãèÿ µa âûáèðàåò âñå àëüòåðíàòèâû èãðîêà a íà ïóòè [0, z]. Íîµa (Z al ) = k, è, çíà÷èò, µa âûáèðàåò âñå àëüòåðíàòèâû èãðîêà a íà ïóòè[0, x]. Ñëåäîâàòåëüíî, x ∈ Poss µa , Z aj ∈ Rel µa è µa ∈ S2 .Ïóñòü µa ∈ S2 . Òîãäà Z aj ∈ Rel µa , è, òàê êàê G − èãðà ñ ïîëíîéïàìÿòüþ äëÿ èãðîêà a, òî x ∈ Poss µa .
Ñëåäîâàòåëüíî (ñì. óïðàæíåíèå14.1), z ∈ Poss µa è µa (Z al ) = k, ò.å. µa ∈ S1 .Ñëåäóþùåå óòâåðæäåíèå ïîêàçûâàåò, ÷òî â èãðàõ ñ ïîëíîé ïàìÿòüþìîæíî îãðàíè÷èòüñÿ ïîèñêîì ðàâíîâåñèé ïî Íýøó â ñòðàòåãèÿõ ïîâåäåíèÿ.Òåîðåìà 14.1. Ïóñòü β − ñèòóàöèÿ â ñòðàòåãèÿõ ïîâåäåíèÿ, ñîîòâåò-ñòâóþùàÿ (ïî ôîðìóëàì (14.1)) ïðîèçâîëüíîé ñèòóàöèè π â ñìåøàííûõñòðàòåãèÿõ â èãðå G, â êîòîðîé âñå ïîçèöèè èìåþò ïî êðàéíåé ìåðå äâåàëüòåðíàòèâû. Òîãäà äëÿ òîãî ÷òîáû ua (β) = ua (π), a ∈ A, äëÿ âñåõ πè äëÿ ëþáûõ çíà÷åíèé ôóíêöèé âûèãðûøà ua (w), a ∈ A, w ∈ T, íåîáõîäèìî è äîñòàòî÷íî, ÷òîáû G áûëà èãðîé ñ ïîëíîé ïàìÿòüþ äëÿ âñåõèãðîêîâ.Äîêàçàòåëüñòâî. Íåîáõîäèìîñòü.
Ïóñòü G íå ÿâëÿåòñÿ èãðîé ñ ïîëíîé ïàìÿòüþ äëÿ íåêîòîðîãî èãðîêà a. Òîãäà äîëæíà ñóùåñòâîâàòü ÷èñòàÿ ñòðàòåãèÿ µa è òàêèå äâå ïîçèöèè x è y â íåêîòîðîì èíôîðìàöèîííîì ìíîæåñòâå Z aj , ÷òî x ∈/ Poss µa è y ∈ Poss µa . Âûáåðåì ñòðàòåaãèþ µ̂ , äëÿ êîòîðîé x ∈ Poss µ̂a è µ̂a (Z aj ) = t 6= µa (Z aj ). Ïðè ýòîìñóùåñòâóåò òàêàÿ ïîçèöèÿ z ∈ [x0 , x] ∩ Z al , â êîòîðîé k -àÿ àëüòåðíàòèâà, ïðèíàäëåæàùàÿ [x0 , x], ñòðàòåãèåé µ̂a âûáèðàåòñÿ, à ñòðàòåãèåé µa −íåò. Ïóñòü µ̂ − òàêàÿ ñèòóàöèÿ, ñîäåðæàùàÿ µ̂a , ÷òî p(x|µ̂) > 0, à w ∈ T− ôèíàëüíàÿ ïîçèöèÿ, ñëåäóþùàÿ çà x, äëÿ êîòîðîé p(w|µ̂) > 0.
 èãðå G ïðèìåðà 14.1 (ñì. ðèñ. 14.1) a = 1, k = 2, t = 1, l = 1, j = 2,µ1 = (1, 2), µ̂1 = (2, 1), µ̂2 = (1).Ïîëîæèì π a = (1/2)µa + (1/2)µ̂a . Äëÿ ñîîòâåòñòâóþùåé ñòðàòåãèè ïîajâåäåíèÿ β a âûïîëíåíî palk = pt = 1/2. Ïóñòü ñèòóàöèÿ β â ñòðàòåãèÿõïîâåäåíèÿ ñîîòâåòñòâóåò ñèòóàöèè π = µ̂||π a . Òîãäà p(w|β) ≤ (1/4)c(w) <(1/2)c(w) = p(w|π). Îïðåäåëèì äëÿ èãðîêà a ôóíêöèþ âûèãðûøà ñëåäóþùèì îáðàçîì:(1, w0 = w,ua (w0 ) =0, w0 ∈ T, w0 6= w.162 14. Ïîçèöèîííûå èãðû îáùåãî âèäàÒîãäà èç ïîñëåäíåãî íåðàâåíñòâà ñëåäóåò, ÷òî ua (β) < ua (π) (ïðîòèâîðå÷èå).Äîñòàòî÷íîñòü.
Ïðåäïîëîæèì, ÷òî G − èãðà ñ ïîëíîé ïàìÿòüþ äëÿâñåõ èãðîêîâ. Òîãäà äîñòàòî÷íî ïîêàçàòü, ÷òî p(w|β) = p(w|π) äëÿ âñåõw ∈ T. Âîçüìåì íåêîòîðóþ ôèíàëüíóþ ïîçèöèþ w.Ïóñòü x1 ∈ Z aj1 , ..., xr(a) ∈ Z ajr(a) − ïîçèöèè èãðîêà a, ðàñïîëîæåííûåâ ïîðÿäêå ñëåäîâàíèÿ âäîëü ïóòè [x0 , w], à k1 ∈ Alaj1 , ..., kr(a) ∈ Alajr(a)− íîìåðà ñîîòâåòñòâóþùèõ àëüòåðíàòèâ, ïðèíàäëåæàùèõ ïóòè [x0 , w].Çàìåòèì, ÷òî Z aj1 ∈ Rel µa äëÿ âñåõ µa (ñì.
óïðàæíåíèå 14.1). ÏîýòîìóXP (π a , j1 ) =πµaa = 1.µa :Z aj1 ∈Rel µaÁåç ïîòåðè îáùíîñòè ìîæíî ñ÷èòàòü, ÷òî âñå èíôîðìàöèîííûå ìíîæåñòâà Z aj2 , ..., Z ajr(a) ñóùåñòâåííû äëÿ ñòðàòåãèè π a . Äåéñòâèòåëüíî, âïðîòèâíîì ñëó÷àå p(w|β) = p(w|π) = 0. äàííûõ îáîçíà÷åíèÿõS a (w) = {µa | Z ajr(a) ∈ Rel µa , µa (Z ajr(a) ) = kr(a) }.Èç ëåììû 14.3 ñëåäóåò, ÷òîPkr−1 (π a , jr−1 ) = P (π a , jr ), r = 2, ..., r(a).Îòñþäà âûòåêàåò, ÷òî äëÿ ñîîòâåòñòâóþùåé π a ñòðàòåãèè ïîâåäåíèÿ β a =aja(pajk , k ∈ Al , j ∈ J ) ïî ôîðìóëàì (14.1)r(a)Yrpajkrr=1r(a)YPkr (π a , jr )== Pkr(a) (π a , jr(a) ) =aP (π , jr )r=1Xπµaa .µa ∈S a (w)Èñïîëüçóÿ ñëåäñòâèå ëåììû 14.2, ïîëó÷àåìp(w|β) = c(w)r(a)YY(14.3)r=pajkra∈A r=1(14.3)= c(w)YXa∈A µa ∈S a (w)Xπµaa = c(w)Yµa ∈S a (w),a∈A a∈A163(14.2)πµaa = p(w|π).(14.3)ÃËÀÂÀ III.
ÈÃÐÛ ÌÍÎÃÈÕ ËÈÖÓïðàæíåíèå 14.2. Èçìåíèì ïðàâèëà èãðû èç ïðèìåðà 14.1. Ïåðâûìäåëàåò õîä èãðîê 2. Îí âûáèðàåò âàðèàíò ðàñêëàäà äâóõ êàðò (ñòàðøåéè ìëàäøåé) Èãðàþùåìó è ñåáå. Èãðàþùèé, íå çíàÿ ðàñêëàäà, ìîæåòîñòàâèòü êàðòû â ïðåæíåì ïîëîæåíèè, ëèáî ïîìåíÿòü èõ ìåñòàìè. Çàòåì, Ïàðòíåð, íàáëþäàâøèé çà äåéñòâèÿìè Èãðàþùåãî, òàêæå ìîæåòâûáðàòü îäíó èç äâóõ àëüòåðíàòèâ: íå òðîãàòü êàðòû, ëèáî ïîìåíÿòü èõìåñòàìè.
Èãðîê, èìåþùèé â èòîãå ñòàðøóþ êàðòó, ïîëó÷àåò îò äðóãîãîèãðîêà äîëëàð è äîïîëíèòåëüíóþ ñóììó, îïðåäåëÿåìóþ ïî ñëåäóþùåìóïðàâèëó. Åñëè èãðîê 1 èìååò ñòàðøóþ êàðòó â ðåçóëüòàòå îäíîãî (èëèäâóõ) åå ïåðåìåùåíèé, òî îí ïîëó÷àåò îò èãðîêà 2 äîïîëíèòåëüíî äâà(èëè òðè) äîëëàðà.  àíàëîãè÷íîé ñèòóàöèè èãðîê 2 ïîëó÷àåò îò èãðîêà1 äîïîëíèòåëüíî îäèí äîëëàð (èëè äâà äîëëàðà). Åñëè ïîñëå ðàçäà÷è,êàðòû íå ïåðåìåùàëèñü, òî äîïîëíèòåëüíûå âûïëàòû íå ïðîèçâîäÿòñÿ.Óñòàíîâèòü, ÷òî îïèñàííàÿ àíòàãîíèñòè÷åñêàÿ èãðà G ÿâëÿåòñÿ èãðîé ñïîëíîé ïàìÿòüþ äëÿ îáîèõ èãðîêîâ.
Íàéòè îïòèìàëüíûå ñòðàòåãèè ïîâåäåíèÿ è çíà÷åíèå èãðû. 15.Êîîïåðàòèâíûå èãðûÊîîïåðàòèâíûå èãðû îòíîñÿòñÿ ê íåñòðàòåãè÷åñêèì èãðàì, â êîòîðûõ èãðîêè äåëÿò íåêîòîðîå êîëè÷åñòâî (äåíåæíîãî äîõîäà, ðåñóðñà èò.ï.), èñïîëüçóÿ êàêîé-ëèáî ïðèíöèï îïòèìàëüíîñòè.Ïðèìåð 15.1. Èãðà "äæàç-îðêåñòð". Âëàäåëåö íî÷íîãî êëóáà â Ïàðèæå îáåùàåò $1000 ïåâöó, ïèàíèñòó è óäàðíèêó (èãðîêè 1,2 è 3) çàñîâìåñòíóþ èãðó â åãî êëóáå. Âûñòóïëåíèå äóýòà ïåâöà è ïèàíèñòà îíðàñöåíèâàåò â $800, óäàðíèêà è ïèàíèñòà − â $650 è îäíîãî ïèàíèñòà −â $300. Äóýò ïåâåö−óäàðíèê çàðàáàòûâàåò $500 çà âå÷åð â îäíîé ñòàíöèè ìåòðî, ïåâåö çàðàáàòûâàåò $200 çà âå÷åð â îòêðûòîì êàôå. Óäàðíèêîäèí íè÷åãî íå ìîæåò çàðàáîòàòü.
Êàêîå ðàñïðåäåëåíèå äîõîäà â $1000ñëåäóåò ñ÷èòàòü ðàçóìíûì, ó÷èòûâàÿ îïèñàííûå âîçìîæíîñòè èãðîêîâ?Ïóñòü A − ìíîæåñòâî íîìåðîâ èãðîêîâ. Ïîäìíîæåñòâà K ⊆ A â êîîïåðàòèâíîé òåîðèè íàçûâàþòñÿ êîàëèöèÿìè. Ôóíêöèÿ v, ñîïîñòàâëÿþùàÿ êàæäîé êîàëèöèè K åå äîõîä v(K), íàçûâàåòñÿ õàðàêòåðèñòè÷åñêîé. Õàðàêòåðèñòè÷åñêàÿ ôóíêöèÿ v íàçûâàåòñÿ ñóïåðàääèòèâíîé, åñëèv(K ∪ T ) ≥ v(K) + v(T ) äëÿ ëþáûõ íåïåðåñåêàþùèõñÿ êîàëèöèé K è T.Óñëîâèå ñóïåðàääèòèâíîñòè îçíà÷àåò, ÷òî ïðè K ∩ T = ∅ äîõîä êîàëèöèèK ∪ T íå ìåíüøå ñóììû äîõîäîâ êîàëèöèé K è T .
 äàëüíåéøåì âìåñòî164 15. Êîîïåðàòèâíûå èãðûv({i, j, ..., l}) áóäåì ïèñàòü v(ij...l). ïðèìåðå 15.1 A = {1, 2, 3}, à õàðàêòåðèñòè÷åñêàÿ ôóíêöèÿ v ïðèíèìàåò ñëåäóþùèå çíà÷åíèÿ: v(1) = 200, v(2) = 300, v(3) = 0, v(12) =800, v(23) = 650, v(13) = 500, v(123) = 1000. Íåòðóäíî âèäåòü, ÷òî vñóïåðàääèòèâíà. Åñëè áû óñëîâèå ñóïåðàääèòèâíîñòè çäåñü íàðóøàëîñü(ñêàæåì, ïðè v(1) = 400), òî ñîáðàòü âåñü ñîñòàâ ìóçûêàíòîâ çà $1000 áûëî áû òðóäíî, åñëè òîëüêî ê ñîâìåñòíîé èãðå èõ íå ïðèâëåêàþò äðóãèåñòèìóëû.Îïðåäåëåíèå. Êîîïåðàòèâíîé èãðîé ( èëèâ ôîðìå õàðàêòåðè èãðîéñòè÷åñêîé ôóíêöèè) íàçûâàåòñÿ ïàðà K = A, v .Óñòàíîâèì ñâÿçü ìåæäó èãðàìè â íîðìàëüíîéè êîîïåðàòèâ- ôîðìåaíûìè èãðàìè.
Ïðåäïîëîæèì, ÷òî â èãðå Γ = A, S , ua (s), a ∈ Aìíîæåñòâà ñòðàòåãèé èãðîêîâ êîíå÷íû, à âûèãðûøè − äåíåæíûå. Èãðîêè ìîãóò îñóùåñòâëÿòü ïîáî÷íûå ïëàòåæè, ò.å. ïåðåðàñïðåäåëÿòü ìåæäó ñîáîé ïîëó÷åííûå âûèãðûøè. Îïðåäåëèì õàðàêòåðèñòè÷åñêóþP a ôóíêöèþ. Äëÿ êîàëèöèè A åñòåñòâåííî ïîëîæèòü v(A) = maxu (s). Äëÿëþáîé êîàëèöèè K 6= A è ñèòóàöèè s îáîçíà÷èìdef NsK = (sa , a ∈ K) ∈ S K =S a.s∈S a∈Aa∈KÒåïåðü ñèòóàöèþ s ìîæíî çàïèñàòü â âèäå s = (sK , sA\K ). Ïóñòü èãðà Γèìååò ïîñòîÿííóþ ñóììó, ò.å.Xua (s) ≡ const.a∈AÄëÿ òàêèõ èãð v(K) ìîæíî îïðåäåëèòü êàê çíà÷åíèå àíòàãîíèñòè÷åñêîéèãðû êîàëèöèè K ïðîòèâ åå äîïîëíåíèÿ A\Kdef X a K A\K ΓK = S K , S A\K , uK (sK , sA\K ) =u (s , s) .a∈KÓïðàæíåíèå 15.1. Äîêàæèòå, ÷òî äëÿ èãðû Γ ñ ïîñòîÿííîé ñóììîéõàðàêòåðèñòè÷åñêàÿ ôóíêöèÿ v ñóïåðàääèòèâíà èv(K) + v(A\K) = v(A) ∀K ⊂ A.(15.1)Îïðåäåëåíèå.
Ãîâîðÿò, ÷òî êîîïåðàòèâíàÿ èãðà K = A, v èìååò ïîñòîÿííóþ ñóììó, åñëè äëÿ íåå âûïîëíåíî óñëîâèå (15.1).165ÃËÀÂÀ III. ÈÃÐÛ ÌÍÎÃÈÕ ËÈÖÏðèìåð 15.2. Ðàññìîòðèì äâåïàðû ìàòðèö2356A1 =, B1 =;417 −2 7 −1−1 2A2 =, B2 =.2 34 3Ïåðâûé èãðîê âûáèðàåò íîìåð ñòðîêè i, âòîðîé − íîìåð ñòîëáöà j, àòðåòèé èãðîê âûáèðàåò íîìåð ïàðû r ∈ {1, 2}. Âûèãðûø ïåðâîãî èãðîêàðàâåí arij , âòîðîãî − brij , à òðåòüåãî − crij = 10 − arij − brij . Èãðà Γ èìååò ïîñòîÿííóþ ñóììó v(123) = 10.
Íàéäåì v(1). Ïåðâûé èãðîê èãðàåò ïðîòèâêîàëèöèè {2, 3} â èãðó ñ ìàòðèöåé12(1, 1) (1, 2) (2, 1) (2, 2)273−14213Âû÷åðêèâàÿ ïåðâûé è âòîðîé ñòîëáöû è ðåøàÿ èãðó 2×2, íàõîäèì çíà÷åíèå èãðû v(1) = 5/3. Èç óñëîâèÿ ïîñòîÿíñòâà ñóììû v(23) = 10 − v(1) =25/3.Óïðàæíåíèå 15.2.  óñëîâèÿõ ïðèìåðà 15.2 íàéäèòå çíà÷åíèÿ õàðàêòåðèñòè÷åñêîé ôóíêöèè v(2), v(13), v(3) è v(12).Îïðåäåëåíèå. Äåëåæîì íàçûâàåòñÿ âåêòîð y = (y a , a ∈ A), óäîâëåòâîðÿþùèé óñëîâèÿìXy a = v(A), y a ≥ v(a) ∀ a ∈ A.a∈AÄåëåæ y çàäàåò ðàñïðåäåëåíèå âûèãðûøà v(A), óäîâëåòâîðÿþùåå óñëîâèþ èíäèâèäóàëüíîé ðàçóìíîñòè y a ≥ v(a) ∀ a ∈ A. Ïóñòü Y − ìíîæåñòâî âñåõ äåëåæåé.Èç ñâîéñòâà ñóïåðàääèòèâíîñòèõàðàêòåðèñòè÷åñêîé ôóíêöèè v âûPòåêàåò íåðàâåíñòâîv(a) ≤ v(A).a∈AÎïðåäåëåíèå.PÊîîïåðàòèâíàÿ èãðà K =ñòâåííîé, åñëèv(a) = v(A).A, víàçûâàåòñÿ íåñóùå-a∈A íåñóùåñòâåííîé èãðå äåëåæ y = (v(a), a ∈ A) − åäèíñòâåííûé.
Âäàëüíåéøåì áóäåì ðàññìàòðèâàòü òîëüêî ñóùåñòâåííûå èãðû.166 15. Êîîïåðàòèâíûå èãðûÎïðåäåëåíèå. Äâå êîîïåðàòèâíûå èãðû K = A, v è K0 = A, v 0íàçûâàþòñÿ ýêâèâàëåíòíûìè, åñëèòàêèå ÷èñëà c > 0 èP íàéäóòñÿa0ad , a ∈ A, ÷òî v (K) = cv(K) +d ∀ K ⊆ A.a∈KÏåðåõîä îò èãðû K ê ýêâèâàëåíòíîé èãðå K0 ìîæíî ñâÿçàòü ñ èçìåíåíèåì â c ðàç äåíåæíîé åäèíèöû. Ïîëîæèòåëüíàÿ âåëè÷èíà da èíòåðïðåòèðóåòñÿ êàê äîïîëíèòåëüíàÿ âûïëàòà èãðîêó a. Åñëè æå âåëè÷èíàda îòðèöàòåëüíà, òî −da ìîæíî ðàññìàòðèâàòü êàê ïëàòó èãðîêà a çàó÷àñòèå â èãðå. Äåëåæ y èãðû K ïåðåõîäèò â äåëåæ z èãðû K0 ñ êîìïîíåíòàìè z a = cy a + da ∀ a ∈ A.Îïðåäåëåíèå.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
