Wednesday, December 02, 2015

Teorema de punto fijo de Brouwer y Equilibrio de Nash con topología general

Hoy es el aniversario luctuoso de Luitzen Egbertus Jan Brouwer, fue un matemático Holandés que murió hace 49 años, él demostró uno de los tantos cientos de teoremas de punto fijo, pero el suyo (teorema de punto fijo de Brouwer), considero es de los más importantes (Junto con el que es más importante para mí que es el de Lefschetz que se usa para hacer cohomología en campos finitos), el de Brouwer es un resultado que movió toda la teoría de topología de espacios euclídeos, ecuaciones diferenciales, topología algebraica y teoría de juegos, donde de hecho el teorema del equilibrio de Nash es una consecuencia/corolario del teorema del punto fijo de Brouwer.

También aparte del aniversario luctuoso de Brouwer escribo este post porque hace pocos meses John Nash murió en un accidente automovilístico, y con mi "modita" de escribir un poco de teoría para recordar sus grandes mentes, dejo este post, que como siempre es personal, sin tanto rigor, pero algunas demostraciones, podrán haber errores, los cuales con gusto me pueden corregir en los comentarios o contactarme.

Equilibrio de Nash

Todos vieron esa película "Beautiful Mind" con Russell Crowe que hace el papel de John Nash, el teorema de John Nash sin matemáticas dice aproximadamente que en cualquier juego multijugador donde se permitan cambiar estrategias, y donde cada quién ya está en cierta parte de la evolución del juego donde se conocen las estrategias de los demás, siempre habrá un punto (de equilibrio de Nash) en el que al haber ejecutado su mejor estrategia cada quien, todos tendrán el mejor resultado posible visto individualmente.

Esto quiere decir que está el punto final del juego donde uno gana y todos los demás pierden, pero también hay un punto en donde todos están en su mejor posición posible con respecto a su estrategia, donde al dejar el juego sería la maximización de sus ganancias.

En la película esto lo ejemplifican de manera un poco machista en la escena del bar, donde al todos "competir" por la chica linda, a nadie los va a pelar por atascados o sólo a uno y los demás no podrán ligarse a las amigas de la chica linda porque no querrán ser "plato de segunda mesa", pero al cambiar la estrategia si no pela nadie a la linda y todos se van con sus amigas, la mayoría habrá "ligado". Este punto es el punto en donde se maximiza la ganancia de todos, esta maximización existe... SIEMPRE, y es lo que probó Nash, y es parte de la base de toda la economía mundial y teoría de decisiones.

Esta teoría impactó mucho la teoría económica ya que Adam Smith antes había descrito el individualismo como principal estrategia para lograr los mejores objetivos, pero aquí entra un juego filosófico/social/económico donde a veces el individualismo no siempre es lo mejor, incluso para el individuo ganador, ya que la maximización de recursos de los contrincantes podría traer otro tipo de consecuencias positivas que en la evolución del juego traerían una mayor ganancia a otro plazo (por ejemplo Paz, economía sólida entre países, et cétera).

Teorema del punto fijo de Brouwer


Aquí expondré el Teorema del punto fijo de Brouwer, pero sólo en dimensión 1, recuerdo que esto fue parte de un examen que tuve, para dimensión $latex n$ desafortundamente no tengo el tiempo (ni tampoco la demostración en mi mente a la mano) para poder hacerla, aunque recuerdo que funciona con grupos de homología, espero pronto (en vacaciones) poder dedicarle un tiempo para dimensión $latex n$.

Teorema (Punto fijo de Brouwer)
Sea $latex f\in C^0$, $latex \mathbb{D}^n=\lbrace \bar{x}\in \mathbb{R}^n : ||\bar{x}||\leq 1 \rbrace$ y $latex f:\mathbb{D}^n \rightarrow \mathbb{D}^n$ entonces existe $latex \bar{x_0}\in \mathbb{D}^n$ tal que $latex f(\bar{x_0})=\bar{x_0}$

