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

редактировать

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

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

Содержание

  • 1 Утверждение
  • 2 Определения
  • 3 Примеры
    • 3.1 Функция с бесконечным количеством фиксированных точек
    • 3.2 Функция с уникальной фиксированной точкой
    • 3.3 Функция, не удовлетворяющая выпуклости
    • 3.4 Функция, не удовлетворяющая закрытому графику
  • 4 Альтернативный оператор
  • 5 Приложения
    • 5.1 Игра теория
    • 5.2 Общее равновесие
    • 5.3 Справедливое деление
  • 6 Схема доказательства
    • 6.1 S = [0,1]
    • 6.2 S - n-симплекс
    • 6.3 Произвольный S
  • 7 Бесконечномерные обобщения
  • 8 Анекдот
  • 9 Ссылки
  • 10 Дополнительная литература
  • 11 Внешние ссылки

Утверждение

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

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

Определения

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

Примеры

Неподвижные точки для φ (x) = [1 − x / 2, 1 − x / 4]

Функция с бесконечным числом фиксированных точек

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

Функция с уникальной фиксированной точкой

функция:

φ (x) = {3/4 0 ≤ x < 0.5 ( 0, 1) x = 0.5 1 / 4 0.5 < x ≤ 1 {\displaystyle \varphi (x)={\begin{cases}3/40\leq x<0.5\\(0,1)x=0.5\\1/40.5{\ displaystyle \ varphi (x) = {\ begin {cases} 3/4 0 \ leq x <0,5 \\ (0,1) x = 0,5 \\ 1/4 0,5 <x \ leq 1 \ end {case}}}

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

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

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

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

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

φ (x) = {3/4 0 ≤ x < 0.5 { 3 / 4, 1 / 4 } x = 0.5 1 / 4 0.5 < x ≤ 1 {\displaystyle \varphi (x)={\begin{cases}3/40\leq x<0.5\\\{3/4,1/4\}x=0.5\\1/40.5{\ displaystyle \ varphi (x) = {\ begin {case} 3/4 0 \ leq x <0.5 \\\ {3/4,1 / 4 \} x = 0.5 \\ 1/4 0.5 <x \ leq 1 \ end {case }}}

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

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

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

φ (x) = {3/4 0 ≤ x < 0.5 1 / 4 0.5 ≤ x ≤ 1 {\displaystyle \varphi (x)={\begin{cases}3/40\leq x<0.5\\1/40.5\leq x\leq 1\end{cases}}}{\ displaystyle \ varphi (x) = {\ begin {cases} 3/4 0 \ leq x <0,5 \\ 1/4 0,5 \ leq x \ leq 1 \ end { case}}}

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

Альтернативное утверждение

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

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

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

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

Приложения

Теория игр

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

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

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

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

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

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

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

Справедливое деление

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

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

S = [0,1]

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

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

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

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

1.1 ≥ b i>ai≥ 02.(bi- a i) ≤ 2
3.pi∈ φ (a i)4.qi∈ φ (b i)
5.pi≥ a i6.qi≤ b i

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

Такую последовательность можно построить следующим образом. Пусть a 0 = 0 и b 0 = 1. Пусть p 0 - любая точка в φ (0), а q 0 - любая точка в φ (1). Тогда условия (1) - (4) немедленно выполняются. Более того, поскольку p 0 ∈ φ (0) ⊂ [0,1], должно быть так, что p 0 ≥ 0 следовательно, условие (5) выполнено. Аналогично условие (6) i s выполняется q 0.

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

m = (a k+bk) / 2.

Тогда m ∈ [0,1], потому что [0,1] выпукло.

Если существует ar ∈ φ (m) такое, что r ≥ m, тогда возьмем,

ak + 1 = m
bk + 1 = b k
pk + 1 = r
qk + 1 = q k

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

ak + 1 = a k
bk + 1 = m
pk + 1 = p k
qk + 1 = s.

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

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

декартово произведение [0,1] × [0,1] × [0,1] × [0,1] - это компакт по теореме Тихонова. Поскольку последовательность (a n, p n, b n, q n) лежит в этом компактном множестве, она должна иметь сходящаяся подпоследовательность по теореме Больцано-Вейерштрасса. Зафиксируем внимание на такой подпоследовательности и пусть ее предел будет (a *, p *, b *, q *). Поскольку график φ замкнут, должно быть, что p * ∈ φ (a *) и q * ∈ φ (b *). Кроме того, по условию (5) p * ≥ a * и по условию (6) q * ≤ b *.

Но поскольку (b i - a i) ≤ 2 по условию (2),

b * - a * = (lim b n) - (lim a n) = lim (b n - a n) = 0.

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

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

φ (x) ∋ q * ≤ x ≤ p * ∈ φ (x).
  • Покажите, что предельная точка является неподвижной точкой.

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

В противном случае мы можем написать следующее. Напомним, что мы можем параметризовать линию между двумя точками a и b как (1-t) a + tb. Используя наш вывод выше, q выпуклый и

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

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

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

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

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

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

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

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

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

Теорема Какутани о неподвижной точке была распространена на бесконечномерные локально выпуклые топологические векторные пространства и Ки Фаном. Чтобы сформулировать теорему в этом случае, нам потребуется еще несколько определений:

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

Тогда отображение Какутани – Гликксберга –Теорема вентилятора может быть сформулирована как:

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

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

Существует еще одна версия, что формулировка теоремы становится такой же, как в Евклидов случай:

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

Анекдот

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

Ссылки

Дополнительная литература

  • Border, Kim C. (1989). Теоремы о неподвижной точке с приложениями к экономике и теории игр. Cambridge University Press. (Стандартный справочник по теории фиксированной точки для экономистов. Включает доказательство теоремы Какутани.)
  • Дугунджи, Джеймс ; Анджей Гранас (2003). Теория неподвижной точки. Спрингер. (Всестороннее математическое рассмотрение теории неподвижной точки, включая бесконечномерные аналоги теоремы Какутани.)
  • Эрроу, Кеннет Дж. ; Ф. Х. Хан (1971). Общий анализ конкуренции. Холден-Дэй. (Стандартная ссылка на теорию общего равновесия. В главе 5 используется теорема Какутани для доказательства существования равновесных цен. Приложение C включает доказательство теоремы Какутани и обсуждает ее связь с другими математическими результатами используется в экономике.)

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

Последняя правка сделана 2021-05-25 10:13:50
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте