Теорема Какутани о неподвижной точке

В математическом анализе теорема Какутани о неподвижной точке является теоремой о неподвижной точке для многозначных функций . Он обеспечивает достаточные условия для того, чтобы многозначная функция, определенная на компактном выпуклом подмножестве евклидова пространства , имела фиксированную точку , то есть точку, которая отображается в содержащее ее множество. Теорема Какутани о неподвижной точке является обобщением теоремы Брауэра о неподвижной точке . Теорема Брауэра о неподвижной точке — фундаментальный результат в топологии , который доказывает существование неподвижных точек для непрерывных функций, определенных на компактных выпуклых подмножествах евклидовых пространств. Теорема Какутани распространяет это на многозначные функции.

Теорему разработал Шизуо Какутани в 1941 году. ^[1] и был использован Джоном Нэшем в его описании равновесий Нэша . ^[2] Впоследствии оно нашло широкое применение в теории игр и экономике . ^[3]

Заявление

Теорема Какутани гласит: ^[4]

Пусть S — непустое , компактное и выпуклое подмножество некоторого евклидова пространства R. ^н.

Пусть φ : S → 2 ^С быть многозначной функцией на S со следующими свойствами:

φ имеет график замкнутый ;
φ ( x ) непусто и выпукло для x ∈ S. всех

Тогда φ имеет неподвижную точку .

Определения

Многозначная функция: Многозначная функция φ из множества X в множество Y которое связывает одну или несколько точек из Y с каждой точкой из X. — это некоторое правило , Формально его можно рассматривать как обычную функцию от X до набора степеней Y , записанную как φ : X → 2. ^И, такой, что φ ( x ) непусто для любого $x\in X$ . Некоторые предпочитают термин «соответствие» , который используется для обозначения функции, которая для каждого ввода может возвращать множество выходных данных. Таким образом, каждый элемент домена соответствует подмножеству одного или нескольких элементов диапазона.
Закрытый график: Многозначная функция φ: X → 2 ^И Говорят, что граф имеет замкнутый характер , если множество {( x , y ) | y ∈ φ ( x )} — замкнутое подмножество X × Y в топологии произведения, т. е. для всех последовательностей $\{x_{n}\}_{n\in \mathbb {N} }$ и $\{y_{n}\}_{n\in \mathbb {N} }$ такой, что $x_{n}\to x$ , $y_{n}\to y$ и $y_{n}\in \varphi (x_{n})$ для всех $n$ , у нас есть $y\in \varphi (x)$ .
Фиксированная точка: Пусть φ: X → 2 ^Х быть функцией с множеством значений. Тогда a ∈ X является неподвижной точкой φ , если a ∈ φ ( a ).

Примеры

Фиксированные точки для φ (x)=[1− x /2, 1− x /4]

Функция с бесконечным числом неподвижных точек

Функция: $\varphi (x)=[1-x/2,~1-x/4]$ , показанная на рисунке справа, удовлетворяет всем условиям Какутани и действительно имеет много неподвижных точек: любая точка на линии 45 ° (пунктирная линия красного цвета), которая пересекает график функции (заштрихован серым цветом), является фиксированной точка, так что на самом деле в этом конкретном случае существует бесконечное количество неподвижных точек. Например, x = 0,72 (пунктирная линия синего цвета) является фиксированной точкой, поскольку 0,72 ∈ [1 — 0,72/2, 1 — 0,72/4].

Функция с единственной неподвижной точкой

Функция:

$\varphi (x)={\begin{cases}3/4&0\leq x<0.5\\{}[0,1]&x=0.5\\1/4&0.5<x\leq 1\end{cases}}$

удовлетворяет всем условиям Какутани и действительно имеет фиксированную точку: x = 0,5 является фиксированной точкой, поскольку x содержится в интервале [0,1].

Функция, не удовлетворяющая выпуклости

Требование, чтобы φ ( x ) было выпуклым для всех x , существенно для справедливости теоремы.

Рассмотрим следующую функцию, определенную на [0,1]:

\varphi (x)={\begin{cases}3/4&0\leq x<0.5\\\{3/4,1/4\}&x=0.5\\1/4&0.5<x\leq 1\end{cases}}

