[учебник] Введение в теорию игр (с приложениями к экономике). Васин, Морозов (2003) (1186146), страница 46
Текст из файла (страница 46)
Íåòðóäíî âèäåòü, ÷òî àíàëîãè÷íûìñâîéñòâîì îáëàäàåò è ñèìïëåêñ y 1 · · · y l b. Ñîâîêóïíîñòü âñåõ òàêèõ ñèìïëåêñîâ y 1 · · · y l b è áàðèöåíòð b äîáàâèì ê ñåìåéñòâó π 0 .  ðåçóëüòàòåïîëó÷èì áàðèöåíòðè÷åñêîå ðàçáèåíèå π1 ñèìïëåêñà K.nÏîêàæåì, ÷òî δ(π1 ) ≤ n+1d, ãäå d − äèàìåòð ñèìïëåêñà K. Äåéñòâèòåëüíî, âîçüìåì ëþáîå ðåáðî b0 b00 ðàçáèåíèÿ π1 , ãäå áåç ïîòåðè îáùíîñòès+1b0 =r+11 X i 001 X jx, b =x , r < s ≤ n.s + 1 i=1r + 1 j=1263ÏðèëîæåíèåÒîãäàs+1 1 X|b0 − b00 | = (xi − b00 ) =s + 1i=1s+1 r+1 11 XX is(r + 1)dndj =(x − x ) ≤≤.s + 1 r + 1 (s + 1)(r + 1)n+1i=1 j=1nÈòàê, δ(π1 ) ≤ n+1d. Åñëè êàæäûé ñèìïëåêñ, ïðèíàäëåæàùèé ðàçáèåíèþ π1 , ïîäâåðãíóòü áàðèöåíòðè÷åñêîìó ðàçáèåíèþ, ïîëó÷èì ñèìïëèn 2öèàëüíîå ðàçáèåíèå π2 , äëÿ êîòîðîãî δ(π2 ) ≤ ( n+1) d. Ïîâòîðÿÿ àíàëîãè÷íóþ ïðîöåäóðó k ðàç, ïîëó÷èì ñèìïëèöèàëüíîå ðàçáèåíèå πk ñn kδ(πk ) ≤ ( n+1) d.Òåîðåìà Ï.3 (ëåììà Øïåðíåðà).
Ïóñòü π − ñèìïëèöèàëüíîåðàçáèåíèå n-ìåðíîãî ñèìïëåêñà K = x1 · · · xn+1 , à ôóíêöèÿ ν : K →{x1 , ..., xn+1 } óäîâëåòâîðÿåò óñëîâèþν(x) ∈ {xi | λi (x) > 0} ∀x ∈ K.Òîãäà íàéäåòñÿ òàêîé n-ìåðíûé ñèìïëåêñ y 1 · · · y n+1 ðàçáèåíèÿ π, ÷òîν(y i ) = xi , i = 1, ..., n + 1. ×èñëî òàêèõ ñèìïëåêñîâ íå÷åòíî.Äîêàçàòåëüñòâî. Äëÿ n = 0 óòâåðæäåíèå òåîðåìû î÷åâèäíî.
Ïðåäïîëîæèì, ÷òî îíà ñïðàâåäëèâà äëÿ (n − 1)-ìåðíûõ ñèìïëåêñîâ. ÏóñòüK1 , ..., Kp − n-ìåðíûå îòêðûòûå ñèìïëåêñû, âõîäÿùèå â ðàçáèåíèå π. Áóäåì ãîâîðèòü, ÷òî (n−1)-ìåðíàÿ ãðàíü y 1 · · · y n ñèìïëåêñà Kj = y 1 · · · y n+1îòìå÷åíà, åñëè ν(y i ) = xi , i = 1, ..., n.Åñëè ñèìïëåêñ Kj óäîâëåòâîðÿåò óòâåðæäåíèþ òåîðåìû, òî, ââèäóðàâåíñòâ ν(y i ) = xi , i = 1, ..., n + 1, îí èìååò ðîâíî îäíó îòìå÷åííóþãðàíü. Äåéñòâèòåëüíî, ëþáàÿ äðóãàÿ (n − 1)-ìåðíàÿ ãðàíü ñèìïëåêñà Kjñîäåðæèò âåðøèíó y n+1 .
Íî ν(y n+1 ) = xn+1 è ýòà ãðàíü íå ÿâëÿåòñÿ îòìå÷åííîé. Ïóñòü ñèìïëåêñ Kj íå óäîâëåòâîðÿåò óòâåðæäåíèþ òåîðåìû èèìååò îòìå÷åííóþ ãðàíü y 1 · · · y n . Òîãäà îí èìååò ðîâíî äâå îòìå÷åííûåãðàíè. Äåéñòâèòåëüíî, ïî ïðåäïîëîæåíèþ ν(y i ) = xi , i = 1, ..., n è áåçïîòåðè îáùíîñòè ν(y n+1 ) = x1 . Òîãäà (n − 1)-ìåðíûå ãðàíè y 1 · · · y n èy 2 · · · y n y n+1 ÿâëÿþòñÿ îòìå÷åííûìè.Ïóñòü σj − ÷èñëî îòìå÷åííûõ ãðàíåé ñèìïëåêñà Kj . Ïî äîêàçàííîìóσj ∈ {0, 1, 2} è σj = 1 òîëüêî â òîì ñëó÷àå, êîãäà ñèìïëåêñ Kj óäîâëåòâîðÿåò óòâåðæäåíèþ òåîðåìû. Ïîýòîìó îñòàëîñü äîêàçàòü, ÷òî îáùååpP÷èñëî îòìå÷åííûõ ãðàíåé χ =σj íå÷åòíî.  ýòîì ñëó÷àå îáÿçàòåëüíîj=1íàéäåòñÿ ñèìïëåêñ Kj , óäîâëåòâîðÿþùèé óòâåðæäåíèþ òåîðåìû.264ÏðèëîæåíèåÏóñòü V = y 1 · · · y n − êàêàÿ-ëèáî (n − 1)-ìåðíàÿ îòìå÷åííàÿ îòêðûòàÿ ãðàíü ñèìïëåêñà Kj .
Åñëè V ⊂ K\K 0 , òî V ïðèíàäëåæèò íåêîòîðîé(n − 1)-ìåðíîé ãðàíè ñèìïëåêñà K è ÿâëÿåòñÿ ãðàíüþ åäèíñòâåííîãî nìåðíîãî ñèìïëåêñà ðàçáèåíèÿ π. Ïðè ýòîì èç ðàâåíñòâ ν(y i ) = xi , i =def1, ..., n, ñëåäóåò, ÷òî V ⊂ W = x1 · · · xn . Äåéñòâèòåëüíî, åñëè áû ãðàíü Vïðèíàäëåæàëà äðóãîé ãðàíè ñèìïëåêñà K, ñêàæåì, x2 · · · xn+1 , òî ïî îïðåäåëåíèþ ôóíêöèè ν ðàâåíñòâî ν(y 1 ) = x1 áûëî áû íåâîçìîæíî. Ïóñòü V6⊂ K\K 0 . Òîãäà V ÿâëÿåòñÿ îáùåé ãðàíüþ ðîâíî äâóõ n-ìåðíûõ ñèìïëåêñîâ, âõîäÿùèõ â ðàçáèåíèå π è â ñóììå χ îíà ó÷èòûâàåòñÿ äâàæäû.Ñëåäîâàòåëüíî, ÷èñëî χ ñðàâíèìî ïî ìîäóëþ 2 ñ ÷èñëîì (n − 1)-ìåðíûõñèìïëåêñîâ V = y 1 · · · y n ⊂ W, äëÿ êîòîðûõ ν(y i ) = xi , i = 1, ..., n.
Ïî èíäóêòèâíîìó ïðåäïîëîæåíèþ, ïðèìåíåííîìó ê (n−1)-ìåðíîìó ñèìïëåêñóW, ýòî ÷èñëî íå÷åòíî. Ïîýòîìó ÷èñëî χ òàêæå íå÷åòíî.Òåîðåìà Ï.4 (Êíàñòåð, Êóðàòîâñêèé, Ìàçóðêåâè÷). Ïóñòü çàìêíóòûå ïîäìíîæåñòâà C1 , ..., Cn+1 ñèìïëåêñà K = x1 · · · xn+1 óäîâëåòâîðÿþò óñëîâèþxj1 · · · xjs ⊆ ∪sr=1 Cjr ∀ 1 ≤ j1 < j2 < ... < js ≤ n + 1.Òîãäà ìíîæåñòâà C1 , ..., Cn+1 èìåþò íåïóñòîå ïåðåñå÷åíèå.Äîêàçàòåëüñòâî. Ðàññìîòðèì ïîñëåäîâàòåëüíîñòü {πk } ïîñòðîåííûõðàíåå ñèìïëèöèàëüíûõ ðàçáèåíèé ñèìïëåêñà K, äëÿ êîòîðîé lim δ(πk ) =k→∞0. Îïðåäåëèì îòîáðàæåíèå ν : K → {x1 , ..., xn+1 } ñëåäóþùèì îáðàçîì.Äëÿ ëþáîãî x ∈ K ïóñòü{xj | λj (x) > 0} = {xj1 , ..., xjs }, j1 < j2 < ... < js .Òîãäà ïî óñëîâèþ x ∈ ∪sr=1 Cjr .
Ïîëîæèì ν(x) = xjt , ãäå t − ìèíèìàëüíîå ÷èñëî, äëÿ êîòîðîãî x ∈ ∪tr=1 Cjr . Îòìåòèì, ÷òî x ∈/ ∪t−1r=1 Cjrè, ñëåäîâàòåëüíî, x ∈ Cjt . Ïî ïðåäûäóùåé òåîðåìå ñóùåñòâóåò ñèìïëåêñy 1 (k) · · · y n+1 (k) ðàçáèåíèÿ πk , äëÿ êîòîðîãî ν(y i (k)) = xi , i = 1, ..., n + 1.Çàìåòèì, ÷òî äëÿ êàæäîãî âåêòîðà y i (k) ïî îïðåäåëåíèþ îòîáðàæåíèÿ νjt = i è ïîýòîìó y i (k) ∈ Ci , i = 1, ..., n + 1. Ïîñêîëüêó K − êîìïàêò,áåç ïîòåðè îáùíîñòè ìîæíî ñ÷èòàòü, ÷òî ïîñëåäîâàòåëüíîñòè {y i (k)}ñõîäÿòñÿ. Íî lim δ(πk ) = 0. Ïîýòîìó ïðè k → ∞ äèàìåòð ñèìïëåêñàk→∞y 1 (k) · · · y n+1 (k) ñòðåìèòñÿ ê íóëþ. Ñëåäîâàòåëüíî, lim y i (k) = y ∗ , i =k→∞1, ..., n + 1. Ïîñêîëüêó ïðè âñåõ i y i (k) ∈ Ci , à ìíîæåñòâà Ci çàìêíóòû,n+1Tèìååì y ∗ ∈Ci .i=1265ÏðèëîæåíèåÓòî÷íèì ôîðìóëèðîâêó òåîðåìû 9.1.
Ïóñòü Z − âûïóêëûé êîìïàêòâ E m è y 1 · · · y n+1 − ñîäåðæàùèéñÿ â íåì ñèìïëåêñ ìàêñèìàëüíîé ðàçìåðíîñòè. Òîãäà ÷èñëî n ≤ m íàçûâàåòñÿ ðàçìåðíîñòüþ ìíîæåñòâà Z.Âûïóêëûé êîìïàêò Z ìàêñèìàëüíîé ðàçìåðíîñòè m èìååò âíóòðåííþþòî÷êó (íàïðèìåð, áàðèöåíòð ñèìïëåêñà y 1 · · · y m+1 ). Îáðàòíî, åñëè Z èìååò âíóòðåííþþ òî÷êó, òî åãî ðàçìåðíîñòü ìàêñèìàëüíà. Ïðåäïîëîæèì,÷òî Z èìååò ðàçìåðíîñòü n < m è ñîäåðæèò íóëü.
Òîãäà ìîæíî ñ÷èòàòü,÷òî y n+1 = 0. Ïðè ýòîì Z ÿâëÿåòñÿ ïîäìíîæåñòâîì åâêëèäîâà ïðîñòðàíñòâà E n ñ áàçèñîì y 1 , ..., y n .Èç ñêàçàííîãî âûòåêàåò, ÷òî â òåîðåìå 9.1 áåç ïîòåðè îáùíîñòè ìîæíîïðåäïîëîæèòü, ÷òî âûïóêëûé êîìïàêò Z èìååò ìàêñèìàëüíóþ ðàçìåðíîñòü m.Äîêàçàòåëüñòâî òåîðåìû 9.1 (Áðàóýðà). Ïóñòü K = x1 · · · xm+1 −m-ìåðíûé ñèìïëåêñ â E m . Ïî òåîðåìå Ï.2 (ñì.
Ï3) íàéäåòñÿ ãîìåîìîðôèçì τ : Z → K. Îòîáðàæåíèå τ ◦ f ◦ τ −1 ïåðåâîäèò òî÷êó y ∈ K â òî÷êóτ (f (τ −1 (y))) ∈ K è ÿâëÿåòñÿ íåïðåðûâíûì. Åñëè y 0 ∈ K − íåïîäâèæíàÿòî÷êà îòîáðàæåíèÿ τ ◦ f ◦ τ −1 , òî x0 = τ −1 (y 0 ) − íåïîäâèæíàÿ òî÷êàîòîáðàæåíèÿ f : Z → Z. Ïîýòîìó áåç ïîòåðè îáùíîñòè ìîæíî ñ÷èòàòü,÷òî Z = K.ÏîëîæèìCi = {x ∈ K | λi (f (x)) ≤ λi (x)}, i = 1, ..., m + 1.Ïîñêîëüêó îòîáðàæåíèå f è ôóíêöèè λi (x) íåïðåðûâíû íà K , ìíîæåñòâà Ci çàìêíóòû.
Ïîêàæåì, ÷òî ìíîæåñòâà Ci óäîâëåòâîðÿþò óñëîâèþïðåäûäóùåé òåîðåìû. Ïóñòü x ∈ xj1 · · · xjs . Òîãäàj1jsλj (x) = 0 ∀j ∈/ {x , ..., x } ⇒sXλjr (x) = 1 ≥r=1sXλjr (f (x)).r=1Ñëåäîâàòåëüíî, íàéäåòñÿ íîìåð r, ïðè êîòîðîì λjr (x) ≥ λjr (f (x)) èx ∈ Cjr . Ïî ïðåäûäóùåé òåîðåìå íàéäåòñÿ∗x ∈m+1\Ci ⇒ λi (x∗ ) ≥ λi (f (x∗ )), i = 1, ..., m + 1.i=1Íîm+1Xi=1∗λi (x ) =m+1Xλi (f (x∗ )) = 1.i=1266ÏðèëîæåíèåÏîýòîìóλi (x∗ ) = λi (f (x∗ )), i = 1, ..., m + 1 ⇒ x∗ = f (x∗ ).Äîêàçàòåëüñòâî òåîðåìû 12.1 (Êàêóòàíè).
Êàê è ïðè äîêàçà-òåëüñòâå òåîðåìû Áðàóýðà, áåç ïîòåðè îáùíîñòè ìîæíî ñ÷èòàòü, ÷òî âûïóêëûé êîìïàêò Z èìååò ìàêñèìàëüíóþ ðàçìåðíîñòü m.Ïóñòü K = x1 · · · xm+1 − m-ìåðíûé ñèìïëåêñ â E m . Ïî òåîðåìå Ï.2(ñì. Ï3) íàéäåòñÿ ãîìåîìîðôèçì ϕ : K → Z. Ðàññìîòðèì ïîñëåäîâàòåëüíîñòü {πk } ñèìïëèöèàëüíûõ ðàçáèåíèé ñèìïëåêñà K, äëÿ êîòîðîélim δ(πk ) = 0. Äëÿ ïðîèçêîëüíîãî k îïðåäåëèì ñëåäóþùåå íåïðåðûâíîåk→∞îòîáðàæåíèå Φk : K → Z. Äëÿ ëþáîé âåðøèíû x èç {πk } âûáåðåì òî÷êóΦk (x) ∈ Φ(ϕ(x)) è çàòåì ïðîäîëæèì îòîáðàæåíèå ëèíåéíî íà êàæäûé èçñèìïëåêñîâ, âõîäÿùèõ â {πk }, ò.å.
åñëèx=m+1Xjλj x ,j=1m+1Xλj = 1, λj ≥ 0, j = 1, ..., m + 1,j=1− òî÷êà ñèìïëåêñà x1 · · · xm+1 ∈ {πk }, òî ïîëàãàåìkΦ (x) =m+1XΦk (xj ).j=1Î÷åâèäíî, ÷òî ïîñëåäíåå ðàâåíñòâî îïðåäåëÿåò íåïðåðûâíîå îòáðàæåíèå Φk : K → Z . Òîãäà f k = ϕ−1 Φk : K → K ÿâëÿåòñÿ íåïðåðûâíûìîòîáðàæåíèåì è èìååò íåïîäâèæíóþ òî÷êó xk . Ïóñòü xk ïðèíàäëåæèòñèìïëåêñó x1k · · · xm+1k ∈ {πk }, ò.å.kx =m+1Xj=1λkj xjk ,m+1Xλkj = 1, λkj ≥ 0, j = 1, ..., m + 1.j=1Íå óìàëÿÿ îáùíîñòè, ìîæíî ñ÷èòàòü, ÷òî ïîñëåäîâàòåëüíîñòè{xk }, {xjk },{λkj },{Φk (xjk )}, j = 1, ..., m + 1, ñõîäÿòñÿ ïðè k → ∞. Ïîñêîëüêó äèàìåòðû ñèìïëåêñîâ x1k · · · xm+1k ñòðåìÿòñÿ ê íóëþ, ïîñëåäîâàòåëüíîñòè {xk } è {xjk } äîëæíû èìåòü îáùèé ïðåäåë x∗ ∈ K.
Ïóñòülim λkj = λ∗j , lim Φk (xjk ) = η j , j = 1, ..., m + 1.k→∞k→∞267Èìååìϕ(xk ) = Φk (xk ) =m+1Xλkj Φk (xjk )(Π.2)j=1è lim ϕ(xjk ) = ϕ(x∗ ), lim ϕ(xk ) = ϕ(x∗ ) â ñèëó íåïðåðûâíîñòè îòáðàæåk→∞k→∞íèÿ ϕ. Ïåðåõîäÿ â ðàâåíñòâå (Π.2) ê ïðåäåëó ïðè k → ∞, ïîëó÷èìϕ(x∗ ) =m+1Xj=1λ∗j η j ,m+1Xλ∗j = 1, λ∗j ≥ 0, j = 1, ..., m + 1.j=1Èç çàìêíóòîñòè îòîáðàæåíèÿ Φ âûòåêàåò, ÷òîη j ∈ Φ(ϕ(x∗ )), j = 1, ..., m + 1. Ïîñêîëüêó ìíîæåñòâî Φ(ϕ(x∗ )) âûïóêëî,òî÷êà ϕ(x∗ ) åìó ïðèíàäëåæèò è ÿâëÿåòñÿ èñêîìîé.Ñïèñîê ëèòåðàòóðû[1] Activity analysis of production and allocation ( Cowles CommissionMonograph 13, ed.
Koopmans T.C.). − N.Y.: J.Wiley, 1951.[2] Allen B., Hellwig M. Bertrand-Edgeworth oligopoly in largemarkets. Rewiew of Economic Studies, 1986, v. 53, p. 175-204.[3] Amir R. Cournot oligopoly and the theory of supermodular games.Games and Economic Behavior, 1996, v. 15, p. 132-148.[4] Atkinson A.B., Stiglitz J.E. Lectures on public economics. −London: McGraw-Hill, 1980.[5] Àøìàíîâ Ñ.À.
Ëèíåéíîå ïðîãðàììèðîâàíèå. − Ì.: Íàóêà, 1981.[6] Àøìàíîâ Ñ.À., Òèìîõîâ À.Â. Òåîðèÿ îïòèìèçàöèè â çàäà÷àõ èóïðàæíåíèÿõ. − Ì.: Íàóêà, 1991.[7] Aumann R.J. The core of a cooperative game without sidepayments. Trans. Amer. Math. Soc., 1961, v.98, 3, p. 539-552.268Ñïèñîê ëèòåðàòóðû[8] Áåëåíüêèé Â.Ç., Âîëêîíñêèé Â.À., Èâàíêîâ Ñ.À., Ïîìàíñêèé À.Á., Øàïèðî À.Ä. Èòåðàòèâíûå ìåòîäû â òåîðèè èãð èïðîãðàììèðîâàíèè. − Ì.: Íàóêà, 1974.[9] Áåñêîíå÷íûå àíòàãîíèñòè÷åñêèå èãðû.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
