Teorema del punto fijo de Kakutani

Teorema del punto fijo para funciones con valores establecidos

En análisis matemático , el teorema del punto fijo de Kakutani es un teorema de punto fijo para funciones de valores establecidos . Proporciona condiciones suficientes para que una función con valores de 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 funciones con valores establecidos.

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 aplicación generalizada 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 con valores establecidos en S con las siguientes propiedades:

• φ tiene una gráfica cerrada ;
• φ ( x ) no está vacío y es convexo para todo x  ∈  S .

Entonces φ tiene un punto fijo .

Definiciones

Función de valor establecido

Una función con valores de conjunto φ del conjunto X al conjunto Y es alguna regla que asocia uno o más puntos en Y con cada punto en X. Formalmente puede verse como una función ordinaria de X al conjunto de potencias de Y , escrita como φ :  X  → 2 ^Y , tal que φ ( x ) no está vacía para cada . Algunos prefieren el término correspondencia , que se utiliza para referirse a una función que por cada entrada puede devolver muchas salidas. Así, cada elemento del dominio corresponde a un subconjunto de uno o más elementos del rango. ${\displaystyle x\in X}$

Gráfico cerrado

Se dice que una función con valores conjuntos φ:  X  → 2 ^Y tiene una gráfica cerrada 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 todas , tenemos . ${\displaystyle \{x_{n}\}_{n\in \mathbb {N} }}$ ${\displaystyle \{y_{n}\}_{n\in \mathbb {N} }}$ ${\displaystyle x_{n}\to x}$ ${\displaystyle y_{n}\to y}$ ${\displaystyle y_{n}\in \varphi (x_{n})}$ ${\displaystyle n}$ ${\displaystyle y\in \varphi (x)}$

Punto fijo

Sea φ:  X  → 2 ^X una función de valores establecidos. 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 en la línea de 45° (línea de puntos en rojo) que corta la gráfica de la función (sombreada 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]. ${\displaystyle \varphi (x)=[1-x/2,~1-x/4]}$

Una función con un punto fijo único

La función:

${\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{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.

Una función sin puntos fijos

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

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

${\displaystyle \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 punto fijo. Aunque satisface todos los demás requisitos del teorema de Kakutani, su valor no logra ser convexo en x = 0,5.

Una función que no satisface el gráfico cerrado.

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

${\displaystyle \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 punto fijo. Aunque satisface todos los demás requisitos del teorema de Kakutani, su gráfica no está cerrada; por ejemplo, considere las secuencias 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 establecer 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 de valores conjuntos en S con la propiedad de que φ ( x ) no está vacía, es cerrada y convexa 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 usando el teorema de la gráfica cerrada para funciones con valores establecidos, ^[5] que dice que para un espacio de rango compacto de Hausdorff Y , una función con valores establecidos φ :  X →2 ^Y tiene una gráfica cerrada si y solo si es hemicontinuo superior y φ ( x ) es un conjunto cerrado para todo x . Dado que todos los espacios euclidianos son Hausdorff (siendo espacios métricos ) y se requiere que φ tenga un valor cerrado en el enunciado alternativo del teorema de Kakutani, el teorema del gráfico cerrado implica que los dos enunciados son equivalentes.

Aplicaciones

Teoría de juego

El teorema del punto fijo de Kakutani se puede utilizar para demostrar el teorema minimax en la teoría de los juegos de suma cero . Esta aplicación fue discutida 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] Dicho de manera informal, 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 el 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 estrategia de cada jugador es el simplex estándar en R ^k . Entonces, S es el producto cartesiano de todos estos simples. De hecho, es un subconjunto no vacío, compacto y convexo de R ^kn .
• La función φ( x ) asocia con cada tupla una nueva tupla donde la estrategia de cada jugador es su mejor respuesta a las estrategias de otros jugadores en x . Dado que puede haber varias respuestas que sean igualmente buenas, φ tiene un valor establecido en lugar de un valor único. Para cada x , φ( x ) no está vacío ya que siempre hay al menos una mejor respuesta. Es convexo, ya que una combinación de dos mejores respuestas para un jugador sigue siendo una mejor respuesta para el jugador. Se puede demostrar que φ tiene una gráfica cerrada.
• Entonces el equilibrio de Nash del juego se define 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 equiparan simultáneamente la oferta con la demanda en todos los mercados de una economía. ^[6] La existencia de tales precios había sido una cuestión abierta en economía que se remontaba al menos a 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 materias primas.
• 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 manera 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 fue construido, este punto fijo debe corresponder a una tupla de precios que iguala la oferta con la demanda en todas partes.

División justa

El teorema del punto fijo de Kakutani se utiliza para demostrar la existencia de asignaciones de pasteles que no tienen 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 mediante el teorema de selección aproximada : ^[8]

Prueba

Según el teorema de selección aproximada, existe una secuencia de continuas tal que . Según el teorema del punto fijo de Brouwer, existe una secuencia tal que , entonces . ${\displaystyle f_{n}:S\to S}$ ${\displaystyle \operatorname {graph} (f_{n})\subset [\operatorname {graph} (\varphi )]_{1/n}}$ ${\displaystyle x_{n}}$ ${\displaystyle f_{n}(x_{n})=x_{n}}$ ${\displaystyle (x_{n},x_{n})\in [\operatorname {graph} (\varphi )]_{1/n}}$

Como es compacto, podemos tomar una subsecuencia convergente . Entonces ya que es un conjunto cerrado. ${\displaystyle S}$ ${\displaystyle x_{n}\to x}$ ${\displaystyle (x,x)\in \operatorname {graph} (\varphi )}$

Esquema de prueba

S = [0,1]

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

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

• Cree una secuencia de subdivisiones de [0,1] con puntos adyacentes moviéndose 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) a (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. Sean a ₀ = 0 y b ₀ = 1. Sea p ₀ cualquier punto en φ(0) y q ₀ sea cualquier punto en φ(1). Entonces, las condiciones (1) a (4) se cumplen inmediatamente. Además, dado que p ₀ ∈ φ(0) ⊂ [0,1], debe darse el caso de que p ₀ ≥ 0 y, por 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). Dejar,

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

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

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

a _{k +1} = m

segundo _{k +1} = segundo _k

p _{k +1} = r

q _{k +1} = q _k

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

ak ₊₁ = ak_​​

segundo _{k +1} = metro

pk ₊₁ = pk_​​

q _{k +1} = s .

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

• Encuentre un punto límite de las subdivisiones.

Tenemos un par de secuencias de intervalos y nos gustaría mostrar que convergen a un punto límite con el teorema de Bolzano-Weierstrass . Para hacerlo , interpretamos estas dos secuencias de intervalos como una única secuencia de puntos ₍ an _, pn , bn , _{qn )} . Esto radica en el producto cartesiano [0,1]×[0,1]×[0,1]×[0,1], que es un conjunto compacto según el teorema de Tychonoff . Dado que nuestra secuencia ( a _n , p _n , b _n , q _n ) se encuentra en un conjunto compacto, debe tener una subsecuencia convergente según Bolzano-Weierstrass . Fijemos la atención en dicha subsecuencia y dejemos que su límite sea ( a *, p *, b *, q *). Dado que la gráfica de φ es cerrada, 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 dado que ( 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 a *. Sea x = b * = a *.

Entonces tenemos la situación que

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

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

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

De lo contrario, podemos escribir lo siguiente. Recuerde 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 convexa y

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

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

S es un n -símplex

En dimensiones mayores a uno, los n -símplices son los objetos más simples sobre los que se puede demostrar el teorema de Kakutani. Informalmente, un n -símplex es la versión de dimensiones superiores de un triángulo. Demostrar el teorema de Kakutani para una función con valores establecidos definida en un símplex no es esencialmente diferente de demostrarlo para intervalos. La complejidad adicional en el caso de dimensiones superiores existe en el primer paso de dividir el dominio en subpartes más finas:

• Cuando dividimos intervalos en dos en el medio en el caso unidimensional, la subdivisión baricéntrica se utiliza para dividir un simplex 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 simples, el resultado combinatorio conocido como lema de Sperner se usa para garantizar la existencia de un subsímplejo apropiado.

Una vez que se han realizado estos cambios en el primer paso, los pasos segundo y tercero de encontrar un punto límite y demostrar que es un punto fijo casi no cambian con respecto al caso unidimensional.

S arbitraria

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

Generalizaciones de dimensión infinita

El teorema del 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 con valores conjuntos φ:  X →2 ^Y es hemicontinua superior si para cada conjunto abierto W  ⊂  Y , el conjunto { x | φ( x ) ⊂  W } está abierto en X . ^[11]

mapa de Kakutani

Sean X e Y espacios vectoriales topológicos y φ:  X →2 ^Y una función con valores establecidos. Si Y es convexo, entonces φ se denomina mapa de Kakutani si es hemicontinuo superior y φ ( x ) no está vacío, es compacto y convexo para todo x  ∈  X. ^[11]

Entonces, el teorema de Kakutani-Glicksberg-Fan se puede enunciar 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 un mapa de Kakutani. Entonces φ tiene un punto fijo.

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

Hay otra versión de que 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 con valores conjuntos en S que tiene una gráfica cerrada y la propiedad de que φ(x) es no vacía y convexa para todo x ∈ S. Entonces el conjunto de puntos fijos de φ no es -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 quedó desconcertado y respondió: "¿Qué es el teorema del punto fijo de Kakutani?"

Referencias

1. Kakutani, Shizuo (1941). "Una generalización del teorema del punto fijo de Brouwer". Revista de Matemáticas de Duke . 8 (3): 457–459. doi :10.1215/S0012-7094-41-00838-4.
2. Nash, JF Jr. (1950). "Puntos de equilibrio en juegos de N personas". Proc. Nacional. Acad. Ciencia. EE.UU . 36 (1): 48–49. Código bibliográfico : 1950PNAS...36...48N. doi : 10.1073/pnas.36.1.48 . PMC 1063129 . PMID  16588946. 
3. Frontera, Kim C. (1989). Teoremas del punto fijo con aplicaciones a la economía y la teoría de juegos . Prensa de la Universidad de Cambridge. ISBN 0-521-38808-2.
4. Osborne, Martín J.; Rubinstein, Ariel (1994). Un curso de teoría de juegos . Cambridge, MA: MIT.
5. Aliprantis, Charlambos; Kim C. Frontera (1999). "Capítulo 17". Análisis dimensional infinito: una guía para el autoestopista (3ª ed.). Saltador.
6. Starr, Ross M. (1997). Teoría del equilibrio general. Prensa de la Universidad de Cambridge. ISBN 978-0-521-56473-1.
7. McKenzie, Lionel (1954). "Sobre el equilibrio en el modelo de comercio mundial y otros sistemas competitivos de Graham". Econométrica . 22 (2): 147–161. doi :10.2307/1907539. JSTOR  1907539.
8. 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.
9. Glicksberg, IL (1952). "Una mayor generalización del teorema del punto fijo de Kakutani, con aplicación al equilibrio de Nash". Actas de la Sociedad Matemática Estadounidense . 3 (1): 170–174. doi :10.2307/2032478. JSTOR  2032478. Archivado desde el original el 22 de septiembre de 2017.
10. Fan, Ky (1952). "Teoremas de punto fijo y Minimax en espacios lineales topológicos localmente convexos". Proc Natl Acad Sci Estados Unidos . 38 (2): 121-126. Código bibliográfico : 1952PNAS...38..121F. doi : 10.1073/pnas.38.2.121 . PMC 1063516 . PMID  16589065. 
11. Dugundji, James ; Andrzej Granas (2003). "Capítulo II, Sección 5.8". Teoría del punto fijo (vista previa limitada) . Saltador. ISBN 978-0-387-00173-9.
12. Binmore, Ken (2007). "¿Cuándo existen los equilibrios de Nash?". Jugar de verdad: un texto sobre teoría de juegos (1ª ed.). Prensa de la Universidad de Oxford. pag. 256.ISBN​ 978-0-19-804114-6.

Otras lecturas

• Frontera, Kim C. (1989). Teoremas del punto fijo con aplicaciones a la economía y la teoría de juegos . Prensa de la Universidad de Cambridge. (Referencia estándar sobre teoría del punto fijo para economistas. Incluye una prueba del teorema de Kakutani).
• Dugundji, James ; Andrzej Granas (2003). Teoría del punto fijo . Saltador. (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).
• Flecha, Kenneth J .; FH Hahn (1971). Análisis Competitivo General . 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]