Функция не имеет фиксированной точки. Хотя оно удовлетворяет всем остальным требованиям теоремы Какутани, его значение не является выпуклым при x = 0,5.

Функция, не удовлетворяющая замкнутому графику

Рассмотрим следующую функцию, определенную на [0,1]:

\varphi (x)={\begin{cases}3/4&0\leq x<0.5\\1/4&0.5\leq x\leq 1\end{cases}}

Функция не имеет фиксированной точки. Хотя он удовлетворяет всем остальным требованиям теоремы Какутани, его график не замкнут; например, рассмотрим последовательности x _n = 0,5 - 1/ n , y _n = 3/4.

Альтернативное заявление

Некоторые источники, включая оригинальную статью Какутани, используют концепцию верхней геминепрерывности при формулировке теоремы:

Пусть S — непустое , компактное и выпуклое подмножество некоторого евклидова пространства R. ^н. Пусть φ : S →2 ^С — полунепрерывная сверху многозначная функция на S, обладающая тем свойством, что φ ( x ) непуста, замкнута и выпукла для всех x ∈ S . Тогда φ имеет неподвижную точку .

Это утверждение теоремы Какутани полностью эквивалентно утверждению, данному в начале статьи.

Мы можем показать это, используя теорему о замкнутом графике для многозначных функций: ^[5] который говорит, что для компактного хаусдорфова пространства значений Y многозначная функция φ : X →2 ^И имеет замкнутый график тогда и только тогда, когда он полунепрерывен сверху и φ ( x ) является замкнутым множеством для всех x . Поскольку все евклидовы пространства являются хаусдорфовыми (являясь метрическими пространствами ), а в альтернативной формулировке теоремы Какутани требуется, чтобы φ была замкнутой, из теоремы о замкнутом графе следует, что эти два утверждения эквивалентны.

Приложения

Теория игр

Теорему Какутани о неподвижной точке можно использовать для доказательства теоремы о минимаксе в теории игр с нулевой суммой . Это приложение специально обсуждалось в оригинальной статье Какутани. ^[1]

Математик Джон Нэш использовал теорему Какутани о неподвижной точке, чтобы доказать важный результат в теории игр . ^[2] Неформально говоря, из этой теоремы следует существование равновесия Нэша в каждой конечной игре со смешанными стратегиями для любого конечного числа игроков. Эта работа позже принесла ему Нобелевскую премию по экономике . В этом случае:

Базовый набор S — это набор кортежей смешанных стратегий, выбранных каждым игроком в игре. Если у каждого игрока есть k возможных действий, то стратегия каждого игрока представляет собой k -кортеж вероятностей, сумма которых равна 1, поэтому пространство стратегий каждого игрока представляет собой стандартный симплекс в R. ^к. Тогда S — декартово произведение всех этих симплексов. Это действительно непустое, компактное и выпуклое подмножество R ^знать.
Функция φ( x ) связывает с каждым кортежем новый кортеж, где стратегия каждого игрока является его лучшим ответом на стратегии других игроков в x . Поскольку может быть несколько одинаково хороших ответов, φ является многозначным, а не однозначным. Для каждого x φ( x ) непусто, поскольку всегда существует хотя бы один лучший ответ. Он выпуклый, поскольку смесь двух лучших ответов для игрока по-прежнему остается лучшим ответом для игрока. Можно доказать, что φ имеет замкнутый график.
Тогда равновесие Нэша в игре определяется как фиксированная точка φ, т.е. набор стратегий, в котором стратегия каждого игрока является лучшим ответом на стратегии других игроков. Теорема Какутани гарантирует существование этой неподвижной точки.

Общее равновесие

В теории общего равновесия в экономике теорема Какутани использовалась для доказательства существования набора цен, которые одновременно приравнивают предложение к спросу на всех рынках экономики. ^[6] Существование таких цен было открытым вопросом в экономической науке, по крайней мере, еще со времен Вальраса . Первое доказательство этого результата было построено Лайонелом Маккензи . ^[7]

В этом случае:

Базовый набор S представляет собой набор кортежей цен на сырьевые товары.
Функция φ( x ) выбирается так, чтобы ее результат отличался от ее аргументов до тех пор, пока набор цен x не уравнивает спрос и предложение повсюду. Задача здесь состоит в том, чтобы построить φ так, чтобы она обладала этим свойством и в то же время удовлетворяла условиям теоремы Какутани. Если это возможно, то согласно теореме φ имеет неподвижную точку. Учитывая способ ее построения, эта фиксированная точка должна соответствовать ценовому кортежу, который повсюду уравнивает предложение и спрос.

