[учебник] Введение в теорию игр (с приложениями к экономике). Васин, Морозов (2003) ([учебник] Введение в теорию игр (с приложениями к экономике). Васин, Морозов (2003).pdf), страница 4

Çäåñü ïðèìåðîì ñìåøàííîé ñòðàòåãèè ìîæåò ñëóæèòü âåðîÿòíîñòíàÿ ìåðà, ñîñðå18Ÿ 3. Ñìåøàííûå ðàñøèðåíèÿ àíòàãîíèñòè÷åñêèõ èãðäîòî÷åííàÿ â êîíå÷íîì ÷èñëå òî÷åê:ϕ(x) =mXpi Ix(i) (x),i=1mXpi = 1, pi ≥ 0, x(i) ∈ X, i = 1, ..., m,i=1ãäå(1, x = x(i) ,Ix(i) (x) =0, x =6 x(i) .Îòìåòèì, ÷òî äëÿ ëþáîãî áîðåëåâñêîãî ìíîæåñòâà B ϕ(B) =Ppi .i:x(i) ∈BÏðè èñïîëüçîâàíèè ìåðû ϕ ñòðàòåãèÿ x(i) âûáèðàåòñÿ ñ âåðîÿòíîñòüþ pi .Èíòåãðàë îò íåïðåðûâíîé ôóíêöèè h(x) ïî ðàññìàòðèâàåìîé ìåðå èìååòâèäZmXh(x)dϕ(x) =pi h(x(i) ).i=1XÎáîçíà÷èì ÷åðåç {ϕ} − ìíîæåñòâî âñåõ ñìåøàííûõ ñòðàòåãèé ïåðâîãî èãðîêà íà ìíîæåñòâå X. Ìîæíî ñ÷èòàòü, ÷òî X ⊂ {ϕ}. Äåéñòâèòåëüíî,â ïîñëåäíåì ñëó÷àå ñòðàòåãèþ x ìîæíî îòîæäåñòâèòü ñ âåðîÿòíîñòíîéìåðîé Ix .

Åñëè ìíîæåñòâî X êîíå÷íî, òî âûáîð i ýêâèâàëåíòåí âûáîðóñìåøàííîé ñòðàòåãèè p = (0, ..., 0, 1, 0, ..., 0), ãäå åäèíèöà ñòîèò íà i-ì ìåñòå, à ïðè X = [a, b] ñòðàòåãèþ x ∈ [a, b] ìîæíî îòîæäåñòâèòü ñ ôóíêöèåéðàñïðåäåëåíèÿ, èìåþùåé ñêà÷îê 1 â òî÷êå x.Ìíîæåñòâî X áóäåì íàçûâàòü ìíîæåñòâîì ÷èñòûõ ñòðàòåãèé ïåðâîãîèãðîêà (â ïðîòèâîâåñ ñìåøàííûì).Çàéìåìñÿ ïîñòðîåíèåì ñìåøàííîãî ðàñøèðåíèÿ àíòàãîíèñòè÷åñêîé èãðû Γ = X, Y, F (x, y) . Ìû îïðåäåëèëè ìíîæåñòâî {ϕ} ñìåøàííûõñòðàòåãèé ïåðâîãî èãðîêà. Àíàëîãè÷íî, ïóñòü {ψ} − ìíîæåñòâî ñìåøàííûõ ñòðàòåãèé âòîðîãî èãðîêà, ò.å.

âåðîÿòíîñòíûõ ðàñïðåäåëåíèé ψ íàìíîæåñòâå Y åãî ÷èñòûõ ñòðàòåãèé. Ïðè çàäàííûõ ñòðàòåãèÿõ ϕ è ψìàòåìàòè÷åñêîå îæèäàíèå âûèãðûøà ïåðâîãî èãðîêà îïðåäåëÿåòñÿ ôîðìóëîéZ ZF (ϕ, ψ) =F (x, y)dϕ(x)dψ(y).X YÇäåñü ïðåäïîëàãàåòñÿ, ÷òî äâîéíîé èíòåãðàë ñóùåñòâóåò.Îïðåäåëåíèå. Àíòàãîíèñòè÷åñêàÿ èãðàΓ = {ϕ}, {ψ}, F (ϕ, ψ)19ÃËÀÂÀ I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛíàçûâàåòñÿ ñìåøàííûì ðàñøèðåíèåì èãðû Γ.Îïðåäåëåíèå. Ðåøåíèå (ϕ0 , ψ 0 , v = F (ϕ0 , ψ 0 )) èãðû Γ íàçûâàåòñÿ ðåøåíèåì èñõîäíîé èãðû Γ â ñìåøàííûõ ñòðàòåãèÿõ.

Ïðè ýòîì ϕ0 , ψ 0 íàçûâàþòñÿ îïòèìàëüíûìè ñìåøàííûìè ñòðàòåãèÿìè èãðîêîâ, à v − çíà÷åíèåì èãðû Γ.Äàëåå áóäóò ïîñòðîåíû ñìåøàííûå ðàñøèðåíèÿ ìàòðè÷íûõ è íåïðåðûâíûõ èãð è áóäåò ïîêàçàíî, ÷òî ýòè èãðû âñåãäà èìåþò ðåøåíèå âñìåøàííûõ ñòðàòåãèÿõ.Íàïîìíèì, ÷òî ìàòðè÷íàÿ èãðà Γ çàäàåòñÿ ìàòðèöåé A = (aij )m×n .Ìíîæåñòâî ñìåøàííûõ ñòðàòåãèé ïåðâîãî èãðîêà −P = {p = (p1 , ..., pm ) |mXpi = 1, pi ≥ 0, i = 1, ..., m},i=1ìíîæåñòâî ñìåøàííûõ ñòðàòåãèé âòîðîãî èãðîêà −Q = {q = (q1 , ..., qn ) |nXqj = 1, qj ≥ 0, j = 1, ..., n},j=1à ìàòåìàòè÷åñêîå îæèäàíèå âûèãðûøà ïåðâîãî èãðîêà −A(p, q) =m XnXpi aij qj .i=1 j=1Òàêèì îáðàçîì, Γ = P, Q, A(p, q) − ñìåøàííîå ðàñøèðåíèå ìàòðè÷íîéèãðû Γ.Òåîðåìà 3.1 (Îñíîâíàÿ òåîðåìà ìàòðè÷íûõ èãð).

Âñÿêàÿ ìàò-ðè÷íàÿ èãðà èìååò ðåøåíèå â ñìåøàííûõ ñòðàòåãèÿõ.Äîêàçàòåëüñòâî. Äîñòàòî÷íî äîêàçàòü ,÷òî ôóíêöèÿ A(p, q) èìååòñåäëîâóþ òî÷êó íà P ×Q. Ìíîæåñòâà P, Q − ìíîãîãðàííèêè åâêëèäîâûõïðîñòðàíñòâ, à ôóíêöèÿ A(p, q) áèëèíåéíà è ïîýòîìó íåïðåðûâíà íà P ×Q, âîãíóòà ïî p è âûïóêëà ïî q . Ïî òåîðåìå 2.3 ôóíêöèÿ A(p, q) èìååòíà P × Q ñåäëîâóþ òî÷êó.Óïðàæíåíèå 3.1. Ïîêàæèòå, ÷òî òðîéêà(p0 , q 0 , v) = ((1/2, 1/2), (1/2, 1/2), 0)− ðåøåíèå â ñìåøàííûõ ñòðàòåãèÿõ èãðû "îðëÿíêà".Îòìåòèì òèïè÷íûå ñëó÷àè, êîãäà ïðèìåíÿþòñÿ ñìåøàííûå ñòðàòåãèè.20Ÿ 3.

Ñìåøàííûå ðàñøèðåíèÿ àíòàãîíèñòè÷åñêèõ èãð1) Èãðà ïîâòîðÿåòñÿ ìíîãî ðàç.  ýòîì ñëó÷àå çà áîëüøîå ÷èñëî ïîâòîðåíèé èãðû ñðåäíèé âûèãðûø ïåðâîãî èãðîêà, èñïîëüçóþùåãî îïòèìàëüíóþ ñìåøàííóþ ñòðàòåãèþ, áóäåò áëèçîê ê çíà÷åíèþ èãðû èëè áóäåò ïðåâûøàòü åãî.2) Ñìåøàííàÿ ñòðàòåãèÿ ðåàëèçóåòñÿ â âèäå "ôèçè÷åñêîé ñìåñè"÷èñòûõñòðàòåãèé. ×òî ýòî îçíà÷àåò, ïîÿñíèì íà ïðèìåðàõ.Ïðèìåð 3.2.