En español: Si tenemos una función continua que va del disco cerrado de dimensión $latex n$ a sí mismo, entonces siempre habrá al menos un punto $latex \bar{x_0}\in \mathbb{D}^n$ donde la función se comporta como la identidad, es decir donde $latex f(\bar{x_0})=\bar{x_0}$.

Demostración para $latex n=1$, usando topología en vez del el trillado teorema de valor intermedio.

Primero vamos a ver qué significa geométricamente, con este dibujito que hice en este sitio.


Aquí tenemos una función $latex f$ en verde claramente continua en $latex \mathbb{D}^1=\lbrace x\in \mathbb{R} : |x| \leq 1\rbrace=[-1,1]$, es decir, el disco de dimensión 1 es un intervalo cerrado en $latex \mathbb{R}$ , también vemos en azul la función identidad que corresponde a la diagonal $latex \Delta=\lbrace (x,x) : x\in\mathbb{D}^1\rbrace \subsetneq \mathbb{D}^1\times\mathbb{D}^1$, que es justamente la gráfica de la función $latex y=x$ en $latex \mathbb{R}^2$ delimitada al cuadrado $latex [-1,1]\times[-1,1]=\mathbb{D}^1\times\mathbb{D}^1$.

La gráfica verde de la función la definiremos como $latex G_f=\lbrace (x,f(x)) : x\in\mathbb{D}^1\ \rbrace\subsetneq \mathbb{D}^1\times\mathbb{D}^1$.

Lo que queremos demostrar para cualquier $latex f\in C^0$ donde $latex f:\mathbb{D}^1\rightarrow \mathbb{D}^1$ es que $latex G_f\cap \Delta \neq \emptyset$, o sea que existe un punto $latex x_0\in \mathbb{D}^1$ tal que $latex f(x_0)=x_0$ y esto lo haremos muy rápidamente usando topología básica.

Sólo necesitamos recordar que un abierto básico  $latex U\subset \mathbb{R}^n$ es aquel que para todo $latex x\in U$ existe un $latex \epsilon$ >  $latex 0$ tal que $latex B_\epsilon(x)\subset U$ es decir, siempre podemos encontrar una bola rellena alrededor de $latex x$ de radio $latex \epsilon$ (la medida del radio está dada por la métrica de $latex \mathbb{R}^n$) totalmente contenida en $latex U$, por más que ese $latex x$ esté cerca de la frontera/orilla de $latex U$, ese punto no puede estar en la frontera de $latex U$ porque la frontera de $latex U$ no es parte del abierto $latex U$ por cómo está definida la noción de abierto.

Continuemos con la demostración. sea $latex f(-1)=a$ y $latex f(1)=b$ , en el dibujo los podemos ver en rojo. Si $latex f(-1)=-1$ o $latex f(1)=1$ ya acabaríamos cuyo caso sería trivial, entonces vamos a suponer lo contrario que es que $latex f(-1)=a > -1$ y $latex f(1)=b < 1$.

Lo que queremos usar es una idea de conexidad topológica, diciendo que cualquier camino entre los puntos rojos $latex (-1,a),(1,b)$ el cual lo denotamos por $latex \gamma_{a,b}\subset \mathbb{D}^1\times\mathbb{D}^1$ debe cruzar por $latex \Delta$ , lo cual intruitivamente parecería muy fácil, pero demostrarlo formalmente requiere topología, ya que lo estamos generalizando para cualquier función continua, sea como sea, y no sólo la función verde linda del dibujo.


Tenemos que por hipótesis $latex f$ es continua, por lo que $latex G_f$ está conectado (es conexo), y esto es porque $latex G_f=Im(\Phi)$ (imagen de $latex \Phi$) donde $latex \Phi$:

$latex \begin{aligned}\Phi:\mathbb{D}^1&\rightarrow \mathbb{D}^1\times\mathbb{D}^1 \\ x&\mapsto (x,f(x)) \end{aligned}$