Ярмарочный отдел

Теорема Какутани о фиксированной точке используется для доказательства существования распределений тортов, которые не вызывают зависти и эффективны по Парето . Этот результат известен как теорема Веллера .

Связь с теоремой Брауэра о неподвижной точке

Теорема Брауэра о неподвижной точке является частным случаем теоремы Какутани о неподвижной точке. И наоборот, теорема Какутани о неподвижной точке является непосредственным обобщением с помощью теоремы приближенного выбора : ^[8]

Доказательство

По приближенной теореме выбора существует последовательность непрерывных $f_{n}:S\to S$ такой, что $\operatorname {graph} (f_{n})\subset [\operatorname {graph} (\varphi )]_{1/n}$ . По теореме Брауэра о неподвижной точке существует последовательность $x_{n}$ такой, что $f_{n}(x_{n})=x_{n}$ , так $(x_{n},x_{n})\in [\operatorname {graph} (\varphi )]_{1/n}$ .

С $S$ компактна, мы можем взять сходящую подпоследовательность $x_{n}\to x$ . Затем $(x,x)\in \operatorname {graph} (\varphi )$ поскольку это закрытое множество.

Схема доказательства

S = [0,1]

Доказательство теоремы Какутани наиболее просто для многозначных функций, определенных на отрезках вещественной прямой. Более того, доказательство этого случая поучительно, поскольку его общая стратегия может быть перенесена и на случай более высокой размерности.

Пусть φ: [0,1]→2 ^[0,1] — многозначная функция на отрезке [0,1], удовлетворяющая условиям теоремы Какутани о неподвижной точке.

Создайте последовательность подразделений [0,1] с соседними точками, движущимися в противоположных направлениях.

Пусть ( a _i , b _i , p _i , q _i ) для i = 0, 1, … будет последовательностью со следующими свойствами:

1.	1 ≥ б _я > а я _≥ 0	2.	( б _я - а _я ) ≤ 2 ^{- я}
3.	п _я ∈ φ( а _я )	4.	qiεφ _i ( би ₎
5.	п _я ≥ а _я	6.	q _я ≤ б _я

Таким образом, замкнутые интервалы [ a _i , b _i ] образуют последовательность подинтервалов [0,1]. Условие (2) говорит нам, что эти подинтервалы продолжают уменьшаться, в то время как условия (3)–(6) говорят нам, что функция φ сдвигает левый конец каждого подинтервала вправо и смещает правый конец каждого подинтервала влево.

Такую последовательность можно построить следующим образом. Пусть a0 _{= 0} и b0 _{любая точка из φ} = 1. Пусть p0 _— любая точка из φ(0), а q0 _— (1). Тогда условия (1)–(4) немедленно выполняются. Более того, поскольку p0 ₀ ∈ φ(0) ⊂ [0,1], должно быть так, что ≥ _p0 и, следовательно, условие (5) выполнено. Аналогично условие (6) выполняется при q ₀ .

Теперь предположим, что мы выбрали a _k , b _k , p _k и q _k, удовлетворяющие (1)–(6). Позволять,

м = ( а _k + б _k )/2.

Тогда m ∈ [0,1], поскольку [0,1] выпукло .

Если существует r ∈ φ( m ) такой, что r ≥ m , то мы берем

а _{к +1} = м

бк ₊₁ = бк

пк ₊₁ = р

дк ₊₁ = q_дк

В противном случае, поскольку φ( m ) непусто, должен существовать s ∈ φ( m ) такой, что s ⩽ m . В этом случае пусть,

а _{к +1} = а _к

бк ₊₁ = м

пк ₊₁ = пк

q _{k +1} знак равно s .

Можно проверить, что a _{k +1} , b _{k +1} , p _{k +1} и q _{k +1} удовлетворяют условиям (1)–(6).

Найдите предельную точку подразделений.

У нас есть пара последовательностей интервалов, и мы хотели бы показать, что они сходятся к предельной точке с помощью теоремы Больцано-Вейерштрасса . этого мы рассматриваем эти две интервальные последовательности как одну последовательность , _точек pn , _bn an , ₍ qn ) _Для . Это лежит в декартовом произведении [0,1]×[0,1]×[0,1]×[0,1], которое является компактом по теореме Тихонова . Поскольку наша последовательность ( , _быть pn , _{сходящаяся} bn , _an qn ) _{Вейерштрассу} лежит в компактном множестве, у нее должна подпоследовательность по Больцано - . Зафиксируем внимание на такой подпоследовательности и пусть ее предел равен ( a *, p *, b *, q *). Поскольку график φ замкнут, должно быть так, что p * ∈ φ( a *) и q * ∈ φ( b *). При этом по условию (5) p * ≥ a * и по условию (6) q * ≤ b *.

