**SVRAI** Juegos No Cooperativos  # Introducción Hasta ahora hemos estado viendo aproximaciones a la deliberación en los casos individuales, es decir, cuando nos preocupamos en cómo un agente modela y extrae conocimiento del mundo para poder optimizar una planificación/estrategia/política en su deliberación. Pero un caso completamente distinto, y tan interesante como el individual, se presenta cuando intentamos generar estrategias para un conjunto de agentes que interactúan bajo el mismo contexto enfrentándose al mismo problema. Este caso, denominado como **Sistemas MultiAgente**, aporta un nuevo marco de trabajo, planteando nuevas razones para razones para la incertidumbre y la necesidad de nuevas herramientas para su modelado y resolución. En este contexto, 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 pueden ir desde el uso de canales de comunicación poco fiables hasta las limitaciones computacionales que tengamos para su ejecución y simulación. Incluso la propia interacción y concurrencias en las actividades conjuntas y simultáneas de los agentes ya supone un reto que no está resuelto de forma satisfactoria. 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 **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 estrategias de los agentes 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 de 1944 [#Neumann], donde los autores introducen un formalismo matemático para analizar ciertos tipos de tomas de decisiones en las que dos o más agentes realizan acciones que repercuten en las decisiones de todos ellos. En este tema del curso nos centramos en los sistemas no cooperativos, y en el siguiente daremos unas pinceladas sobre sistemas cooperativos. Comenzamos hablando de **Juegos en Forma Normal** para pasar a continuación a presentar los **Juegos en Forma Extensiva**, las dos formalizaciones más habituales de esta teoría. Con el fin de que sirva de introducción a esta nueva aproximación, en ambos temas haremos uso de la notación habitual de la literatura, que algunas veces no es exactamente igual a la que hemos visto en temas anteriores en el marco de los MDP. # 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 (todos ellos ya usados para aproximaciones anteriores): - El conjunto de *agentes* 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*, que asigna un valor numérico determinista a cada resultado. Nos limitaremos a juegos con un número finito de agentes, aunque se pueden considerar variantes con una cantidad infinita de ellos, o incluso un *continuo* de agentes, pero no supondremos que los conjuntos de acciones de los agentes 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\}$ representa el conjunto de agentes. 2. Para cada $i\in N$, $A_i$ es el conjunto de acciones disponible 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. Obsérvese que la recompensa/utilidad que recibe un agente no depende únicamente de su acción, sino de las acciones ejecutadas por todos los agentes del sistema. Además, a menudo tendremos que razonar sobre las acciones de un agente manteniendo fijas las acciones de todos los demás agentes. Por ello, usamos una notación especial para el vector de acciones de todos los agentes que no sean el agente $i$: !!! Dado un perfil de acción $a = (a_1,\dots,a_n)$ y un agente $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 que lo haga: * Si ambos sospechosos guardan silencio, serán condenados por una infracción menor (por falta de pruebas concluyentes), 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$)... obviamente, no se les permite comunicarse durante este proceso. 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$$ que podemos representar de forma más compacta como: | | $nD$ | $D$ | | :--: | :-------: | :-------: | | $nD$ | $(-1,-1)$ | $(-4,0)$ | | $D$ | $(0,-4)$ | $(-3,-3)$ | y resume de forma estándar las condiciones del juego. En los juegos de dos agentes con un número finito de acciones, las recompensas (también llamadas *pagos* en este contexto) de los agentes 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))$. La cuestión principal que estudia la Teoría de Juegos es cómo predecir el resultado de un juego bajo ciertas suposiciones y, de forma derivada, intentar determinar las estrategias más convenientes para los agentes. ## 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 agentes para obtener el mejor resultado?, ¿cuál es la mejor acción en un juego determinado? Cuando para un agente tenemos una forma de decidir su *mejor acción* hablamos de una **estrategia**, por lo que las estrategias se asocian a *soluciones* al juego. En general una estrategia se puede ver como una aplicación, $s$, que indica qué acción debe tomar cada agente del juego. También podemos verlas desde el punto de vista del agente $i$-ésimo, en cuyo caso $s_i : A_i \to [0,1]$ solo indicaría la acción que debe tomar ese agente. !!! Observa que el papel de $s$ es el mismo que en MDP jugaba $\pi$, la política o estrategia a seguir por el agente. 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**. ### MaxMin Las primeras aproximaciones a la definición de estrategias dentro del caso no cooperativo 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 las pérdidas en lugar de maximizar las ganancias). En concreto, en un juego con dos agentes, $i$ y $j$, la estrategia maxmin del agente $i$ vendrá dada por: !!!Def $$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$. En los juegos que consideró inicialmente Neumann las acciones buenas para un agente normalmente daban un resultado malo para el otro. Desgraciadamente, la estrategia global en la que ambos agentes 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 agentes [#Neumann2]. ### Bienestar Social y Óptimo de Pareto Otra aproximación a la definición de bondad es intentar maximizar el bienestar general de todos los agentes. La estrategia de **bienestar social** es la que maximiza la suma de los beneficios de todos, es decir: !!!Def $$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, sino la posibilidad o no de que cada uno mejore su condición sin empeorar las de otros. !!!Def:Óptima de Pareto 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 agente puede tener un incentivo para realizar 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]: !!!Def:Equilibrio de 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 agentes seguirán la misma estrategia. Es decir, si todos los demás están siguiendo el equilibrio de Nash, entonces lo mejor para todos es seguir 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 problemas puede haber muchos equilibrios de este tipo. Además, algunos de esos equilibrios de Nash pueden ser mejores para unos agentes que para otros, por lo que los agentes 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. !!!note 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 agentes, lo mejor depende de cuánto estemos dispuestos a respetar el egoísmo de cada uno de ellos, 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 !!!Tip En el Dilema del Prisionero, no es difícil predecir lo que haría un agente racional (perfectamente racional). En efecto, el agente $X$ puede razonar de la siguiente manera: * *Si $Y$ me delata, es más rentable para mí delatar ($u_X=-3$) que permanecer en silencio ($u_X=-4$).* * *Si $Y$ no me delata, es más rentable para mi delatar ($u_X=0$) que permanecer en silencio ($u_x=-1$).* Por lo tanto, $X$ no necesita saber qué pretende hacer $Y$: en cualquier caso, obtiene un mejor resultado si él delata. El agente $Y$ razona de la misma manera, por lo que el único resultado racional de este juego es que ambos agentes delaten. En este ejemplo, ocurre que para cada agente hay una estrategia que es preferible, independientemente de la elección del otro agente. 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 Para ambos agentes en el juego del Dilema del Prisionero, la estrategia $D$ domina estrictamente a la estrategia $nD$ y, por tanto, es una estrategia estrictamente dominante. Si cambiamos la descripción del juego de modo que cuando $X$ delata, $Y$ es encarcelado durante $3$ años, delate o no, entonces $D$ sigue siendo una estrategia débilmente dominante para $Y$, pero ya no es estrictamente dominante: si $X$ delata, a $Y$ le resulta indiferente $D$ o $nD$. Es fácil ver que cada agente puede tener como máximo una estrategia débilmente dominante (y, por tanto, como máximo una estrategia estrictamente dominante). Además, si un agente 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 los agentes (o todos) 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 agente 1 y Bob el agente 2): | | $F$ | $P$ | | :--: | :-----: | :-----: | | $F$ | $(1,3)$ | $(0,0)$ | | $P$ | $(0,0)$ | $(3,1)$ | En este ejemplo, ninguno de los agentes 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 agente (o, en este caso particular, ambos agentes) puede cambiar su acción para aumentar su recompensa. El equilibrio de Nash pretende capturar la noción de estrategia resistente 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. !!! Si decimos que una acción $a$ es **la mejor respuesta del agente $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$, entonces un equilibrio de Nash es un perfil de estrategia en el que la acción de cada agente es la mejor respuesta a las acciones de los otros agentes. !!!Tip Así pues, 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, usar como estrategia un equilibrio de Nash sólo es racional si todos los demás agentes siguen 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 muestra el siguiente juego. !!!Tip: Ejemplo (Emparejar monedas) Consideremos un juego de $2$ agentes 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 agente (*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 agente (*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 emparejador o como desemparejador, 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 $s_i$, $supp(s_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 agente $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, 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 agente $i$. Obsérvese que una acción $a^j_i$ corresponde a una estrategia mixta, $s_i$, dada por $p^j_i = 1$, $p^k_i = 0$ para $k\neq j$. Por ello, nos referiremos a las estrategias de esta forma como **estrategias puras** del agente $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 que lo hace muy atractivo: !!!def:Teorema Todo juego en forma normal con un número finito de agentes y un número finito de estrategias para cada agente admite un equilibrio de Nash mixto. 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 agente $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 agente $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 agente posee una estrategia dominante, tiene un incentivo muy fuerte para utilizarla. Del mismo modo, si una de las estrategias del agente 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 agentes asumir que esta estrategia nunca se utilizará y, por lo tanto, pueden eliminarla de la lista de estrategias de ese agente (de nuevo, suponemos racionalidad en todos los agentes). Pero, al hacer esto, el agente ha de tener en cuenta que el juego ha cambiado, y en este nuevo juego algunas de sus propias estrategias pueden llegar a estar ahora dominadas y, por lo tanto, pueden ser eliminadas. La formalización de este procedimiento se denomina **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 de la resolución del problema. !!!Tip:Ejemplo Consideremos $N=\{1,2\}$, cada agente debe elegir un $n_i∈ \{1,\dots,10\}$, y un agente gana ($u_i=1$) si $n_i$ está más cerca de la mitad de la media de los dos números; si $n_1=n_2$ ninguno gana. Por ejemplo, si $n_1 = 9$ y $n_2 = 5$, entonces $2$ gana, ya que $5$ está más cerca de $3.5$ que $9$. El agente $1$ puede razonar de la siguiente manera: 1. $\frac{1}{2}\frac{n_1 + n_2}{2}≤ 5$, por lo que para el agente $2$ elegir $n_2 = 10$ está estrictamente dominado por elegir $n_2 = 1$. Por lo tanto, puede suponer que el agente $2$ nunca elegirá $n_2 = 10$. 2. El mismo argumento funciona para el propio agente $1$. Así, ambos agentes pueden asumir que el espacio de acción está, de hecho, limitado a $\{1,\dots,9\}$. 3. Por tanto, $\frac{1}{2}\frac{n_1 + n_2}{2}≤ 4.5$ y, en consecuencia, para ambos agentes elegir $9$ está estrictamente dominado por elegir $1$. 4. 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 agentes 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 agente dispone de 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 para este entorno más general el famoso resultado de Nash ya no se verifica y la existencia de equilibrios de Nash mixtos 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**: 1. Cada agente presenta una puja en un sobre cerrado (respectivamente, $x,y∈ \mathbb{R}^+$). 2. A continuación se abren los sobres y el agente 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 la valoración del otro. Entonces, si Alice gana el cuadro y paga $x$, $u_A=300 - x$, mientras que si Bob gana y paga $y$, $u_B=200 - y$ (nótese que podrían llegar a ser recompensas negativas). 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 $u_A=100$. * Si Alice puja más, tendrá que pagar más, y si puja menos, perderá la subasta, por lo que su recompensa sería $u_A=0$. * Por otro lado, si Bob puja menos, el resultado seguirá siendo el mismo, y si puja más, ganará, pero $u_B < 0$. El mismo argumento muestra que cualquier perfil de acción de la forma $(x,x)$, con $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 agente 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€$ 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. !!!Note: 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 agente a las estrategias de los otros agentes se alcanza en el punto donde la derivada parcial de $u_i$ con respecto a la elección del agente $i$ se anula. 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 Hay un tipo de juegos que expresan una competencia directa entre los agentes. Se trata de juegos en los que el beneficio de un agente es igual a la pérdida de los demás. De hecho, los **Juegos de Suma Cero**, que es como se llaman, históricamente fue la primera clase de juegos que se estudió ampliamente antes de pasar a los juegos generales en forma normal, siendo 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 agentes está completamente especificado por los pagos de uno de los agentes, ya que los pagos del otro agente son simplemente el opuesto, por lo que muchas veces se representan por la matriz de pago del agente $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 agente señalado, esto significa asumir que, independientemente de lo que elija, el otro agente 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 agente $1$ jugará para maximizar este valor mínimo. Con el mismo espíritu, si el agente $2$ también piensa de forma pesimista, pensará que, elija lo que elija, el agente $1$ elegirá la acción que maximice su ganancia, es decir, para una columna $j$ el agente acabará pagando $\max_i P_{ij}$. El segundo agente querrá entonces asegurarse de minimizar este pago en el peor de los casos. Por lo tanto, los dos agentes 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 ahora la maximización y la minimización anteriores son sobre el conjunto de estrategias mixtas. Como el espacio de estrategias mixtas contiene a las puras, 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 agentes, $\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, y sin embargo ambos agentes 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 los agentes resuelvan el mismo problema un cierto número de veces de forma secuencial. 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: !!!Tip 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 agente ya que es la última partida. Por supuesto, como te has dado cuenta de esto, también sabes que el otro agente 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 agentes 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 agente 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 agente 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 le enviara estrategias (como programas en Fortran) que se usarían para jugar al dilema del prisionero unas contra otras durante $200$ rondas. El ganador sería el que acumulara más puntos. Se enviaron muchas estrategias, entre las que se incluían: - **ALL-D**: siempre delatar. - **RANDOM**: elegir la acción al azar. - **TIT-FOR-TAT** (ojo por ojo): no delatar en la primera ronda, y luego hacer lo que el otro agente hizo la última vez. - **TESTER**: delatar en la primera ronda. Si el otro agente delata, entonces usar TIT-FOR-TAT. Si el otro agente no delató, entonces no delatar durante dos rondas y luego delatar. - **JOSS**: usar TIT-FOR-TAT pero el $10\%$ de las veces delatar en lugar de no delatar. La estrategia TIT-FOR-TAT ganó el torneo. Aún así, ganó menos que ALL-D en los enfrentamientos entre los dos, 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 no delatar. No delató con los que podían delatar y delató contra el resto. Este resultado, aunque intrigante, no es teóricamente sólido. Por ejemplo, TIT-FOR-TAT perdería contra una estrategia que actuara como TIT-FOR-TAT pero delatara en la última ronda. Aun así, TIT-FOR-TAT se ha utilizado ampliamente y se considera una estrategia sencilla pero robusta. Otro método para analizar los juegos iterados consiste en suponer que los agentes utilizan algún algoritmo de aprendizaje y, a continuación, intentar determinar hacia qué estrategia convergerá su aprendizaje. Esta aproximació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 agentes, $n$, y el número de acciones disponibles para cada agente, $m$. Para los juegos de dos agentes (y, en general, para los juegos con un número constante de agentes) la complejidad de la representación no es un problema: si cada uno de los agentes 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 agentes es grande, el tamaño de la representación matricial explota: para un juego de $n$ agentes con dos acciones por agente, la matriz tiene $2^n$ casillas. Esto es, en cierto sentido, inevitable: !!!note Un argumento de recuento estándar muestra que cualquier formalismo que pueda expresar cada juego de $n$ agentes producirá descripciones de tamaño exponencial para la mayoría de los juegos. Por lo tanto, para los juegos multiagente 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 agentes 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 se comportan igual, se sabe que el cálculo de un equilibrio de Nash es completo para la clase de complejidad **PPAD**, incluso para juegos de dos agentes 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 agentes) es **NP**-completo. De hecho, incluso encontrar un equilibrio de Nash aproximado, es decir, un perfil de estrategia en el que cada agente 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 agente 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 agentes 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 $\varepsilon$, para cualquier constante $\varepsilon > 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 agentes realizan sus acciones **secuencialmente**, pero 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 agentes se turnan y toman una decisión después de ser informados de las decisiones de sus oponentes. Los juegos en Forma Extensiva poporcionan algunas herramientas para analizar este tipo de situaciones. Vamos a comenzar describiendo un juego sencillo con jugadas secuenciales que servirá para ilustrar todo lo que hay que especificar para definir un juego en Forma Extensiva: !!!Tip:Ejemplo Consideremos el juego con dos agentes representado en la figura siguiente: el agente $1$ actúa primero y tiene que decidir entre las alternativas $A$ y $B$; a continuación, el agente $2$ actúa y, dependiendo de lo que haya elegido el agente $1$, tendrá que decidir entre $C$ y $D$, o entre $E$ y $F$. Finalmente, tras la acción del agente $2$, el juego termina y cada agente recibe una recompensa dependiendo del estado terminal que hayan alcanzado. Por ejemplo, si el agente $1$ elige $A$ y el agente $2$ elige $C$, sus pagos son $2$ y $5$, respectivamente. ![](./img/extensive1.png align="center" width=30%) Tal y como se muestra en el ejemplo, 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 alguno de los agentes. Todos los nodos internos del árbol representan estados del juego. En cada estado, uno de los agentes 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 una acción al azar (para cada $v\in V_c$, se da también una distribución de probabilidad sobre el conjunto de aristas que salen de él), y * $V_L$ denota el conjunto de hojas. - 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. Como existe una correspondencia biyectiva entre las historias terminales y las hojas, en lo que sigue, por un 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)\}$. * 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 acciones al azar, por lo que $V_c = \emptyset$. * La función de recompensa del agente $1$ viene dada por: $$u_1((A,C)) = 2,\ u_1((A,D)) = 1,\ u_1((B,E)) = 3,\ u_1((B,F)) = 1$$ * La función de recompensa del agente $2$ viene dada por: $$u_2((A,C)) = 5,\ u_2((A,D)) = 1,\ u_2((B,E)) = 4,\ u_2((B,F)) = 2$$ Veamos 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 agente se le debe asignar un número (entero) de magdalenas. Además, 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 quiere 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$. Entonces, Alice recibe $4 - n_B$ magdalenas, Bob recibe $n_B$ magdalenas, y el juego termina. 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, entonces, formalizar la noción de estrategia. En este caso, una estrategia para el agente $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 que sigue un orden impuesto en $\cup_{i=1}^n V_i$. Dada una estrategia $s = (a_1, \dots ,a_n)$, sea $o(s)$ la historia terminal (hoja) que resulta cuando los agentes actúan según $s$. La recompensa para el agente $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 agente $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 intentan proporcionar un concepto de estabilidad que sea robusto frente a posibles errores o cambios en el plan de acción de los otros agentes. 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 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 agente $1$ no tiene elección, pero el agente $2$ puede que elegir entre $C$ y $D$; y el subjuego $G(B)$, en el que el agente $1$ no tiene elección y el agente $2$ puede 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 agentes pueden haberse desviado de $s$). Intuitivamente, el perfil $s$ es robusto si para cada agente $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 agentes 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 agentes desde 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. 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. ### Inducción hacia atrás !!!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 agente 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 agentes 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 agentes 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 agentes 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 agente $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 agentes de la figura siguiente. El agente $1$ tiene que actuar primero y decidir entre las alternativas $A$ y $B$. Después, hay un evento aleatorio representado por los dos nodos de azar ($c$ en la figura), y entonces el agente $2$ tiene que actuar. Obsérvese que entre los estados terminales hay estados indiferentes para el agente $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 agente $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 agente $2$ tiene que moverse. Podemos ver que para el agente $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 agente $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 agentes). Para las cuatro opciones del agente $2$ identificadas en la ronda anterior, encontramos los pagos esperados para los dos agentes: - 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 agente $1$ tiene que decidir en la raíz si juega $A$ o $B$. Para cada una de las acciones óptimas del agente $2$, puede comparar su resultado esperado y ver que debe jugar $B$ sólo cuando el agente $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 se puede resumir en el siguiente teorema: !!!def:Teorema Los perfiles estratégicos devueltos por el procedimiento de inducción hacia atrás son los equilibrios de subjuego perfecto del juego. Cuando los espacios de acción de todos los agentes son finitos, siempre tenemos una acción óptima en cada nodo del juego. Por 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. ## Juegos de Información Perfecta Hasta ahora hemos asumido que los agentes 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 agentes. Este tipo de juegos se conocen como **Juegos de Información Perfecta**: !!!def: Información Perfecta Decimos que un juego en forma extensiva es de **información perfecta** si todos los agentes 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 de 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 tiene porqué ser 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.