А.А. Васин, В.В. Морозов - Введение в теорию игр с приложениями к экономике (1184512), страница 27
Текст из файла (страница 27)
� êàæäîã� èãðîê� a èìååòñ� ôóíêöè� âûèãðûø� ua (s), îïðåäåëåííà� í� ìíîæåñòâ� ñèòóàöè� S, êîòîðó� èãðî� ñòðåìèòñÿ, ï� âîçìîæíîñòè, ìàêñèìèçèðîâàòü. Òàêè� îáðàçîì, èãð� ìíîãè� ëè� � íîðìàëüíî� ôîðì� çàäàåòñ� íàáîðî� Γ = A, S a , u a (s), a ∈ A . Âàæíåéøè� ïðèíöèïî� ïðèíÿòè� ðåøåíè� � êîíôëèêòíû� ñèòóàöèÿ� ÿâëÿåòñ� ïîíÿòè� ðàâíîâåñè� ï� Íýøó.
Îïðåäåëåíèå. Ñèòóàöè� s = (sa , a ∈ A) íàçûâàåòñ� ñèòóàöèå� ðàâíîâåñè� (ðàâíîâåñèå� ï� Íýøó) èãð� Γ, åñë� max u a (s||s a ) = u a (s) ∀ a ∈ A. sa ∈S a Ñòðàòåãè� sa , ñîñòàâëÿþùè� ñèòóàöè� ðàâíîâåñèÿ, áóäå� íàçûâàò� ðàâíîâåñíûìè. Âûðàæåíè� "s||sa "÷èòàåòñ� "s ïð� óñëîâè� sa ". Îí� îáîçíà÷àå� ñèòóàöèþ, � êîòîðî� âñ� êîìïîíåíòû, êðîì� ñòðàòåãè� èãðîê� a , ñîâïàäàþ� � s , � ñòðàòåãè� èãðîê� a åñò� sa .
Îïðåäåëåíè� ðàâíîâåñè� ïîêàçûâàåò, ÷ò� ñòðàòåãè� sa , âõîäÿùà� � ñèòóàöè� s, ÿâëÿåòñ� îïòèìàëüíî� äë� èãðîê� a ïð� ôèêñèðîâàííû� ñòðàòåãèÿ� âñå� îñòàëüíû� èãðîêîâ. Òàêè� îáðàçîì, ìîæí� ñêàçàòü, ÷ò� ðàâíîâåñè� ï� Íýø� − ýò� òàêà� ñèòóàöèÿ, î� êîòîðî� í� îäíîì� è� èãðîêî� í� âûãîäí� îòêëîíÿòüñ� èíäèâèäóàëüíî. Îïèøå� îäè� êëàñ� èãð, äë� êîòîðû� ðàâíîâåñè� âñåãä� ñóùåñòâóåò.
Îïðåäåëåíèå. Ôóíêöè� h(z), îïðåäåëåííà� í� âûïóêëî� ìíîæåñòâ� Z åâêëèäîâ� ïðîñòðàíñòâà, íàçûâàåòñ� êâàçèâîãíóòîé, åñë� äë� ëþáû� z 0 , z 0� ∈ Z � ëþáîã� ÷èñë� 0 < λ < 1 âûïîëíåí� íåðàâåíñòâ� 134 12. Ðàâíîâåñè� ï� Íýøó. Ðåøåíè� èã� � íîðìàëüíî� ôîðì�h(λz � + (1 − λ)z 00 ) ≥ min[h(z 0 ), h(z 00 )]. Íåòðóäí� âèäåòü, ÷ò� ëþáà� âîãíóòà� ôóíêöè� ÿâëÿåòñ� êâàçèâîãíóòîé. Ïðèìåðî� êâàçèâîãíóòî� ôóíêöè� í� ïðÿìî� ìîæå� ñëóæèò� ïðîèçâîëüíà� âîçðàñòàþùà� (èë� óáûâàþùà� ) ôóíêöèÿ. Îïðåäåëåíèå.
Ïóñò� z 0 ∈ Z. Äë� ôóíêöè� h(z), îïðåäåëåííî� í� Z , ìíîæåñòâ� âèä� Z + (z 0 ) = {z ∈ Z | h(z) ≥ h(z 0 )} íàçûâàþòñ� ìíîæåñòâàì� Ëåáåãà. Óïðàæíåíè� 12.1. Äë� òîã� ÷òîá� ôóíêöè� h(z) áûë� êâàçèâîãíóòî� í� âûïóêëî� ìíîæåñòâ� Z, íåîáõîäèì� � äîñòàòî÷íî, ÷òîá� å� ìíîæåñòâ� Ëåáåã� Z + (z 0 ) áûë� âûïóêëûì� ïð� ëþáû� z 0 ∈ Z. Äîêàæèòå. Ïóñò� Z1 � Z2 − âûïóêëû� êîìïàêò� åâêëèäîâû� ïðîñòðàíñòâ. Îïðåäåëè� òî÷å÷íî-ìíîæåñòâåííî� îòîáðàæåíè� Φ : Z1 → 2Z2 , ñîïîñòàâëÿþùå� êàæäîì� z ∈ Z1 êîìïàê� Φ(z) ⊆ Z2 . Îïðåäåëåíèå. Òî÷å÷íî-ìíîæåñòâåííî� îòîáðàæåíè� Φ : Z1 → 2Z2 íàçûâàåòñ� âûïóêëîçíà÷íûì, åñë� ïð� êàæäî� z ∈ Z1 ìíîæåñòâ� Φ(z) âûïóêëî. Îí� íàçûâàåòñ� çàìêíóòûì, åñë� åã� ãðàôè� {(z, y) | z ∈ Z1 , y ∈ Φ(z)} − çàìêíóòî� ìíîæåñòâî, ò.å.
äë� ëþáû� ïîñëåäîâàòåëüíîñòå� {z n ∈ Z1 } � {y n ∈ Φ(z n )}, òàêèõ, ÷ò� z n → z 0 � y n → y 0 , íåîáõîäèì� y 0 ∈ Φ(z 0 ). � ÷àñòíî� ñëó÷à� Φ ìîæå� áûò� ïðîñò� îòîáðàæåíèå� è� Z � Z. Òîãä� ñâîéñòâ� çàìêíóòîñò� îòîáðàæåíè� Φ ñîâïàäàå� ñ� ñâîéñòâî� íåïðåðûâíîñòè. Òàêè� îáðàçîì, ïðåäûäóùå� îïðåäåëåíè� îáîáùàå� ïîíÿòè� íåïðåðûâíîñò� äë� òî÷å÷íî-ìíîæåñòâåííû� îòîáðàæåíèé. Òåîðåì� 12.1 (Êàêóòàíè). Ïóñò� Z − âûïóêëû� êîìïàê� êîíå÷íîìåðíîã� åâêëèäîâ� ïðîñòðàíñòâà, � Φ : Z → 2Z − çàìêíóòî� âûïóêëîçíà÷íî� òî÷å÷íî-ìíîæåñòâåííî� îòîáðàæåíèå. Òîãä� ñóùåñòâóå� íåïîäâèæíà� òî÷ê� z 0 îòîáðàæåíè� Φ, ò.å. z 0 ∈ Φ(z 0 ).
Äîêàæå� òåîðåì� äë� Z ⊂ E 1 . � äàííî� ñëó÷à� � ñîîòâåòñòâè� � óñëîâèå� òåîðåì� Z − îòðåçî� [a, b]. Ðàññìîòðè� ìíîæåñòâ� Ẑ = {z ∈ˆ Ïóñò� Z | max Φ(z) ≥ z}. Ýò� ìíîæåñòâ� íåïóñòî, òà� êà� a ∈ Z. 0 0 0z = sup Z � ïîêàæåì, ÷ò� z ∈ Φ(z ). Äåéñòâèòåëüíî, max Φ(z 0 ) ≥ z 0 , òà� êà� Φ(z) − çàìêíóòî� îòîáðàæåíèå. Äîêàæåì, ÷ò� min Φ(z 0 ) ≤ z 0 .
Åñë� z 0 = b, ò� óòâåðæäåíè� î÷åâèäíî. Ïóñò� z 0 < b. Ðàññìîòðè� ïîñëåäîâàòåëüíîñò� {z k }, ñõîäÿùóþñ� � z 0 � äë� êîòîðî� z k > z 0 , k = 1, 2, .... 135ÃËÀÂ� III. ÈÃÐ� ÌÍÎÃÈ� ËÈ�Ï� îïðåäåëåíè� z 0 äë� íå� max Φ(z k ) < z k , k = 1, 2, .... Ïîýòîì� íàéäåòñ� òàêà� ïîñëåäîâàòåëüíîñò� {y k ∈ Φ(z k )}, ÷ò� y k < z k , k = 1, 2, .... Áå� ïîòåð� îáùíîñò� ìîæí� ñ÷èòàòü, ÷ò� ïîñëåäîâàòåëüíîñò� {y k } ñõîäèòñ� � y 0 ≤ z 0 . Ïîñêîëüê� Φ(z) − çàìêíóòî� îòîáðàæåíèå, y 0 ∈ Φ(z 0 ) � min Φ(z 0 ) ≤ z 0 . Îòñþä� z 0 ∈ Φ(z 0 ). Äîêàçàòåëüñòâ� òåîðåì� Êàêóòàí� � îáùå� ñëó÷à� îñíîâàí� í� òåîðåì� Áðàóýð� � ñîäåðæèòñ� � Ïðèëîæåíè� (Ï3).
Òåîðåì� 12.2. Ïóñò� � èãð� Γ ìíîæåñòâ� S a − âûïóêëû� êîìïàêò� åâêëèäîâû� ïðîñòðàíñòâ, � ôóíêöè� ua (s) íåïðåðûâí� í� S � êâàçèâîãíóò� ï� sa (ïð� ëþáû� ôèêñèðîâàííû� sb ∈ S b , b ∈ A\{a}). Òîãä� � èãð� Γ ñóùåñòâóå� ñèòóàöè� ðàâíîâåñèÿ. Äîêàçàòåëüñòâî. Îïðåäåëè� òî÷å÷íî-ìíîæåñòâåííî� îòîáðàæåíè� Φ : S → 2S ñëåäóþùè� îáðàçîì: ëþáî� ñèòóàöè� s ∈ S ïîëîæè� � äë� a bΦ(s) = Φ (s , b ∈ A\{a}), ãä� a∈A def Φa (sb , b ∈ A\{a}) = Arg max ua (s||ha ) aa h ∈S− ìíîæåñòâ� íàèëó÷øè� îòâåòî� èãðîê� a í� ñòðàòåãè� sb , b ∈ A\{a}, îñòàëüíû� èãðîêîâ.
Íåòðóäí� ïðîâåðèòü, ÷ò� îòîáðàæåíè� Na a b Φ : S → 2Sb∈A\{a} çàìêíóò� (ñì. çàìå÷àíè� � òåîðåì� 2.2) � âûïóêëîçíà÷íî. Ïîýòîì� îòîáðàæåíè� Φ óäîâëåòâîðÿå� óñëîâèÿ� òåîðåì� 12.1 � èìåå� íåïîäâèæíó� òî÷ê� s ∈ Φ(s), êîòîðà� � áóäå� ðàâíîâåñèå� ï� Íýø� � èãð� Γ. Ñìåøàííî� ðàñøèðåíè� èãð� Ïóñò� � èãð� Γ ìíîæåñòâ� ñòðàòåãè� èãðîêî� êîíå÷íû: S a = {1, ..., ma }, a ∈ A. Ñòðàòåãè� sa , âõîäÿùè� � S a , íàçûâàþòñ� ÷èñòûì� ñòðàòåãèÿì� èãðîê� a.
Cìåøàííà� ñòðàòåãè� èãðîê� a îïðåäåëÿåòñ� a a êà� âåðîÿòíîñòíî� ðàñïðåäåëåíè� π a = (π1 a , ..., πma ), ãä� πsa − âåðîÿòíîñò� âûáîð� ÷èñòî� ñòðàòåãè� sa ∈ S a � êà÷åñòâ� ðåàëüíî� ñòðàòåãè� èãðîê� a. Ìíîæåñòâ� ñìåøàííû� ñòðàòåãè� èãðîê� a − ýò� ñèìïëåê� maPa Πa = {π a = (π1 a , ..., πmπsa a = 1, πsa a ≥ 0, sa = 1, ..., ma }. a ) | sa =1 Äë� çàäàííîã� íàáîð� ñìåøàííû� ñòðàòåãè� N a π = (π a , a ∈ A) ∈ Π = Πa∈A 136 12. Ðàâíîâåñè� ï� Íýøó. Ðåøåíè� èã� � íîðìàëüíî� ôîðì�def îïðåäåëè� p(s|π) = � πsa a − âåðîÿòíîñò� ðåàëèçàöè� ñèòóàöè� a∈A s = (sa , a ∈ A).
Òîãä� ìàòåìàòè÷åñêî� âûèãðûø� èãðîê� a P îæèäàíè� áóäå� çàäàâàòüñ� ôóíêöèå� ua (π) = p(s|π)ua (s). Òàêè� îáðàçîì, ñìås∈S øàííî� ðàñøèðåíè� èãð� Γ � íîðìàëüíî� ôîðì� èìåå� âè� Γ = A, Πa , u a (π), a ∈ A . Ñèòóàöè� ðàâíîâåñè� èãð� Γ áóäå� íàçûâàò� ñèòóàöèÿì� ðàâíîâåñè� � ñìåøàííû� ñòðàòåãèÿ� èãð� Γ èë� ñìåøàííûì� ðàâíîâåñèÿì� ï� Íýøó. Êàæäà� ôóíêöè� ua (π), î÷åâèäíî, íåïðåðûâí� ï� π � ëèíåéí� ï� π a ïð� ëþáû� ôèêñèðîâàííû� π b , b ∈ A\{a}.
Ïîýòîì� è� òåîðåì� 12.2 âûòåêàå� ñëåäóþùè� ðåçóëüòàò. Òåîðåì� 12.3. � ëþáî� èãð� Γ � êîíå÷íûì� ìíîæåñòâàì� ñòðàòåãè� ñóùåñòâóå� ñìåøàííî� ðàâíîâåñè� ï� Íýøó. Äë� àíàëèç� � âû÷èñëåíè� ñìåøàííîã� ðàâíîâåñè� ï� Íýø� ïîëåçí� ñëåäóþùå� óòâåðæäåíèå. Óòâåðæäåíè� 12.1. Äë� òîã� ÷òîá� ñèòóàöè� π = (π a , a ∈ A) áûë� ñìåøàííû� ðàâíîâåñèå� ï� Íýøó, íåîáõîäèì� � äîñòàòî÷íî, ÷òîá� max u a (π||s a ) = u a (π) ∀ a ∈ A. sa ∈S a Áîëå� òîãî, ua (π||sa ) = ua (π) äë� ëþáî� òàêî� ñòðàòåãè� sa , ÷ò� π asa > 0.
Äîêàçàòåëüñòâ� ýòîã� óòâåðæäåíè� ïîëíîñòü� àíàëîãè÷í� äîêàçàòåëüñòâà� ëåìì� 10.1 � òåîðåì� 10.1. Ïðèìå� 12.1. Êàæäî� è� òðå� ïðåäïðèÿòèé, èñïîëüçóþùè� âîä� è� ïðèðîäíîã� âîäîåìà, ðàñïîëàãàþ� äâóì� ñòðàòåãèÿìè: ñòðîèò� ñîîðóæåíè� äë� ïîëíî� î÷èñòê� îòðàáîòàííî� âîä� (ñòðàòåãè� 1) èë� æ� ñáðàñûâàò� å� ÷åðå� èìåþùèåñ� î÷èñòíû� ñîîðóæåíè� áå� áèîëîãè÷åñêî� î÷èñòê� (ñòðàòåãè� 2). Ïðåäïîëàãàåòñÿ, ÷ò� îñîáåííîñò� âîäîåì� � òåõíîëîãè÷åñêè� ïðîöåññî� òàêîâû, ÷ò� � ñëó÷àå, êîãä� í� ïîëíîñòü� î÷èùåííó� âîä� ñáðàñûâàå� í� áîëå� îäíîã� ïðåäïðèÿòèÿ, âîä� � âîäîåì� îñòàåòñ� ïðèãîäíî� äë� èñïîëüçîâàíè� � ïðåäïðèÿòè� óáûòê� í� íåñóò.
Åñë� æ� í� ïîëíîñòü� î÷èùåííó� âîä� ñáðàñûâàþ� í� ìåíå� äâó� ïðåäïðèÿòèé, ò� 137ÃËÀÂ� III. ÈÃÐ� ÌÍÎÃÈ� ËÈ�êàæäû� ïîëüçîâàòåë� âîä� íåñå� óáûòê� � ðàçìåð� òðå� åäèíèö. Íàéäå� âñ� ñèòóàöè� ðàâíîâåñè� � ÷èñòû� � ñìåøàííû� ñòðàòåãèÿ� îïèñàííî� èãð� òðå� ëèö. Èñõîäíà� èãð� Γ ïðåäñòàâëåí� � òàáë. 12.1. Òàáë.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
