Введение в теорию игр (сторонняя методичка) (1184510), страница 24
Текст из файла (страница 24)
Ïðåäïîëàãàåòñÿ, ÷òî îñîáåííîñòè âîäîåìà è òåõíîëîãè÷åñêèõ ïðîöåññîâ òàêîâû, ÷òî â ñëó÷àå, êîãäà íå ïîëíîñòüþ î÷èùåííóþâîäó ñáðàñûâàåò íå áîëåå îäíîãî ïðåäïðèÿòèÿ, âîäà â âîäîåìå îñòàåòñÿïðèãîäíîé äëÿ èñïîëüçîâàíèÿ è ïðåäïðèÿòèÿ óáûòêà íå íåñóò. Åñëè æå íåïîëíîñòüþ î÷èùåííóþ âîäó ñáðàñûâàþò íå ìåíåå äâóõ ïðåäïðèÿòèé, òî137ÃËÀÂÀ III. ÈÃÐÛ ÌÍÎÃÈÕ ËÈÖêàæäûé ïîëüçîâàòåëü âîäû íåñåò óáûòêè â ðàçìåðå òðåõ åäèíèö. Íàéäåìâñå ñèòóàöèè ðàâíîâåñèÿ â ÷èñòûõ è ñìåøàííûõ ñòðàòåãèÿõ îïèñàííîéèãðû òðåõ ëèö.Èñõîäíàÿ èãðà Γ ïðåäñòàâëåíà â òàáë. 12.1.Òàáë.
12.1.s111112222s211221122s312121212u1 (s) u2 (s) u3 (s)-1-1-1-1-10-10-1-4-3-30-1-1-3-4-3-3-3-4-3-3-3Ïîñòðîèì ñìåøàííîå ðàñøèðåíèå Γ. Ïóñòü pa ∈ [0, 1], a = 1, 2, 3, −âåðîÿòíîñòü, ñ êîòîðîé ïðåäïðèÿòèå a âûáèðàåò ñòðàòåãèþ 1. Âîçìîæíûåñèòóàöèè â èãðå Γ ñîñòàâëÿþò ìíîæåñòâîΠ = {π = (p1 , p2 , p3 ) | pa ∈ [0, 1], a = 1, 2, 3}.Ôóíêöèÿ âûèãðûøà ïåðâîãî ïðåäïðèÿòèÿ â èãðå Γu1 (π) = p1 [−p2 p3 − p2 (1 − p3 ) − (1 − p2 )p3 − 4(1 − p2 )(1 − p3 )]++(1 − p1 )[−3p2 (1 − p3 ) − 3(1 − p2 )p3 − 3(1 − p2 )(1 − p3 )] == (−6p2 p3 + 3p2 + 3p3 − 1)p1 + 3p2 p3 − 3 = k 1 (p2 , p3 )p1 + l1 (p2 , p3 ).Àíàëîãè÷íî,u2 (π) = k 2 (p1 , p3 )p2 + l2 (p1 , p3 ), u3 (π) = k 3 (p1 , p2 )p3 + l3 (p1 , p2 ),ãäål1 (p2 , p3 ) = 3p2 p3 − 3, l2 (p1 , p3 ) = 3p1 p3 − 3, l3 (p1 , p2 ) = 3p1 p2 − 3,k 1 (p2 , p3 ) = −6p2 p3 + 3p2 + 3p3 − 1, k 2 (p1 , p3 ) = −6p1 p3 + 3p1 + 3p3 − 1,k 3 (p1 , p2 ) = −6p1 p2 + 3p1 + 3p2 − 1.138 12.
Ðàâíîâåñèå ïî Íýøó. Ðåøåíèå èãð â íîðìàëüíîé ôîðìåÏóñòü π = (pa , a = 1, 2, 3) − ïðîèçâîëüíàÿ ñèòóàöèÿ ðàâíîâåñèÿ. Ïîëîæèì123k = k 1 (p2 , p3 ), k = k 2 (p1 , p3 ), k = k 1 (p1 , p2 ).aaÇàìåòèâ, ÷òî åñëè k > 0, òî pa = 1, à åñëè k < 0, òî pa = 0, ðàññìîòðèìâñå âîçìîæíûå ñëó÷àè.aaÏóñòü k > 0, a = 1, 2, 3; òîãäà pa = 1 è k = −1 − ïðîòèâîðå÷èå.a3Ïóñòü k > 0, a = 1, 2, k < 0.
 ýòîì ñëó÷àå ñèòóàöèÿ ðàâíîâåñèÿ(1,1,0). Àíàëîãè÷íî, (1,0,1) è (0,1,1) − òàêæå ñèòóàöèè ðàâíîâåñèÿ.1231Ïóñòü k > 0, k , k < 0. òîãäà p1 = 1 è p2 = p3 = 0, k = −1 −ïðîòèâîðå÷èå.Àíàëîãè÷íî, íåò è äðóãèõ ñèòóàöèé ðàâíîâåñèÿ, ñîîòâåòñòâóþùèõañëó÷àþ îäíîé ïîëîæèòåëüíîé è äâóõ îòðèöàòåëüíûõ âåëè÷èí k .aÏóñòü k < 0, a = 1, 2, 3; òîãäà ñèòóàöèÿ ðàâíîâåñèÿ (0,0,0).aÏóñòü k = 0, a = 1, 2, 3. Ðåøàÿ ïîëó÷åííóþ ñèñòåìó, íàéäåì äâåñèòóàöèè√ ðàâíîâåñèÿ:√√√√√((3 − 3)/6, (3 − 3)/6, (3 − 3)/6) è ((3 + 3)/6, (3 + 3)/6, (3 + 3)/6).a3Ïóñòü k = 0, a = 1, 2, k > 0; òîãäà p3 = 1. Ðåøàÿ ñîîòâåòñòâóþùóþañèñòåìó, ïîëó÷àåì ñèòóàöèþ ðàâíîâåñèÿ (2/3, 2/3, 1).