Но поскольку ( b _i − a _i ) ≤ 2 ^{- я} по условию (2),

б * - а * знак равно (lim б _п ) - (lim а _п ) знак равно lim ( б _п - а _п ) знак равно 0.

Итак, b * равно a *. Пусть х = b * = а *.

Тогда мы имеем ситуацию, что

φ( x ) ∋ q * ≤ x ≤ p * ∈ φ( x ).

Докажите, что предельная точка является фиксированной.

Если p * = q *, то p * = x = q *. Поскольку p * ∈ φ( x ), x является неподвижной точкой φ.

В противном случае мы можем написать следующее. Напомним, что мы можем параметризовать линию между двумя точками a и b с помощью (1-t)a + tb. Используя наш вывод о том, что q<x<p, мы можем создать такую линию между p и q как функцию x (обратите внимание, что дроби ниже относятся к единичному интервалу). Благодаря удобному написанию x, а также поскольку φ( x ) выпукла и

x=\left({\frac {x-q^{*}}{p^{*}-q^{*}}}\right)p^{*}+\left(1-{\frac {x-q^{*}}{p^{*}-q^{*}}}\right)q^{*}

отсюда еще раз следует, что x должна принадлежать φ( x ), поскольку p * и q * принадлежат и, следовательно, x является неподвижной точкой φ.

S является n -симплексом

В размерностях больше единицы n -симплексов являются простейшими объектами, на которых может быть доказана теорема Какутани. Неформально n -симплекс — это многомерная версия треугольника. Доказательство теоремы Какутани для многозначной функции, определенной на симплексе, по существу не отличается от ее доказательства для интервалов. Дополнительная сложность в случае более высокой размерности возникает на первом этапе разделения области на более мелкие части:

Там, где в одномерном случае мы разбиваем интервалы на два посередине, барицентрическое подразделение используется для разбиения симплекса на более мелкие подсимплексы.
В то время как в одномерном случае мы могли бы использовать элементарные аргументы, чтобы выбрать один из полуинтервалов таким образом, чтобы его конечные точки были перемещены в противоположных направлениях, в случае симплексов комбинаторный результат, известный как лемма Спернера для гарантии используется . существование соответствующего подсимплекса.

После внесения этих изменений в первый шаг второй и третий шаги по нахождению предельной точки и доказательству того, что это фиксированная точка, практически не изменились по сравнению с одномерным случаем.

Произвольный S

Теорему Какутани для n-симплексов можно использовать для доказательства теоремы для произвольного компактного выпуклого S . Мы снова используем ту же технику создания все более тонких подразделений. Но вместо треугольников с прямыми краями, как в случае n-симплексов, мы теперь используем треугольники с изогнутыми краями. Формально мы находим симплекс, который покрывает S , а затем перемещаем задачу из S в симплекс, используя ретракт деформации . Тогда мы можем применить уже установленный результат для n-симплексов.

Бесконечномерные обобщения

Теорема Какутани о неподвижной точке была распространена на бесконечномерные локально выпуклые топологические векторные пространства Ирвингом Гликсбергом. ^[9]и Кай Фан . ^[10]Для формулировки теоремы в этом случае нам понадобится еще несколько определений:

Верхняя геминепрерывность: Многозначная функция φ: X →2 ^И является геминепрерывным сверху , если для любого открытого множества W ⊂ Y множество { x | φ( x ) ⊂ W } открыто в X . ^[11]
Скачать карту: Пусть X и Y — топологические векторные пространства и φ: X →2 ^И быть функцией с множеством значений. Если Y выпукло, то φ называется отображением Какутани, если оно полунепрерывно сверху и φ( x ) непусто, компактно и выпукло для всех x ∈ X . ^[11]

