Teorema del punto fijo de Kakutani

En análisis matemático , el teorema del punto fijo de Kakutani es un teorema del punto fijo para funciones de valor conjunto . Proporciona condiciones suficientes para que una función de valor conjunto definida en un subconjunto compacto y convexo de un espacio euclidiano tenga un punto fijo , es decir, un punto que se asigna a un conjunto que lo contiene. El teorema del punto fijo de Kakutani es una generalización del teorema del punto fijo de Brouwer . El teorema del punto fijo de Brouwer es un resultado fundamental en topología que demuestra la existencia de puntos fijos para funciones continuas definidas en subconjuntos compactos y convexos de espacios euclidianos. El teorema de Kakutani extiende esto a las funciones de valor conjunto.

El teorema fue desarrollado por Shizuo Kakutani en 1941, ^[1] y fue utilizado por John Nash en su descripción de los equilibrios de Nash . ^[2] Posteriormente ha encontrado una amplia aplicación en la teoría de juegos y la economía . ^[3]

Declaración

El teorema de Kakutani establece: ^[4]

Sea S un subconjunto no vacío , compacto y convexo de algún espacio euclidiano R ⁿ .

Sea φ : S → 2 ^S una función de valor conjunto en S con las siguientes propiedades:

φ tiene un gráfico cerrado ;
φ ( x ) no es vacío y es convexo para todo x ∈ S .

Entonces φ tiene un punto fijo .

Definiciones

Función con valor establecido: Una función de valor conjunto φ del conjunto X al conjunto Y es una regla que asocia uno o más puntos en Y con cada punto en X . Formalmente puede verse simplemente como una función ordinaria de X al conjunto potencia de Y , escrita como φ : X → 2 ^Y , tal que φ ( x ) no está vacío para cada . Algunos prefieren el término correspondencia , que se utiliza para referirse a una función que para cada entrada puede devolver muchas salidas. Por lo tanto, cada elemento del dominio corresponde a un subconjunto de uno o más elementos del rango. $x\en X$
Gráfico cerrado: Se dice que una función de valor conjunto φ: X → 2 ^Y tiene un gráfico cerrado si el conjunto {( x , y ) | y ∈ φ ( x )} es un subconjunto cerrado de X × Y en la topología del producto , es decir, para todas las secuencias y tales que , y para todos los , tenemos . $\{x_{n}\}_{n\in \mathbb {N}}$ $\{y_{n}\}_{n\in \mathbb {N}}$ $x_{n}\to x$ $y_{n}\to y$ ${\ Displaystyle y_ {n} \ en \ phi (x_ {n})}$ ${\estilo de visualización n}$ $y\en \phi (x)$
Punto fijo: Sea φ: X → 2 ^X una función de valor conjunto. Entonces a ∈ X es un punto fijo de φ si a ∈ φ ( a ).

Ejemplos

Puntos fijos para φ (x)=[1− x /2, 1− x /4]

Una función con infinitos puntos fijos

La función: , que se muestra en la figura de la derecha, satisface todas las condiciones de Kakutani y, de hecho, tiene muchos puntos fijos: cualquier punto de la línea de 45° (línea punteada en rojo) que interseca el gráfico de la función (sombreado en gris) es un punto fijo, por lo que, de hecho, hay una infinidad de puntos fijos en este caso particular. Por ejemplo, x = 0,72 (línea discontinua en azul) es un punto fijo ya que 0,72 ∈ [1 − 0,72/2, 1 − 0,72/4]. $\varphi(x)=[1-x/2,~1-x/4]$

Una función con un punto fijo único

La función:

\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}}

satisface todas las condiciones de Kakutani y, de hecho, tiene un punto fijo: x = 0,5 es un punto fijo, ya que x está contenido en el intervalo [0,1].

Una función que no satisface la convexidad

El requisito de que φ ( x ) sea convexo para todo x es esencial para que el teorema se cumpla.

Considere la siguiente función definida en [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}}

La función no tiene un punto fijo. Aunque satisface todos los demás requisitos del teorema de Kakutani, su valor no es convexo en x = 0,5.

Una función que no satisface gráfico cerrado

Considere la siguiente función definida en [0,1]:

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

La función no tiene un punto fijo. Aunque satisface todos los demás requisitos del teorema de Kakutani, su gráfico no es cerrado; por ejemplo, considérense las sucesiones x _n = 0,5 - 1/ n , y _n = 3/4.

