Intro a la Teoría de Juegos, parte 3

3. Juegos con un Valor

El juego {G=(X,Y,M)} se dice que tiene un valor si

\displaystyle  v_1=v_2  \ \ \ \ \ (9)

o sea, si

\displaystyle \sup_{x\in X}\inf_{y\in Y} M(x,y)=\inf_{y\in Y}\sup_{x\in X} M(x,y),

y en este caso se llama valor del juego al número {v=v_1=v_2}.

Cuando el juego tiene un valor {v}, las estrategias maximin y minimax (si existen) se llaman estrategias óptimas. Las estrategias maximin y minimax {\bar{x},\bar{y}} cumplen la condición (8) vista anteriormente, y, si ademas el juego tiene un valor {v}, entonces evidentemente vale

\displaystyle  M(x,\bar{y})\leq v\leq M(\bar{x},y),\quad\forall x\in X,\forall y\in Y.  \ \ \ \ \ (10)

A estas relaciones (10) se hace referencia diciendo que {(\bar{x},\bar{y})} es un punto de silla de la función {M}, o que {M} tiene un punto de silla en {(\bar{x},\bar{y})}.

De (10) se sigue fácilmente que {v=M(\bar{x},\bar{y})}; así pues (10) se puede escribir así

\displaystyle  M(x,\bar{y})\leq M(\bar{x},\bar{y})\leq M(\bar{x},y),\quad\forall x\in X,\forall y\in Y.

Se ha visto que la existencia de un valor (9) y de estrategias maximin y minimax {\bar{x},\bar{y}} implica la existencia de un punto de silla (10). Recíprocamente, si valen las relaciones (10) de punto de silla, el juego tiene un valor {v}, y {\bar{x},\bar{y}} son estrategias óptimas para J1 y J2 respectivamente.

En este caso en que la función {M} posee un punto de silla se dice que el valor del juego {v} y las estrategias óptimas {\bar{x},\bar{y}} constituyen la solución del juego. Resolver un juego es, pues, encontrar {v,\bar{x},\bar{y}} si es que existen.

De las propiedades expuestas resulta que si hubiese dos puntos de silla, por ejemplo {(\bar{x},\bar{y}),(\tilde{x},\tilde{y})} sucedería que

\displaystyle  M(x,\bar{y})\leq v\leq M(\bar{x},y),\quad\forall x\in X,\forall y\in Y \ \ \ \ \ (11)

y

\displaystyle  M(x,\tilde{y})\leq v^\prime\leq M(\tilde{x},y),\quad\forall x\in X,\forall y\in Y \ \ \ \ \ (12)

Sustituyendo en las primeras relaciones las variables {x,y} por {\tilde{x},\tilde{y}} y en la segunda por {\bar{x},\bar{y}} resulta

\displaystyle  M(\tilde{x},\bar{y})\leq v\leq M(\bar{x},\tilde{y}),\ M(\bar{x},\tilde{y})\leq v^\prime\leq M(\tilde{x},\bar{y})

de donde resulta {v=v^\prime}. Además los cuatro puntos {(\bar{x},\bar{y}),(\tilde{x},\tilde{y}),(\bar{x},\tilde{y}),(\tilde{x},\bar{y})} son puntos de silla por lo que es indiferente para cada jugador elegir una cualquiera de sus estrategias óptimas. Es fácil ver que el punto de silla definido para los juegos de dos personas es un punto de equilibrio con la definición que se dio para los juegos de {n} personas. Debe notarse que muchas propiedades enunciadas para los jugadores 1 y 2 siguen siendo válidas con ciertos cambios permutando entre sí los jugadores. Esto se debe a que el juego {G=(X,Y,M)} se corresponde con el juego {G^\prime=(Y,X,M^\prime)}, donde {M^\prime(y,x)=-M(x,y)} ya que ambos son el mismo juego cambiando de nombre a los dos jugadores. Este hecho permite omitir las demostraciones de las propiedades que resulten análogas en este tipo de correspondencia.

Posted in Teoría de Juegos | Tagged , | 2 Comments

varasdemate:

Very interesting article on recent developments concerning solving open problems.

Originally posted on Gödel's Lost Letter and P=NP:

HamiltonClaypic

Richard Hamilton is the mathematician who laid out the route that eventually led to the positive solution to the three-dimensional Poincaré Conjecture by Grigori Perelman. He is the Davies Professor of Mathematics at Columbia University. While Perelman famously declined both the Fields Medal in 2006 and the official Clay Millennium Prize recognition in 2010, citing among other factors the lack of concomitant recognition for Hamilton, Hamilton was awarded the Leroy Steele prize in 2009, shared the Shaw Prize in 2011, and had earlier won the 2003 Clay Research Award alongside Terence Tao.

Today Ken and I wish to talk about programs in mathematics, not C++ programs, but programs of attack on a hard open problem. Ken likes the British form “programme” for this.

View original 1,581 more words

Posted in math culture | Leave a comment

Teorema del punto fijo de Brouwer

Nos damos un pequeño break de la teoría de juegos para hablar un poco del teorema del punto fijo de Brouwer. Como vimos en el post sobre teoría de juegos y el teorema del punto fijo éste es un teorema que fundamenta la teoría de juegos y un teorema muy importante en topología y topología algebraica. Veremos el teorema y su prueba en inglés.

The theorem states the following: Let {f:D^2\rightarrow D^2} be a continuous map, where

\displaystyle D^2 = \{(x, y)\in\mathbb{R}^2 : x^2 + y^2\leq 1\}

Then {f} has a fixed point, i.e., there is some point {(x, y)\in D^2} with the property that {f(x, y) = (x, y)}

Proof Suppose that {f:D^2\rightarrow D^2} does not have a fixed point, so that {f(x, y) \neq (x, y)} for all {(x, y) \in D^2}. So, for each point {(x, y) \in D^2} we get two points {(x, y)} and {f(x, y)}, and we can draw a line through them both. Extend this line beyond {(x, y)} until it meets the boundary of {D^2} (i.e., {\mathbb{S}^1}), and let {g(x, y)} be the point where this happens. So we get a function {g : D^2\rightarrow \mathbb{S}^1} as in the picture.

brouwer1
This map {g} is continuous, essentially because if {(x', y')} is sufficiently close to {(x, y)}, then {f(x', y')} will be close to {f(x, y)} (since {f} is continuous) and, hence, {g(x', y')} will be reasonably close to {g(x, y)}. More rigorously, if {A} is an open arc around {g(x, y)}, then there is some radius {r} such that whenever {(x', y')} is in the open ball {B_r(x, y)} and {f(x', y')} is in the open ball {B_r(f(x, y))}, then {g(x', y')} is in {A}, as depicted below, where {A} is indicated by a bold line, and the balls around {(x, y)} and {f(x, y)} are indicated by the dotted circles of their perimeters. Any straight line which passes through both balls will hit the circle in the region {A}.

brouwer2
Since {f} is continuous, there is some radius {\delta} such that {f(x', y')\in B_r(f(x, y))} whenever {(x', y')\in B_\delta(x, y)}. Hence the preimage {g^{-1}(A)} contains {B_{\min(\delta,r)}(x, y)}. The same argument can be applied to any point in the preimage, so {g^{-1}(A)} is open, i.e., {g} is continuous. If {(x, y)} is on the boundary of {D^2}, then {g(x, y) = (x, y)} no matter what {f(x, y)} is. Now define a map

\displaystyle F : \mathbb{S}^1\times I \rightarrow \mathbb{S}^1

by {F((x, y), t) = g(tx, ty)}. This map {F} is continuous, so we can think of it as a homotopy between the map {h : \mathbb{S}^1\rightarrow \mathbb{S}^1} defined by { h(x, y) = F((x, y), 0)} and {j : \mathbb{S}^1\rightarrow \mathbb{S}^1} defined by {j(x, y) = F((x, y), 1)}. Now {h(x, y) = g(0, 0)} for all {(x, y)}, so {h} is the constant map and thus {\deg(h) = 0}. On the other hand, however, {j(x, y) = g(x, y) = (x, y)} for all {(x, y)}, so {j} is the identity map and {\deg(j) = 1}. If {F} is a homotopy between {h} and {j}, then these degrees must be equal. Since they are not, the map {F} cannot exist. Hence nor can {g}, showing in turn that the map {f} must have had a fixed point in the first place.

El teorema de Brouwer es un teorema de punto fijo que dice que una aplicación continua de un conjunto convexo y compacto en si mismo tiene un punto fijo. Schauder y Tychonoff ademas probaron que el teorema sigue siendo valido para espacios normados; y también para espacios localmente compactos. Luitzen Egbertus Jan Brouwer fue el principal teórico del Intuicionismo Matemático y el fundador de la topologia moderna.

Referencias:
-Mathematics – The Harper Collins Dictionary. Borowski & Borwein 1991
-Essential Topology – Martin Crossley 2005
Links de interes:
-Brouwer fixed point theorem by Palmieri
-The Brouwer fixed point theorem and the game of Hex

Posted in Compacidad y punto fijo, Teoría de Juegos | Tagged , , | 1 Comment

Intro a la Teoría de Juegos, parte 2

2. Juegos Rectangulares

Adaptando las definiciones que se dieron anteriormente para los juegos rectangulares al caso de juegos de dos personas y de suma cero, resulta la definición que veremos a continuación en la que omitimos los calificativos “de dos personas” y “de suma cero”, que quedarán sobreentendidos en lo sucesivo. Por cierto, el juego se llama “rectangular” por la facilidad de acomodar los datos de una manera rectangular, tipo matriz.

Despliegue rectangular de un juego

Un juego rectangular {G} está determinado por una terna

\displaystyle G=(X,Y,M)\ \ \ \ \ (1)

donde {X,Y} son conjuntos cualesquiera y {M} una función que tiene por dominio el producto cartesiano {X\times Y} y que toma valores reales

\displaystyle M:X\times Y\rightarrow\mathbb{R}.

Mientras no se diga nada en contra se supone que {M} es una función acotada. Para una realización del juego {G} se supone que existen dos jugadores que llamaremos jugador 1, J1, y jugador 2, J2. El J1 elige un elemento {x\in X} y el J2 elige un elemento {y\in Y}, estas elecciones las hacen los dos jugadores ignorando cuál ha sido la elección del otro jugador.

Una vez hechas estas elecciones, el J2 paga al J1 la cantidad {M(x,y)}. Así pues la ganancia del J1 es {M(x,y)} y la del J2 es el valor opuesto {\left(-M(x,y)\right)}. Por lo tanto el objetivo del J1 es conseguir el mayor valor posible de su ganancia {M(x,y)}; mientras que, por su parte, el J2 tratará de minimizar su pago {M(x,y)}.

Los elementos {x\in X} se llaman estrategias (o estrategias puras) del J1 y los elementos {y\in Y} se llaman estrategias (o estrategias puras) del J2. La función {M} se llama función de pago del juego {G}.

En un juego rectangular {G=(X,Y,M)} desempeñan un importante papel las dos funciones

\displaystyle  V_1:X\rightarrow \mathbb{R},\quad V_2:Y\rightarrow \mathbb{R}

definidas por

\displaystyle  V_1(x)=\inf_{y\in Y} M(x,y),\quad V_2(y)=\sup_{x\in X} M(x,y)  \ \ \ \ \ (2)

y los dos números

\displaystyle  v_1=\sup_{x\in X} V_1(x),\quad v_2=\inf_{y\in Y} V_2(y). \ \ \ \ \ (3)

entre estos elementos del juego siempre vale

\displaystyle  V_1(x)\leq v_1,\quad v_2\leq V_2(y). \ \ \ \ \ (4)

La interpretación intuitiva de estos datos es inmediata. El valor {V_1(x)} es la ganancia que tiene asegurada el J1 si elige la estrategia {x}; el número {v_1} es lo máximo que puede asegurarse si la estrategia la elige convenientemente. Análogas interpretaciones valen para {V_2(y)} y {v_2}. Un teorema importante que relaciona los valores {v_1,v_2} es el siguiente:

Sea {G=(X,Y,M)} un juego rectangular. Entonces se verifica que

\displaystyle v_1\leq v_2.\ \ \ \ \ (5)

Cuando existe una estrategia {\bar{x}\in X} tal que

\displaystyle  V_1(\bar{x})=\sup_{x\in X}V_1(x)=v_1  \ \ \ \ \ (6)

entonces a esta estrategia {\bar{x}} se le llama estrategia maximin para el J1. Esta estrategia existe si el supremo de {V_1(x)} es accesible. De modo análogo, una estrategia minimax es una estrategia {\bar{y}\in Y} tal que

\displaystyle  V_2(\bar{y})=\inf_{y\in Y}V_2(y)=v_2  \ \ \ \ \ (7)

y su existencia equivale a decir que el extremo inferior de {V_2(y)} es accesible.

Para estas estrategias se tiene, de (2), (6) y (7), que

\displaystyle  v_1\leq M(\bar{x},y),\quad M(x,\bar{y})\leq v_2,\quad \forall x\in X,\forall y\in Y.  \ \ \ \ \ (8)

Si existe la estrategia maximin {\bar{x}}, {v_1} es la ganancia que puede asegurarse el J1 jugando con ella. Del mismo modo, eligiendo la estrategia minimax (si existe), el J2 se asegura de que su pago no supere a {v_2} (o bien, que su ganancia no quede por debajo de {-v_2})

proxima semana: Juegos con valor.

Posted in Teoría de Juegos | Tagged , | Leave a comment

Intro a Teoría de Juegos

1. Generalidades

El objeto de la llamada “Teoría de Juegos” es el estudio de los juegos de estrategia.

Las primeras referencias a los juegos de estrategia se deben a E. Zermelo (1913) Uber eine anwendung der Mengenlehre auf die theorie des Schaschpiels, E. Borel (1924) Sur les jeux aus interviennent l’asard et l’habilité des joueux, y John von Neumann (1928) Zur theorie der Gesellschaftspiele. Se señala a la histórica obra de John von Neumann y Oskar Morgenstern (1944) Theory of Games and Economic Behaviour como la que consagra definitivamente la Teoría de Juegos colocándola, por su valor teórico y práctico, al mismo nivel que las otras teorías matemáticas.

Entre las primeras aplicaciones aparte de los temas económicos y militares recibieron una gran atención las relativas a la Estadística, a lo que contribuyó en gran medida la ingente labor de A. Wald quien además de su obra Statistical Decision Functions (1950), publicó numerosos trabajos sobre este tema.

Recientemente la Teoría de Juegos ha vuelto a destacar con la concesión del premio Nobel de Economía en 1994 a John F. Nash, Reinhard Selten y John Harsanyi, y en 2005 a Robert J. Aumann y Thomas C. Schelling; en ambos casos por sus estudios en Teoría de Juegos.

En un sentido amplio, un juego es una confrontación entre varias personas o equipos que llamaremos jugadores, cada uno de los cuales puede ejecutar algunas acciones de las que resulta como consecuencia final una ganancia (o pérdida) para cada jugador.

Generalmente, en la práctica, un juego de estrategia se desarrolla en etapas sucesivas en las que los jugadores intervienen alternativamente, y el resultado final del juego depende de las elecciones tomadas por los jugadores en los momentos en que les toca intervenir. Por un proceso de sintetización, un juego de este tipo se puede reducir a un juego con una estructura particularmente simplificada y que llamaremos juego rectangular o juego en forma normal. Podríamos decir que los juegos rectangulares constituyen la forma canónica o forma normal de los juegos de estrategia.

En un juego rectangular de {n} personas, el jugador {i} dispone de un conjunto {X_i} de acciones o estrategias, de modo que en una realización del juego, dicho jugador {i} debe elegir un elemento

\displaystyle  x_i\in X_i.

Además, en estos juegos deben estar definidas {n} funciones

