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

Èç íåå âûòåêàþò íåðàâåíñòâà| 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 c2cn c1A= ... ...c2 ...− öèêëè÷åñêàÿ:... cn... cn−1 .... ... cn c1Ïîêàæåì, ÷òî p0 = q 0 = (1/n, ..., 1/n), v =nPk=1ck /n − ðåøåíèå èãðûâ ñìåøàííûõ ñòðàòåãèÿõ. Äåéñòâèòåëüíî, óñëîâèå (∗) çäåñü âûïîëíåíî,ïîñêîëüêó âñå íåðàâåíñòâà â íåì âûïîëíåíû êàê ðàâåíñòâà.  êà÷åñòâåêîíêðåòíîãî ïðèìåðà ðàññìîòðèì èãðó "ìåøîê, êàìåíü, íîæíèöû"ñ ìàòðèöåéM KHM01 −101 .A = K  −1H1 −1029ÃËÀÂÀ I. ÀÍÒÀÃÎÍÈÑÒÈ×ÅÑÊÈÅ ÈÃÐÛÌîæíî äàòü ñëåäóþùóþ èíòåðïðåòàöèþ ýòîé èãðû. Äâîå âûáèðàþòîäèí èç òðåõ ïðåäìåòîâ: ìåøîê, êàìåíü èëè íîæíèöû. Êàæäûé ïðåäìåòïðîòèâ ñàìîãî ñåáÿ íèêàêîãî âûèãðûøà íå äàåò, ïîýòîìó íà äèàãîíàëèñòîÿò 0. Íîæíèöû òóïÿòñÿ î êàìåíü, ïîýòîìó îíè ïðîèãðûâàþò êàìíþ 1,à òîò â ñâîþ î÷åðåäü âûèãðûâàåò ó íîæíèö 1. Êàìåíü ìîæíî ïîìåñòèòüâ ìåøîê, ïîýòîìó ìåøîê âûèãðûâàåò ó êàìíÿ 1, à êàìåíü ïðîèãðûâàåòìåøêó 1.

Íîæíèöû ðåæóò ìåøîê, ïîýòîìó îíè âûèãðûâàþò ó ìåøêà 1,à ìåøîê ïðîèãðûâàåò íîæíèöàì 1.Óïðàæíåíèå 4.2. Ïóñòü B − ìàòðèöà, ïîëó÷åííàÿ ïðèáàâëåíèåì êîíñòàíòû c êî âñåì ýëåìåíòàì ìàòðèöû A. Ïîêàçàòü, ÷òî çíà÷åíèÿ ñîîòâåòñòâóþùèõ ìàòðè÷íûõ èãð ñâÿçàíû ñîîòíîøåíèåì v(B) = v(A) + c, àîïòèìàëüíûå ñìåøàííûå ñòðàòåãèè èãðîêîâ ñîâïàäàþò.Ïðèìåð 4.2. Ïðîäàâåö âûñòàâëÿåò íà ïðîäàæó òðè ïðåäìåòà, íå ïðåäñòàâëÿþùèå äëÿ íåãî îñîáîé öåííîñòè (ñòàðûå òåëåâèçîðû è ò.ï.). Îí ãîòîâ èõ ïðîäàòü äàæå çà íåçíà÷èòåëüíóþ öåíó. Èìåþòñÿ äâà ïîêóïàòåëÿ(èãðîêà), ðàñïîëàãàþùèå îäèíàêîâûìè ñóììàìè äåíåã A.

Èãðîê ñòàíîâèòñÿ îáëàäàòåëåì ïðåäìåòà, åñëè ïðåäëàãàåò çà íåãî ñóììó, áóëüøóþ,÷åì ïàðòíåð. Öåëü ïåðâîãî èãðîêà ñîñòîèò â ïîêóïêå äâóõ êàêèõ-ëèáîïðåäìåòîâ èç òðåõ. Öåëü âòîðîãî èãðîêà − âîñïðåïÿòñòâîâàòü ýòîìó.3PÏóñòü x = (x1 , x2 , x3 ) ∈ X = {x |xi = A, x1 , x2 , x3 ≥ 0} −i=1ñòðàòåãèÿ ïåðâîãî èãðîêà, ñîñòîÿùàÿ â ïðåäëîæåíèè ñóììû xi çà i-ûéïðåäìåò.

Àíàëîãè÷íóþ ñòðàòåãèþ y = (y1 , y2 , y3 ) ∈ Y = X èñïîëüçóåòâòîðîé èãðîê.Áóäåì ïèñàòü x  y, åñëè êàêèå-ëèáî äâå êîìïîíåíòû âåêòîðà x áîëüøå ñîîòâåòñòâóþùèõ êîìïîíåíò âåêòîðà y . Îïðåäåëèì ôóíêöèþ âûèãðûøà ïåðâîãî èãðîêà(1, x  y,F (x, y) =0, â ïðîòèâíîì ñëó÷àå.Çàìåòèì, ÷òî∀x ∈ X ∃ y ∈ Y : ¬(x  y) ⇒ v = 0;∀y ∈ Y ∃ x ∈ X : x  y ⇒ v = 1.Îòñþäà ñëåäóåò, ÷òî èãðà íå èìååò ðåøåíèÿ â ÷èñòûõ ñòðàòåãèÿõ. Íàéäåìåå ðåøåíèå â ñìåøàííûõ ñòðàòåãèÿõ.Ìíîæåñòâî ñòðàòåãèé X (ñîâïàäàþùåå ñ Y ) èçîáðàçèì íà ïëîñêîñòè â âèäå ðàâíîñòîðîííåãî òðåóãîëüíèêà âûñîòû A. Òî÷êà y èìååò áàðèöåíòðè÷åñêèå êîîðäèíàòû y1 , y2 , y3 , îïðåäåëÿþùèå åå ðàññòîÿíèÿ îò30Ÿ 4.