Declaración alternativa

Algunas fuentes, incluido el artículo original de Kakutani, utilizan el concepto de hemicontinuidad superior al enunciar el teorema:

Sea S un subconjunto no vacío , compacto y convexo de algún espacio euclidiano R ⁿ . Sea φ : S →2 ^S una función hemicontinua superior con valores de conjunto en S con la propiedad de que φ ( x ) es no vacío, cerrado y convexo para todo x ∈ S . Entonces φ tiene un punto fijo .

Esta afirmación del teorema de Kakutani es completamente equivalente a la afirmación dada al principio de este artículo.

Podemos demostrar esto utilizando el teorema de grafo cerrado para funciones de valor conjunto, ^[5] que dice que para un espacio de rango de Hausdorff compacto Y , una función de valor conjunto φ : X →2 ^Y tiene un grafo cerrado si y solo si es hemicontinua superior y φ ( x ) es un conjunto cerrado para todo x . Dado que todos los espacios euclidianos son de Hausdorff (al ser espacios métricos ) y se requiere que φ sea de valor cerrado en el enunciado alternativo del teorema de Kakutani, el Teorema de grafo cerrado implica que los dos enunciados son equivalentes.

Aplicaciones

Teoría de juegos

El teorema del punto fijo de Kakutani se puede utilizar para demostrar el teorema del minimax en la teoría de juegos de suma cero . Esta aplicación se analizó específicamente en el artículo original de Kakutani. ^[1]

El matemático John Nash utilizó el teorema del punto fijo de Kakutani para demostrar un resultado importante en la teoría de juegos . ^[2] En términos informales, el teorema implica la existencia de un equilibrio de Nash en cada juego finito con estrategias mixtas para cualquier número finito de jugadores. Este trabajo le valió posteriormente un Premio Nobel de Economía . En este caso:

El conjunto base S es el conjunto de tuplas de estrategias mixtas elegidas por cada jugador en un juego. Si cada jugador tiene k acciones posibles, entonces la estrategia de cada jugador es una k -tupla de probabilidades que suman 1, por lo que el espacio de estrategias de cada jugador es el símplex estándar en R ^k . Entonces, S es el producto cartesiano de todos estos símplex. Es, de hecho, un subconjunto no vacío, compacto y convexo de R ^kn .
La función φ( x ) asocia a cada tupla una nueva tupla en la que la estrategia de cada jugador es su mejor respuesta a las estrategias de los otros jugadores en x . Puesto que puede haber varias respuestas que sean igualmente buenas, φ tiene un valor fijo en lugar de un valor único. Para cada x , φ( x ) no está vacío puesto que siempre hay al menos una mejor respuesta. Es convexo, puesto que una mezcla de dos mejores respuestas para un jugador sigue siendo una mejor respuesta para el jugador. Se puede demostrar que φ tiene un gráfico cerrado.
El equilibrio de Nash del juego se define entonces como un punto fijo de φ, es decir, una tupla de estrategias donde la estrategia de cada jugador es la mejor respuesta a las estrategias de los otros jugadores. El teorema de Kakutani asegura que este punto fijo existe.

Equilibrio general

En la teoría del equilibrio general en economía, el teorema de Kakutani se ha utilizado para demostrar la existencia de un conjunto de precios que simultáneamente igualan la oferta y la demanda en todos los mercados de una economía. ^[6] La existencia de tales precios ha sido una cuestión abierta en economía desde al menos Walras . La primera prueba de este resultado fue construida por Lionel McKenzie . ^[7]

En este caso:

El conjunto base S es el conjunto de tuplas de precios de productos básicos.
La función φ( x ) se elige de modo que su resultado difiera de sus argumentos siempre que la tupla de precios x no iguale la oferta y la demanda en todas partes. El desafío aquí es construir φ de modo que tenga esta propiedad y al mismo tiempo satisfaga las condiciones del teorema de Kakutani. Si esto se puede hacer, entonces φ tiene un punto fijo según el teorema. Dada la forma en que se construyó, este punto fijo debe corresponder a una tupla de precios que iguale la oferta y la demanda en todas partes.

División justa

El teorema del punto fijo de Kakutani se utiliza para demostrar la existencia de asignaciones de tortas que no generan envidia y son eficientes en el sentido de Pareto . Este resultado se conoce como teorema de Weller .

