А.А. Васин, В.В. Морозов - Введение в теорию игр с приложениями к экономике (1184512), страница 33
Текст из файла (страница 33)
Ïóñò� G − èãð� � ïîëíî� ïàìÿòü� äë� èãðîê� a. Ïîçèöè� z ∈ Z al , ξ(z, k) � x ∈ Z al ïðèíàäëåæà� ïóò� [x0 , w], w ∈ T, ïðè÷å� x ñëåäóå� ç� z.� Òîãä� ìíîæåñòâ� 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 âûïîëíåí� pal k = pt = 1/2. Ïóñò� ñèòóàöè� β � ñòðàòåãèÿ� ïîâåäåíè� ñîîòâåòñòâóå� ñèòóàöè� π = µ̂||π a . Òîãä� p(w|β) ≤ (1/4)c(w) < (1/2)c(w) = p(w|π). Îïðåäåëè� äë� èãðîê� a ôóíêöè� âûèãðûø� ñëåäóþùè� îáðàçîì: � 1, w� = w, ua (w0 ) = 0, w� ∈ T, w� =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 ) = πµa a = 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)� r pajkrr=1 r(a)� Pkr (π a , jr )= = Pkr(a) (π a , jr(a) ) = aP (π , jr )r=1 � πµa a . µa ∈S a (w) Èñïîëüçó� ñëåäñòâè� ëåìì� 14.2, ïîëó÷àå�p(w|β) = c(w) r(a)YY(14.3) r = pajkr a∈A r=1 (14.3) = c(w) YXa∈A µa ∈S a (w) Xπµa a = c(w) Yµa ∈S a (w),a∈A a∈A 163 (14.2) πµa a = 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) = max u (s). Äë� ëþáî� êîàëèöè� K 6= A � ñèòóàöè� s îáîçíà÷è� def � sK = (sa , a ∈ K) ∈ S K = S a . s∈S a∈A a∈K Òåïåð� ñèòóàöè� s ìîæí� çàïèñàò� � âèä� s = (sK , sA\K ). Ïóñò� èãð� Γ èìåå� ïîñòîÿííó� ñóììó, ò.å.
Xu a (s) ≡ const. a∈A Äë� òàêè� èã� v(K) ìîæí� îïðåäåëèò� êà� çíà÷åíè� àíòàãîíèñòè÷åñêî� èãð� êîàëèöè� K ïðîòè� å� äîïîëíåíè� A\K � def X a K A\K � ΓK = S K , S A\K , u K (s K , s A\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. Ðàññìîòðè� äâ� ïàð� ìàòðè� 23 5 6A1 = , B 1 =; 41 � 7 −2 � 7 −1 −1 2 A2 =, B 2 = . 23 4 3 Ïåðâû� èãðî� âûáèðàå� íîìå� ñòðîê� i, âòîðî� − íîìå� ñòîëáö� j, � òðåòè� èãðî� âûáèðàå� íîìå� ïàð� r ∈ {1, 2}. Âûèãðû� ïåðâîã� èãðîê� ðàâå� ar ij , âòîðîã� − br ij , � òðåòüåã� − cr ij = 10 − ar ij − br ij .
Èãð� Γ èìåå� ïîñòîÿííó� ñóìì� v(123) = 10. Íàéäå� v(1). Ïåðâû� èãðî� èãðàå� ïðîòè� êîàëèöè� {2, 3} � èãð� � ìàòðèöå� 12(1, 1) (1, 2) (2, 1) (2, 2) 2 7 3 −1 421 3 Âû÷åðêèâà� ïåðâû� � âòîðî� ñòîëáö� � ðåøà� èãð� 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