Èãðà ïðîòèâ ïðèðîäû. Ôåðìåð (èãðîê 1 ) èìååò ó÷àñòîêçåìëè, êîòîðûé ìîæíî çàñåÿòü òðåìÿ ñåëüñêîõîçÿéñòâåííûìè êóëüòóðàìè. Ãîä ìîæåò áûòü íîðìàëüíûì, çàñóøëèâûì è äîæäëèâûì (ýòî òðèñòðàòåãèè èãðîêà 2 − ïðèðîäû). Ïóñòü H = (hij )3×3 − ìàòðèöà óðîæàéíîñòè, à bi − öåíà çà åäèíèöó ïðîäóêöèè i-ãî âèäà. Òîãäà A = (bi hij )3×3 −ìàòðèöà èãðû, ãäå âûèãðûø ôåðìåðà − ñòîèìîñòü ïðîèçâåäåííîé ïðîäóêöèè. Ïóñòü p0 = (1/2, 1/4, 1/4) − îïòèìàëüíàÿ ñìåøàííàÿ ñòðàòåãèÿïåðâîãî èãðîêà.

Ðåàëèçîâàòü åå ìîæíî, çàñåÿâ ïîëîâèíó ó÷àñòêà ïåðâîéêóëüòóðîé, à îñòàâøèåñÿ äâå ÷åòâåðòè − âòîðîé è òðåòüåé êóëüòóðàìè.Ïðèìåð 3.3. Íåêîòîðàÿ ñòðàíà (èãðîê 1) èñïîëüçóåò òðè òèïà èñòðåáèòåëåé äëÿ áîðüáû ñ ñàìîëåòàìè ïðîòèâíèêà (èãðîêà 2). Åñëè èñòðåáèòåëüòèïà i ïåðâîãî èãðîêà âñòðå÷àåòñÿ ñ ñàìîëåòîì òèïà j âòîðîãî èãðîêà,òî îí ïîáåæäàåò ïðîòèâíèêà ñ âåðîÿòíîñòüþ aij . Ñìåøàííàÿ ñòðàòåãèÿp0 = (1/2, 1/4, 1/4) ïåðâîãî èãðîêà ìîæåò áûòü ðåàëèçîâàíà â âèäå ïàðêàèñòðåáèòåëåé ñ ïðîïîðöèÿìè òèïîâ 2:1:1.3) Ñìåøàííûå ñòðàòåãèè ìîæíî ïðèìåíÿòü è ïðè îäíîêðàòíîì ïîâòîðåíèè èãðû, êîãäà èãðîê äåéñòâóåò â óñëîâèÿõ ðèñêà. Ïðè ýòîì íåîáõîäèìî âûèãðûøè çàìåíèòü íà èõ "ïîëåçíîñòè", ó÷èòûâàþùèå îòíîøåíèåèãðîêà ê ðèñêó.ÏðèìåðÏóñòü èãðîê âûíóæäåí îäèí ðàç ñûãðàòü â èãðó ñ ìàòðè 3.4.

