Articulo de referencia

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 multivaluadas . Proporciona condiciones suficientes para que una funci...

En análisis matemático , el teorema del punto fijo de Kakutani es un teorema del punto fijo para funciones multivaluadas . Proporciona condiciones suficientes para que una función multivaluada definida en un subconjunto compacto y convexo de un espacio euclidiano tenga un punto fijo , es decir, un punto que se mapea 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 este teorema a funciones multivaluadas.

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 n .
Sea φ : S → 2 S una función multivaluada en S con las siguientes propiedades:   
  • φ tiene una gráfica cerrada ;
  • φ ( x ) es no vacío y convexo para todo x S . 
Entonces φ tiene un punto fijo .

Definiciones

Función con valores de conjunto
Una función multivaluada φ del conjunto X al conjunto Y es una regla que asocia uno o más puntos de Y con cada punto de X. Formalmente, puede verse como una función ordinaria de X al conjunto potencia de Y , escrita como φ : X → 2 Y , tal que φ ( x ) es no vacío para cada   incógnitaincógnita{\displaystyle x\in X}Algunos prefieren el término correspondencia , que se utiliza para referirse a una función que, para cada entrada, puede devolver múltiples salidas. Así, cada elemento del dominio corresponde a un subconjunto de uno o más elementos del rango.
Gráfico cerrado
Se dice que una función multivaluada φ: 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 producto , es decir, para todas las secuencias         {incógnitanorte}nortenorte{\displaystyle \{x_{n}\}_{n\in \mathbb {N} }}y{ynorte}nortenorte{\displaystyle \{y_{n}\}_{n\in \mathbb {N} }}de tal manera queincógnitanorteincógnita{\displaystyle x_{n}\to x},ynortey{\displaystyle y_{n}\to y}yynorteϕ(incógnitanorte){\ Displaystyle y_ {n} \ en \ phi (x_ {n})}a pesar denorte{\displaystyle n}, tenemosyϕ(incógnita){\displaystyle y\in \phi (x)}.
Punto fijo
Sea φ: X → 2 X una función multivaluada. Entonces aX 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:φ(incógnita)=[1incógnita/2, 1incógnita/4]{\displaystyle \varphi (x)=[1-x/2,~1-x/4]}La función, mostrada 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 punteada en rojo) que interseca 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].

Una función con un único punto fijo.

La función:

