А.А. Васин, В.В. Морозов - Введение в теорию игр с приложениями к экономике (1184512), страница 52
Текст из файла (страница 52)
Â� âòîðî� ñëó÷à� y(x∗ ) = 0 � ïåðâà� ôèðì� âûòåñíÿå� âòîðó� � ðûíêà. � îáîè� ñëó÷àÿ� F1 ≥ F (x0 , y 0 ) = Kc1 c2 /(c1 + c2 )−2 , ãä� (x0 , y 0 ) = (Kc2 (c1 + c2 )−2 , Kc1 (c1 + c2 )−2 ) − ñèòóàöè� ðàâíîâåñè� � èãð� Γ ïð� k = 1. 11.6. Ðàâíîâåñè� ï� Øòàêåëüáåðã� � ïðèìåð� 11.1 (i0 , j 0 ) = (2, 1), à � ïðèìåð� 11.2 (x0 , y 0 ) = (1/2, 1). 249 22. Ðåøåíè� óïðàæíåíè�12.1.
Íåîáõîäèìîñòü. Ïóñò� ôóíêöè� h(z) êâàçèâîãíóòà. Äîêàæåì, ÷ò� ìíîæåñòâ� Ëåáåã� Z + (z 0 ) âûïóêë� äë� ïðîèçâîëüíîã� z 0 ∈ Z. Âîçüìå� ëþáû� äâ� òî÷ê� z 0 , z 0� ∈ Z + (z 0 ) � ëþáî� ÷èñë� 0 < λ < 1. Òîãä� h(λz � + (1 − λ)z 00 ) ≥ min[h(z 0 ), h(z 00 )] ≥ h(z 0 ). Äîñòàòî÷íîñòü. Ïóñò� ìíîæåñòâ� Ëåáåã� Z + (z 0 ) âûïóêë� ïð� âñå� 0 z ∈ Z.
Âîçüìå� ëþáû� äâ� òî÷ê� z 0 , z 0� ∈ Z � ëþáî� ÷èñë� 0 < λ < 1. Áå� ïîòåð� îáùíîñò� ìîæí� ñ÷èòàòü, ÷ò� h(z 0 ) ≤ h(z 00 ). Òîãä� z 0 , z 0� ∈Z + (z 0 ) � � ñèë� âûïóêëîñò� ìíîæåñòâ� Z + (z 0 ) òî÷ê� λz � + (1 − λ)z 0� òàêæ� ïðèíàäëåæè� Z + (z 0 ), ò.å.
h(λz � + (1 − λ)z 00 ) ≥ h(z 0 ) = min[h(z 0 ), h(z 00 )]. Ñëåäîâàòåëüíî, ôóíêöè� h(z) êâàçèâîãíóò� í� Z. 13.1. p(i, µ) = 0, i = 1, 2, 4, 6, p(3, µ) = 1/4, p(5, µ) = 3/4. 13.2. Èãðî� 1 èìåå� ñòðàòåãè� µ1 = (k, l) ∈ {(1, 1), (1, 2), (2, 1), (2, 2)}, ãä� k � l − íîìåð� àëüòåðíàòè� åã� ëåâî� � ïðàâî� ëè÷íî� ïîçèöè� (ñì. ðèñ. 13.4). Àíàëîãè÷íû� âè� èìåþ� ñòðàòåãè� âòîðîã� èãðîêà.
Íîðìàëüíà� ôîðì� èãð� G çàäàåòñ� ìàòðèöàì� ⎛ 1/2215/2−2 −1/2 −11/4 −1/4 1/2 −11 −1/2 7/4 −11/4 2 , B = −2 A = ⎝1/4⎝−7/4 −1/4 −7/4 −1/4 ⎠ ,7/4 1/4 7/4 ⎠1/4 −5/4 1/4 −5/4−7/42 −7/42 � íîðìàëüíà� ôîðì� ïîäèãð� Gz − ìàòðèöàì� 1 3 −3 −1 Az =, Bz = . 1 −1 −3 2 13.3. µ = ((1, 1), (1, 2)).
14.1. Ïóñò� x ∈ Poss µa . Åñë� � íåêîòîðî� ïîçèöè� � x ∈ [x0 , x] ∩ X a , x� =6 x ñòðàòåãè� µa âûáèðàå� àëüòåðíàòèâó, í� ïðèíàäëåæàùó� ïóò� [x0 , x], ò� âåðîÿòíîñò� ïîïàñò� � âåðøèí� x ðàâí� íóë� (ïðîòèâîðå÷èå). Îáðàòíî, ïóñò� � êàæäî� âåðøèí� x� ∈ [x0 , x] ∩ X a , x� 6= x, ñòðàòåãè� µa âûáèðàå� àëüòåðíàòèâó, ïðèíàäëåæàùó� ïóò� [x0 , x].
Ïîêàæåì, ÷ò� � ýòî� ñëó÷à� x ∈ Poss µa . Äåéñòâèòåëüíî, îïðåäåëè� ñòðàòåãè� µb , b ∈ A\{a}, äðóãè� èãðîêî� òàêè� îáðàçîì, ÷òîá� ýò� ñòðàòåãè� âûáèðàë� � êàæäî� âåðøèí� x� ∈ [x0 , x] ∩ X b , x� 6= x,, àëüòåðíàòèâ� ïðèíàäëåæàùè� ïóò� [x0 , x].
Åñë� x� ∈ [x0 , x] ∩ X 0 , x� 6= x, ò� âåðîÿòíîñò� âûáîð� òàêî� àëüòåðíàòèâ� ïîëîæèòåëüíà. Ñëåäîâàòåëüíî, p(x|µ) > 0. 14.2. Í� ðèñ. 22.1 èçîáðàæåí� äåðåâ� èãðû. Èãðî� 1 èìåå� ïîëíó� ïàìÿòü, ïîñêîëüê� Ïàðòíå� íàáëþäàå� ç� äåéñòâèÿì� Èãðàþùåãî. Èãðî� 250 22. Ðåøåíè� óïðàæíåíè�2 õîäè� òîëüê� îäè� ðà� � ïîýòîì� òàêæ� èìåå� ïîëíó� ïàìÿòü. Çàïèøå� ñòðàòåãè� ïîâåäåíè� èãðîê� 1 � âèä� β 1 = (h, r, t), ãä� 0 ≤ h, r, t ≤ 1 −âåðîÿòíîñò� âûáîð� ïåðâî� àëüòåðíàòèâ� � ìíîæåñòâà� Z 11 , Z 12 � Z 13 ñîîòâåòñòâåííî. Èãðî� 2 èìåå� äâ� ÷èñòû� ñòðàòåãèè: (1) � (2).
21 • Z H� HH� • Z 11 •h�Z 12 •B•1 ••CC• C � r ht � � BB� B• •� −2−2C� � B � r CCC• •4 −1 Z 13 C� t � BB� B• •� 3 3 C� � � � � •−3 Ðèñ. 22.1 Îæèäàåìû� âûèãðû� èãðîê� 1 ðàâåí(hr − 2h(1 − r) − 2(1 − h)t + 4(1 − h)(1 − t), åñë� µ2 = (1), −hr + 3h(1 − r) + 3(1 − h)t − 3(1 − h)(1 − t), åñë� µ2 = (2), èë� � h(3r − 2) + (1 − h)(2 − 6t), åñë� µ2 = (1), h(3 − 4r) + (1 − h)(6t − 3), åñë� µ2 = (2). Ïîýòîì� ìàêñèìàëüíû� ãàðàíòèðîâàííû� âûèãðû� èãðîê� 1 ðàâå� v = max min[h(3r − 2) + (1 − h)(2 − 6t), h(3 − 4r) + (1 − h)(6t − 3)].
0≤h,r,t≤1 Åã� ìîæí� çàïèñàò� êà� max v(r, t), ãä� v(r, t) − çíà÷åíè� èãð� Γrt � ìàòðèöå� 0≤r,t≤1 � 3r − 2 3 − 4r. 4 − 6t 6t − 3 Èãðî� 2, ïðèìåíÿ� ñìåøàííó� ñòðàòåãè� 1/2(1)+1/2(2) í� ïîçâîëè� èãðîê� 1 âûèãðàò� � èãð� Γrt áîëüøå, ÷å� 1/2 ïð� ëþáû� r, t. Í� èãðî� 1, èñïîëüçó� ñòðàòåãè� β = (7/12, 0, 0), îáåñïå÷èâàå� ñåá� âûèãðû� 1/2. Ñëåäîâàòåëüíî, óêàçàííû� ñòðàòåãè� îïòèìàëüí� � çíà÷åíè� èãð� v = 1/2.
14.3. � ïðîöåññ� Áðàóí� ht = ((ik , jk ), k = 1, ..., t) � p1 (j|ht ) = |{k|jk = j, 1 ≤ k ≤ t}|/t → 0 ïð� t → ∞, åñë� ñòðàòåãè� j èãðîê� 2 � òðàåêòîðè� ((it , jt ), t = 1, 2, ...) ïðèìåíÿëàñ� êîíå÷íî� ÷èñë� ðàç. 251 22. Ðåøåíè� óïðàæíåíè�15.1.
Âîçüìå� äâ� íåïåðåñåêàþùèåñ� êîàëèöè� K � T . Ïóñò� P K −ìíîæåñòâ� ñìåøàííû� ñòðàòåãè� pK êîàëèöè� K. Íåòðóäí� âèäåòü, ÷ò� P K∪T ⊃ P K × P T . Îòñþä� v(K ∪ T ) = max min pK∪T ∈P K∪T sA\(K∪T ) ∈S A\(K∪T ) ≥ max max min pK ∈P K pT ∈P T sA\(K∪T ) ∈S A\(K∪T )[u K (p K , p T , s A\(K∪T ) )++u T (p T , p K , s A\(K∪T ) )] ≥ max max pK ∈P K pT ∈P T +u K∪T (p K∪T , s A\(K∪T ) ) ≥u K (p K , s A\K )+ min sA\K ∈S A\K u T (p T , s A\T ) = v(K) + v(T ). min sA\T ∈S A\T Äîêàæå� ðàâåíñòâ� (15.1).
v(K) = max min pK ∈P K sA\K ∈S A\K = max min pK ∈P K sA\K ∈S A\K= v(A) − min [v(A) − u A\K (p K , s A\K )] = max pK ∈P K sA\K ∈S A\K = v(A) − max pA\K ∈P A\K u K (p K , s A\K ) = u A\K (p K , s A\K ) = min u A\K (p A\K , s K ) = v(A) − v(A\K). sK ∈S K 15.2. v(2) = 1, v(13) = 9, v(3) = 4, v(12) = 6.
15.3. c = 1/500, b1 = −2/5, b2 = −3/5, b3 = 0, v 0 (12) = v 0 (13) = 3/5, v 0 (23) = 7/10. � a 15.4. Çàìåòèì, ÷ò� ìíîæåñòâ� C � í� ïóñòî, � ôóíêöè� y îãðàíè÷åa∈A � í� í� íå� ñíèç� âåëè÷èíî� v(a). Îòñþä� ñëåäóåò, ÷ò� çàäà÷� ëèíåéa∈A íîã� z. Ïóñò� P a ïðîãðàììèðîâàíè� � (15.2) èìåå� îïòèìàëüíî� P ðåøåíè� 0a z ≤ v(A). Âîçüìå� òàêî� âåêòî� h ∈ C , ÷ò� h > v(A).
Òîãä� a∈Aa∈A âûïóêëà� êîìáèíàöè� λz + (1 − λ)h, ãä� λ ∈ (0, 1] îïðåäåëÿåòñ� è� óðàâíåíè� X� λz a + (1 − λ) ha = v(A), a∈Aa∈A ïðèíàäëåæè� ÿäð� C. Îáðàòíî, äîïóñòèì, ÷ò� ÿäð� C í� ïóñòî. Òîãä� (15.2) ñëåäóå� è� âêëþ÷åíè� ìíîæåñò� C ⊂ C 0 . 252 22. Ðåøåíè� óïðàæíåíè�15.5. Ïóñò� λ − çàäàííî� � óñëîâè� ïðèâåäåííî� ñáàëàíñèðîâàííî� ïîêðûòèå. Òîãä� λT ∪L = 0, ïîñêîëüê� � ïðîòèâíî� ñëó÷à� âåêòîð� χ(T ), χ(L) � χ(T ∪ L) áûë� á� ëèíåéí� çàâèñèìûìè. Èìåå� λT χ(T ) + λL χ(L) = (λT − λL )χ(T ) + λL (χ(T ) + χ(L)) = = µ T χ(T ) + µ T ∪L χ(T ∪ L). Ïîýòîì� Xµ K χ(K) = K=A6� λK χ(K) = χ(A), K=A 6� ñèñòåì� âåêòîðî� {χ(K) | µ K > 0} = {χ(K) | λK > 0} ∪ {χ(T ∪ L)}\{χ(L)} ëèíåéí� íåçàâèñèìà.
Òàêè� îáðàçîì, âåêòî� µ − ïðèâåäåííî� ñáàëàíñèðîâàííî� ïîêðûòèå. Äàëåå, λT v(T ) + λL v(L) = (λT − λL )v(T ) + λL (v(T ) + v(L)) ≤ ≤ (λT − λL )v(T ) + λL v(T ∪ L) = µ T v(T ) + µ T ∪L v(T ∪ L). Îòñþä� âûòåêàå� íåðàâåíñòâ� (15.4). 15.6. Ïðîåêöè� ÿäð� C í� ïëîñêîñò� (y 1 , y 2 ) èìåå� âè� {(y 1 , y 2 ) | v(12) ≤ y 1 + y 2 ≤ v(123) − v(3), v(1) ≤ y 1 ≤ v(123) − v(23), v(2) ≤ y 2 ≤ v(123) − v(13)} = = {(y 1 , y 2 ) | 800 ≤ y 1 + y 2 ≤ 1000, 200 ≤ y 1 ≤ 350, 300 ≤ y 2 ≤ 500}. Âåðøèí� ìíîæåñòâ� C : y(1) = (300, 500, 200), y(2) = (350, 450, 200), y(3) = (350, 500, 150).
15.7. Íåîáõîäèìîñòü. Âîçüìå� äåëå� y(0) è� ÿäð� C. Îáîçíà÷è� ÷åðå� y(k), k = 1, ..., |A| − 1, äåëåæè, ïîëó÷åííû� è� y(0) öèêëè÷åñêè� ñäâèãî� í� k êîìïîíåí� âïðàâî. Òîãä� äåëå� |A|−1 z = Xy(k)/|A| = (v|A| /|A|, ..., v|A| /|A|) k=0 ïðèíàäëåæè� ÿäð� è, ñëåäîâàòåëüíî, � a∈K z a = |K |v|A| ≥ v|K| ∀ K ⊂ A ⇒ (15.5). |A| 253 22. Ðåøåíè� óïðàæíåíè�Äîñòàòî÷íîñòü. Ïóñò� âûïîëíåí� íåðàâåíñòâ� (15.5).
Òîãä� óêàçàííû� âåêòî� z ïðèíàäëåæè� ÿäð� C. P15.8. Ïðîâåðè� ðàâåíñòâ� a∈A ϕa = = X � (|K| − 1)! (|A| − |K|)!(v(K) − v(K\{a})) = v(A). |A|! a∈A K:a∈K (22.6) Âîçüìå� êîàëèöè� K 6= A � ïîäñ÷èòàå� � ïîñëåäíå� äâîéíî� ñóìì� KKêîýôôèöèåí� cK = cK + + c− ïð� v(K). Î� âêëþ÷àå� ñóìì� c+ ïîëîæèòåëüíû� ñëàãàåìûõ, âñòðå÷àþùèõñ� ïð� âêëàäà� � êîàëèöè� K � ñóìì� cK − îòðèöàòåëüíû� ñëàãàåìûõ, âñòðå÷àþùèõñ� ïð� âêëàäà� � êîàëèöè� K ∪ {a}, ãä� a ∈/ K.
Ïîñêîëüê� êàæäû� è� èãðîêî� êîàëèöè� K èìåå� ñâî� âêëà� � K, c K + = |K|(|K| − 1)! (|A| − |K|)! |K |= C|A| .|A|! Àíàëîãè÷íî, c K − = −(|A| − |K |)|K|! (|A| − |K| − 1)! |K|= −C|A| .|A|! |A|Îòñþä� cK = 0. Åñë� K = A, ò� cA + = C|A| = 1 � ðàâåíñòâ� (22.6) äîêàçàíî. Îñòàëîñ� ïðîâåðèò� óñëîâè� ϕa ≥ v(a), ∀ a ∈ A.
Äåéñòâèòåëüíî, è� ñâîéñòâ� ñóïåðàääèòèâíîñò� õàðàêòåðèñòè÷åñêî� ôóíêöè� � ðàâåíñòâ� (15.6) ϕa = � (|K| − 1)! (|A| − |K|)!(v(K) − v(K\{a})) ≥ |A|! K:a∈K ≥ X (|K| − 1)! (|A| − |K|)! v(a) = v(a).|A|! K:a∈K 15.9. 1 111 ϕ1 = (v(123) − v(23)) + (v(12) − v(2)) + (v(13) − v(3)) + v(1),3663 1 111 ϕ2 = (v(123) − v(13)) + (v(12) − v(1)) + (v(23) − v(3)) + v(2),3663 254 22. Ðåøåíè� óïðàæíåíè�1 111 ϕ3 = (v(123) − v(12)) + (v(13) − v(1)) + (v(23) − v(2)) + v(3). 3663 � èãð� "äæàç-îðêåñòð"âåêòî� Øåïë� ϕ = (350, 475, 175).