10 0öåé A =. Âûèãðûøàì 10 è 0 ïðèïèøåì ïîëåçíîñòè 1 è 0. Îïðå0 5äåëèì ïîëåçíîñòü âûèãðûøà 5. Ïóñòü â íåêîòîðîé ëîòåðåå âûèãðûø 10îæèäàåòñÿ ñ âåðîÿòíîñòüþ 0 < a < 1. Ïåðâîìó èãðîêó ïðåäëàãàåòñÿ âûáðàòü òàêîå çíà÷åíèå a, ïðè êîòîðîì èãðîê ñîãëàñåí êóïèòü ëîòåðåéíûéáèëåò ïî öåíå 5. Âûáðàííîå çíà÷åíèå a è áóäåò ïîëåçíîñòüþ âûèãðûøà5. Åñëè a = 1/2, òî îòíîøåíèå èãðîêà ê ðèñêó íåéòðàëüíîå, åñëè a > 1/2,òî èãðîê îñòîðîæåí, à åñëè a < 1/2, òî èãðîê àçàðòåí.Ýëåìåíòû òåîðèè ïîëåçíîñòè ñì. â êîíöå äàííîãî ïàðàãðàôà.Çàéìåìñÿ ñìåøàííûì ðàñøèðåíèåì íåïðåðûâíîé èãðû Γ. Îãðàíè21ÃËÀÂÀ I.

ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛ÷èìñÿ èãðîé íà ïðÿìîóãîëüíèêå X × Y = [a, b] × [c, d]. Ïðè çàäàííûõñòðàòåãèÿõ ϕ è ψ − ôóíêöèÿõ ðàñïðåäåëåíèÿ íà îòðåçêàõ X è Y − îæèäàåìûé âûèãðûø F (ϕ, ψ) ïåðâîãî èãðîêà ðàâåíZb ZdF (ϕ, ψ) =F (x, y)dϕ(x)dψ(y).acÇäåñü äâîéíîé èíòåãðàë îò íåïðåðûâíîé ôóíêöèè F (x, y) ñóùåñòâóåò.Áîëåå òîãî, ïî òåîðåìå Ôóáèíè îí ðàâåí ïîâòîðíîìóZbF (ϕ, ψ) =ZdF (x, ψ)dϕ(x) =aF (ϕ, y)dψ(y),cãäåZdF (x, ψ) =ZbF (x, y)dψ(y), F (ϕ, y) =cF (x, y)dϕ(x).aÈòàê, ïîñòðîåíî cìåøàííîå ðàñøèðåíèå Γ = {ϕ}, {ψ}, F (ϕ, ψ) íåïðåðûâíîé èãðû Γ íà ïðÿìîóãîëüíèêå.