Тогда теорему Какутани–Гликсберга–Фана можно сформулировать как: ^[11]

Пусть S — непустое , компактное и выпуклое подмножество хаусдорфова локально выпуклого топологического векторного пространства . Пусть φ: S→2 ^С быть картой Какутани. Тогда φ имеет неподвижную точку.

Соответствующим результатом для однозначных функций является теорема Тихонова о неподвижной точке .

Есть и другая версия, что формулировка теоремы становится такой же, как и в евклидовом случае: ^[5]

Пусть S — непустое , компактное и выпуклое подмножество пространства локально выпуклого хаусдорфова . Пусть φ: S→2 ^С — многозначная функция на S, имеющая замкнутый график и то, что φ(x) непуста и выпукла для всех x ∈ S. Тогда множество неподвижных точек φ непусто и компактно.

Анекдот

В своем учебнике по теории игр ^[12] Кен Бинмор вспоминает, что Какутани однажды спросил его на конференции, почему на его выступление пришло так много экономистов. Когда Бинмор сказал ему, что это, вероятно, из-за теоремы Какутани о неподвижной точке, Какутани был озадачен и ответил: «Что такое теорема Какутани о неподвижной точке?»

Ссылки

^ Jump up to: ^а ^б Какутани, Шизуо (1941). «Обобщение теоремы Брауэра о неподвижной точке». Математический журнал Дьюка . 8 (3): 457–459. дои : 10.1215/S0012-7094-41-00838-4 .
^ Jump up to: ^а ^б Нэш, Дж. Ф. младший (1950). «Точки равновесия в играх N» . Учеб. Натл. акад. наук. США . 36 (1): 48–49. Бибкод : 1950ПНАС...36...48Н . дои : 10.1073/pnas.36.1.48 . ПМЦ 1063129 . ПМИД 16588946 .
^ Бордер, Ким К. (1989). Теоремы о неподвижной точке с приложениями к экономике и теории игр . Издательство Кембриджского университета. ISBN 0-521-38808-2 .
^ Осборн, Мартин Дж.; Рубинштейн, Ариэль (1994). Курс теории игр . Кембридж, Массачусетс: Массачусетский технологический институт.
^ Jump up to: ^а ^б Алипрантис, Чарламбос; Ким С. Бордер (1999). «Глава 17». Бесконечный размерный анализ: Путеводитель для путешественника (3-е изд.). Спрингер.
^ Старр, Росс М. (1997). Теория общего равновесия . Издательство Кембриджского университета. ISBN 978-0-521-56473-1 .
^ Маккензи, Лайонел (1954). «О равновесии в модели мировой торговли Грэма и других конкурентных системах». Эконометрика . 22 (2): 147–161. дои : 10.2307/1907539 . JSTOR 1907539 .
^ Шапиро, Джоэл Х. (2016). Фарраго с фиксированной точкой . Международное издательство Спрингер. стр. 68–70. ISBN 978-3-319-27978-7 . OCLC 984777840 .
^ Гликсберг, Иллинойс (1952). «Дальнейшее обобщение теоремы Какутани о неподвижной точке с применением к равновесию Нэша» . Труды Американского математического общества . 3 (1): 170–174. дои : 10.2307/2032478 . JSTOR 2032478 . Архивировано из оригинала 22 сентября 2017 года.
^ Фан, Кай (1952). «Теоремы о неподвижной точке и минимаксе в локально выпуклых топологических линейных пространствах» . Proc Natl Acad Sci США . 38 (2): 121–126. Бибкод : 1952PNAS...38..121F . дои : 10.1073/pnas.38.2.121 . ПМЦ 1063516 . ПМИД 16589065 .
^ Jump up to: ^а ^б ^с Дугунджи, Джеймс ; Анджей Гранас (2003). «Глава II, раздел 5.8». Теория фиксированной точки (ограниченный предварительный просмотр) . Спрингер. ISBN 978-0-387-00173-9 .
^ Бинмор, Кен (2007). «Когда существуют равновесия Нэша?» . Игра по-настоящему: текст по теории игр (1-е изд.). Издательство Оксфордского университета. п. 256. ИСБН 978-0-19-804114-6 .

