BLOQUE 7: Introducción a la Teoría de Juegos
Clase 1: Los juegos y su representación
La Teoría de Juegos ha sido diseñada para tratar de entender las interacciones del ser humano. Es decir, para tratar de predecir cómo va a comportarse un individuo, interactuando con su entorno, bajo ciertos supuestos.
En esta introducción vamos a asumir, como supuesto más importante, que el individuo es racional. Ser racional implica, en este contexto, que el individuo tiene toda la información disponible y que la sabe utilizar para su propio beneficio. Pero, además, que el resto de individuos con los que interactúa hace lo mismo. Si esto es asumible, entonces podemos plantear un juego. Pero… ¿qué es un juego?
Un juego:
Un juego, en principio, es un modelo matemático para especificar interacción entre individuos y tiene, entre otros, estos ingredientes
- jugadores o agentes (en nuestro caso, va a ser un conjunto finito. De hecho, sólo trabajaremos con 2 jugadores)
- estrategias: son la descripción de los posibles movimientos que compondrán el juego. En nuestro caso, como mucho cada jugador tendrá 4 posibles estrategias
- pagos: es el beneficio o pérdida que le supondrá a un jugador llevar a cabo cada estrategia. Nosotros, como tendremos 2 jugadores y estrategias finitas, podremos ponerlos en una matriz.
Ahora, veamos un ejemplo y su especificación
Dos alumnos han copiado en un examen y el profesor lo sabe. Pero necesita que confiesen. Para ello, los profesores elaboran un mecanismo de incentivos. Reúnen a los dos alumnos en dos aulas distintas, sin la posibilidad de que se comuniquen entre ellos. Y le dicen a cada alumno: “si los dos confesáis, os pondremos un 4 a cada uno e iréis a la extraordinaria. Si uno confiesa, pero el otro no, al que confiesa se le pondrá un 7 como premio pero, al que no confiese, se le expulsará. Si los dos no confiesan, se os dejará con un 5, porque el examen está aprobado, ya que habéis copiado de alguien que sabe”. Si representamos las estrategias y los pagos en una tabla, tendremos algo así:
| \(A1 \ A2\) | Confesar | No Confesar | |
| Confesar | 4, 4 | 7, Exp | |
| No Confesar | Exp,7 | 5,5 |
- Qué harías si fueras uno de ellos?.Lo normal es pensar “no confesamos”. Si no confesamos, se verán obligados a aprobarnos porque no tienen pruebas de que hayamos copiado. Veremos que, en realidad, tal y como está configurado el juego, la predicción que obtendremos es distinta. Pero no nos adelantemos.
Estrategias dominadas
Para tratar de ver cómo predecir qué harán los jugadores (o agentes) en un juego, vamos a empezar a definir estrategias dominadas. Es un concepto muy sencillo: diremos que una estrategia para un jugador estará dominada por otra si sus pagos son menores que los de la dominante, independientemente de los pagos del otro jugador. En cambio, decimos que una estrategia es débilmente dominada si hay pagos iguales y peores al de los de la estrategia dominante. Si eso ocurre, esa estrategia se elimina porque el jugador, al ser racional y tener toda la información, nunca la querrá jugar.
Por ejemplo, sea el siguiente juego
| Player 2 | ||||
| \(X\) | \(Y\) | \(Z\) | ||
| \(X\) | 1,-1 | 2, -2 | 4,-4 | |
| Player 1 | \(Y\) | 1,-1 | 0,0 | 5,-5 |
| \(Z\) | 0,0 | 1, -1 | -1,1 |
Para analizar si alguna estrategia está o no dominada, podemos empezar por el jugador que queramos: en este caso, empecemos por filas. Nos olvidamos, por un momento, de los pagos del jugador 2
| Player 2 | ||||
| \(X\) | \(Y\) | \(Z\) | ||
| \(X\) | \(\color{green}{1},\color{grey}{-1}\) | \(\color{green}{2},\color{grey}{-2}\) | \(\color{green}{4},\color{grey}{-4}\) | |
| Player 1 | \(Y\) | \(\color{green}{1},\color{grey}{-1}\) | \(\color{green}{0},\color{grey}{0}\) | \(\color{green}{5},\color{grey}{-5}\) |
| \(Z\) | \(\color{green}{0},\color{grey}{0}\) | \(\color{green}{1},\color{grey}{-1}\) | \(\color{green}{-1},\color{grey}{1}\) |
Y , ahora, miramos fila a fila si alguna es tan buena o mejor que otra. Si analizamos, la estrategia \(X\) del jugador 1, vemos que no siempre es preferida a la \(Y\), por lo que no hay dominación entre ambas. Por otro lado, entre la \(Y\) y la \(Z\), tampoco. Pero -si nos fijamos- entre la \(X\) y la \(Z\) del jugador 1 , la \(X\) domina a la \(Z\), por lo que podemos eliminarla: el jugador 1 nunca querrá jugar esa estrategia
| Player 2 | ||||
| \(X\) | \(Y\) | \(Z\) | ||
| \(X\) | \(\color{green}{1},\color{grey}{-1}\) | \(\color{green}{2},\color{grey}{-2}\) | \(\color{green}{4},\color{grey}{-4}\) | |
| Player 1 | \(Y\) | \(\color{green}{1},\color{grey}{-1}\) | \(\color{green}{0},\color{grey}{0}\) | \(\color{green}{5},\color{grey}{-5}\) |
Ahora, seguimos buscando. Como en el jugador 1 no encontramos más estrategias dominadas, cambiamos de jugador: analizamos por columnas. Nos “olvidamos” entonces, de los pagos del jugador 1:
| Player 2 | ||||
| \(X\) | \(Y\) | \(Z\) | ||
| \(X\) | \(\color{grey}{1},\color{green}{-1}\) | \(\color{grey}{2},\color{green}{-2}\) | \(\color{grey}{4},\color{green}{-4}\) | |
| Player 1 | \(Y\) | \(\color{grey}{1},\color{green}{-1}\) | \(\color{grey}{0},\color{green}{0}\) | \(\color{grey}{5},\color{green}{-5}\) |
Como vemos, la estrategia \(Z\) está dominada para el jugador 2 por ambas estrategias. La eliminamos.
| Player 2 | ||||
| \(X\) | \(Y\) | |||
| \(X\) | \(\color{grey}{1},\color{green}{-1}\) | \(\color{grey}{2},\color{green}{-2}\) | ||
| Player 1 | \(Y\) | \(\color{grey}{1},\color{green}{-1}\) | \(\color{grey}{0},\color{green}{0}\) |
Volvemos ahora otra vez a analizar al jugador en filas (hay que iterar de esta manera hasta que ya no se pueda seguir)
| Player 2 | ||||
| \(X\) | \(Y\) | |||
| \(X\) | \(\color{green}{1},\color{grey}{-1}\) | \(\color{green}{2},\color{grey}{-2}\) | ||
| Player 1 | \(Y\) | \(\color{green}{1},\color{grey}{-1}\) | \(\color{green}{0},\color{grey}{0}\) |
Como vemos, para el jugador 1, la estrategia \(Y\) está dominada, por lo que finalmente, llegamos a
| Player 2 | ||||
| \(X\) | \(Y\) | |||
| Player 1 | \(X\) | \(\color{green}{1},\color{grey}{-1}\) | \(\color{green}{2},\color{grey}{-2}\) | |
En este caso, es fácil ver que la predicción del juego es que ambos jueguen la estrategia \(\left\{ X,X\right\}\). No hay otra que incentive a ambos jugadores a salirse de esta estrategia sin que salgan perdiendo.
| Player 2 | ||||
| \(X\) | ||||
| Player 1 | \(X\) | \(\color{green}{1},\color{green}{-1}\) | ||
Sin embargo,¿ Se podrá siempre predecir el resultado de un juego usando esa manera de “podar” estrategias?
Prueba a hacerlo en este juego
| Player 2 | ||||
| \(X\) | \(Y\) | \(Z\) | ||
| \(X\) | 1,-1 | 2, -2 | 4,-4 | |
| Player 1 | \(Y\) | 0,0 | 3,3 | 5,-5 |
| \(Z\) | 4,-4 | 3, -3 | -1,1 |
Como ves, no encontrará estrategias dominadas. Entonces ¿Qué podremos predecir de este juego?
Equilibrio de Nash
Para tratar de uscar una solución al juego anterior, vino J.F Nash y desarrolló una idea de equilibrio. Para escribir su definición de manera propia, vamos a definir algo mejor los elementos de un juego entre dos personas:
- Llamaremos \(\mathcal{X},\mathcal{Y}\) a los conjuntos de estrategias del primer y segundo jugadores. Para abreviar se los suele llamar: espacios de estrategias.
- El pago que recibe cada jugador dadas las estrategias de ambos jugadores serán: \(U_{1}(x,y),U_{2}(x,y)\) donde tenemos la “utilidad” que le reporta a cada jugador la estrategia tomada por el jugador 1 (\(x\in\mathcal{X},\)\(y\in\mathcal{Y})\).
De esta manera, Nash definió su equilibrio como:
Equilibrio de Nash:
sean \(x^{*}\in\mathcal{X}\),\(y^{*}\in\mathcal{Y}\) un par de estategias. Serán Equilibrio (de Nash) si satisfacen:
\[ U_{1}(x^{*},y^{*})\geq U_{1}(x,y^{*})\:para\:x\in\mathcal{X} \]
\[ U_{2}(x^{*},y^{*})\geq U_{2}(x^{*},y)\:para\:y\in\mathcal{Y}, \]
es decir el jugador 1 buscará su óptimo fijando el óptimo del jugador 2 y viceversa. Como ves, son problemas de optimización “acoplados”: uno busca su óptimo pensando que su contrincante también optimiza. Ese es otro aspecto de la racionalidad.
Consecuentemente, cada jugador individual no gana nada modificando su estrategia mientras los otros mantengan las suyas. Así, cada jugador está ejecutando el mejor movimiento posible teniendo en cuenta la mejor respuesta (movimientos) de los demás jugadores.
En otras palabras, un equilibrio de Nash es una situación en la cual todos los jugadores han puesto en práctica, y saben que lo han hecho, una estrategia que maximiza sus ganancias dadas las estrategias de los otros. Consecuentemente, ningún jugador tiene ningún incentivo para modificar individualmente su estrategia.
Es importante tener presente que un equilibrio de Nash no implica que se logre el mejor resultado conjunto para los participantes, sino sólo el mejor resultado para cada uno de ellos considerados individualmente. Es perfectamente posible que el resultado fuera mejor para todos si, de alguna manera, los jugadores coordinaran su acción.
Buscamos un equilibrio de Nash
Volvemos al problema de los que han pillado copiando
| \(A1 \ A2\) | Confesar | No Confesar | |
| Confesar | 4, 4 | 7, Exp | |
| No Confesar | Exp,7 | 5,5 |
Siguendo las instrucciones de la definición, tenemos que pensar lo siguiente:
- “me sitúo en el jugador A1 y señalo, para cada estrategia de A1, las mejores estrategias de A2 (es decir, qué haría A2 si fuera racional)
| \(A1 \ A2\) | Confesar | No Confesar | |
| Confesar | \(4,\color{red}{4}\) | 7, Exp | |
| No Confesar | \(Exp,\color{red}{7}\) | 5,5 |
Como vemos, si el jugador 1 confiesa, el jugador 2 prefiere confesar. Si el jugador 1 no confiesa, entonces, el jugador 2 prefiere confesar
Ahora, hago lo mismo con el jugador A2.
- Me sitúo en este y, para cada estrategia de A2, busco las mejores estrategias de A1:
| \(A1 \ A2\) | Confesar | No Confesar | |
| Confesar | \(\color{green}4,\color{red}{4}\) | \(\color{green}7, Exp\) | |
| No Confesar | \(Exp,\color{red}{7}\) | 5,5 |
Como vemos, hay un par de estrategias: \(\left\{ C,C\right\}\), que es elegida por ambos jugadores, por lo que esta será el equilibrio. Veamos:
- Si el jugador 1 o 2 cambiaran a no confesar, estarían peor (los expulsarían)
- Los dos estarían mejor si NO confiesan. De hecho, aprobarían. Pero eso no va a ocurrir, dado el comportamiento egoísta (maximizador) que se supone que tendrán los jugadores: “si yo confieso, tendré un 7”.
¡Esa es la predicción del juego mediante el equilibrio de Nash!
Siempre habrá equilibrio de Nash?
Podría, incluso, haber más de uno (lo cual no será muy informativo). Mira este ejemplo:
Una pareja se quiere mucho y sólo puede verse los fines de semana. Han inventado un juego para aportar diversión a la relación. Todos los fines de semana elegirán si van al parque de atracciones o a un concierto de dodecafonismo de Arnold Schoenberg (escucha aquí su maravillosa obra “noche transfigurada’’: youtube.com/watch?v=Xrmsl2bkvak )
A P1 le encantan los parques de atracciones y a P2 le encanta el dodecafonismo. Pero hay otra cosa que les gusta: coicidir. Pero la dificultad en coincidir va a estar en que el viernes tomarán la decisión de donde ir sin decírselo entre ellos. La sorpresa será “si se encuentran o no”
Vamos a proponer una matriz de pagos que refleje lo que pretendemos. Por ejemplo, esta
| \(P1 \ P2\) | Parque | Schonberg | |
| Parque | 7, 4 | 0,0 | |
| Schonberg | 0,0 | 4,7 |
(nota que los valores son arbitrarios. Lo importante es que si no coinciden van a estar más infelices que si coinciden. Además, si acaban en el parque de atracciones, P1 estará más feliz y, si acaban en el concierto de Schonberg, será P2 el que esté más feliz. ¿Qué va a pasar?
Vamos a buscar el equilibrio de Nash. Empecemos por P1. ¿Qué hará el jugador P2 ante cada estrategia de P1?
| \(P1 \ P2\) | Parque | Schonberg | |
| Parque | \(7,\color{red}{4}\) | 0,0 | |
| Schonberg | 0,0 | \(4,\color{red}{7}\) |
Y ahora, ¿qué hará P1 ante cada estrategia de P2?
| \(P1 \ P2\) | Parque | Schonberg | |
| Parque | \(\color{green}7,\color{red}{4}\) | 0,0 | |
| Schonberg | 0,0 | \(\color{green}4,\color{red}{7}\) |
Tenemos ¡Dos equilibrios de Nash! ¿Qué hacemos?
En realidad, tener dos equilibrios de Nash es casi igual que no tener ninguno. No nos aporta gran información sobre la predicción el juego. Sin embargo, Nash probó que los juegos con jugadores y estrategias finitas tenían un equilibrio en…estrategias mixtas.
Bien, antes de ver qué es una estrategia mixta, diremos que las estrategias que hemos visto hasta ahora se llaman PURAS.
Clase 2: Equilibrios en estrategias mixtas
La idea de este equilibrio es pensar que el juego se puede repetir más de una vez en las mismas condiciones (como en el caso de las parejas). Si esto es así, y la información que tienen los individuos es simpre la misma (por ejemplo, en el juego de la pareja, si una semana no coicidimos, no quiere decir que la semana siguiente no vayamos a coincidir: si las instrucciones son las mismas, podría pasar cualquier cosa. En realidad vamos a asumir que podría pasar cualquier cosa, pero que estará dirigida por cierta aleatoriedad. Es decir, cada jugador, en función de sus preferencias, tendrá una distribución de probabilidades para cada estrategia. Por ejemplo, P1 tendrá la siguiente:
\[ P1\begin{cases} P(parque) & p\\ P(Schonberg) & 1-p \end{cases} \]
donde \(0\leq p\leq1\). Por otro lado, P2:
\[ P2\begin{cases} P(parque) & q\\ P(Schonberg) & 1-q \end{cases} \]
donde \(0\leq q\leq1\).
¿Qué estrategia elegir si cada una tiene una probabilidad asociada?
Incluyamos las probabilidades en la tabla:
| P.2 | ||||
| \(q\) | \(1-q\) | |||
| Parque | Schonberg | |||
| P.1 | \(p\) | Parque | \(7,4\) | 0,0 |
| \(1-p\) | Schonberg | 0,0 | \(4,7\) |
Ahora, calcularemos lo que llamamos “utilidad esperada” que es el pago que recibirá cada jugador, ante cada estrategia, teniendo en cuenta que esos pagos son aleatorios (dependen de \(p,q)\). Entonces, para cada jugador/estrategia:
| P.2 | |||||
| \(q\) | \(1-q\) | ||||
| Parque | Schonberg | ||||
| P.1 | \(p\) | Parque | \(7,4\) | 0,0 | \(7q+0(1-q)\) |
| \(1-p\) | Schonberg | 0,0 | \(4,7\) | \(0q+4(1-q)\) | |
| \(4p+0(1-p)\) | \(0p+7(1-p)\) |
Como ves, cada jugador se ve influido por las probabilidades del contrario. Por ejemplo \(7q+0(1-q)\), significa que P1 espera ganar 7 con probabilidad \(q\) y 0 con probabilidad \(1-q\), si P1 juega Parque.
Ahora bien, como P1 debería manternerse indiferente ante Parque, Schonberg, ya que ninguna es preferible (lo mismo hará P2) la estrategia consistirá en resolver:
\[ \begin{cases} 7q+0(1-q)=0q+4(1-q)\\ 4p+0(1-p)=0p+7(1-p) \end{cases} \]
de donde \(p=2/3\),\(q=1/3.\) Fíjate entonces que la interpretación del juego es la siguiente:
- De cada tres veces, P1 irá 2 veces al parque de atracciones y P2 al concierto de Schonmberg
- El valor del juego se obtiene sustituyendo para cada jugador en cualquiera de las utilidades. Por ejemplo \(V_{P1}=7/3,V_{P2}=8/3.\)
- En los juegos de suma cero se obtendrá el mismo valor para ambos jugadores solo que con signo cambiado.
Ejemplo con un juego de suma cero
Considera el siguiente juego de suma nula 2x2, donde se presenta la matriz de pagos asociada al jugador 1 (en filas):
| P.2 | |||||
| A | S | ||||
| P.1 | A | \(-2\) | \(2\) | ||
| S | \(0\) | \(1\) |
Si escribimos la matriz para los dos jugadores, que es más cómodo:
| P.2 | |||||
| A | S | ||||
| P.1 | A | \((-2,2)\) | \((2,-2)\) | ||
| S | \((0,0)\) | \((1,-1)\) |
como verás, no hay estrategias dominadas ni equilibrios en estrategias puras. Es por ello que planteamos la solución en mixtas:
| P.2 | |||||
| \(q\) | \(1-q\) | ||||
| A | S | ||||
| P.1 | \(p\) | A | \(-2,2\) | \(2,-2\) | \(-2q+2(1-q)\) |
| \(1-p\) | S | \(0,0\) | \(1,-1\) | \(0q+1(1-q)\) | |
| \(2p+0(1-p)\) | \(2p+1(1-p)\) |
De esta forma, obtendremos \[ -2q+2-2q=-1-q\Rightarrow q=\frac{3}{5} \]
y, por otro lado: \[ 2p=-2p+1-p\Rightarrow p=\frac{1}{5} \]
Por lo que los jugadores seguirán estas estrategias: \(\left\{ p,1-p,q,1-q\right\} =\left\{ \frac{1}{5},\frac{4}{5},\frac{3}{5},\frac{2}{5}\right\}\) y el valor del juego es (sustituye en cualquiera de los pagos esperados) \(\left\{ \frac{2}{5},-\frac{2}{5}\right\}\). Es decir, en promedio el jugador 1 recibirá \(2/5\) y el jugador 2 pagará \(2/5.\)