Íàøà áëèæàéøàÿ öåëü − äîêàçàòüñóùåñòâîâàíèå ðåøåíèÿ èãðû Γ.Íàì ïîòðåáóåòñÿ èçâåñòíûé ðåçóëüòàò.Òåîðåìà 3.2. Ìíîæåñòâî ñìåøàííûõ ñòðàòåãèé {ϕ} íà îòðåçêå [a, b]ÿâëÿåòñÿ ñëàáûì êîìïàêòîì. Ýòî îçíà÷àåò, ÷òî èç ëþáîé ïîñëåäîâàòåëüíîñòè ñìåøàííûõ ñòðàòåãèé {ϕk } ìîæíî âûäåëèòü ïîäïîñëåäîâàòåëüíîñòü {ϕkl }, ñëàáî ñõîäÿùóþñÿ ê íåêîòîðîé ñòðàòåãèè ϕ0 , ò.å.

òàêóþ, ÷òîäëÿ ëþáîé íåïðåðûâíîé íà îòðåçêå [a, b] ôóíêöèè h(x) âûïîëíåíîZbliml→∞h(x)dϕkl (x) =aZbh(x)dϕ0 (x).aËåììà 3.1.  íåïðåðûâíîé èãðå Γ íà ïðÿìîóãîëüíèêå ñóùåñòâóþòìàêñèìèííàÿ è ìèíèìàêñíàÿ ñìåøàííûå ñòðàòåãèè èãðîêîâ.Äîêàçàòåëüñòâî. Ðàññìîòðèì âûðàæåíèÿv = sup inf F (ϕ, ψ), v = infϕ∈{ϕ} ψ∈{ψ}sup F (ϕ, ψ)ψ∈{ψ} ϕ∈{ϕ}22Ÿ 3. Ñìåøàííûå ðàñøèðåíèÿ àíòàãîíèñòè÷åñêèõ èãðè äîêàæåì, ÷òî âíåøíèå sup è inf â íèõ äîñòèãàþòñÿ. Ïî îïðåäåëåíèþâåðõíåé ãðàíè v íàéäåòñÿ òàêàÿ ïîñëåäîâàòåëüíîñòü ñìåøàííûõ ñòðàòåãèé {ϕk }, ÷òîinf F (ϕk , ψ) ≥ v − εk , εk → 0+,ψ∈{ψ}èëèZF (x, ψ)dϕk (x) ≥ v − εk ∀ ψ ∈ {ψ}, k = 1, 2, ....(3.1)XÂûäåëèì èç {ϕk } ïîäïîñëåäîâàòåëüíîñòü {ϕkl }, ñëàáî ñõîäÿùóþñÿ êñìåøàííîé ñòðàòåãèè ϕ0 .

Çàìåòèì, ÷òî ïðè ôèêñèðîâàííîé ñòðàòåãèè ψôóíêöèÿ F (x, ψ) íåïðåðûâíà ïî x. Ïåðåõîäÿ â (3.1) ê ïðåäåëó ïî ïîäïîñëåäîâàòåëüíîñòè {kl }, ïîëó÷èì íåðàâåíñòâî F (ϕ0 , ψ) ≥ v ∀ ψ ∈ {ψ}.Îòñþäàinf F (ϕ0 , ψ) ≥ v ⇒ inf F (ϕ0 , ψ) = vψ∈{ψ}ψ∈{ψ}è ϕ0 − ìàêñèìèííàÿ ñìåøàííàÿ ñòðàòåãèÿ ïåðâîãî èãðîêà. Àíàëîãè÷íîäîêàçûâàåòñÿ ñóùåñòâîâàíèå ìèíèìàêñíîé ñìåøàííîé ñòðàòåãèè.Ëåììà 3.2.

