Введение в теорию игр (сторонняя методичка) (Введение в теорию игр (сторонняя методичка).PDF), страница 5
Описание файла
PDF-файл из архива "Введение в теорию игр (сторонняя методичка).PDF", который расположен в категории "". Всё это находится в предмете "теория игр и исследование операций" из 9 семестр (1 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 5 страницы из PDF
Íåïðåðûâíàÿ èãðà Γ ôàêòè÷åñêè ïðèáëèæåíà èãðîé ñ ìàòðèöåéA = (aij )m×n = (F (xi , y j ))m×n .Âñÿêîé ñìåøàííîé ñòðàòåãèè ϕ ïîñòàâèì â ñîîòâåòñòâèå âåêòîðZp = (p1 , ..., pm ) : pi = dϕ(x), i = 1, ..., m,Xiãäå pi − âåðîÿòíîñòü ïîïàäàíèÿ ðåàëèçàöèè ñìåøàííîé ñòðàòåãèè â ìíîæåñòâî X i (ìåðà ìíîæåñòâà X i ). Î÷åâèäíî, ÷òî p ÿâëÿåòñÿ ñìåøàííîéñòðàòåãèåé ïåðâîãî èãðîêà â ìàòðè÷íîé èãðå, ò.å. p ∈ P.
Ïîñòðîåííîåîòîáðàæåíèå P : {ϕ} → P ÿâëÿåòñÿ îòîáðàæåíèåì íà P. Äåéñòâèòåëüíî, äëÿ ëþáîé ñòðàòåãèè p ∈ P ôóíêöèÿ ðàñïðåäåëåíèÿ ϕ ñî ñêà÷êàìè24 3. Ñìåøàííûå ðàñøèðåíèÿ àíòàãîíèñòè÷åñêèõ èãðpi â òî÷êàõ xi ÿâëÿåòñÿ ïðîîáðàçîì p ïðè îòîáðàæåíèè P . Àíàëîãè÷íîîïðåäåëÿåòñÿ îòîáðàæåíèå Q : {ψ} → Q, ãäå Q − ìíîæåñòâî ñìåøàííûõñòðàòåãèé âòîðîãî èãðîêà ìàòðè÷íîé èãðû. Äàëåå, äëÿ ëþáûõ ñòðàòåãèéϕ, ψ è ñîîòâåòñòâóþùèõ ñòðàòåãèé p = P(ϕ), q = Q(ψ) ñïðàâåäëèâàôîðìóëàF1 (ϕ, ψ) =Zb Zd=F1 (x, y)dϕ(x)dψ(y) =am XnXpi F (xi , y j )qj = A(p, q).(3.4)i=1 j=1cÊðîìå òîãî, èñïîëüçóÿ (3.3), ïîëó÷èìZb Zd|F (ϕ, ψ) − F1 (ϕ, ψ)| = |(F (x, y) − F1 (x, y))dϕ(x)dψ(y)| ≤acZb Zd≤Zb Zd|F (x, y) − F1 (x, y)|dϕ(x)dψ(y) ≤acεdϕ(x)dψ(y) = ε.acÏîñëåäíåå íåðàâåíñòâî îçíà÷àåò, ÷òî äëÿ ôóíêöèé F (ϕ, ψ), F1 (ϕ, ψ) âûïîëíåíû óñëîâèÿ ëåììû 3.2. Èç íåå âûòåêàþò íåðàâåíñòâà| max inf F (ϕ, ψ) − max min F1 (ϕ, ψ)| ≤ ε,(3.5)| min sup F (ϕ, ψ) − min max F1 (ϕ, ψ)| ≤ ε.(3.6)ϕ∈{ϕ} ψ∈{ψ}ψ∈{ψ} ϕ∈{ϕ}ϕ∈{ϕ} ψ∈{ψ}ψ∈{ψ} ϕ∈{ϕ}Èç (3.4) è îñíîâíîé òåîðåìû ìàòðè÷íûõ èãð ñëåäóåò, ÷òîmax min F1 (ϕ, ψ) = max min A(p, q) =p∈P q∈Qϕ∈{ϕ} ψ∈{ψ}= min max A(p, q) = min max F1 (ϕ, ψ).q∈Q p∈Pψ∈{ψ} ϕ∈{ϕ}Îòñþäà è èç íåðàâåíñòâ (3.5),(3.6) ñëåäóåò |v − v| ≤ 2ε.
 ñèëó ïðîèçâîëüíîñòè ε > 0 ïîëó÷àåì v = v.Ýëåìåíòû òåîðèè ïîëåçíîñòèÏðàâîìåðíîñòü èñïîëüçîâàíèÿ ìàòåìàòè÷åñêîãî îæèäàíèÿ âûèãðûøà â ñìåøàííîì ðàñøèðåíèè èãðû âûçûâàåò ñîìíåíèÿ. Êîãäà èãðîêè25ÃËÀÂÀ I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛïðèìåíÿþò çàäàííûå ñìåøàííûå ñòðàòåãèè, òî âûèãðûø êàæäîãî ÿâëÿåòñÿ ñëó÷àéíîé âåëè÷èíîé ñ çàäàííûì çàêîíîì ðàñïðåäåëåíèÿ.  òåîðèèïîëåçíîñòè òàêóþ âåëè÷èíó íàçûâàþò ëîòåðååé.
Ôîðìàëüíî îíà çàäàåòñÿ íàáîðîì ïàðàìåòðîâ (A1 , ..., Ak ; x1 , ..., xk ), ãäå âûèãðûø Al âîçíèêàåòkPñ âåðîÿòíîñòüþ xl , l = 1, ..., k, èxl = 1.l=1Óïðàæíåíèå 3.2. Óêàçàòü ïàðàìåòðû ëîòåðåè, êîòîðàÿ ñîîòâåòñòâóåòïàðå ñìåøàííûõ ñòðàòåãèé (p, q) â ìàòðè÷íîé èãðå.Îöåíêà èñõîäà ëþáîé èãðû ïî ìàòåìàòè÷åñêîìó îæèäàíèþ ïðåäïîëàãàåò, ÷òî ëîòåðåè (0; 1), ($5000, $ − 5000; 1/2, 1/2) è(−1ðóá.,10000 ðóá.;10000/10001,1/10001) ýêâèâàëåíòû äëÿ èíäèâèäóóìà.Ìîæíî ïðåäïîëîæèòü, ÷òî äëÿ ìíîãèõ ÷èòàòåëåé ýòî íå òàê.
Äàëåêî íåâñå ìîãóò ñåáå ïîçâîëèòü ñûãðàòü âî âòîðóþ ëîòåðåþ, äàæå åñëè íåñêîëüêî óâåëè÷èòü ðàçìåð âûèãðûøà.  òî æå âðåìÿ çíà÷èòåëüíàÿ ÷àñòü íàñåëåíèÿ ó÷àñòâóåò â ëîòåðåÿõ, ïîäîáíûõ òðåòüåé, äàæå ïðè îòðèöàòåëüíîìñðåäíåì âûèãðûøå: ìíîãèå ãîòîâû ðèñêíóòü ìàëåíüêîé ñóììîé â ðàñ÷åòå íà ñ÷àñòëèâûé ñëó÷àé. Âîîáùå, îòíîøåíèå ëþäåé ê ðèñêó äîñòàòî÷íîñëîæíî è íå äî êîíöà èññëåäîâàíî.
Åãî èçó÷åíèåì çàíèìàåòñÿ òåîðèÿïîëåçíîñòè (â ýêîíîìèêå ôóíêöèè âûèãðûøà îáû÷íî íàçûâàþò ôóíêöèÿìè ïîëåçíîñòè).Îäèí èç âàæíåéøèõ ðåçóëüòàòîâ ýòîé òåîðèè ñîñòîèò â ñëåäóþùåì.Ïðåäïîëîæèì, ÷òî ó èíäèâèäóóìà åñòü îòíîøåíèå ïðåäïî÷òåíèÿ íà ìíîæåñòâå âñåâîçìîæíûõ ëîòåðåé, ò.å. äëÿ ëþáûõ äâóõ ëîòåðåé L1 , L2 îí ìîæåò óêàçàòü, êàêîå èç ñîîòíîøåíèé ( ïðè÷åì òîëüêî îäíî) âûïîëíÿåòñÿ:L1 L2 (L1 ïðåäïî÷òèòåëüíåé L2 ), L2 L1 èëè L1 ∼ L2 (ëîòåðåè ýêâèâàëåíòíû). Ïóñòü ýòè ñîîòíîøåíèÿ óäîâëåòâîðÿþò ñëåäóþùèì (äîâîëüíîåñòåñòâåííûì) àêñèîìàì:I. Åñëè L1 L2 è L2 L3 , òî L1 L3 .II. Åñëè L1 ∼ L2 è L2 ∼ L3 , òî L1 ∼ L3 .III. Åñëè L1 ∼ L2 è L2 L3 , òî L1 L3 .IV. Åñëè L1 L2 è L2 ∼ L3 , òî L1 L3 .V. Ëîòåðåè, êîòîðûì ñîîòâåòñòâóåò îäèíàêîâîå ðàñïðåäåëåíèå âåðîÿòíîñòåé, ÿâëÿþòñÿ ýêâèâàëåíòíûìè.Ïóñòü L1 , L2 − äâå ëîòåðåè, 0 ≤ r ≤ 1.
Îáîçíà÷èì ÷åðåçrL1 + (1 − r)L2 ëîòåðåþ, â êîòîðîé c âåðîÿòíîñòüþ r ðàçûãðûâàåòñÿ ëîòåðåÿ L1 , à ñ âåðîÿòíîñòüþ 1 − r − ëîòåðåÿ L2 .26 3. Ñìåøàííûå ðàñøèðåíèÿ àíòàãîíèñòè÷åñêèõ èãðÈç àêñèîìû V âûòåêàåò, ÷òî äëÿ ëþáûõ ëîòåðåé L1 , L2 , L3 è âåðîÿòíîñòåé r, s ñïðàâåäëèâû ñîîòíîøåíèÿrL1 + (1 − r)L2 ∼ (1 − r)L2 + rL1 ,rL1 + (1 − r)(L2 + (1 − s)L3 ) ∼ rL1 + (1 − r)L2 + (1 − r)(1 − s)L3 .V I. Åñëè L1 ∼ L2 (L1 L2 ), òî äëÿ ëþáîé ëîòåðåè L3 è ëþáîé âåðîÿòíîñòè r > 0 âûïîëíåíî ñîîòíîøåíèårL1 + (1 − r)L3 ∼ rL2 + (1 − r)L3 (rL1 + (1 − r)L3 rL2 + (1 − r)L3 ).V II.
Åñëè L1 L2 L3 , òî íàéäåòñÿ òàêàÿ âåðîÿòíîñòü r, ÷òî rL1 +(1 − r)L3 ∼ L2 .Àêñèîìà V II ïîõîæà íà òåîðåìó î ïðîìåæóòî÷íîì çíà÷åíèè äëÿíåïðåðûâíîé ôóíêöèè íà îòðåçêå è îçíà÷àåò, ÷òî îòíîøåíèå ïðåäïî÷òåíèÿ íåïðåðûâíî â íåêîòîðîì ñìûñëå. Ïóñòü, íàêîíåö, ñïðàâåäëèâààêñèîìàV III. Åñëè Al > Ah , òî (Al ; 1) (Ah ; 1).Ëåììà 3.3. Ïóñòü íà ìíîæåñòâå ëîòåðåé ïðåäïî÷òåíèå èíäèâèäóóìàóäîâëåòâîðÿåò àêñèîìàì I − V III è L1 L2 .
Òîãäà äëÿ ëþáûõ âåðîÿòíîñòåé β < α âûïîëíåíî ñîîòíîøåíèå αL1 + (1 − α)L2 βL1 + (1 − β)L2 .Äîêàçàòåëüñòâî. Ïî àêñèîìå V I ïðè L3 = L2 ïîëó÷àåìαL1 + (1 − α)L2 L2 . Ïðåäñòàâèì β â âèäå β = γα, ãäå γ ∈ [0, 1). Òîãäàïî àêñèîìàì V I è VαL1 + (1 − α)L2 γ(αL1 + (1 − α)L2 ) + (1 − γ)L2 ∼∼ γαL1 + [γ(1 − α) + 1 − γ]L2 ∼ βL1 + (1 − β)L2 .Òåîðåìà 3.4. Ïðè âûïîëíåíèè óêàçàííûõ àêñèîì I −V III ñóùåñòâó-åò ôóíêöèÿ ïîëåçíîñòè u(L), îïðåäåëåííàÿ íà ìíîæåñòâå ëîòåðåé âèäà(A1 , ..., Ak ; x1 , ..., xk ) è òàêàÿ, ÷òî âûïîëíåíû ñëåäóþùèå ñâîéñòâà:1) Äëÿ ëþáûõ ëîòåðåé L1 , L2 u(L1 ) > u(L2 ) ⇔ L1 L2 .kP2) Äëÿ ëþáîé ëîòåðåè L = (A1 , ..., Ak ; x1 , ..., xk ) u(L) =xl u(Al ).l=13) Ôóíêöèÿ u(A; 1) ìîíîòîííî âîçðàñòàåò ïî A.Áîëåå òîãî, ýòà ôóíêöèÿ åäèíñòâåííà ñ òî÷íîñòüþ äî ëèíåéíîãî ïðåîáðàçîâàíèÿ: åñëè äðóãàÿ ôóíêöèÿ v(L) óäîâëåòâîðÿåò òåì æå ñâîéñòâàì1)−3), òî ñóùåñòâóþò òàêèå êîíñòàíòû c > 0 è b, ÷òî äëÿ ëþáîé ëîòåðåèL v(L) = cu(L) + b.Óòâåðæäåíèå òåîðåìû îçíà÷àåò, ÷òî äëÿ êàæäîãî èíäèâèäóóìà (ïðèâûïîëíåíèè àêñèîì I − V III ) ñóùåñòâóåò ìîíîòîííîå ïðåîáðàçîâàíèå27ÃËÀÂÀ I.
ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛôóíêöèè âûèãðûøà, êîòîðîå ïîçâîëÿåò îöåíèâàòü ëþáóþ ëîòåðåþ, èñõîäÿ èç ìàòåìàòè÷åñêîãî îæèäàíèÿ âûèãðûøà.  ÷àñòíîñòè, åñëè â ìàòðè÷íîé èãðå âçÿòü ïðåîáðàçîâàííóþ ôóíêöèþ âûèãðûøà u(aij ), òî ñëó÷àéíûé èñõîä ïðè èñïîëüçîâàíèè ñìåøàííûõ ñòðàòåãèé p è q ìîæíîm PnPîöåíèâàòü ïî ìàòåìàòè÷åñêîìó îæèäàíèþpi u(aij )qj . Îòìåòèì, ÷òîi=1 j=1ôóíêöèÿ ïîëåçíîñòè u(L) − ñâîÿ äëÿ êàæäîãî èíäèâèäóóìà, ïîýòîìó èãðà ñ ïðåîáðàçîâàííûìè ìàòðèöàìè âûèãðûøåé (u1 (aij )) è (u2 (aij )) âïîëíåìîæåò îêàçàòüñÿ íåàíòàãîíèñòè÷åñêîé.Óïðàæíåíèå 3.3. Äîêàæèòå òåîðåìó 3.4.Óêàçàíèå.
Áåç ïîòåðè îáùíîñòè ìîæíî ñ÷èòàòü, ÷òî A1 A2 ... Ak . Ïîëîæèì u(A1 ) = r1 = 1, u(Ak ) = rk = 0, à âåëè÷èíû u(Al ) = rl , l =2, ..., k − 1 îïðåäåëèì èç ñîîòíîøåíèé rl (A1 ) + (1 − rl )Al ∼ Al , 0 < rl < 1,èñïîëüçóÿ àêñèîìó V II. Ñ ïîìîùüþ ëåììû 3.3 ïîêàæèòå, ÷òî ôóíêöèÿkPu(L) = u(A1 , ..., Ak ; x1 , ..., xk ) =x l rll=1óäîâëåòâîðÿåò âñåì óòâåðæäåíèÿì òåîðåìû. 4.Ñâîéñòâà ðåøåíèé â ñìåøàííûõ ñòðàòåãèÿõ äàííîì ïàðàãðàôå ðàññìàòðèâàþòñÿ ñâîéñòâà ðåøåíèé â ñìåøàííûõ ñòðàòåãèÿõ ìàòðè÷íûõ èãð è íåïðåðûâíûõ èãð íà ïðÿìîóãîëüíèêå.Ýòè ñâîéñòâà â ÷àñòíûõ ñëó÷àÿõ ïîçâîëÿþò íàõîäèòü îïòèìàëüíûå ñìåøàííûå ñòðàòåãèè.Òåîðåìà 4.1. Äëÿ òîãî ÷òîáû òðîéêà (ϕ0 , ψ 0 , v) áûëà ðåøåíèåì âñìåøàííûõ ñòðàòåãèÿõ íåïðåðûâíîé èãðû Γ, íåîáõîäèìî è äîñòàòî÷íî,÷òîáû áûëî âûïîëíåíî óñëîâèåF (x, ψ 0 ) ≤ v ≤ F (ϕ0 , y) ∀ x ∈ X, ∀ y ∈ Y.(∗)Äîêàçàòåëüñòâî.
Íåîáõîäèìîñòü. Ïóñòü (ϕ0 , ψ 0 , v) − ðåøåíèå íåïðåðûâíîé èãðû â ñìåøàííûõ ñòðàòåãèÿõ. Òîãäà v = F (ϕ0 , ψ 0 ) è ïî îïðåäåëåíèþ ñåäëîâîé òî÷êèF (ϕ, ψ 0 ) ≤ F (ϕ0 , ψ 0 ) = v ≤ F (ϕ0 , ψ) ∀ ϕ ∈ {ϕ}, ∀ ψ ∈ {ψ}.Âîçüìåì â ïîñëåäíèõ íåðàâåíñòâàõ âìåñòî ϕ è ψ ÷èñòûå ñòðàòåãèè x èy.  ðåçóëüòàòå ïîëó÷èì óñëîâèå (∗).28 4. Ñâîéñòâà ðåøåíèé â ñìåøàííûõ ñòðàòåãèÿõÄîñòàòî÷íîñòü. Ïóñòü äëÿ òðîéêè (ϕ0 , ψ 0 , v) âûïîëíåíî óñëîâèå (∗).Ïðîèíòåãðèðóåì ïåðâîå íåðàâåíñòâî ýòîãî óñëîâèÿ ïî ëþáîé ñòðàòåãèèϕ, à âòîðîå − ïî ëþáîé ñòðàòåãèè ψ è ïîëó÷èìF (ϕ, ψ 0 ) ≤ v ≤ F (ϕ0 , ψ) ∀ ϕ ∈ {ϕ}, ∀ ψ ∈ {ψ}.Ïîäñòàâëÿÿ, â ÷àñòíîñòè, ϕ = ϕ0 è ψ = ψ 0 , íàõîäèì, ÷òî F (ϕ0 , ψ 0 ) = v èïàðà (ϕ0 , ψ 0 ) − ñåäëîâàÿ òî÷êà ôóíêöèè F (ϕ, ψ) íà {ϕ} × {ψ}.Îòìåòèì, ÷òî òåîðåìà 4.1 ñïðàâåäëèâà äëÿ ïðîèçâîëüíûõ ñìåøàííûõðàñøèðåíèé àíòàãîíèñòè÷åñêèõ èãð.Ñôîðìóëèðóåì àíàëîãè÷íóþ òåîðåìó äëÿ ìàòðè÷íûõ èãð.Òåîðåìà 4.1 0 .
Äëÿ òîãî ÷òîáû òðîéêà (p0 , q 0 , v) áûëà ðåøåíèåì âñìåøàííûõ ñòðàòåãèÿõ èãðû ñ ìàòðèöåé A, íåîáõîäèìî è äîñòàòî÷íî,÷òîáû áûëî âûïîëíåíî óñëîâèåA(i, q 0 ) ≤ v ≤ A(p0 , j), i = 1, ...m, j = 1, ..., m.(∗)Óïðàæíåíèå 4.1. Äîêàæèòå òåîðåìó 4.1 0 .Îòìåòèì, ÷òî ïðîâåðêà âûïîëíåíèÿ óñëîâèÿ (∗) òåîðåìû 4.1 0 ñâîäèòñÿ ê ïîäñ÷åòó ñêàëÿðíûõ ïðîèçâåäåíèé âåêòîðà p0 íà ñòîëáöû, à òàêæåâåêòîðà q 0 íà ñòðîêè ìàòðèöû A è ñðàâíåíèþ èõ ñ ÷èñëîì v.Ïðèìåð 4.1. Ïóñòü ìàòðèöà èãðûc1 c2cn c1A= ... ...c2 ...− öèêëè÷åñêàÿ:... cn...
cn−1 .... ... cn c1Ïîêàæåì, ÷òî p0 = q 0 = (1/n, ..., 1/n), v =nPk=1ck /n − ðåøåíèå èãðûâ ñìåøàííûõ ñòðàòåãèÿõ. Äåéñòâèòåëüíî, óñëîâèå (∗) çäåñü âûïîëíåíî,ïîñêîëüêó âñå íåðàâåíñòâà â íåì âûïîëíåíû êàê ðàâåíñòâà.  êà÷åñòâåêîíêðåòíîãî ïðèìåðà ðàññìîòðèì èãðó "ìåøîê, êàìåíü, íîæíèöû"ñ ìàòðèöåéM KHM01 −101 .A = K −1H1 −1029ÃËÀÂÀ I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛÌîæíî äàòü ñëåäóþùóþ èíòåðïðåòàöèþ ýòîé èãðû. Äâîå âûáèðàþòîäèí èç òðåõ ïðåäìåòîâ: ìåøîê, êàìåíü èëè íîæíèöû. Êàæäûé ïðåäìåòïðîòèâ ñàìîãî ñåáÿ íèêàêîãî âûèãðûøà íå äàåò, ïîýòîìó íà äèàãîíàëèñòîÿò 0. Íîæíèöû òóïÿòñÿ î êàìåíü, ïîýòîìó îíè ïðîèãðûâàþò êàìíþ 1,à òîò â ñâîþ î÷åðåäü âûèãðûâàåò ó íîæíèö 1.