Donde este mapeo es fácil demostrar que es continuo usando la continuidad de $latex f$.
Y de la continuidad es sabido por topología básica que una función continua $latex \phi:X\rightarrow Y$ entre dos espacios topológicos, si $latex X$ es conexo (o aún más fuerte, conexo por trayectorias) , entonces $latex Im(\phi)\subseteq Y$ también es conexo (por trayectorias si $latex X$ lo era), en este caso aquí la $latex \phi$ es nuestra $latex \Phi$. Este resultado es una especie de generalización del teorema del valor intermedio que todos vieron en su clase de cálculo 1.

Ahora, construiremos dos conjuntos abiertos.

$latex A=\lbrace (x,f(x)) : f(x) > x \rbrace$
$latex B=\lbrace (x,f(x)) : f(x) < x \rbrace$

Nota que estos dos conjuntos jamás pueden ser vacíos, ya que $latex (-1,a)\in A$ y $latex (1,b)\in B$.

Estos dos conjuntos representan intuitivamente lo que está arriba ($latex A$) y lo que está abajo ($latex B$) de la diagonal $latex \Delta$, y también nota que no tienen puntos fijos (ya que es lo que queremos demostrar).

Procediendo por contradicción, si suponemos que de hecho $latex f$ no tiene puntos fijos, entonces debería suceder que $latex G_f\cap \Delta = \emptyset$, lo cual implicaría que por como construimos $latex A$ y $latex B$ entonces $latex G_f = A\cup B$, pero $latex A,B\subset G_f$ son abiertos en $latex G_f$, y disjuntos, por lo que su unión es disjunta, esto contradice que la imagen de $latex \Phi$ que es $latex G_f$ es conexa $latex \blacksquare$

Nota sobre $latex A$ y $latex B$ al final de la demostración

¿por qué $latex A$ y $latex B$ son abiertos EN $latex G_f$?

Esto no lo justifiqué hace algunos años en mi examen, y me causó un comentario al final de la demostración en mi escrito, pero aquí dejo una idea con la que ustedes pueden demostrarlo (que es muy fácil en $latex \mathbb{R}$), ya que la métrica de $latex \mathbb{R}$ heredada a $latex G_f$ te permite demostrar que en este caso intervalos semi-abiertos/semi-cerrados  (con un extremo que incluya su frontera) , realmente son ABIERTOS, ya que lo obtienes de la topología heredada de $latex \mathbb{R}^2$ intersectándolo con un abierto, por ejemplo si $latex \alpha\in \mathbb{D}^1$ y $latex \beta >1$:

$latex U=(\alpha,1]=\mathbb{D}^1\cap (\alpha,\beta)$.

Donde $latex (\alpha,\beta)\subset \mathbb{R}$ , por lo que $latex U\subset\mathbb{D}^1$ es abierto con respecto a $latex \mathbb{D}^1$.

La demostración en general para cualquier dimensión, no existe generalizada de esta forma, se utiliza álgebra homológica para construir algo así como el teorema del valor intermedio generalizado, o el teorema que generaliza esto aún más es el de Borsuk-Ulam  si eres más ambicioso.

El teorema del equilibrio de Nash y el teorema del punto fijo de Brouwer están conectados en que la funcion de ganancia (que él demuestra que es continua) de todos los jugadores con respecto al espacio de todas las estrategias de cada uno (ambas están en N variables, donde N es el número de jugadores que es fínito para asegurar que se trabaje en un espacio compacto), tienen un punto fijo, y él demuestra que este punto es de equilibrio, no puedo entrar en más detalles de la prueba porque no conozco los artificios de teoría de Juegos a ese nivel, pero espero les haya servido.


Eduardo Ruíz Duarte (beck)
Twitter: @toorandom


1 comment:

Anonymous said...

Amigo, llegue unos 7 años tarde a tu página pero me encantó. Me he leído muchos de tus post y te aseguro que me los leeré todos.

Un abrazo desde bien lejos.

;)

Sr. Conejo