Ðàññìîòðèì äâå àíòàãîíèñòè÷åñêèå èãðûΓ = X, Y, F (x, y) , Γ = X, Y, F 0 (x, y) ,â êîòîðûõ ôóíêöèè F (x, y) è F 0 (x, y) îãðàíè÷åíû íà X × Y è ïðè ε > 0âûïîëíåíî óñëîâèå|F (x, y) − F 0 (x, y)| ≤ ε ∀ (x, y) ∈ X × Y.Òîãäà |v − v 0 | ≤ ε, |v − v 0 | ≤ ε.Äîêàçàòåëüñòâî. Äëÿ âñÿêîãî x ∈ X ñïðàâåäëèâû íåðàâåíñòâàinf F (x, y) − inf F 0 (x, y) ≥ inf (F (x, y) − F 0 (x, y)) ≥ −ε.y∈Yy∈Yy∈YÌîæíî ïîëó÷èòü àíàëîãè÷íûå íåðàâåíñòâà, ìåíÿÿ ìåñòàìè ôóíêöèèF (x, y) è F 0 (x, y).  ðåçóëüòàòå íàõîäèì, ÷òî| inf F (x, y) − inf F 0 (x, y)| ≤ ε ∀x ∈ X.y∈Yy∈YÄàëåå,sup inf F (x, y) − sup inf F 0 (x, y) ≤ sup( inf F (x, y) − inf F 0 (x, y)) ≤ ε.x∈X y∈Yx∈X y∈Yx∈X y∈Y23y∈YÃËÀÂÀ I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛÊàê è âûøå, íàõîäèì, ÷òî |v − v 0 | ≤ ε.

Àíàëîãè÷íî äîêàçûâàåòñÿ íåðàâåíñòâî |v − v 0 | ≤ ε.Òåîðåìà 3.3 (Îñíîâíàÿ òåîðåìà íåïðåðûâíûõ èãð). Âñÿêàÿíåïðåðûâíàÿ èãðà Γ íà ïðÿìîóãîëüíèêå èìååò ðåøåíèå â ñìåøàííûõñòðàòåãèÿõ.Äîêàçàòåëüñòâî. Ïî òåîðåìå 2.1 äîñòàòî÷íî äîêàçàòü ðàâåíñòâî âåëè÷èí v = max inf F (ϕ, ψ) è v = min sup F (ϕ, ψ).ϕ∈{ϕ} ψ∈{ψ}ψ∈{ψ} ϕ∈{ϕ}Çàìåòèì, ÷òî äîñòèæèìîñòü çäåñü âíåøíèõ ìàêñèìóìîâ è ìèíèìóìîâ âûòåêàåò èç ëåììû 3.1.

Âîçüìåì ïðîèçâîëüíîå ε > 0. Èç íåïðåðûâíîñòè ôóíêöèè F (x, y) ñëåäóåò ñóùåñòâîâàíèå òàêîãî ðàçáèåíèÿ îòðåçêàX = [a, b] íà íåïåðåñåêàþùèåñÿ ïðîìåæóòêè (îòðåçîê è ïîëóèíòåðâàëû)X i , i = 1, ..., m è òàêîãî ðàçáèåíèÿ îòðåçêà Y = [c, d] íà àíàëîãè÷íûåïðîìåæóòêè Y j , j = 1, ..., n, ÷òî|F (x, y) − F (x0 , y 0 )| ≤ ε ∀ (x, y), (x0 , y 0 ) ∈ X i × Y j , ∀ i, j.(3.2)Äëÿ ëþáûõ i, j âîçüìåì òî÷êè xi ∈ X i , y j ∈ Y j è îïðåäåëèì ñòóïåí÷àòóþ ôóíêöèþF1 (x, y) = F (xi , y j ) ∀ (x, y) ∈ X i × Y j , i = 1, ..., m, j = 1, ..., n.Òîãäà èç (3.2) ñëåäóåò, ÷òî|F (x, y) − F1 (x, y)| ≤ ε ∀ (x, y) ∈ X × Y.(3.3)Èòàê, ôóíêöèÿ F1 (x, y) àïïðîêñèìèðóåò ôóíêöèþ F (x, y) ñ òî÷íîñòüþ äîε > 0. Íåïðåðûâíàÿ èãðà Γ ôàêòè÷åñêè ïðèáëèæåíà èãðîé ñ ìàòðèöåé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.