Åñëè k = 0, a =331, 2, k < 0, òî p3 = 0, p1 = p2 = 1/3, k = 1/3 − ïðîòèâîðå÷èå.Àíàëîãè÷íî, (1, 2/3, 2/3) è (2/3, 1, 2/3) − ñèòóàöèè ðàâíîâåñèÿ.Íàêîíåö, ðàññóæäàÿ àíàëîãè÷íî, óáåæäàåìñÿ, ÷òî íåò ñèòóàöèé ðàâaíîâåñèÿ, ñîîòâåòñòâóþùèõ îäíîé èç âåëè÷èí k , ðàâíîé íóëþ, è äâóì,îòëè÷íûì îò íóëÿ.Èòàê, â èãðå Γ äåâÿòü ñèòóàöèé ðàâíîâåñèÿ â ÷èñòûõ è ñìåøàííûõñòðàòåãèÿõ.Äîìèíèðîâàíèå â èãðàõ ìíîãèõ ëèöÏîíÿòèÿ è ðåçóëüòàòû î äîìèíèðîâàíèè ñòðàòåãèé â èãðàõ äâóõ ëèö,èçëîæåííûå â 10., ëåãêî îáîáùàþòñÿ íà èãðû ìíîãèõ ëèö Γ.Îïðåäåëåíèå.
Áóäåì ãîâîðèòü, ÷òî ñòðàòåãèÿ ha ñòðîãî äîìèíèðóåòñòðàòåãèþ g a (ha g a ) íà ìíîæåñòâå ñèòóàöèé S ⊆ S, åñëè âûïîëíåíîíåðàâåíñòâî ua (s||ha ) ≥ ua (s||g a ) ∀ s ∈ S. Áóäåì ãîâîðèòü î ñëàáîìäîìèíèðîâàíèè (ha g a ), åñëè ua (s||ha ) ≥ ua (s||g a ) ∀ s ∈ S.Îïðåäåëåíèå. Áóäåì ãîâîðèòü, ÷òî ìíîæåñòâî S ñòðîãî (ñîîòâåòñòâåííî ñëàáî) äîìèíèðóåò ìíîæåñòâî S (îáîçíà÷àåòñÿ S S è S S ñîîòâåòñòâåííî), åñëè îíî ìîæåò áûòü ïîëó÷åíî èç S â ðåçóëüòàòå ïî139ÃËÀÂÀ III.
ÈÃÐÛ ÌÍÎÃÈÕ ËÈÖñëåäîâàòåëüíîãî èñêëþ÷åíèÿ ñòðîãî (ñîîòâåòñòâåííî ñëàáî) äîìèíèðóåìûõ ñòðàòåãèé, ò.å. ñóùåñòâóåò ïîñëåäîâàòåëüíîñòü âëîæåííûõ ìíîæåñòâS = S1 ⊃ S2 ⊃ ... ⊃ Sk = S , äëÿ êîòîðîé ïðè ëþáîì l = 1, ..., k − 1 âûïîëíåíûóñëîâèÿ:N ñëåäóþùèåaaSl =Sl è äëÿ ëþáûõ a ∈ A, g a ∈ Sla \Sl+1íàéäåòñÿ òàêàÿ ñòðàòåãèÿa∈Aaha ∈ Sl+1, ÷òî ha g a (ha g a ) íà Sl .Ïðîöåäóðà ïîñëåäîâàòåëüíîãî èñêëþ÷åíèÿ äîìèíèðóåìûõ (â ñòðîãîìèëè ñëàáîì ñìûñëå) ñòðàòåãèé ñîñòîèò â ñëåäóþùåì. Íà ïåðâîì øàãå âûÿñíÿåì äëÿ êàæäîãî èãðîêà, êàêèå ñòðàòåãèè ÿâëÿþòñÿ äîìèíèðóåìûìèíà ìíîæåñòâå âñåõ ñèòóàöèé S1 = S è âûáðàñûâàåì èõ. Ïîëó÷àåì ñóæåííîå ìíîæåñòâî S2 .
Òåïåðü ñòðàòåãèè, êîòîðûå íå áûëè äîìèíèðóåìûìèíà ìíîæåñòâå S1 , ìîãóò îêàçàòüñÿ äîìèíèðóåìûìè íà ìíîæåñòâå S2 . Íàñëåäóþùåì øàãå ìû èõ âûêèäûâàåì, ïîëó÷àåì ìíîæåñòâî S3 è ò.ä.Îïðåäåëåíèå. Áóäåì ãîâîðèòü, ÷òî èãðà Γ ðàçðåøèìà ïî äîìèíèðîâàíèþ, åñëè äëÿ íåêîòîðîãî ñëàáî äîìèíèðóþùåãî ìíîæåñòâà S äëÿ êàæäîãî a ∈ A ôóíêöèÿ ua (s) íå çàâèñèò îò sa íà S, ò.å. äëÿ ëþáûõ s ∈ S èaha ∈ S ua (s) = ua (s||ha ).Îïðåäåëåíèå. Áóäåì ãîâîðèòü, ÷òî ñìåøàííàÿ ñòðàòåãèÿ π a ñòðîãîäîìèíèðóåò ñòðàòåãèþ g a (π a g a ) íà ìíîæåñòâå ñèòóàöèé S ⊆ S, åñëèâûïîëíåíî íåðàâåíñòâî ua (s||π a ) > ua (s||g a ) ∀ s ∈ S.
Áóäåì ãîâîðèòü îñëàáîì äîìèíèðîâàíèè (π a g a ), åñëèua (s||π a ) ≥ ua (s||g a ) ∀ s ∈ S.Îïðåäåëåíèå. Áóäåì ãîâîðèòü, ÷òî ìíîæåñòâî S ñòðîãî (ñîîòâåòñòâåííî ñëàáî) äîìèíèðóåò ìíîæåñòâî S â ñìåøàííûõ ñòðàòåãèÿõ (îáîçíà÷àåòñÿ S S è S S ñîîòâåòñòâåííî), åñëè ñóùåñòâóåò ïîñëåäîâàòåëüíîñòüâëîæåííûõ ìíîæåñòâ S = S1 ⊃ S2 ⊃ ...
⊃ Sk = S , äëÿ êîòîðîé ïðè ëþáîìl = 1, N..., k − 1 âûïîëíåíû ñëåäóþùèå óñëîâèÿ:aSl =Sla è äëÿ ëþáûõ a ∈ A, g a ∈ Sla \Sl+1íàéäåòñÿ òàêàÿ ñòðàòåãèÿa∈Aaaπ a ∈ Sl+1, ÷òî π a g a (π a g a ) íà Sl è πsaa = 0 ∀ sa ∈/ Sl+1.Ñëåäóþùåå óòâåðæäåíèå àíàëîãè÷íî òåîðåìåN 10.4.Òåîðåìà 12.4. 1) Ïóñòü ìíîæåñòâî S̃ =S̃ a ñòðîãî äîìèíèðóåòa∈Aìíîæåñòâî S â ñìåøàííûõ ñòðàòåãèÿõ. Òîãäà äëÿ ëþáîãî ñìåøàííîãîðàâíîâåñèÿ ïî Íýøó π = (π a , a ∈ A) âûïîëíåíî óñëîâèå:äëÿ ëþáûõ a ∈ A è sa ∈/ S̃ a íåîáõîäèìî π asa = 0.140 12. Ðàâíîâåñèå ïî Íýøó. Ðåøåíèå èãð â íîðìàëüíîé ôîðìå2) Ïóñòü ìíîæåñòâî S̃ =NS̃ a ñëàáî äîìèíèðóåò ìíîæåñòâî S â ñìå-a∈Aøàííûõ ñòðàòåãèÿõ èD π̃ = (π̃saa , sa ∈ S̃ a , aE∈ A) − ñìåøàííîå ðàâíîâåñèåïî Íýøó â èãðå Γ̃ = A, S̃ a , ua (s), a ∈ A ñ ñîêðàùåííûìè ìíîæåñòâàìè ñòðàòåãèé. Îïðåäåëèì ñèòóàöèþ â ñìåøàííûõ ñòðàòåãèÿõ π èñõîäíîéèãðû Γ : äëÿ ëþáîãî a ∈ A(π̃saa , åñëè sa ∈ S̃ a ,π asa =0,åñëè sa ∈/ S̃ a .Òîãäà π − ðàâíîâåñèå ïî Íýøó â èñõîäíîé èãðå Γ.Ìîäåëè èãðîâîé äèíàìèêèÌîäåëè ýòîãî òèïà ðàçâèòû êàê àëüòåðíàòèâà ñòàòè÷åñêèì ïðèíöèïàì îïòèìàëüíîñòè (òàêèì, êàê ðàâíîâåñèå ïî Íýøó, ðåøåíèÿ ïî äîìèíèðîâàíèþ).
Óêàçàííûå ïðèíöèïû ïðèíÿòèÿ ðåøåíèÿ òðåáóþò äëÿ ñâîåéðåàëèçàöèè ïîëíîé èíôîðìèðîâàííîñòè èãðîêîâ îòíîñèòåëüíî óñëîâèéèãðû (ò.å. îòíîñèòåëüíî ìíîæåñòâ ñòðàòåãèé è ôóíêöèé âûèãðûøà âñåõó÷àñòíèêîâ). Áîëåå òîãî, èãðîêè äîëæíû áûòü ðàöèîíàëüíû â ïðèíÿòèè ñîáñòâåííûõ ðåøåíèé è ïðåäïîëàãàòü òàêóþ æå ðàöèîíàëüíîñòü îòñâîèõ ïàðòíåðîâ. Ðàññìàòðèâàåìûå äèíàìè÷åñêèå ìîäåëè ïðåäúÿâëÿþòçíà÷èòåëüíî ìåíüøå òðåáîâàíèé ê èíôîðìèðîâàííîñòè è ðàöèîíàëüíîñòè èãðîêîâ è áîëüøå ïîõîæè íà ðåàëüíûå ìåòîäû ïðèíÿòèÿ ðåøåíèé.÷òî Ïðåäïîëîæèì, êîíôëèêòíàÿ ñèòóàöèÿ îïèñûâàåòñÿ èãðîé Γ =A, S a , ua (s), a ∈ A ñ êîíå÷íûìè ìíîæåñòâàìè ñòðàòåãèé S a , a ∈ A.Ïóñòü èãðà ïîâòîðÿåòñÿ â ïåðèîäû âðåìåíè t = 1, 2, ....
Êàæäûé èãðîêâûáèðàåò ñòðàòåãèþ sa (t + 1) íà ïåðèîä (øàã) t + 1, èñõîäÿ èç èñòîðèèht = {s(τ ) = (sa (τ ), a ∈ A)}τ ≤t , ñëîæèâøåéñÿ ê ýòîìó ïåðèîäó. Áåñêîíå÷íóþ ïîñëåäîâàòåëüíîñòü ñèòóàöèé {s(t)} áóäåì íàçûâàòü òðàåêòîðèåéïðîöåññà. Îáîçíà÷èì ÷åðåç H ìíîæåñòâîS t âñåâîçìîæíûõ èñòîðèé, ò.å.H = {h }.t≥1Ïðàâèëî ïîâåäåíèÿ èãðîêàçàäàåòñÿ îòîáðàæåíèåì â aýòîì ïðîöåññåaaµ : H → S . Ñîâîêóïíîñòü Γ; µ , a ∈ A íàçûâàåòñÿ äåòåðìèíèðîâàííûì èãðîâûì ïðîöåññîì.Îïðåäåëèì ïîíÿòèå àäàïòèâíîãî ïîâåäåíèÿ.
Ñìûñë åãî ñîñòîèò â òîì,÷òî èãðîê ïðîãíîçèðóåò âåðîÿòíîñòè ðåàëèçàöèè ñòðàòåãèé ïàðòíåðîâsA\{a} = (sb , b ∈ A\{a}), èñõîäÿ èç ïðåäûñòîðèè, è ìàêñèìèçèðóåò ñîáñòâåííûé âûèãðûø íà îñíîâàíèè òàêîãî ïðîãíîçà.  êà÷åñòâå ïðèìåðà141ÃËÀÂÀ III. ÈÃÐÛ ÌÍÎÃÈÕ ËÈÖðàññìîòðèì ìîäåëü íàèëó÷øèõ îòâåòîâ.Ïðîöåññ íà÷èíàåòñÿ ñ âûáîðà èãðîêàìè ïðîèçâîëüíûõ ñòðàòåãèéas (1), a ∈ A. Äàëåå ïîñëå t øàãîâ íà ñëåäóþùåì, (t + 1)-ì øàãåsa (t + 1) ∈ Arg maxua (s(t)||sa ), a ∈ A.aas ∈SÒàêèì îáðàçîì, èãðîê ìàêñèìèçèðóåò ñîáñòâåííûé âûèãðûø, èñõîäÿ èçïðåäïîëîæåíèÿ, ÷òî äðóãèå èãðîêè íå ìåíÿþò ñâîèõ ñòðàòåãèé ïî ñðàâíåíèþ ñ ïðåäûäóùèì øàãîì. áîëåå îáùåì ñëó÷àå ïðåäïîëîæåíèÿ î ïîâåäåíèè ïàðòíåðîâ â ìîìåíò âðåìåíè t + 1 ìîæíîíàáîðîì ïàðàìåòðîâPõàðàêòåðèçîâàòüaa{λt,τ ≥ 0}τ ≤t , òàêèì, ÷òîλt,τ = 1. Èãðîê a ñ÷èòàåò, ÷òî ñ âåðîÿòíîñòüþτ ≤tλat,τ â ìîìåíò t + 1 ïîâòîðèòñÿ íàáîð ñòðàòåãèé äðóãèõ èãðîêîâ sA\{a} (τ ),ñëó÷èâøèéñÿ â ìîìåíò τ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