Дальнейшее чтение

Бордер, Ким К. (1989). Теоремы о неподвижной точке с приложениями к экономике и теории игр . Издательство Кембриджского университета. (Стандартный справочник по теории фиксированной точки для экономистов. Включает доказательство теоремы Какутани.)
Дугунджи, Джеймс ; Анджей Гранас (2003). Теория фиксированной точки . Спрингер. (Комплексное математическое рассмотрение теории неподвижной точки высокого уровня, включая бесконечномерные аналоги теоремы Какутани.)
Эрроу, Кеннет Дж .; Ф. Х. Хан (1971). Общий конкурентный анализ . Холден-Дэй. ISBN 978-0-8162-0275-1 . (Стандартный справочник по теории общего равновесия . В главе 5 теорема Какутани используется для доказательства существования равновесных цен. Приложение C включает доказательство теоремы Какутани и обсуждает ее связь с другими математическими результатами, используемыми в экономике.)

Внешние ссылки

«Теорема Какутани» , Математическая энциклопедия , EMS Press , 2001 [1994]

[kakutani-1] Jump up to: ^а ^б Какутани, Шизуо (1941). «Обобщение теоремы Брауэра о неподвижной точке». Математический журнал Дьюка . 8 (3): 457–459. дои : 10.1215/S0012-7094-41-00838-4 .

[nash-2] Jump up to: ^а ^б Нэш, Дж. Ф. младший (1950). «Точки равновесия в играх N» . Учеб. Натл. акад. наук. США . 36 (1): 48–49. Бибкод : 1950ПНАС...36...48Н . дои : 10.1073/pnas.36.1.48 . ПМЦ 1063129 . ПМИД 16588946 .

[3] Бордер, Ким К. (1989). Теоремы о неподвижной точке с приложениями к экономике и теории игр . Издательство Кембриджского университета. ISBN 0-521-38808-2 .

[Osborne-4] Осборн, Мартин Дж.; Рубинштейн, Ариэль (1994). Курс теории игр . Кембридж, Массачусетс: Массачусетский технологический институт.

[aliprantis-5] Jump up to: ^а ^б Алипрантис, Чарламбос; Ким С. Бордер (1999). «Глава 17». Бесконечный размерный анализ: Путеводитель для путешественника (3-е изд.). Спрингер.

[6] Старр, Росс М. (1997). Теория общего равновесия . Издательство Кембриджского университета. ISBN 978-0-521-56473-1 .

[7] Маккензи, Лайонел (1954). «О равновесии в модели мировой торговли Грэма и других конкурентных системах». Эконометрика . 22 (2): 147–161. дои : 10.2307/1907539 . JSTOR 1907539 .

[8] Шапиро, Джоэл Х. (2016). Фарраго с фиксированной точкой . Международное издательство Спрингер. стр. 68–70. ISBN 978-3-319-27978-7 . OCLC 984777840 .

[9] Гликсберг, Иллинойс (1952). «Дальнейшее обобщение теоремы Какутани о неподвижной точке с применением к равновесию Нэша» . Труды Американского математического общества . 3 (1): 170–174. дои : 10.2307/2032478 . JSTOR 2032478 . Архивировано из оригинала 22 сентября 2017 года.

[10] Фан, Кай (1952). «Теоремы о неподвижной точке и минимаксе в локально выпуклых топологических линейных пространствах» . Proc Natl Acad Sci США . 38 (2): 121–126. Бибкод : 1952PNAS...38..121F . дои : 10.1073/pnas.38.2.121 . ПМЦ 1063516 . ПМИД 16589065 .

[dugundji-11] Jump up to: ^а ^б ^с Дугунджи, Джеймс ; Анджей Гранас (2003). «Глава II, раздел 5.8». Теория фиксированной точки (ограниченный предварительный просмотр) . Спрингер. ISBN 978-0-387-00173-9 .

[12] Бинмор, Кен (2007). «Когда существуют равновесия Нэша?» . Игра по-настоящему: текст по теории игр (1-е изд.). Издательство Оксфордского университета. п. 256. ИСБН 978-0-19-804114-6 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]