**SVRAI** Teoría de Juegos I Juegos No Cooperativos  # Introducción Los sistemas multiagente pueden agruparse a grandes rasgos en dos categorías: * los **Sistemas Cooperativos**, en los que todos los agentes comparten un objetivo común y cooperan plenamente para alcanzarlo, y * los **Sistemas No Cooperativos**, en los que cada agente tiene sus propios deseos y preferencias, que pueden entrar en conflicto con los de otros agentes. La primera situación suele darse cuando todos los agentes están controlados por un único propietario (por ejemplo, una misión de exploración y rescate con varios robots), mientras que la segunda situación es más probable cuando los agentes tienen diferentes propietarios (por ejemplo, en un proceso de subasta electrónica, en la que los agentes representan a diferentes postores en un mercado electrónico y todos ellos tratan de maximizar su propia utilidad). Incluso con agentes cooperativos, garantizar el buen funcionamiento de un sistema multiagente no es fácil debido a factores que van desde el uso de canales de comunicación poco fiables hasta las limitaciones computacionales. Ir un paso más allá y permitir la existencia de agentes no cooperativos añade una nueva dimensión a la complejidad de este problema, ya que hay que incentivar a los agentes para que elijan un plan de acción deseable en un entorno donde no pueden estar seguros de las prioridades ni objetivos de los demás agentes. Esta dificultad suele abordarse utilizando herramientas de la **Teoría de Juegos**, una rama de las Matemáticas que, en su relación con los sistemas multiagente, describe las consecuencias de las interacciones entre las estategias de los jugadores en términos de las recompensas individuales que se reciben o pagan [#Shoham]. La Teoría de Juegos se funda formalmente en el libro *The Theory of Games and Economic Behavior*, de Neumann y Morgenstern en 1944 [#Neumann], donde los autores introducen una forma matemática de analizar ciertos tipos de decisiones en las que dos o más partes realizan acciones que repercuten en las decisiones de todas ellas. En [#Osborne] se puede encontrar un contenido suficientemente amplio del tema general, y en [#Marden] un curso más actual sobre su relación con Sistemas Multiagente. En este capítulo nos centramos en los sistemas no cooperativos (en el siguiente capítulo daremos unas pinceladas sobre sistemas cooperativos). Comenzamos hablando de **Juegos en Forma Normal**, es decir, en los que todos los jugadores tienen información completa sobre las preferencias de los demás y eligen sus acciones simultáneamente, para pasar a continuación a presentar los **Juegos en Forma Extensiva**, donde los agentes/jugadores actúan de forma secuencial. # Juegos en Forma Normal Desde el punto de vista de la **Teoría de Juegos**, un juego es una interacción entre múltiples agentes con intereses propios. Para describir este tipo de escenario, necesitamos especificar los siguientes componentes: - El conjunto de agentes, o *jugadores*, que participan en el juego. - Para cada agente, el conjunto de acciones disponibles. Como tenemos varios agentes, este conjunto lo notaremos a partir de un vector de acciones elegidas (una por cada agente) al que llamaremos **perfil de acción**. - El conjunto de *resultados posibles* por las acciones colectivas, que supondremos deterministas, es decir, están determinados únicamente por las acciones seleccionadas por todos los agentes. - Para cada agente, una *función de recompensa o utilidad* (como vimos ya en los [Procesos de Markov](MDP.md.html)), que asigna un valor numérico determinista a cada resultado. Nos limitaremos a juegos con un número finito de jugadores, aunque se pueden considerar variantes con una cantidad infinita de ellos, o incluso un continuo de jugadores, pero no supondremos que los conjuntos de acciones de los jugadores tengan que ser finitos. Más formalmente: !!!def: Definición: Juego en Forma Normal Un **Juego en Forma Normal** es una tupla $G = (N,(A_i)_{i\in N},(u_i)_{i\in N})$, donde: 1. $N = \{1,\dots,n\}$ es el conjunto de agentes. 2. Para cada $i\in N$, $A_i$ es el conjunto de acciones, o estrategias, disponibles para el agente $i$, y 3. $u_i : A \to \mathbb{R}$ es la función de recompensa del agente $i$, que asigna una recompensa numérica a cada perfil de acción $a = (a_1,\dots,a_n) \in A=A_1\times \dots\times A_n$. Salvo que se indique lo contrario, en lo que sigue trabajaremos bajo las condiciones de esta definición. Además, a menudo tendremos que razonar sobre las acciones de un jugador manteniendo fijas las acciones de todos los demás jugadores. Por ello, usamos una notación especial para el vector de acciones de todos los jugadores que no sean el jugador $i$: !!! Dado un perfil de acción $a = (a_1,\dots,a_n)$ y un jugador $i\in N$, denotaremos por: * $a_{-i}=(a_1,\dots,a_{i-1},a_{i+1},\dots,a_n)\in A_{-i}=A_1\times\dots\times A_{i-1}\times A_{i+1}\times\dots\times A_n$, * $(a_{-i},b) = (a_1,\dots,a_{i-1},b,a_{i+1},\dots,a_n)$, donde $b$ es alguna acción en $A_i$. Para fijar ideas, vamos a dar el que sea, probablemente, el juego más famoso de los Juegos en Forma Normal de la literatura: !!!Tip:Ejemplo (Dilema del prisionero) ![](./img/prisoners_dilemma.png align="right" width=30%)Dos sospechosos, $X$ e $Y$, son acusados de un crimen. La fiscalía no tiene pruebas suficientes para condenarlos a menos que uno de los sospechosos confiese, por lo que está dispuesta a llegar a un acuerdo con el confesor. Si ambos sospechosos guardan silencio, serán condenados por una infracción menor, por lo que cada uno de ellos será encarcelado durante $1$ año. Si uno de ellos confiesa, pero el otro permanece en silencio, el testigo colaborador queda libre, mientras que el otro sospechoso es encarcelado durante $4$ años. Sin embargo, si ambos confiesan, cada sospechoso será encarcelado durante $3$ años. Ambos sospechosos son puestos en aislamiento, y cada uno de ellos tiene que elegir si delata al compañero (D) o permanece en silencio (nD), sin consultar con el otro sospechoso. Esta situación puede modelarse como un juego de forma normal con $N = \{X,Y\}$, $A_X = A_Y = \{D, nD\}$, y las funciones de recompensa $u_X$, $u_Y$ dadas por $$u_X(nD,nD) = −1,\ u_X(nD,D) = −4,\ u_X(D,nD) = 0,\ u_X(D,D) = −3$$ $$u_Y(nD,nD) = −1,\ u_Y(nD,D) = 0,\ u_Y(D,nD) = −4,\ u_Y(D,D) = −3$$ En los juegos de dos jugadores con un número finito de acciones, los pagos de los jugadores suelen especificarse de forma más compacta mediante lo que se conoce como una **matriz de pagos**, $P$, donde las filas corresponden a $A_1$, las columnas a $A_2$, y $P_{ij}=(u_1(a_i,a_j), u_2(a_i,a_j))$. !!!Tip Por ejemplo, para el ejemplo del dilema del prisionero considerado anteriormente, la matriz de pagos viene dada por: | | $nD$ | $D$ | | :--: | :-------: | :-------: | | $nD$ | $(-1,-1)$ | $(-4,0)$ | | $D$ | $(0,-4)$ | $(-3,-3)$ | donde podemos ver los elementos mencionados anteriormente. La cuestión principal que estudia la Teoría de Juegos es cómo predecir el resultado de un juego, es decir, cómo determinar qué estrategias son las más convenientes para los jugadores. ## Conceptos de Solución Una vez definidas las características principales de un juego, la pregunta natural que surge es: ¿qué acción deben utilizar los jugadores para obtener el mejor resultado?, ¿cuál es la mejor acción en un juego determinado? Cuando para un jugador tenemos una forma de decidir su *mejor acción* hablamos de una **estrategia**, que proporcionan *soluciones* al juego. En general una estrategia se puede ver como una aplicación $s : A \to [0,1]^n$ que indica qué acción debe jugar cada jugador del juego. También podemos verlas desde el punto de vista del jugador $i$-ésimo, en cuyo caso $s_i : A_i \to [0,1]$ solo indicaría la acción que debe tomar ese jugador. El primer problema, por supuesto, es que no hay una forma sencilla de definir qué entendemos por *mejor*, ya que lo que puede ser bueno para un agente puede no ser bueno para otro. Por ello, se han propuesto diferentes **conceptos de solución**. Las primeras aproximaciones a la definición de estrategias fueron, por supuesto, propuestas por von Neumann, que se dio cuenta de que, en cualquier juego, un agente podía tomar siempre la acción que maximizara la peor utilidad posible que pudiera obtener, que se conoce como **estrategia maxmin** (o **minmax**, si hablamos de minimizar la pérdidas en lugar de ganancias). En concreto, en un juego con dos agentes, $i$ y $j$, la estrategia maxmin del agente $i$ vendrá dada por: $$s^*_i = \displaystyle{\max_{a\in A_i} \min_{b\in A_j} u_i(a, b)}$$ es decir, $i$ asume que, haga lo que haga, $j$ tomará la acción que será peor para $i$. Por ello, $i$ toma su mejor acción posible bajo este supuesto. En los juegos que consideró inicialmente Neumann las acciones buenas para un jugador normalmente daban un resultado malo para el otro. Desgraciadamente, la estrategia en la que ambos jugadores juegan su estrategia máxima puede no ser estable en el caso general, es decir, para algunos juegos puede ocurrir que si $i$ sabe que $j$ jugará su estrategia máxima, entonces $i$ preferirá una estrategia diferente a su estrategia máxima. Este problema hizo necesario definir otro tipo de conceptos de solución que fueran más adecuados. La existencia de una estrategia óptima es esencial. Para las estrategias de tipo minmax o maxmin tenemos el **Teorema Minimax** que afirma que siempre se puede encontrar una estrategia que minimice la pérdida máxima (es decir, una estrategia minmax),... al menos, para todos los juegos de suma cero de dos jugadores [#Neumann2]. Por tanto, sabemos que funcionará al menos para este subconjunto de juegos, que veremos más adelante. Otra aproximación a la definición de bondad es intentar maximizar el bienestar general de todos los jugadores. La estrategia de **bienestar social** es la que maximiza la suma de los beneficios de todos. Es decir: $$s^* = \displaystyle{\arg\max_{a\in A} \sum_{i=1}^N u_i(a)}$$ Sin embargo, una vez más tenemos el problema de que una estrategia de bienestar social podría no ser estable. Cada agente egoísta sólo se preocupa por su propia utilidad y, por lo tanto, jugará una estrategia diferente si puede obtener una mayor utilidad, incluso si eso significa que todos los demás están mucho peor. Además, la estrategia de bienestar social podría no parecer justa, ya que podría ocurrir que con ella un agente obtuviera una utilidad extremadamente alta y todos los demás no obtuvieran casi nada. Podemos resolver el problema de la injusticia definiendo un concepto de solución que no tenga en cuenta los valores absolutos de utilidad de los agentes. Se dice que una estrategia $s$ es **óptima de Pareto** si no hay ninguna otra estrategia $s'$ tal que al menos un agente esté mejor en $s'$ que en $s$ y ningún agente esté peor en $s'$ que en $s$: $$\neg \exists\ s'\neq s\ (\exists i\ (u_i(s') > u_i(s) \wedge \neg \exists j\neq i\ (u_j(s) > u_j(s')))$$ En principio, puede haber más de una solución óptima de Pareto para un problema determinado. En economía, las soluciones de Pareto suelen denominarse **soluciones eficientes de Pareto**, y son deseables desde la perspectiva del bienestar social, ya que garantizan que ningún agente pueda quejarse de que podría obtener más utilidad sin perjudicar a otro en el proceso. Por desgracia, las soluciones de Pareto también pueden ser inestables en el sentido de que un jugador puede tener un incentivo para jugar una acción diferente porque obtiene una mayor utilidad, incluso perjudicando a otros. Como veremos más adelante, el problema de la falta de estabilidad fue resuelto por John F. Nash introduciendo el concepto de equilibrio en estrategias [#Nash]: una estrategia es un **equilibrio de Nash** si para todos los agentes la estrategia para ese agente es su mejor estrategia supuesto que todos los demás jugadores jugarán la misma estrategia. Es decir, si todos los demás están jugando el equilibrio de Nash, entonces lo mejor para todos es jugar el equilibrio de Nash. Al igual que con la solución de Pareto, un juego puede tener más de un equilibrio de Nash. Nash demostró que todas las matrices de juego tienen al menos una estrategia de equilibrio probabilística. El único problema con el equilibrio de Nash es que en muchos juegos puede haber muchos equilibrios de este tipo. Además, algunos de esos equilibrios de Nash pueden ser mejores para unos jugadores que para otros, por lo que los jugadores pueden acabar discutiendo sobre cuál adoptar. Aun así, una vez que los agentes se han puesto de acuerdo en uno, se trata de una solución muy estable. Obsérvese que no existe una relación general entre el equilibrio de Nash y la solución de Pareto. Es decir, una estrategia puede ser un equilibrio de Nash pero no ser una solución de Pareto, y viceversa. Todos estos conceptos de solución dejan claro que no es sencillo definir cuál es la mejor estrategia de forma global. Con múltiples jugadores, lo mejor depende de cuánto estemos dispuestos a respetar el egoísmo de los agentes, de cómo compensemos las utilidades de los distintos agentes, y de lo justos que queramos ser. El problema más común al que nos enfrentamos al diseñar sistemas multiagente es la existencia de múltiples equilibrios. Es decir, por lo general podemos diseñar un sistema para el que los agentes egoístas converjan a una solución de equilibrio (cuando la haya), pero hemos de añadir mecanismos de coordinación adicionales para garantizar que los agentes converjan a la misma situación en caso de que haya varias, para que no haya fuerzas que desestabilizan el sistema. En lo que sigue, nos centraremos en definir formalmente todos los conceptos que se han introducido aquí informalmente. ## Estrategia dominante !!! En el Dilema del Prisionero, no es difícil predecir lo que haría un agente racional. En efecto, el agente $X$ puede razonar de la siguiente manera: Si $Y$ me delata, es más rentable para mí ($X$) delatar (una recompensa de $-3$) que permanecer en silencio (una recompensa de $-4$), y si $Y$ permanece en silencio, es más rentable para mi ($X$) delatar (una recompensa de $0$) que permanecer en silencio (una recompensa de $-1$). Por lo tanto, $X$ no necesita saber qué pretende hacer $Y$: en cualquier caso, obtiene un mejor resultado si él delata. El jugador $Y$ razona de la misma manera, por lo que el único resultado racional de este juego es que ambos jugadores delaten. En este ejemplo, ocurre que para cada jugador hay una estrategia que es preferible, independientemente de la elección del otro jugador. Estas estrategias se denominan **dominantes**. Formalmente: !!!def:Definición Dado un juego en forma normal, $G$, y un par de acciones $a_i,\ a'_i \in A_i$, se dice que la acción $a_i$ **domina débilmente** a $a'_i$ si $u_i(a_{−i},a_i) \geq u_i(a_{−i},a'_i)$ para cada $a_{-i} \in A_{-i}$, y la desigualdad anterior es estricta para al menos un $a_{-i}\in A_{-i}$. Se dice que la acción $a_i$ **domina estrictamente** a $a'_i$ si la desigualdad anterior es estricta para cada $a_{-i}\in A_{-i}$. Se dice que una estrategia $a_i$ del agente $i$ es **débilmente/estrictamente dominante** si domina débilmente/estrictamente a todas las demás estrategias de ese agente. Del mismo modo, una estrategia $a'_i$ del agente $i$ se dice que es **débilmente/estrictamente dominada** si es débilmente/estrictamente dominada por alguna otra estrategia de ese agente. !!!Tip Utilizando la terminología de la definición anterior, podemos ver que, para ambos jugadores en el juego del Dilema del Prisionero, la estrategia $D$ domina estrictamente a la estrategia $nD$ y, por tanto, es una estrategia estrictamente dominante. Supongamos ahora que cambiamos la descripción del juego de modo que cuando $X$ delata, $Y$ es encarcelado durante $3$ años, delate o no. Entonces, delatar sigue siendo una estrategia débilmente dominante para $Y$, pero ya no es estrictamente dominante: si $X$ delata, a $Y$ le resulta indiferente delatar o permanecer en silencio. Es fácil ver que cada jugador puede tener como máximo una estrategia débilmente dominante (y, por tanto, como máximo una estrategia estrictamente dominante). Además, si un jugador posee tal estrategia, tiene un incentivo muy fuerte para elegirla, ya que no puede hacerlo mejor eligiendo cualquier otra estrategia. Sin embargo, en muchos juegos puede ocurrir que algunos de, o todos, los jugadores no tengan estrategias dominantes. !!!Tip:Ejemplo (Batalla de sexos) Alice y Bob quieren pasar la noche juntos. Cada uno de ellos tiene que elegir entre ir a ver un partido de fútbol ($F$) o una película ($P$). Bob prefiere el fútbol al cine, y Alice prefiere el cine al fútbol, pero ambos tienen muchas más ganas de pasar la noche juntos, por lo que, si terminaran eligiendo actividades diferentes, la noche se arruinaría para ambos. Por ejemplo, supongamos que la matriz de pago pudiera ser (Alice es el jugador 1 y Bob el jugador 2): | | $F$ | $P$ | | :--: | :-----: | :-----: | | $F$ | $(1,3)$ | $(0,0)$ | | $P$ | $(0,0)$ | $(3,1)$ | En este ejemplo, ninguno de los jugadores tiene una estrategia (débilmente) dominante: Alice prefiere $P$ a $F$ cuando Bob elige $P$, pero prefiere $F$ a $P$ cuando Bob elige $F$. De hecho, ambos resultados $(F,F)$ y $(P,P)$ parecen razonables en esta situación. Por otra parte, el sentido común sugiere que los resultados $(P,F)$ y $(F,P)$ son menos plausibles que $(F,F)$ o $(P,P)$: de hecho, si el resultado es $(P,F)$, la recompensa de Alice es $0$, pero puede cambiar unilateralmente su acción a $F$, aumentando así su recompensa a $1$; análogamente para Bob. A continuación trataremos de formalizar la intuición que nos permite decir que en este juego, $(P,P)$ es más plausible que $(F,P)$, para poder aplicarla a una gama más amplia de escenarios. ## Equilibrio de Nash En el juego de la Batalla de los Sexos, los resultados $(P,F)$ y $(F,P)$ son intrínsecamente inestables: un jugador (o, en este caso particular, ambos jugadores) puede cambiar su acción para aumentar su recompensa. La noción de equilibrio de Nash pretende capturar el conjunto de resultados que son resistentes a tales desviaciones. !!!def:Definición Dado un juego de forma normal, $G$, se dice que un perfil de estrategia $a = (a_1,\dots,a_n)$ es un **equilibrio de Nash** si para cada agente $i\in N$ y para cada acción $a'_i\in A_i$ tenemos $u_i(a_{−i},a_i) \geq u_i(a_{−i},a'_i)$, es decir, ningún agente puede aumentar unilateralmente su retribución cambiando su acción. !!!def:Definición Decimos que una acción $a$ es **la mejor respuesta del jugador $i$ a un perfil estratégico** $a_{-i}$ si $u_i(a_{-i},a) \geq u_i(a_{-i},a')$ para cada $a'\in A_i$. !!! Así pues, un equilibrio de Nash es un perfil de estrategia en el que la acción de cada jugador es la mejor respuesta a las acciones de los otros jugadores. Es inmediato que en el juego de la Batalla de los Sexos $(P,P)$ y $(F,F)$ son equilibrios de Nash, pero $(P,F)$ y $(F,P)$ no lo son. El equilibrio de Nash es quizás el concepto de solución más frecuente en Teoría de Juegos. Sin embargo, tiene algunas propiedades indeseables: 1. En primer lugar, jugar una estrategia de equilibrio de Nash sólo es racional si todos los demás agentes juegan según el mismo equilibrio de Nash; aunque esta suposición es razonable si se sabe que los demás agentes son racionales, en muchos escenarios de la vida real no se puede dar por supuesto la racionalidad de los demás agentes. En cambio, si un agente tiene una estrategia dominante, no necesita asumir nada sobre los demás agentes. Suponer que todos los demás agentes actúan según un equilibrio de Nash fijo es especialmente problemático si el equilibrio de Nash no es único (por ejemplo, en el juego de la Batalla de los Sexos, si Alice y Bob tienen que elegir sus acciones de forma simultánea e independiente, no hay una forma obvia de que elijan entre $(P,P)$ y $(F,F)$). 2. Además, hay juegos que no tienen un equilibrio de Nash, como ocurre en el siguiente juego: !!!Tip: Ejemplo (Emparejar monedas) Consideremos un juego de $2$ jugadores en el que cada uno de ellos tiene una moneda de $1€$, y tiene que colocarla en la mesa de manera que la cara superior sea cara ($C$) o cruz ($X$). Si ambas monedas obtienen el mismo resultado ($CC$ o $XX$), el primer jugador (*emparejador*) se lleva las dos monedas y, por tanto, gana $1€$. En caso contrario (es decir, si el resultado es $CX$ o $XC$), el segundo jugador (*desemparejador*) se lleva las dos monedas. ## Estrategias mixtas y equilibrio de Nash mixto Si intentamos participar en el juego de emparejamiento de monedas, ya sea como jugador $1$ o como jugador $2$, nos daremos cuenta rápidamente de que la mejor estrategia es lanzar la moneda de forma que tenga las mismas posibilidades de salir cara o cruz. La noción teórica de esta estrategia es lo que se denomina una **estrategia mixta**: !!!def:Definición Dado un juego en forma normal, $G$, en el que el conjunto de acciones de cada agente es finito (sin pérdida de generalidad, podemos suponer que cada agente tiene exactamente $m$ estrategias disponibles), una **estrategia mixta** de un agente $i$ con un conjunto de acciones $A_i =\{a^1_i,\dots,a^m_i\}$ es una distribución de probabilidad sobre $A_i$, es decir un vector $s_i = (p^1_i,\dots,p^m_i)$ que satisface $p^j_i\geq 0$ para todo $j = 1,\dots,m$, y $\sum_{j=1}^m p^j_i=1$. El **soporte** de una estrategia mixta $p_i$, $supp(p_i)$, es el conjunto de todas las acciones a las que se asigna una probabilidad distinta de cero: $supp(s_i) = \{a^j_i\ :\ p^j_i > 0\}$. Un **perfil de estrategia mixta** es un vector $(s_1,\dots,s_n)$ de estrategias mixtas (una estrategia mixta por cada agente). Dado un perfil de estrategia mixta $(s_1,\dots,s_n)$, la recompensa esperada del jugador $i$ se calcula como: $$U_i(s_1,\dots,s_n) =\sum_{(a^{i_1}_1,\dots,a^{i_n}_n)\in A} p^{i_1}_1\cdot \dots \cdot p^{i_n}_n\cdot u_i(a^{i_1}_1,\dots,a^{i_n}_n)$$ Ya tenemos las herramientas necesarias para definir nuestro siguiente concepto de solución, a saber, el **equilibrio de Nash mixto**: !!!def:Definición Dado un juego en forma normal, $G$, un perfil de estrategia mixta $(s_1,\dots,s_n)$ es un **equilibrio de Nash mixto** si ningún agente puede mejorar su resultado esperado cambiando su estrategia, es decir, si $U_i(s_1,\dots,s_n) \geq U_i(s_1, \dots ,{s_i}', \dots, s_n)$ para cada agente $i\in N$ y cada estrategia mixta ${s_i}'$ del jugador $i$. Obsérvese que una acción $a^j_i$ corresponde a una estrategia mixta, $s_i$, dada por $s^j_i = 1$, $s^k_i = 0$ para $k\neq j$. Por ello, nos referiremos a las estrategias de esta forma como **estrategias puras** del jugador $i$, y a la noción de equilibrio de Nash definida en la sección anterior como **equilibrio de Nash puro**. Aunque la noción de equilibrio de Nash mixto adolece de muchos de los mismos problemas conceptuales que el equilibrio de Nash puro, así como de algunos adicionales, tiene la siguiente propiedad atractiva: !!!def:Teorema Todo juego en forma normal con un número finito de jugadores y un número finito de estrategias para cada jugador admite un equilibrio de Nash en estrategias mixtas. Este resultado fue demostrado por John Nash en su tesis doctoral [#Nash], y es una de las piedras angulares de la Teoría de Juegos moderna. !!!Tip Volviendo al ejemplo de emparejamiento de monedas, podemos comprobar que el perfil de estrategia mixta $(s_1,s_2)$, donde $s_1 = s_2 = (1/2,1/2)$, es un equilibrio de Nash mixto y, además, puede comprobarse que es el único equilibrio de Nash mixto de este juego. !!!def:Propiedades Equilibrios de Nash Mixtos Algunas propiedades importantes de los equilibrios de Nash mixtos que pueden utilizarse para simplificar el cálculo de las estrategias de equilibrio (sus pruebas pueden encontrarse en [#Osborne]) son: 1. Si $(s_1, \dots ,s_n)$ es un equilibrio de Nash mixto en $G$, entonces para cada jugador $i\in N$, todas las acciones en $supp(s_i)$ son las mejores respuestas de $i$ a $s_{-i}$: * si $a_i\in supp(s_i)$, entonces $U_i(s_{-1},a_i)\geq U_i(s_{-i},s_i')$ para cada estrategia mixta $s_i'$ del jugador $i$. Por tanto, $\forall a_i,a_j\in supp(s_i)\ (U_i(s_{-i},a_i) = U_i(s_{-i},a_j))$. 2. Para verificar si un perfil $s=(s_1, \dots ,s_n)$ es un equilibrio de Nash mixto, basta con comprobar las desviaciones a estrategias puras únicamente. Es decir, $(s_1, \dots ,s_n)$ es un equilibrio de Nash mixto en $G$ si $\forall i\ \forall a_i\in A_i\ (U_i(s) \geq U_i(s_{-i},a_i))$. 3. Si un perfil de estrategia $(a^{i_1}_1 , \dots ,a^{i_n}_n)$ es un equilibrio de Nash puro en $G$, entonces también es un equilibrio de Nash mixto en $G$. ## Eliminación de estrategias dominadas Hemos argumentado que si un jugador posee una estrategia dominante, tiene un incentivo muy fuerte para utilizarla. Del mismo modo, si una de las estrategias del jugador está dominada, es poco probable que la utilice (esto es especialmente cierto si esta estrategia está estrictamente dominada, por lo que, en lo que sigue, nos centramos en este caso de dominación estricta). Por ello, es racional para otros jugadores asumir que esta estrategia nunca se utilizará y, por lo tanto, pueden eliminarla de la lista de estrategias de ese jugador. Ahora el juego ha cambiado, y en este nuevo juego, algunas de sus propias estrategias pueden llegar a estar dominadas, y por lo tanto pueden ser eliminadas. Este procedimiento suele denominarse **eliminación iterada de estrategias estrictamente dominadas**, y aunque no siempre conduce a un perfil de estrategia único, puede reducir considerablemente el número de estrategias y, en consecuencia, la complejidad computacional del juego. !!!Tip:Ejemplo Consideremos dos jugadores $X$ e $Y$ que participan en el siguiente juego: cada jugador debe elegir un número entero entre $1$ y $10$, y un jugador gana (y obtiene una recompensa de $1$) si su número está más cerca de la mitad de la media de los dos números; si ambos jugadores eligen el mismo número, ninguno de ellos gana. Por ejemplo, si el jugador $X$ elige $n_X = 9$ y el jugador $Y$ $n_Y = 5$, entonces $Y$ gana, ya que $5$ está más cerca de $3.5$ que $9$. El jugador $X$ puede razonar de la siguiente manera. La mitad de la media de los dos números nunca supera el $5$, por lo que para el jugador $Y$ establecer $n_Y = 10$ está estrictamente dominado por establecer $n_Y = 1$. Por lo tanto, puede suponer que el jugador $Y$ nunca elegirá $n_Y = 10$. El mismo argumento funciona para el propio jugador $X$. Así, ambos jugadores pueden asumir que el espacio de acción está, de hecho, limitado a todos los enteros entre $1$ y $9$. Por tanto, la mitad de la media de los dos números no excede $4.5$ y, en consecuencia, para ambos jugadores elegir $9$ está estrictamente dominado por elegir $1$. Repitiendo este argumento, podemos concluir que el único par de estrategias que no puede ser eliminado de esta manera es $(1,1)$. Nótese que bajo este perfil de estrategia ninguno de los dos jugadores gana. Se puede demostrar que cualquier equilibrio puro de Nash siempre sobrevivirá a la eliminación iterada de estrategias estrictamente dominadas (en el ejemplo anterior el perfil de estrategia $(1,1)$ es un equilibrio de Nash). Además, si una acción pertenece al soporte de un equilibrio de Nash mixto, tampoco será eliminada. Por lo tanto, la eliminación iterada de las estrategias estrictamente dominadas puede verse como un paso de preprocesamiento útil para calcular los equilibrios de Nash mixtos. Además, el conjunto de estrategias que sobreviven a este procedimiento es independiente del orden de eliminación. ## Juegos con espacios de acción infinitos Aunque en todos los ejemplos vistos hasta ahora cada jugador un conjunto de acciones finito, todas las definiciones vistas (excepto las de estrategias mixtas), se pueden aplicar a juegos en los que los $A_i$ son infinitos. !!! Aunque este tipo de juegos pueden parecer a primera vista algo extraños, en realidad son bastante comunes, por ejemplo, cuando la acción es decidir la cantidad de tiempo que se dedica a una determinada actividad, o la cantidad de cierto recurso (infinitamente divisible) que se usa. Se puede comprobar fácilmente que las nociones de equilibrio puro de Nash, mejor respuesta y estrategias débilmente/estrictamente dominadas tienen perfecto sentido en estos escenarios. La noción de equilibrio de Nash mixto puede extenderse también a espacios de acción infinitos, aunque se requiere una maquinaria algo más pesada que no veremos. El único problema es que, sin embargo, para este entorno más general, el famoso resultado de Nash ya no se puede aplicar y la existencia de un equilibrios de Nash mixto no está, en general, garantizada. Aunque no veremos resultados teóricos en estos juegos, vamos a poner un ejemplo sencillo que resalta algunas de las cuestiones que surgen en el análisis de juegos con espacios de acción infinitos: !!!Tip:Ejemplo Alice y Bob pujan por un cuadro que se vende mediante una subasta de **pujas cerradas de primer precio**, que funcionan de la siguiente manera: 1. Cada jugador presenta una puja en un sobre cerrado. 2. A continuación se abren los sobres y el jugador que presenta la puja más alta gana y paga su oferta. 3. Los empates se deshacen a favor de Alice. Supongamos que Alice valora el cuadro en $300€$, Bob lo valora en $200€$ y ambos conocen los valores del otro. Entonces, si Alice gana el cuadro y paga $x$, su recompensa es de $300 - x$, mientras que si Bob gana y paga $y$, su recompensa es de $200 - y$ (nótese que podrían ser negativas). Cada jugador puede pujar cualquier número real no negativo, es decir, el espacio estratégico de cada jugador es $\mathbb{R}^+$. Podemos observar inmediatamente que $(200,200)$ es un equilibrio de Nash de este juego. En efecto, con este vector de ofertas, Alice gana debido a la regla de desempate, y su recompensa es de $100$. Si Alice puja más, tendrá que pagar más, y si puja menos, perderá la subasta, por lo que su recompensa bajará de $100$ a $0$. Por otro lado, si Bob puja menos, el resultado seguirá siendo el mismo, y si puja más, ganará, pero su recompensa será negativa. El mismo argumento muestra que cualquier perfil de acción de la forma $(x,x)$, donde $200 \leq x \leq 300$, es un equilibrio de Nash. Por el contrario, ningún perfil de acción de la forma $(x,y)$, donde $x \neq y$, puede ser un equilibrio de Nash de este juego: el jugador que presenta la oferta más alta tiene un incentivo para bajar un poco su oferta (de modo que sigue siendo el postor ganador, pero paga menos). Supongamos ahora que Alice valora el cuadro en $200€$, mientras que Bob lo valora en $300€$. En este caso, el juego no tiene un equilibrio puro de Nash. De hecho, el mismo argumento anterior muestra que en cualquier equilibrio de Nash, Alice y Bob presentan la misma oferta (y, por tanto, Alice gana). Además, esta oferta es de al menos $300$ dólares ya que, de lo contrario, Bob puede desviarse provechosamente aumentando su oferta. Sin embargo, esto significa que Alice está perdiendo dinero y puede desviarse provechosamente bajando su oferta para perder la subasta. ### Juegos con funciones de pago diferenciables En algunas clases de juegos con conjuntos de acciones infinitos podemos razonar sobre los equilibrios de Nash de forma más sistemática si las funciones de pago satisfacen algunas condiciones de *bondad analítica*, por ejemplo, cuando para cada $i\in N$, $A_i = \mathbb{R}$ y $u_i$ es continua y diferenciable. Cuando las utilidades son diferenciables y no hay restricciones en los conjuntos de acciones, la mejor respuesta de un jugador a las estrategias de los otros jugadores se alcanza en el punto donde la derivada parcial de $u_i$ con respecto a la elección del jugador $i$ se hace cero. Por tanto, podemos identificar el conjunto de equilibrios de Nash resolviendo el siguiente sistema de $n$ ecuaciones, y verificando después que las soluciones obtenidas son efectivamente equilibrios de Nash del juego: $$\frac{\partial u_i(a_1, \dots, a_n)}{\partial a_i} = 0,\ \forall\ i = 1, \dots ,n$$ Si el conjunto $A_i$ es un subconjunto estricto de $\mathbb{R}$, por ejemplo, un intervalo acotado, o si hay alguna otra restricción en el espacio de estrategias, puede ocurrir que las soluciones al sistema anterior caigan fuera de nuestro subconjunto, en cuyo caso debemos tenerlo en cuenta para la verificación de resultados. ## Juegos de Suma Cero En esta sección nos centraremos en los juegos en forma normal que expresan una competencia directa entre los jugadores. Se trata de juegos en los que el beneficio de un jugador es igual a la pérdida de los demás. Históricamente, esta es la primera clase de juegos que se estudió ampliamente antes de pasar a los juegos generales en forma normal. De hecho, los **Juegos de Suma Cero**, que es como se llaman, fueron el tema central del primer libro de texto sobre Teoría de Juegos de von Neumann y Morgenstern [#Neumann]. !!!def:Definición Un juego de forma normal, $G$, es un **Juego de Suma Cero** si para cada $a\in A$ se cumple que $\sum_{i} u_i(a)= 0$. Obviamente, un juego de suma cero de dos jugadores está completamente especificado por los pagos de uno de los jugadores, ya que los pagos del otro jugador son simplemente el opuesto, por lo que muchas veces se representan por la matriz de pago del jugador 1. Una forma de empezar a pensar en cómo jugar en un juego de este tipo es ser pesimista y asumir el peor escenario posible para cualquier estrategia elegida. Para el jugador señalado, esto significa asumir que, independientemente de lo que elija, el otro jugador hará la elección que minimice su ganancia, es decir, que para cada fila $i$ que pueda elegir, se obtendrá el valor $min_j P_{ij}$. Por tanto, el jugador 1 jugará para maximizar este valor mínimo. Con el mismo espíritu, si el jugador 2 también piensa de forma pesimista, pensará que, elija lo que elija, el jugador 1 elegirá la acción que maximice su ganancia, es decir, para una columna $j$ el jugador acabará pagando $max_i P_{ij}$. El segundo jugador querrá entonces asegurarse de minimizar este pago en el peor de los casos. Por lo tanto, los dos jugadores están interesados en alcanzar, respectivamente, los valores: $$v_1 = \max_i \min_j P_{ij}$$ $$v_2 = \min_j \max_i P_{ij}$$ Podemos realizar el mismo razonamiento sobre el espacio de estrategias mixtas. Para ello necesitamos definir los valores: $$\bar{v}_1 = \max_s \min_t u_1(s,t)$$ $$\bar{v}_2 = \min_t \max_s u_1(s,t)$$ donde la maximización y la minimización anteriores son sobre el conjunto de estrategias mixtas. Como ahora estamos optimizando sobre un conjunto mayor, se deduce que: $v_1 \leq \bar{v}_1\leq \bar{v}_2\leq v_2$. El teorema principal sobre los juegos de suma cero puede enunciarse como sigue: !!!def:Teorema Para todo juego finito de suma cero: 1. $\bar{v}_1 = \bar{v}_2$, y este valor común, denotado por $\bar{v}$, se denomina **valor del juego**. 2. El perfil $(s,t)$ donde se alcanza $\bar{v}$ es un equilibrio de Nash. 3. Todos los equilibrios de Nash dan los mismos resultados a los jugadores, $\bar{v}$ y $-\bar{v}$, respectivamente. Además, si $(s,t)$ y $(s',t')$ son equilibrios de Nash, entonces $(s,t')$ y $(s',t)$ son también equilibrios de Nash con el mismo resultado. Por lo tanto, en los juegos de suma cero la noción de equilibrio de Nash no se enfrenta a la crítica relativa a la existencia de múltiples equilibrios y al problema de elegir entre ellos, ya que todos los equilibrios proporcionan los mismos pagos y la coordinación nunca es un problema. Además, desde el punto de vista algorítmico, aunque encontrar $\bar{v}$ para un juego arbitrario de suma cero no es tan fácil como para el caso $2 \times 2$ del ejemplo anterior, sigue siendo un problema manejable. ## Juegos Iterados Hemos visto cómo en el dilema del prisionero la estrategia dominante era delatar, pero ambos jugadores podrían haber recibido una mayor utilidad permaneciendo en silencio. Una forma de intentar salir de este enigma, y simular mejor las interacciones del mundo real, es dejar que dos jugadores jueguen el mismo juego un cierto número de veces. Esta nueva modalidad se conoce como **Dilema del Prisionero Iterado** y, en general, nos referimos a este tipo de juegos como **Juegos Iterados**. Los juegos iterados con un horizonte finito son un caso especial de los Juegos en Forma Extensiva que trataremos en la siguiente sección, pero a veces se han estudiado de forma independiente por las características particulares que tienen. Una forma de analizar los juegos iterados que duran un número finito de períodos es retroceder desde el final: supongamos que estamos jugando un dilema del prisionero iterado que durará 50 rondas. Sabemos que en la última ronda delataremos porque esa es la estrategia dominante y no hay necesidad de ser amable con el otro jugador ya que es la última partida. Por supuesto, como te has dado cuenta de esto, también sabes que el otro jugador se ha dado cuenta de lo mismo y por lo tanto también nos delatará en la última ronda. Por lo tanto, sabes que no tienes nada que ganar callando en la ronda 49, así que delatarás en la 49, y él también. Esta inducción hacia atrás puede repetirse cualquier número de veces, lo que nos lleva a la conclusión de que, para cualquier número finito de iteraciones, la estrategia racional es delatar siempre. Sin embargo, la gente no actúa así. La novedad se introduce cuando no sabemos cuándo acabara el juego. Podemos demostrar formalmente que existe un equilibrio cooperativo para el dilema del prisionero iterado si en lugar de un número fijo conocido de interacciones hay siempre una pequeña probabilidad de que cada interacción sea la última. Es decir, si los jugadores nunca saben si cada ronda será su última interacción o no. En este escenario, se puede demostrar que la estrategia dominante para el dilema del prisionero iterado es callar con una cierta probabilidad. Sin embargo, de forma más general, en un juego iterado cualquier estrategia que no esté dominada por otra y en la que cada agente obtenga una utilidad superior a su utilidad máxima es una estrategia de equilibrio factible. En estos casos, cada jugador sabe que puede obtener su utilidad máxima jugando la acción adecuada, independientemente de lo que hagan los demás. Por lo tanto, ningún jugador estará satisfecho con menos de su utilidad máxima. Por otro lado, si los agentes se ponen de acuerdo en una estrategia que proporcione a todos al menos su utilidad máxima y no esté dominada, cualquier agente que se desvíe de ella podría ser penalizado por los demás agentes, de modo que cualquier ganancia en la que haya incurrido por la desviación sería eliminada. De este modo, los agentes pueden vigilar cualquier estrategia elegida y asegurarse así de que es una estrategia estable. Este análisis sigue dejando abierta la cuestión de cuál es, en la práctica, la estrategia óptima para el dilema del prisionero iterado. A principios de los años 80, Robert Axelrod realizó algunos experimentos sobre el dilema del prisionero iterado (Axelrod, 1984). Envió un correo electrónico en el que pedía a la gente que enviara programas en Fortran que jugaran al dilema del prisionero unos contra otros durante $200$ rondas. El ganador sería el que acumulara más puntos. Se enviaron muchos programas mostrando muchas estrategias, entre las que se incluían: - **ALL-D**: jugar siempre a delatar. - **RANDOM**: elegir la acción al azar. - **TIT-FOR-TAT** (ojo por ojo): callar en la primera ronda, y luego hacer lo que el otro jugador hizo la última vez. - **TESTER**: delatar en la primera ronda. Si el otro jugador delata, entonces juega TIT-FOR-TAT. Si calló, entonces callar durante dos rondas y luego delatar. - **JOSS**: juega al TIT-FOR-TAT pero el $10\%$ de las veces delata en lugar de callar. La estrategia de TIT-FOR-TAT ganó el torneo. Aún así, ganó menos que ALL-D al jugar en contra, pero, en general, ganó más que cualquier otra estrategia. Tuvo éxito porque tuvo la oportunidad de jugar contra otros programas que estaban dispuestos a callar. Calló con los que podían callar y delató contra el resto. Este resultado, aunque intrigante, no es teóricamente sólido. Por ejemplo, una estrategia de TIT-FOR-TAT perdería contra una estrategia que jugara TIT-FOR-TAT pero delatara en la última ronda. Aun así, la estrategia de TIT-FOR-TAT se ha utilizado ampliamente y se considera una estrategia sencilla pero robusta. Otro método para analizar las partidas repetidas consiste en suponer que los jugadores utilizan algún algoritmo de aprendizaje y, a continuación, intentar determinar hacia qué estrategia convergerá su aprendizaje. Esta área de investigación se conoce como **aprendizaje en juegos**. ## Aspectos computacionales Muchos investigadores han argumentado que para que los enfoques teóricos de los juegos sean relevantes en la práctica, el juego en cuestión debe admitir una representación compacta y el concepto de solución elegido debe ser eficiente desde el punto de vista computable. Estos criterios suelen significar que el tamaño de la representación de un juego y el tiempo de ejecución de los algoritmos para calcular los conceptos de solución deben ser como máximo polinomiales en el número de jugadores, $n$, y el número de acciones disponibles para cada jugador, $m$. Para los juegos de dos jugadores (y, en general, para los juegos con un número constante de jugadores) la complejidad de la representación no es un problema: si cada uno de los jugadores tiene $m$ acciones y todos los pagos se pueden reescalar para que sean enteros con un valor absoluto que no exceda de $2^{pol(m)}$, el tamaño de la representación matricial es polinómico en $m$. Sin embargo, si el número de jugadores es grande, el tamaño de la representación matricial explota: para un juego de $n$ jugadores con dos acciones por jugador, la matriz tiene $2^n$ casillas. Esto es, en cierto sentido, inevitable: un argumento de recuento estándar muestra que cualquier formalismo que pueda expresar cada juego de $n$ jugadores producirá descripciones de tamaño exponencial para la mayoría de los juegos. Por lo tanto, para los juegos multijugador se suelen considerar formalismos de representación específicos de la aplicación que pueden no ser universalmente expresivos, pero proporcionan una codificación compacta para esa clase relevante de juegos. En cuanto a la eficiencia de la computabilidad de los conceptos de solución, las estrategias estrictamente/débilmente dominantes y los equilibrios de Nash puros se comportan bien en este sentido, al menos para juegos con un número constante de jugadores: es sencillo comprobar si una estrategia es dominante o si un perfil de estrategia forma un equilibrio de Nash puro. Sin embargo, los equilibrios de Nash mixtos no superan esta prueba: se sabe que el cálculo de un equilibrio de Nash es completo para la clase de complejidad **PPAD**, incluso para juegos de dos jugadores con pagos $0$-$1$. Aunque **PPAD** es una clase de complejidad algo exótica, se sabe que contiene varios problemas importantes que, según parece, no admiten un algoritmo de tiempo polinomial (no se sabe). Además, se sabe que encontrar un equilibrio de Nash con ciertas propiedades deseables (como, por ejemplo, un equilibrio de Nash que maximice la suma de las utilidades de los jugadores) es **NP**-completo. De hecho, incluso encontrar un equilibrio de Nash aproximado, es decir, un perfil de estrategia en el que cada jugador sólo tenga un pequeño incentivo para desviarse, parece ser difícil desde el punto de vista computacional: los mejores algoritmos de tiempo polinómico conocidos actualmente sólo garantizan una solución en la que ningún jugador puede aumentar su beneficio en más de un 33% aproximadamente. Si uno está dispuesto a pasar a tiempos de ejecución más altos, entonces para juegos con un número constante de jugadores existen algoritmos superpolinomiales (que logran un tiempo de ejecución mejor que el exponencial, aunque no polinomial) que pueden encontrar perfiles de estrategia en los que el incentivo a desviarse es como máximo $\epsilon$, para cualquier constante $\epsilon > 0$. Por último, para los juegos de suma cero, se puede calcular eficientemente un equilibrio de Nash mixto. # Juegos en Forma Extensiva Los juegos en Forma Normal no pueden capturar situaciones en las que los jugadores realizan sus jugadas secuencialmente. Sin embargo, hay muchos ejemplos en los que es la forma más correcta de modelarlos, como la mayoría de los juegos de mesa (ajedrez, go, etc.), los protocolos de negociación y las subastas públicas. Todos estos casos evolucionan por rondas, de modo que los jugadores se turnan y toman una decisión después de ser informados de las decisiones de sus oponentes. Veremos ahora algunas de las herramientas para analizar este tipo de juegos. Para empezar, describiremos un juego sencillo con jugadas secuenciales que nos servirá de ejemplo al principio de la sección. !!!Tip:Ejemplo Consideremos el juego con dos jugadores representado en la figura siguiente, donde el jugador 1 mueve primero y tiene que decidir entre las alternativas $A$ y $B$. Después, el jugador 2 mueve; dependiendo de lo que haya elegido el jugador 1, tendrá que decidir entre $C$ y $D$ o entre $E$ y $F$. Finalmente, tras el movimiento del jugador 2, el juego termina y cada jugador recibe una recompensa dependiendo del estado terminal que haya alcanzado el juego. Por ejemplo, si el jugador 1 elige $A$ y el jugador 2 elige $C$, sus pagos son $2$ y $5$, respectivamente. ![](./img/extensive1.png align="center" width=30%) El ejemplo anterior ilustra todo lo que hay que especificar para definir un juego en forma extensiva. Un juego de este tipo suele representarse mediante un **árbol enraizado**, en el que la raíz denota el inicio del juego y cada hoja es un posible final del mismo. Asumiremos que este árbol tiene una profundidad finita, es decir, hay un límite finito en la longitud máxima de un camino desde la raíz a una hoja; sin embargo, los nodos pueden tener ramificación infinita, correspondientes a un número infinito de acciones disponibles para un jugador. Todos los nodos internos del árbol representan estados del juego. En cada estado, uno de los jugadores tiene que tomar una decisión o se produce un evento aleatorio (como el lanzamiento de una moneda) que determina el siguiente estado. Dado un árbol que representa un juego, una **historia** es simplemente una secuencia válida de acciones que comienza en la raíz y llega hasta algún nodo del árbol. También permitimos que el conjunto vacío, $\emptyset$, sea una historia válida. Una **historia terminal** es una historia que termina en una hoja. Por lo tanto, una historia terminal representa una posible jugada completa del juego. En un árbol, hay un único camino desde la raíz hasta una hoja, y por lo tanto hay una correspondencia biyectiva entre las historias terminales y las hojas. !!!def:Definición Un **Juego en Forma Extensiva** viene dado por una tupla $G = (N,T,(u_i)_{i\in N})$, donde: - $N = \{1, \dots ,n\}$ es un conjunto de agentes; - $T = (V,E)$ es un árbol enraizado, donde el conjunto de nodos se particiona en conjuntos disjuntos $V = \bigcup_{i\in N} V_i \cup V_c \cup V_L$, donde $V_i,\ i = 1, \dots ,n$, denota el conjunto de nodos en los que le toca al agente $i$ tomar una decisión, $V_c$ denota el conjunto de nodos en los que se selecciona un movimiento al azar, y $V_L$ denota el conjunto de hojas. Para cada nodo $v\in V_c$, se da también una distribución de probabilidad sobre el conjunto de aristas que salen de $v$. - Para cada $i \in N$, $u_i : V_L \to \mathbb{R}$ es una función de recompensa que asigna a cada hoja de $T$ un valor real. Dado que existe una correspondencia uno a uno entre las historias terminales y las hojas, en lo que sigue, por un ligero abuso de la notación, veremos las funciones de pago como aplicaciones sobre las historias terminales. !!!Tip Considerando el juego anterior, el conjunto de todas las historias es $H = \{\emptyset,A,B,(A,C),(A,D),(B,E),(B,F)\}$ y el conjunto de historias terminales es $HT = \{(A,C),(A,D),(B,E),(B,F)\}$. El conjunto de nodos se divide en $V_1$, $V_2$, $V_L$, donde $V_1$ contiene sólo la raíz, $V_2$ contiene los dos hijos de la raíz, y $V_L$ es el conjunto de las cuatro hojas. No hay movimientos al azar, por lo que $V_c = \emptyset$. La función de recompensa del jugador 1 viene dada por: $$u_1((A,C)) = 2,\ u_1((A,D)) = 1,\ u_1((B,E)) = 3,\ u_1((B,F)) = 1$$ mientras que la función de recompensa del jugador 2 viene dada por: $$u_2((A,C)) = 5,\ u_2((A,D)) = 1,\ u_2((B,E)) = 4,\ u_2((B,F)) = 2$$ A continuación presentaremos un ejemplo menos abstracto que ilustra la aplicabilidad de los juegos de forma extensiva en el análisis de escenarios realistas. !!!Tip:Ejemplo Alice y Bob tienen que compartir $8$ magdalenas idénticas; las magdalenas no se pueden cortar en trozos, por lo que a cada jugador se le debe asignar un número entero de magdalenas. Las magdalenas se estropean rápidamente, por lo que después de cada ronda de negociación habrá que tirar la mitad de ellas. El procedimiento de negociación consiste en dos rondas de ofertas. En la primera ronda, Alice propone el número de magdalenas $n_A$ que debe recibir, donde $0 \leq n_A \leq 8$. Bob puede aceptar esta oferta (en cuyo caso Alice recibe $n_A$ magdalenas, Bob recibe $8-n_A$ magdalenas, y el juego termina), o rechazarla. Si Bob la rechaza, en la segunda ronda puede decidir el número de magdalenas $n_B$ que debe recibir; sin embargo, en ese momento la mitad de las magdalenas habrán perecido, por lo que tenemos $0 \leq n_B \leq 4$. Este juego puede describirse mediante el árbol que se muestra en la figura siguiente (donde solo se muestra una de las posibles respuestas de Bob):  !!!note:Relación con MDP Los juegos en forma extensiva son una forma útil de representar interacciones multiagente más complejas. Sin embargo, hay que tener en cuenta que son un caso especial de un proceso de decisión de Markov multiagente. Por ello, la mayoría de los investigadores han optado por utilizar el modelo de Markov, más completo, en lugar del juego de forma extensiva, más sencillo, para modelar sistemas multiagente. ## Equilibrio de Nash y críticas Para seguir un camino similar al seguido con los Juegos en Forma Normal, hemos de definir un concepto de solución apropiado para los Juegos en Forma Extensiva, y para ellos hemos de formalizar la noción de estrategia. En este caso, una estrategia para el jugador $i$ debe especificar una elección para cada nodo que pertenece a $V_i$, incluso si un nodo puede no ser alcanzable en una jugada particular del juego. !!!def:Definición Sea $G$ un Juego en Forma Extensiva. Para un agente $i\in N$ y un nodo $v\in V_i$, sea $A_i(v)$ el conjunto de acciones disponibles para el agente $i$ cuando el juego llega al nodo $v$. Entonces una **estrategia** (**pura**) para el agente $i$ en $G$ es una función que asigna a cada nodo $v\in V_i$ una acción de $A_i(v)$. En general, podemos representar una estrategia mediante una secuencia de acciones, empezando por el nodo superior de $V_i$ y bajando de izquierda a derecha. Dada una estrategia $s = (a_1, \dots ,a_n)$, sea $o(s)$ la historia terminal (hoja) que resulta cuando los jugadores actúan según $s$. La recompensa para el jugador $i$ será entonces $u_i(o(s))$. Por lo tanto, de forma análoga a como se hizo en el caso de los juegos en forma normal, un equilibrio de Nash puede definirse como sigue: !!!def:Definición Una estrategia $s = (a_1, \dots ,a_n)$ es un **equilibrio de Nash de un Juego en Forma Extensiva**, $G$, si para cada agente $i\in N$ y cada estrategia $a_i'$ del jugador $i$ se cumple que $u_i(o(s)) \geq u_i(o(s_{-i},a_i'))$. ## Equilibrio de Subjuego Perfecto El problema de la adaptación directa de la definición de Equilibrio de Nash a los Juegos en Forma Extensiva plantea ciertos problemas que no parecen cumplir las expectativas de un equilibrio, por lo que se han dado definiciones más adecuadas ([#Selten]) que intentar proporcionar un concepto de estabilidad que sea robusto frente a posibles errores o cambios en el plan de acción de los otros jugadores. Para ello, necesitamos introducir la noción de **subjuego**: !!!def:Definición Sea $G$ un juego en forma extensiva. Dada una historia no terminal $h = (a_1, \dots ,a_k)$, sea $p$ el nodo donde termina $h$, y sea $T_p$ el subárbol que tiene su raíz en $p$. El **subjuego** que corresponde a la historia $h$, denotado por $G(h)$, es el juego donde: 1. El conjunto de agentes es el mismo que en $G$. 2. Los nodos del árbol $T_p$ siguen la partición del árbol original, es decir: $V_1 \cap T_p,\ V_2\cap T_p, \dots ,\ V_n \cap T_p,\ V_c \cap T_p,\ V_L \cap T_p$. 3. El conjunto de historias (terminales) es simplemente el conjunto de todas las secuencias $h'$ para las que $(h,h')$ es una historia (terminal) en $G$. 4. Los pagos de todos los agentes en todas las hojas de $T_p$ son iguales a sus pagos en las respectivas hojas de $T$. !!!Tip En el ejemplo anterior hay tres subjuegos, a saber, el juego $G$ propiamente dicho, que corresponde a $G(\emptyset)$; el juego $G(A)$, en el que el jugador 1 no tiene elección, pero el jugador 2 tiene que elegir entre $C$ y $D$; y el subjuego $G(B)$, en el que el jugador 1 no tiene elección y el jugador 2 tiene que elegir entre $E$ y $F$. En general, el número de subjuegos es igual al número de historias no terminales. Consideremos un perfil de estrategia $s = (s_1, \dots ,s_n)$. Supongamos que el juego ha comenzado hace algún tiempo, y que se ha producido una historia (no terminal) $h$. Esta historia puede, o no, ser consistente con el perfil $s$ (debido a posibles errores o cambios inesperados, algunos de los jugadores pueden haberse desviado de $s$). Intuitivamente, el perfil $s$ es robusto si para cada jugador $i$, la estrategia $s_i$ proyectada en el subjuego $G(h)$ es la mejor que puede hacer $i$ si, desde el principio del subjuego $G(h)$ y en adelante, el resto de los jugadores se adhieren a $s$. Es decir, bajo la suposición de que no habrá más desviaciones, $s$ sigue siendo la mejor opción: !!!def:Definición Dado un perfil de estrategia $s = (a_1, \dots ,a_n)$ en un juego en forma extensiva, $G$, sea $o_h(s)$ la historia terminal que surge si, tras la ocurrencia de una historia $h$, los agentes juegan según el perfil $s$. Entonces $s$ es un **equilibrio de subjuego perfecto** (**SPE**) si para cada agente $i$, para cada historia $h$ tras la que es el turno del agente $i$, y para cada estrategia $a'_i$ del agente $i$ en el juego $G(h)$, tenemos $u_i(o_h(s)) \geq u_i(o_h(s_{-i},a'_i))$. Es decir, en un equilibrio de subjuego perfecto, cada estrategia no sólo es la mejor respuesta al principio del juego, sino que también sigue siendo la mejor respuesta a las estrategias de los demás jugadores en cualquier punto posible al que llegue el juego. !!!note Se puede probar que todo equilibrio de subjuego perfecto es un equilibrio de Nash. Sin embargo, lo contrario no es cierto. ## Inducción hacia atrás Los equilibrios de subjuego perfecto siempre existen y pueden encontrarse de forma sistemática: el procedimiento para calcularlos se conoce como **inducción hacia atrás**, que pasamos a esbozar brevemente a continuación. !!!def: Definición Definimos la longitud de un subjuego como la longitud de la historia más larga de este subjuego (es decir, el camino más largo desde la raíz hasta una hoja). Una primera aproximación a este proceso de inducción hacia atrás sería: 1. Empezamos por encontrar las estrategias óptimas en todos los subjuegos de longitud 1 (juegos en los que sólo un jugador tiene que hacer un movimiento). 2. Luego continuamos inductivamente, moviéndonos hacia la raíz, y en el paso $k$ encontramos las estrategias óptimas de los jugadores que se mueven al principio de todos los subjuegos de longitud $k$, dadas las estrategias óptimas que hemos encontrado en los subjuegos más cortos. Sin embargo, hay algunas cuestiones que deben tratarse con cuidado: 1. Si algunos agentes tienen un número infinito de acciones disponibles en algunos nodos, el procedimiento puede atascarse simplemente porque no hay una estrategia óptima alcanzable. 2. Los nodos que corresponden a jugadas al azar requieren un tratamiento especial. Para cualquier nodo de este tipo, tenemos que calcular los resultados esperados de todos los jugadores teniendo en cuenta las estrategias que hemos calculado en las subjugadas con raíz en los descendientes de este nodo. 3. Una estrategia óptima en un nodo determinado puede no ser única. En este caso, cada combinación de estrategias óptimas que identificamos a lo largo del análisis da lugar a un equilibrio de subjuego perfecto diferente. Para los juegos con espacios estratégicos finitos o, más generalmente, para los juegos en los que existe una acción óptima en cada nodo (dado cualquier perfil de estrategia para el subjuego que desciende desde este nodo), la extensión de la inducción hacia atrás para manejar todos los problemas mencionados es la siguiente: * Empezando por $k = 1$: - Para cada subjuego, $G'$, de longitud $k$: Sea $v$ la raíz de $G'$. - Si $v\in V_c$, entonces calcular los pagos esperados para todos los jugadores usando la distribución de probabilidad de $v$. Hacer esto para cada combinación de estrategias óptimas que ya se ha calculado para los subjuegos más cortos. - Si $v\notin V_c$ (sea $i$ tal que $v\in V_i$), entonces para cada combinación de estrategias óptimas para los subjuegos más cortos, encontrar la acción óptima del jugador $i$ en $v$. Si hay más de una, se registran todas, de modo que se siguen llevando la cuenta de todas las combinaciones de acciones óptimas en todos los nodos considerados hasta ahora. !!!Tip Consideremos el juego con dos jugadores de la figura siguiente. El jugador 1 tiene que mover primero y decidir entre las alternativas $A$ y $B$. Después, hay un evento aleatorio representado por los dos nodos de azar, y entonces el jugador 2 tiene que mover. Obsérvese que entre los estados terminales hay estados indiferentes para el jugador 2, por ejemplo, al elegir una acción en el subárbol más a la izquierda y en el más a la derecha.  Para que la notación sea más compacta, podemos utilizar una cadena de $4$ bits que codifican la estrategia del jugador 2 para los cuatro nodos a los que tiene que moverse, con el significado previsto de que $0$ significa elegir la hoja de la izquierda y $1$ la de la derecha. Con esta notación, el análisis procede como sigue: 1. Hay cuatro subjuegos de longitud $1$, en todos los cuales el jugador 2 tiene que moverse. Podemos ver que para el jugador 2 son indiferentes el subjuego de la izquierda y el de la derecha (en cada uno de ellos obtiene el mismo resultado haga lo que haga). En los otros dos subjuegos hay una única acción óptima. Por lo tanto, en total tenemos cuatro estrategias óptimas para el jugador 2, a saber, $0100$, $0101$, $1100$ y $1101$ (depende de las combinaciones que haga en los dos juegos indiferentes). 2. Hay dos subjuegos de longitud $2$, que comienzan ambos con una jugada al azar (no pertenece a ninguno de los dos jugadores). Para las cuatro opciones del jugador 2 identificadas en la ronda anterior, encontramos los pagos esperados para los dos jugadores: - En el nodo de azar izquierdo, son, respectivamente, $(5/3,1)$, $(5/3,1)$, $(7/3,1)$ y $(7/3,1)$. - En el nodo de azar de la derecha son, respectivamente, $(6/4,2)$, $(7/4,2)$, $(6/4,2)$ y $(7/4,2)$. 3. Sólo hay un subjuego de longitud $3$, el propio juego completo, y el jugador 1 tiene que decidir en la raíz si juega $A$ o $B$. Para cada una de las acciones óptimas del jugador 2, puede comparar su resultado esperado y ver que debe jugar $B$ sólo cuando el jugador 2 elige la estrategia $0101$. Por tanto, hemos identificado cuatro equilibrios de subjuego perfecto: $(A,0100)$, $(B,0101)$, $(A,1100)$ y $(A,0101)$. Para los juegos en los que no existe una acción óptima para algún nodo del árbol, el procedimiento no puede terminar con una solución, y podemos concluir que el juego no posee un equilibrio de subjuego perfecto. Por lo tanto, la conclusión principal de esta subsección se puede resumir en el siguiente teorema: !!!def:Teorema Los perfiles estratégicos devueltos por el procedimiento de inducción hacia atrás son precisamente los equilibrios de subjuego perfecto del juego. Cuando los espacios de acción de todos los jugadores son finitos, siempre tenemos una acción óptima en cada nodo del juego. Por lo tanto, el procedimiento de inducción hacia atrás siempre terminará, lo que nos lleva al siguiente corolario: !!!def:Corolario Todo Juego en Forma Extensiva en el que cada nodo tiene un número finito de acciones tiene al menos un equilibrio de subjuego perfecto. Hasta ahora hemos asumido que los jugadores tienen pleno conocimiento del juego que están jugando, es decir, conocen todas las jugadas posibles del juego, siempre tienen toda la información necesaria acerca de la configuración actual del juego y conocen las preferencias de los otros jugadores. Este tipo de juegos se conocen como **Juegos de Información Perfecta**: !!!def: Información Perfecta Decimos que un juego en forma extensiva tiene **información perfecta** si todos los jugadores saben exactamente en qué nodo del árbol están en cualquier momento del juego. Para este tipo de juegos existe un resultado fundamental: !!!def: Teorema de Zermelo Todo Juego finito en Forma Extensiva con información perfecta tiene un equilibro de estrategias puras. El equilibrio que se indica en el teorema anterior se obtiene plegando el árbol por medio de la inducción hacia atrás. Pero ha de tenerse en cuenta que el equilibrio obtenido por este método, a pesar de poder tener propiedades muy interesantes, no es único ni el más razonable. # Referencias [#Neumann]: Von Neumann, J., & Morgenstern, O. *[Theory of games and economic behavior](https://uvammm.github.io/docs/theoryofgames.pdf)*. Princeton University Press, 1944. [#Neumann2]: John von Neumann. *[Zur theorie der gesellschaftsspiele](https://www.roulette-forum.de/info/archiv/bilder/nostradamus1500/Theoriedergesellschaftsspiele.pdf)*. Mathematische Annalen, 100:295–320, 1928. [#Osborne]: Martin Osborne and Ariel Rubinstein. *[A Course in Game Theory](http://zhangjun.weebly.com/uploads/2/8/1/8/2818435/martin.pdf)*. MIT Press, 1994. [#Shoham]: Yoav Shoham and Kevin Leyton-Brown. *[Multiagent Systems: Algorithmic, Game Theoretic and Logical Foundations](http://www.masfoundations.org/mas.pdf)*. Cambridge University Press, 2009. [#Nash]: John F. Nash. *[Non-cooperative games](https://www.gwern.net/docs/statistics/decision/1951-nash.pdf)*. Annals of Mathematics, 54:286–295, 1951. [#Selten]: R. Selten. *[Reexamination of the perfectness concept for equilibrium points in extensive games](http://www.control.ece.ntua.gr/GraduateCourses/GameTheory/R.%20Selten%20-%20Perfectness.pdf)*. International Journal of Game Theory, 4:25–55, 1975. [#Marden]: J. R. Marden. Curso *[Game Theory and Multiagent Systems (ECE 149)](https://web.ece.ucsb.edu/~jrmarden/ece149.html)*, 2020.