\displaystyle M_i:X_1\times X_2\times\cdots\times X_n\rightarrow\mathbf{R}\quad\forall i=1,\ldots,n

llamadas funciones de pago, de modo que si los jugadores {1,2,\ldots,n} han elegido respectivamente las estrategias

\displaystyle x_1,x_2,\ldots,x_n

entonces el jugador {i} gana la cantidad representada por

\displaystyle M_i(x_1,x_2,\ldots,x_n).

Si este número es negativo, el jugador {i} sufre una pérdida igual al valor absoluto de dicho número.

La forma de desarrollarse este juego es pues, la siguiente:

Cada jugador {i} elige una de las estrategias {x_i\in X_i}. Estas elecciones se hacen de modo que cada jugador ignora las estrategias que eligen los restantes jugadores. Una vez que los {n} jugadores han hecho su elección, se reúnen las estrategias {x_i} para calcular los valores de las {n} funciones de pago {M_i(x_1,x_2,\ldots,x_n)} y estas son las ganancias de los jugadores {1,2,\ldots,n}.

Los jugadores conocen, previamente a su elección, las funciones {M_i}, y el modo de llevar a cabo el proceso anterior, por lo que pueden hacer un estudio previo para ver cuál es su estrategia mas favorable. La dificultad está en que el jugador {i} controla solamente una variable de la función {M_i} que determina su ganancia, mientras que las restantes {   n-1} variables las controlan los restantes jugadores.
El jugador {i} intenta maximizar {M_i(x_1,x_2,\ldots,x_n)} pero seguramente el efecto de la elección de los otros jugadores sobre esta función le es desfavorable.

El juego rectangular de {n} personas se dice ser de suma cero si se cumple que

\displaystyle \sum_{i=1}^n{M_i(x_1,x_2,\ldots,x_n)}=0,\quad\forall (x_1,x_2,\ldots,x_n)\in X_1\times X_2\times\cdots\times X_n.

En un juego rectangular de {n} personas, se dice que

\displaystyle (\bar{x}_1,\bar{x}_2,\ldots,\bar{x}_n)\in X_1\times X_2\times\cdots\times X_n

es un punto de equilibrio del juego si se verifica

\displaystyle M_i(\bar{x}_1,\bar{x}_2,\ldots,\bar{x}_{i-1},x_i,\bar{x}_{i+1},\ldots,\bar{x}_n)\leq M_i(\bar{x}_1,\bar{x}_2,\ldots,\bar{x}_{i-1},\bar{x}_i,\bar{x}_{i+1},\ldots,\bar{x}_n)

para todo {i} y todo {x_i\in X_i}.

Se considera que la existencia de un punto de equilibrio debe inducir a los jugadores a elegir las estrategias que componen dicho punto, con lo que el juego queda resuelto.

proxima semana: Juegos Rectangulares

Posted in Teoría de Juegos | Tagged , | 4 Comments

Pequeña nota sobre Teoría de Juegos y el Teorema del punto fijo

Como complemento del curso sobre Topología, presento aquí un resumen de un teorema fundamental de la teoría de juegos, cuya prueba depende fundamentalmente en el Teorema del punto fijo de Brouwer, que a su vez debe su resultado a la necesidad de compacidad del espacio en cuestión.

El enunciado del Teorema del punto fijo de Brouwer es el siguiente:

Sea {C} un conjunto convexo y compacto de {\mathbb{R}^n}. Si {f:C\rightarrow C} es continua, entonces

\displaystyle \exists x\in C\ni f(x)=x

La simplicidad del teorema es evidente y su resultado es poderoso. Pero tal belleza y simplicidad dependen fuertemente del hecho de que el espacio sea compacto. Pues, como contraejemplo, la generalización que parece inmediata de que el resultado sería cierto en el caso de un espacio infinito-dimensional de Hilbert falla precisamente por la ausencia de compacidad de la bola unitaria infinito-dimensional en dicho espacio. Un ejemplo es el de la función {f:\ell^2\rightarrow\ell^2} que manda una sucesión {x=(x_n)} dentro de la bola unitaria cerrada a la sucesión {(y_n)} definida por

