Теория игр. Оуэн (1971) (Теория игр. Оуэн (1971).djvu), страница 43

Ясно тогда, что теорема будет верна для всех (и — 11-мерных множеств, даже если они являются подмножествами пространства более высокой размерности. Пусть множество Я удовлетворяет условиям теоремы, и пусть у ~5. Возьмем любую прямую, проходящую через у. Ввиду замкнутости и выпуклости пересечение этой прямой и 5 есть замкнутый отрезок с концами у' и у". Рассмотрим точку у'. Она является граничной точкой 3, и поэтому (см.

задачу П.1) существует такая гиперплоскость Р, проходящая через у, что множество 5 целиком лежит в этой гиперплоскости или по одну сторону от нее. Множество Р, очевидно, замкнуто и выпукло, поэтому о () Р— компактное выпуклое множество-размерности ие более и — 1. Так как у'яо П Р, она может быть представлена как выпуклая линейная комбинация не более п крайних точек множества 5() Р. Предположим, что х ~ $ () Р и что х = (х'+'х")/2, где х', х" ев о, Множество Р может быть задано уравнением Е(х) = а, где Š— линейный функционал, причем мы знаем, что Е(х)~к для всех х ~ 5. Ввиду линейности мы должны иметь Е(х') = Е(х") = а, так что х', х" ~ Р. А это означает, что если точка х — крайняя в о() Р, то она является крайней в $.

Таким образом, мы показали, что у — выпуклая линейная комбинация точки у" и не более чем п крайних точек о. Но у" была получена выбором произвольной прямой, проходящей через у; эту прямую всегда можно выбрать так, что точка у" будет крайней. Тогда у будет выпуклой линейной комбинацией не более п+ 1 крайних точек о. П. 2, ТЕОРЕМЫ О НЕПОДВИЖНОИ ТОЧКЕ Ниже мы приведем без доказательства две теоремы, которые были использованы в основном тексте.

Доказательства этих теорем весьма длинны, и их можно найти в соответствующих работах (см. список литературы). П.2.1. Т е о р е м а (теорема Брауэра о неподвижной точке). Пусть 5 — компактное выпуклое подмножество п-мерного евкли- П.е. Теоремы о неподвижной точке 2!9 дава пространства, а Т вЂ” непрерывная функция, отображающая Я в себя, Тогда существует по крайней лере одна такая точка х ен Я, что )(х) = х. Эта теорема носит топологпческий характер и поэтому применима к любому множеству, топологически эквивалентному множеству Я.

(Очень часто эта теорема формулируется в предположении, что Я представляет собой и-мерный симплекс.) В общем случае доказательство этой теоремы весьма длинно и требует существенной топологической подготовки, хотя для п = 1 эта теорема есть непосредственное следствие теоремы о промежуточном значении (в этом случае теорема о неподвижной точке сводится к доказательству того, что уравнение Т(х) — х = О имеет корень в заданном интервале).

Ее обобщением, которое оказалось весьма полезным в теории игр, является приводимая ниже теорема Каку- тани о неподвижной точке. П.2.2. Определение. Пусть ) — такая функция, заданная в топологическом пространстве Х, что )(х) для х~Х есть подмножество некоторого топологического пространства У. Тогда функция ) называется полунепрерывной сверху в точке хо, если для любой последовательности хь хе, ..., сходящейся к хе, и любой такой последовательности точек уь уе, ..., что у! ~)(хе), предел последовательности (у ) (если она сходится) принадлежит Т(хе), Функция ) полунепрерывна сверху, если она полунепрерывиа сверху в каждой точке Х.

П.23. Теорема (Какутани). Пусть 8 — компактное выпуклое подмножество п-мерного евклидова пространства, и пусть)— полунепрерывная сверху функция которая каждому х ен Я ставит в соответствие замкнутое выпуклое подмножество множества Я.