Relación con el teorema del punto fijo de Brouwer

El teorema del punto fijo de Brouwer es un caso especial del teorema del punto fijo de Kakutani. Por el contrario, el teorema del punto fijo de Kakutani es una generalización inmediata a través del teorema de selección aproximada : ^[8]

Prueba

Por el teorema de selección aproximada, existe una secuencia de continuas tal que . Por el teorema de punto fijo de Brouwer, existe una secuencia tal que , por lo que . $f_{n}:S\to S$ $\operatorname {gráfico} (f_{n})\subconjunto [\operatorname {gráfico} (\varphi )]_{1/n}$ $Estilo de visualización x_{n}}$ $f_{n}(x_{n})=x_{n}$ $(x_{n},x_{n})\in [\operatorname {grafo} (\varphi )]_{1/n}$

Como es compacto, podemos tomar una subsucesión convergente . Entonces, como es un conjunto cerrado. ${\estilo de visualización S}$ $x_{n}\to x$ $(x,x)\in \operatorname {grafo} (\varphi )$

Esquema de prueba

S= [0,1]

La demostración del teorema de Kakutani es más sencilla para funciones de valores conjuntos definidas en intervalos cerrados de la recta real. Además, la demostración de este caso es instructiva, ya que su estrategia general se puede trasladar también al caso de dimensiones superiores.

Sea φ: [0,1]→2 ^[0,1] una función de valor conjunto en el intervalo cerrado [0,1] que satisface las condiciones del teorema de punto fijo de Kakutani.

Crea una secuencia de subdivisiones de [0,1] con puntos adyacentes que se mueven en direcciones opuestas.

Sea ( a _i , b _i , p _i , q _i ) para i = 0, 1, … una secuencia con las siguientes propiedades:

Así, los intervalos cerrados [ a _i , b _i ] forman una secuencia de subintervalos de [0,1]. La condición (2) nos dice que estos subintervalos continúan haciéndose más pequeños, mientras que las condiciones (3)–(6) nos dicen que la función φ desplaza el extremo izquierdo de cada subintervalo hacia su derecha y desplaza el extremo derecho de cada subintervalo hacia su izquierda.

Una secuencia de este tipo se puede construir de la siguiente manera. Sea a ₀ = 0 y b ₀ = 1. Sea p ₀ cualquier punto en φ(0) y q ₀ cualquier punto en φ(1). Entonces, las condiciones (1)–(4) se cumplen inmediatamente. Además, como p ₀ ∈ φ(0) ⊂ [0,1], debe darse el caso de que p ₀ ≥ 0 y, por lo tanto, se cumple la condición (5). De manera similar, la condición (6) se cumple con q ₀ .

Ahora supongamos que hemos elegido a _k , b _k , p _k y q _k que satisfacen (1)–(6). Sea,

m = ( a _k + b _k )/2.

Entonces m ∈ [0,1] porque [0,1] es convexo .

Si hay un r ∈ φ( m ) tal que r ≥ m , entonces tomamos,

una _{k + 1} = m

bk ₊₁ = bk

pk ₊ 1 ₌ r

qk ₊₁ = _qk

De lo contrario, dado que φ( m ) no es vacío, debe haber un s ∈ φ( m ) tal que s ≤ m . En este caso, sea,

una _{k + 1} = una _k

bk ₊₁ = m

pk ₊₁ = pk

qk ₊₁ = s .

Se puede verificar que a _{k +1} , b _{k +1} , p _{k +1} y q _{k +1} satisfacen las condiciones (1)–(6).

Encuentra un punto límite de las subdivisiones.

Tenemos un par de sucesiones de intervalos y nos gustaría demostrar que convergen a un punto límite con el teorema de Bolzano-Weierstrass . Para ello, construimos estas dos sucesiones de intervalos como una única sucesión de puntos, ( a _n , p _n , b _n , q _n ). Esto se encuentra en el producto cartesiano [0,1]×[0,1]×[0,1]×[0,1], que es un conjunto compacto por el teorema de Tichonoff . Dado que nuestra sucesión ( a _n , p _n , b _n , q _n ) se encuentra en un conjunto compacto, debe tener una subsucesión convergente por Bolzano-Weierstrass . Fijemos la atención en dicha subsucesión y dejemos que su límite sea ( a *, p *, b *, q *). Como el gráfico de φ es cerrado, debe darse el caso de que p * ∈ φ( a *) y q * ∈ φ( b *). Además, por la condición (5), p * ≥ a * y por la condición (6), q * ≤ b *.