φ(incógnita)={3/40incógnita<0,5[0,1]incógnita=0,51/40,5<incógnita1{\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 convexa para todo x es esencial para que el teorema sea válido.

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

φ(incógnita)={3/40incógnita<0,5{3/4,1/4}incógnita=0,51/40,5<incógnita1{\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 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 la condición de grafo cerrado

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

φ(incógnita)={3/40incógnita<0,51/40,5incógnita1{\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 un punto fijo. Aunque satisface todos los demás requisitos del teorema de Kakutani, su gráfica no es cerrada; por ejemplo, considérense 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 enunciar el teorema:

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

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

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

Aplicaciones

teoría de juegos

El teorema del punto fijo de Kakutani puede utilizarse para demostrar el teorema minimax en la teoría de juegos de suma cero . Esta aplicación fue analizada 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 fundamental en la teoría de juegos . [ 2 ] En términos informales, el teorema implica la existencia de un equilibrio de Nash en todo 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 cuya suma es igual a 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ímplexes. Es, en efecto, un subconjunto no vacío, compacto y convexo de R kn .
  • La función φ( x ) asocia a cada tupla una nueva tupla donde la estrategia de cada jugador es su mejor respuesta a las estrategias de los demás jugadores en x . Dado que puede haber varias respuestas igualmente buenas, φ es una función multivaluada en lugar de univaluada. Para cada x , φ( x ) no es vacía, ya que siempre hay al menos una mejor respuesta. Es convexa, puesto que una combinación de dos mejores respuestas para un jugador sigue siendo una mejor respuesta para ese jugador. Se puede demostrar que φ tiene una gráfica cerrada.
  • 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 demás jugadores. El teorema de Kakutani garantiza la existencia de este punto fijo.

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 igualan simultáneamente la oferta y 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 desde al menos Walras . La primera demostración de este resultado fue elaborada 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 forma 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 reto consiste en construir φ de manera que posea esta propiedad y, al mismo tiempo, satisfaga las condiciones del teorema de Kakutani. Si esto se logra, 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 pasteles que son a la vez libres de envidia y eficientes en el sentido de Pareto . Este resultado se conoce como el 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. A la inversa, 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 sucesión de continuosFnorte:SS{\displaystyle f_{n}:S\to S}de tal manera quegráfico(Fnorte)[gráfico(φ)]1/norte{\displaystyle \operatorname {graph} (f_{n})\subset [\operatorname {graph} (\varphi )]_{1/n}}Por el teorema del punto fijo de Brouwer, existe una secuenciaincógnitanorte{\displaystyle x_{n}}de tal manera queFnorte(incógnitanorte)=incógnitanorte{\displaystyle f_{n}(x_{n})=x_{n}}, entonces(incógnitanorte,incógnitanorte)[gráfico(φ)]1/norte{\displaystyle (x_{n},x_{n})\in [\operatorname {graph} (\varphi )]_{1/n}}.

DesdeS{\displaystyle S}es compacto, podemos tomar una subsecuencia convergenteincógnitanorteincógnita{\displaystyle x_{n}\to x}. Entonces(incógnita,incógnita)gráfico(φ){\displaystyle (x,x)\in \operatorname {graph} (\varphi )}ya que es un conjunto cerrado.

Esquema de demostración

S = [0,1]

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

Sea φ: [0,1] →2 [0,1] una función multivaluada en el intervalo cerrado [0,1] que satisface las condiciones del teorema del 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 sucesión 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.

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

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 existe un r ∈ φ( m ) tal que rm , entonces tomamos,

a k +1 = m
b k +1 = b k
p k +1 = r
q k +1 = q k

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

a k +1 = a k
b k +1 = m
p k +1 = p k
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).

  • Encuentra un punto límite de las subdivisiones.

Tenemos un par de secuencias de intervalos y queremos demostrar que convergen a un punto límite mediante el teorema de Bolzano-Weierstrass . Para ello, interpretamos estas dos secuencias de intervalos como una única secuencia de puntos, ( a n , p n , b n , q n ). Esta secuencia se encuentra 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 el teorema de Bolzano-Weierstrass . Centrémonos en dicha subsecuencia y sea su límite ( a *, p *, b *, q *). Dado que la gráfica de φ es cerrada, debe cumplirse 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 ia i ) ≤ 2 i por la condición (2),

b * − a * = (lim b n ) − (lim a n ) = lim ( b na n ) = 0.

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

Entonces tenemos la situación de que

φ( x ) ∋ q * ≤ xp * ∈ φ( x ).
  • Demuestra 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. 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 dicha línea entre p y q como una función de x (nótese 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

incógnita=(incógnitaqpagq)pag+(1incógnitaqpagq)q{\displaystyle 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 ) puesto que p * y q * lo hacen y, por lo tanto, x es un punto fijo de φ.

S es un n -símplex

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

  • Mientras que en el caso unidimensional dividimos los intervalos en dos por la mitad, la subdivisión baricéntrica se utiliza 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 extremos se movieran en direcciones opuestas, en el caso de los símplices se utiliza el resultado combinatorio conocido como el lema de Sperner para garantizar la existencia de un subsímplex apropiado.

Una vez realizados estos cambios en el primer paso, el segundo y el tercer paso, que consisten en encontrar un punto límite y demostrar que es un punto fijo, permanecen prácticamente inalterados con respecto al caso unidimensional.

Arbitrario S

El teorema de Kakutani para n-símplices puede utilizarse para demostrar el teorema para un S compacto y convexo arbitrario . Nuevamente, empleamos la misma técnica de crear subdivisiones cada vez más finas. Pero en lugar de triángulos con lados rectos, como en el caso de los n-símplices, ahora usamos triángulos con lados curvos. Formalmente, encontramos un símplice que cubre S y luego trasladamos el problema de S al símplice mediante una retracción por deformación . Después, podemos aplicar el resultado ya establecido para los n-símplices.

Cálculo

Papadimitriou, Vlatakis-Gkaragkounis y Zampetakis [ 9 ] demuestran que calcular un teorema de punto fijo de Kakutani es PPAD completo .

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 [ 10 ] y Ky Fan . [ 11 ] Para enunciar el teorema en este caso, necesitamos algunas definiciones más:

hemicontinuidad superior
Una función multivaluada φ: X →2 Y es hemicontinua superiormente si para todo conjunto abierto WY , el conjunto { x | φ( x ) ⊂ W } es abierto en X. [ 12 ]      
Mapa de Kakutani
Sean X e Y espacios vectoriales topológicos y φ: X2Y una función multivaluada. Si Y es convexa, entonces φ se denomina aplicación de Kakutani si es hemicontinua superiormente y φ( x ) es no vacía, compacta y convexa para todo xX. [ 12 ]   

Entonces, el teorema de Kakutani-Glicksberg-Fan se puede enunciar como: [ 12 ]

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 aplicación de Kakutani. Entonces φ tiene un punto fijo. 

El resultado correspondiente para funciones unívocas es el teorema del punto fijo de Tychonoff .

Existe otra versión en la que el enunciado del teorema se vuelve 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 multivaluada 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 φ es no vacío y compacto.   

Anécdota

En su libro de texto sobre teoría de juegos, [ 13 ] Ken Binmore recuerda que Kakutani le preguntó una vez 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 mostró perplejo y respondió: "¿Qué es el teorema del punto fijo de Kakutani?".

Referencias

  1. 1 2 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 .
  2. 1 2 Nash, JF Jr. (1950). "Puntos de equilibrio en juegos de N personas" . Proc. Natl. Acad. Sci. USA . 36 (1): 48– 49. Bibcode : 1950PNAS...36...48N . doi : 10.1073 / pnas.36.1.48 . PMC 1063129. PMID 16588946 .  
  3. Border, Kim C. (1989). Teoremas de punto fijo con aplicaciones a la economía y la teoría de juegos . Cambridge University Press. ISBN 0-521-38808-2.
  4. Osborne, Martin J.; Rubinstein, Ariel (1994). Un curso de teoría de juegos . Cambridge, MA: MIT.
  5. 1 2 Aliprantis, Charlambos; Kim C. Border (1999). "Capítulo 17". Análisis de dimensión infinita: Guía del autoestopista (3.ª ed.). Springer. 
  6. Starr, Ross M. (1997). Teoría del equilibrio general . Cambridge University Press. ISBN 978-0-521-56473-1.
  7. 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 . 
  8. ^ Shapiro, Joel H. (2016). "Un fárrago de punto fijo ". Publicaciones internacionales Springer. págs. 68 a 70. ISBN  978-3-319-27978-7. OCLC 984777840 . 
  9. ^ Papadimitriou, Christos H.; Vlatakis-Gkaragkounis, Emmanouil-Vasileios; Zampetakis, Manolis (2022). "La complejidad computacional de los juegos cóncavos multijugador y los puntos fijos de Kakutani". arXiv : 2207.07557 [ cs.CC ].
  10. Glicksberg, IL (1952). «Una generalización adicional del teorema del punto fijo de Kakutani, con aplicación al equilibrio de Nash» . Actas de la Sociedad Matemática Americana . 3 (1): 170– 174. doi : 10.2307/2032478 . JSTOR 2032478. Archivado del original el 22 de septiembre de 2017. 
  11. 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 .  
  12. 1 2 3 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.
  13. Binmore, Ken (2007). "¿Cuándo existen los equilibrios de Nash?" . Jugando de verdad: Un texto sobre teoría de juegos (1.ª ed.). Oxford University Press. pág. 256. ISBN   978-0-19-804114-6.

Lecturas adicionales

  • Border, Kim C. (1989). Teoremas de punto fijo con aplicaciones a la economía y la teoría de juegos . Cambridge University Press.(Obra de referencia estándar sobre la teoría del punto fijo para economistas. Incluye una demostración del teorema de Kakutani).
  • Dugundji, James ; Andrzej Granas (2003). Teoría del punto fijo . Springer.(Tratamiento matemático exhaustivo y de alto nivel de la teoría del punto fijo, incluyendo los análogos de dimensión infinita del teorema de Kakutani).
  • Arrow, 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 demostración del teorema de Kakutani y analiza su relación con otros resultados matemáticos utilizados en economía).