Тогда существует такое хан Я, что хан Т(х). ЛИТЕРАТУРА ') Общие работы Глава ! В е г й е С., Торо!оп!са( паше» сЛй рег1ес1 ш(оггпаВоп, сборник [В), 165 — ! 78. Оа(е О., 51емаг( Е М., !пВпце пагпез сдй рег1ес1 (п1оггпа!1оп, сборник [Е), 245 — 266. [Ц [2) ') Литература, добавленнан при переводе, отмечена звездочкой.

— Прим. перва. ») Для переводов в скобках указан год выхода оригинала. — Прим. рвд. Следующие книги и статьи содержат материал, представляющий общий интерес; работы, которые непосредственно относятся к той илн иной главе настоящей книги, помещены в списках литературы, относящихся к главам. [А] Адчапсез (п Саве ТЬеогу (О гезйегМ., 5Ь а р!еу 1..5.,Тцсйег А.!Ч., едз.), Апп. о1 Май. 5йб!ез, № 52, Рг(псе1оп, 1964. [В) Соп!г(Ьп!(опз!о йе ТЬеогу о( Сапэез, 111 (Огезйег М., Тцсйег А. Ж., ЪЧо !1е Р., ебз.), Апп. о1 Май. 51иб!ез, № 39, РПпсе1оп, 1957.

К а р л и н С., Математические методы в теории игр, программировании и экономике, М., «Мир», 1964 (1959! '), Соп!г!Ьц!!опз 1а йе ТЬеогу о1 Оашез, 1 (К ц Ь п Н. !Ч., Т ц с йе г А. )Ч., едз.), Апп. о1 Ма!Ь. 5(цб!ез, № 24, РНпсе1оп, 1950. Соп1г1Ьц1!опз 1о йе ТЬеогу о1 Оащез, И (К ц Ь и Н. !Ч., Тцс йег А. !Ч., ебз.), Апп. о1 Май. 5(цб!ез, № 28, РПпсе1оп, 1953. Линейные неравенства и смежные вопросы, под ред Г, Куна и А. Таккер а (с приложением перевода книги С. В айда «Теория игр и линейное программирование»), М., ИЛ, 1959 (1956). [С] Лью с Р Д., Р а й ф а Х., Игры и решения, М., ИЛ, 1961 (1957). [Н) Соп1г(Ьц!!опз (о йе ТЬеогу о( Сашек, !Ч (Тцсйег А.

!Ч., 1.цсе В. О., едз.), Апп. о( Май. 51цб!ез, № 40, Рг!псе1оп, !959. [1] фон Нейман Дж., Моргенштерн О., Теория игр и экономическое поведение, М., «Наука», 1970 (1947). [3*) «51атричные игры», под ред. Н. Н. Воробьева, М., Физматгиз, 1961.

[К*) «Бесконечные антагонистические игры», под ред. Н. Н. В о р о б ь е в ш М., Физматгнз, !963- [Ь»] «Позипионные игры», под ред Н. Н. Воробьева, И. Н. Врублевс к о й, М., «Наука», 1967 [М'] «Применение теории пгр в военном деле», под ред. В. О. Ашкеназы, М., «Сов. радио», 196!.

[Ы«] Д р е ш е р М., Стратегические игры. Теория и приложения, М., «Сов. Радио», 1964 [О*) Воробьев Н. Н., Современное состояние теории игр, УМН, 25, № 2 (1970), 81 — 140. [Р*] Воробьев Н. Н., Некоторые методологические проблемы теории игр, Вопр. философии, № 1 (19661, 93 — 103. [13»] К(а из О., Бр!е!(Ьеог!е (п рМ!озоршзсцег 51«ЬЬ Ве»Вп, !968. Литера тура 221 Глава П Глава 1!1 Глава 1Ч Ж [2) 13] [5) (6*) [7«) [8*] [9«) [1] [2] [3) [4) [5] [6) [7) [8) [2) ]3] [5) [6] [71 [8") [9*] Кий п Н. йг„А з!шрЕЕед 1тго-регзоп ройег, сборник [О], 97 — 103.

К ун Г. У., Позиционные игры н проблема информации, сборник [Е«]„ 13 — 40. И азЬ 3., 5Ь ар 1еу 1.. 5., А з!гпр!е Гпгее-регзоп ройег цагпе, сборнин ]О]. Воробьев Н. Н., Конечные бескоалиционные игры, УМО, 14, 77т 4, (1959), 21 — 56. В р уб левская И. Н., Эквивалентность смешанных стратегий и стра- тегий поведения в счетной позиционной структуре, сборник [Е'), 246 †2, П е троса н Л.

А., Сигнальные стратегии и стратегии поведения в од- ном классе бесконечных позиционных игр, сборнии [1*), 221 — 2Ю, Петросян Л. А., Еще одно обобщение теоремы Куна, сборник [1.*,, 230 — 245. В го в п С. %., топ Ь[еиш а п п 3., Бойй1опз о1 Кащея Ьу гВНегепЕа[ ейпаЕопз, сборник [О], 73 — 79. 0гезЬег М., Каг!1п Я., Бо[ц1!опз о1 соптех Кагпез аз Вхеб ро!пйи сборник [Е], 75 — 86. Ра гй аз 3., ТЬеоПе бег е!п1асЬеп Спц1е!сЬипйеп, А Ле1пе Агглеш. Масм, 124 (19021, ! — 27. Ге й л Д., К у н Г.

У., Та к к е р А. У., О симметричных играх, сборник [3'), 62 — 71. Моцкнн Т. С., Райфа Х., Томпсон Дж, Л„Тролл Р, М., Метод двойного описания, сборник [3«), 81 †1. Р о б и и с о н Дж., Итеративный метод решения игр, сборник [3*], 110 — 117. ЗЬ а р[е у 1. 5., 8 поэт Е. Ь[., Ваз1с зо1иВопз о1 бВсге1е цагпез, сбор- ник [О], 27 — 36 'вгеу1 Н., Е[ешеп(агу ргоо[ о1 а ппп!шах 1Ьеогеш дие 1о топ Ыеишапп. сборник [О). Данциг Дж. Б., Форд Л. Р., Фулкерсон Д. Р., Алгорифм для одновременного решения прямой и двойственной задач линейного программирования, сборник [Р], 277 — 286. Да н ц н г Дж. Б., Ф улке р сон Д. Р., Теорема о максимальном потоке и минимальном разрезе в сетях, сборник [Р], 318 — 324.

Гаос С. И., Линейное программирование, М., Физматгиз, 1961 (1958). Голд м а н А. Дж., Та к к е р А. У., Теория линейного программирования, сборник [Р], 172 †2. Та к ке р А. У., Двойственные системы однородных линейных соотношений, сборник [Р], 127 — !41. В а й д а С., Теория игр и линейное программирование, сборник [Р],. 11 — 108.

Вулф Ф., Определенность полиэдральных игр, сборник [Р], 298 — 301. Д а н ц и г Дж., Линейное программирование, его применения и обобщения, М., «Прогресс», 1966 (1963). Юдин Д. Б., Гольштейн Е. Г., Линейное программирование. Теория, методы н приложения, М., «Наука», 1969. Бо не н б ласт Х. Ф., Карпин С,, Шепли Л. С., Игры с непрерывной выпуклой функцией выигрыша, сборник [К'], 337 — 352.

Боненбласт Х. Ф., Карлнн С., Шепли Л. С., Решения дискретных игр двух лиц, сборник [3«], 17 — 44. Литература [3] [4] [ч [8] [9) [10) 111) [№*] Глава У [1] [2) [3) [4] [5] Цб [! 2] [13) [14] [15*] [16*] [1 7"! [18*] [19') В о ге! Е., Бит !е 1еих ой 1п1егч!еппеп1 1е Ьавагб е1 ГЬаЫ!е1е дев 1оиеигз, Е!степ!в де !а ТЬеог(е без РгоЬаЫ1114з, 3 ед., РагВ, 1924. Д реш е р М., К а рлн н С., Ш епл и Л. С., Полнномнальные игры, сбор- ннк [К*], 154 — 180. Д а фф н н Дж. Р., Бесконечные программы, сборник [Р), 263 — 276.