Pero como ( b _i − a _i ) ≤ 2 ^{− i} por la condición (2),

b * − a * = (lim b _n ) − (lim a _n ) = lim ( b _n − a _n ) = 0.

Entonces, b * es igual a *. Sea x = b * = a *.

Entonces tenemos la situación de que

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

Demuestre que el punto límite es un punto fijo.

Si p * = q * entonces p * = x = q *. Como p * ∈ φ( x ), x es un punto fijo de φ.

De lo contrario, podemos escribir lo siguiente. Recordemos que podemos parametrizar una línea entre dos puntos a y b mediante (1-t)a + tb. Usando nuestro hallazgo anterior de que q<x<p, podemos crear una línea entre p y q como una función de x (observe que las fracciones a continuación están en el intervalo unitario). Mediante una escritura conveniente de x, y dado que φ( x ) es convexo y

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

de ello se deduce una vez más que x debe pertenecer a φ( x ) ya que p * y q * lo hacen y, por lo tanto, x es un punto fijo de φ.

Ses unnorte-simplex

En dimensiones mayores que uno, los n -símplices son los objetos más simples en los que se puede demostrar el teorema de Kakutani. De manera informal, un n -símplice es la versión de dimensión superior de un triángulo. Demostrar el teorema de Kakutani para una función de valor conjunto definida en un símplice no es esencialmente diferente de demostrarlo para intervalos. La complejidad adicional en el caso de dimensión superior existe en el primer paso de dividir el dominio en subpartes más finas:

Donde dividimos los intervalos en dos en el medio en el caso unidimensional, se utiliza la subdivisión baricéntrica para dividir un símplex en subsímplices más pequeños.
Mientras que en el caso unidimensional podríamos usar argumentos elementales para elegir uno de los semiintervalos de manera que sus puntos finales se movieran en direcciones opuestas, en el caso de los símplices se utiliza el resultado combinatorio conocido como lema de Sperner para garantizar la existencia de un subsímplex apropiado.

Una vez realizados estos cambios en el primer paso, el segundo y tercer paso de encontrar un punto límite y demostrar que es un punto fijo prácticamente no sufren modificaciones respecto del caso unidimensional.

ArbitrarioS

El teorema de Kakutani para n-símplices se puede utilizar para demostrar el teorema para un S arbitrario, compacto y convexo . Una vez más, empleamos la misma técnica de crear subdivisiones cada vez más finas. Pero en lugar de triángulos con bordes rectos como en el caso de n-símplices, ahora usamos triángulos con bordes curvos. En términos formales, encontramos un símplex que cubre S y luego trasladamos el problema de S al símplex utilizando una retracción de deformación . Luego podemos aplicar el resultado ya establecido para n-símplices.

Generalizaciones de dimensión infinita

El teorema de punto fijo de Kakutani fue extendido a espacios vectoriales topológicos localmente convexos de dimensión infinita por Irving Glicksberg ^[9] y Ky Fan ^[10] . Para enunciar el teorema en este caso, necesitamos algunas definiciones más:

Hemicontinuidad superior: Una función de valor conjunto φ: X →2 ^Y es hemicontinua superior si para cada conjunto abierto W ⊂ Y , el conjunto { x | φ( x ) ⊂ W } es abierto en X . ^[11]
Mapa de Kakutani: Sean X e Y espacios vectoriales topológicos y φ: X →2 ^Y una función de valor conjunto. Si Y es convexa, entonces φ se denomina función de Kakutani si es hemicontinua superior y φ( x ) no está vacía, es compacta y convexa para todo x ∈ X . ^[11]

Entonces el teorema de Kakutani–Glicksberg–Fan puede enunciarse como: ^[11]

Sea S un subconjunto no vacío , compacto y convexo de un espacio vectorial topológico localmente convexo de Hausdorff . Sea φ: S→2 ^S una función de Kakutani. Entonces φ tiene un punto fijo.

El resultado correspondiente para funciones de un solo valor es el teorema de punto fijo de Tichonoff .

Existe otra versión según la cual el enunciado del teorema es el mismo que en el caso euclidiano : ^[5]