\displaystyle y_n=\begin{cases}\sqrt{1-||x||_2^2}, & n=0\\x_{n-1}, & n\geq 1\end{cases}

En este caso se verifica que esta aplicación es continua, su imagen es subconjunto de la bola unitaria de {\ell^2}, pero no tiene un punto fijo.

Existen diversas demostraciones para este teorema. Este argumento procede por contradicción. Para simplificar, suponemos que {C=D^n}, la bola unitaria cerrada de dimensión {n}. Suponemos que {f:D^n\rightarrow D^n} no tiene ningún punto fijo. Así, para todo {x\in D^n}, existe una línea que pasa por {x} y {f(x)}. Tal línea interseca a {S^{n-1}} – la frontera de {D^n} – en un punto que llamamos {F(x)}. Esto define una retracción {F:D^n\rightarrow S^{n-1}}. Sabiendo que no puede existir tal retracción, llegamos a la contradicción. Probar que no existe una retracción de la esfera {D^n} en su frontera {S^{n-1}} en el caso {n>2} utiliza herramientas de Homología de grupos (aunque en el caso {n=1} es bastante claro). Otra prueba es una prueba casi elemental que utiliza el lema de Sperner en {n} dimensiones. Pero de esa no hablaremos acá.

Vemos, por ende, la condición de compacidad es fundamental para la existencia del teorema anterior, que a su vez sustenta el teorema Fundamental de los juegos finitos, el cual enunciamos a continuación:

Sea {G=(X,Y,M)} un juego finito, con {X=\{1,\ldots,m\},Y=\{1,\ldots,n\},M(i,j)=a_{ij}, i\in X, j\in Y}. Sea {\Gamma=(X^*,Y^*,M)} su extensión mixta. Entonces el juego tiene un valor {v}, es decir, {v_1^*=v_2^*=v}, donde {v_1^*=\sup_\xi\inf_\eta M(\xi,\eta)} y {v_2^*=\inf_\eta\sup_\xi M(\xi,\eta)}, y existen estrategias óptimas {\overline{\eta},\overline{\xi}} para el jugador 1, 2; respectivamente.

En otras palabras {V_1(\overline{\xi})=v_1^*,V_2(\overline{\eta})=v_2^*}

Como se mencionó al principio, el paso clave en la prueba de este teorema utiliza el teorema del punto fijo. Tal prueba fue hecha por el mismo John von Neumann – reconocido matemático húngaro-estadounidense que realizó importantes contribuciones a la ramas de matemática, economía, informática, entre otras.

Este teorema es fundamental en la teoría de juegos. Su resultado establece que cualquier juego finito de dos jugadores tiene un valor, es decir, una “solución”, o más específicamente una estrategia óptima para cada jugador.

Teoremas de la teoría de juegos subsiguientes que tácitamente suponen la existencia de un valor de juego, y que son a su vez teoremas absolutamente necesarios en la resolución y búsqueda de estrategias óptimas de juegos específicos, dependen del resultado del teorema fundamental de juegos finitos.

De esta manera, tenemos una cadena de resultados fundamentales que comienza con la suposición de compacidad del espacio en cuestión. De aquí la importancia de la interiorización del concepto de compacidad para todo matemático.

Referencias

Posted in Teoría de Juegos | Tagged , , , | 5 Comments

example within latex2wp

Look at the document source to see how to strike out text, how to use different colors, and how to link to URLs with snapshot preview and how to link to URLs without snapshot preview.

There is a command which is ignored by pdflatex and which defines where to cut the post in the version displayed on the main page Continue reading

Posted in pruebas | Tagged , , | 2 Comments

Cronograma doctorado (pba latex2wp)

2010-2013: Doctorado en Matemáticas

  • Inicio: setiembre 2010
  • Fin de investigación y entrega de documento de tesis: junio 2013
  • Defensa de la tesis: setiembre 2013
Posted in pruebas | 2 Comments

First!

…post.

Hello World.

Algunas varas de mate apareceran por aquí pronto, así que no se desesperen. Mate al rescate.

Posted in pruebas | 1 Comment