Sea S un subconjunto no vacío , compacto y convexo de un espacio de Hausdorff localmente convexo . Sea φ: S→2 ^S una función de valor conjunto en S que tiene un grafo cerrado y la propiedad de que φ(x) es no vacío y convexo para todo x ∈ S. Entonces el conjunto de puntos fijos de φ es no vacío y compacto.

Anécdota

En su libro de texto de teoría de juegos, ^[12] Ken Binmore recuerda que Kakutani una vez le preguntó en una conferencia por qué tantos economistas habían asistido a su charla. Cuando Binmore le dijo que probablemente se debía al teorema del punto fijo de Kakutani, Kakutani se quedó perplejo y respondió: "¿Qué es el teorema del punto fijo de Kakutani?".

Referencias

^ ab Kakutani, Shizuo (1941). "Una generalización del teorema del punto fijo de Brouwer". Duke Mathematical Journal . 8 (3): 457–459. doi :10.1215/S0012-7094-41-00838-4.
^ ab Nash, JF Jr. (1950). "Puntos de equilibrio en juegos de N personas". Proc. Natl. Sci. USA . 36 (1): 48–49. Bibcode :1950PNAS...36...48N. doi : 10.1073/pnas.36.1.48 . PMC 1063129 . PMID 16588946.
^ Border, Kim C. (1989). Teoremas del punto fijo con aplicaciones a la economía y la teoría de juegos . Cambridge University Press. ISBN 0-521-38808-2.
^ Osborne, Martin J.; Rubinstein, Ariel (1994). Un curso de teoría de juegos . Cambridge, MA: MIT.
^ ab Aliprantis, Charlambos; Kim C. Border (1999). "Capítulo 17". Análisis de dimensión infinita: Guía del autoestopista (3.ª ed.). Springer.
^ Starr, Ross M. (1997). Teoría del equilibrio general. Cambridge University Press. ISBN 978-0-521-56473-1.
^ McKenzie, Lionel (1954). "Sobre el equilibrio en el modelo de Graham del comercio mundial y otros sistemas competitivos". Econometrica . 22 (2): 147–161. doi :10.2307/1907539. JSTOR 1907539.
^ Shapiro, Joel H. (2016). "Un fárrago de punto fijo" . Publicaciones internacionales Springer. págs. 68–70. ISBN 978-3-319-27978-7.OCLC 984777840 .
^ Glicksberg, IL (1952). "Una generalización adicional del teorema del punto fijo de Kakutani, con aplicación al equilibrio de Nash". Actas de la American Mathematical Society . 3 (1): 170–174. doi :10.2307/2032478. JSTOR 2032478. Archivado desde el original el 22 de septiembre de 2017.
^ Fan, Ky (1952). "Teoremas de punto fijo y minimax en espacios lineales topológicos localmente convexos". Proc Natl Acad Sci USA . 38 (2): 121–126. Bibcode :1952PNAS...38..121F. doi : 10.1073/pnas.38.2.121 . PMC 1063516 . PMID 16589065.
^ abc Dugundji, James ; Andrzej Granas (2003). "Capítulo II, Sección 5.8". Teoría del punto fijo (vista previa limitada) . Springer. ISBN 978-0-387-00173-9.
^ Binmore, Ken (2007). "¿Cuándo existen los equilibrios de Nash?". Playing for Real: A Text on Game Theory (1.ª ed.). Oxford University Press. pág. 256. ISBN 978-0-19-804114-6.

Lectura adicional

Border, Kim C. (1989). Teoremas del punto fijo con aplicaciones a la economía y la teoría de juegos . Cambridge University Press. (Referencia estándar sobre la teoría del punto fijo para economistas. Incluye una prueba del teorema de Kakutani).
Dugundji, James ; Andrzej Granas (2003). Teoría del punto fijo . Springer. (Tratamiento matemático integral de alto nivel de la teoría del punto fijo, incluidos los análogos de dimensión infinita del teorema de Kakutani).
Arrow, Kenneth J. ; FH Hahn (1971). Análisis general de la competencia . Holden-Day. ISBN 978-0-8162-0275-1. (Referencia estándar sobre la teoría del equilibrio general . El capítulo 5 utiliza el teorema de Kakutani para demostrar la existencia de precios de equilibrio. El Apéndice C incluye una prueba del teorema de Kakutani y analiza su relación con otros resultados matemáticos utilizados en economía.)

Enlaces externos

"Teorema de Kakutani", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]