**SVRAI** **Aplicación a Juegos Estratégicos** Los modelos relacionales pueden utilizarse para codificar la información esencial de un Juego en Forma Normal. Veamos el caso de 2 jugadores: !!!side:1 El símbolo $⊔$ representa la unión disjunta de los conjuntos. Así se garantiza que, si hay un elemento $x$ que pertenece tanto a $A$ como a $B$, la unión disjunta $A ⊔ B$ tendrá dos copias de $x$: una identificada como la procedente de $A$ (digamos, $x_A$), y otra identificada como la procedente de $B$ (digamos, $x_B$). Formalmente, la unión disjunta de $A$ y $B$ puede definirse como $A ⊔ B := \{a_A | a ∈ A\} ∪ \{b_B | b ∈ B\}$. !!!def: Definición (Modelo Relacional de Juego) Sea $G = ⟨\{1, 2\} , A {\times} B, u⟩$ un juego en forma normal para dos jugadores, con $A$ y $B$ como sus respectivos conjuntos de acciones. Definamos el conjunto de proposiciones atómicas (es decir, las propiedades básicas) como $P_G := A ⊔ B$ $^1$. El juego $G$ induce un modelo multirrelacional $M_G = ⟨A {\times} B, ↭_1, ↭_2, ≼_1, ≼_2, V⟩$, cuyos componentes se definen de la siguiente manera: * Los mundos de $M_G$ son los posibles perfiles de acción $(a, b) ∈ A {\times} B$. * Las relaciones $↭_1$ y $↭_2$ indican el control que cada jugador tiene para modificar el perfil de acción: $$(a, b) ↭_1 (a′, b′) \iff b = b′\\ (a, b) ↭_2 (a′, b′) \iff a = a′$$ Así, si $(a, b)$ es el perfil de acción actual, un jugador tiene la libertad de mover el juego al perfil de acción $(a′, b′)$ pero modificando solo su acción, no la del otro jugador. * Las relaciones $≼_1$ y $≼_2$ indican las preferencias de cada jugador, relacionándolo con la utilidad proporcionada por el juego: $$(a, b) ≼_1 (a′, b′) \iff u_1(a, b) ⩽ u_1(a′, b′)\\ (a, b) ≼_2 (a′, b′) \iff u_2(a, b) ⩽ u_2(a′, b′)$$ * La valoración atómica $V$ indica cuáles son los mundos en los que se está jugando cada una de las acciones en $A ⊔ B$. Formalmente: $$V(a_A)=\{(a,b)\ |\ b \in B\}$$ $$V(b_B)=\{(a,b)\ |\ a \in A\}$$ !!!teorema:Proposición Para cualquier juego $G = ⟨\{1, 2\} , A {\times} B, u⟩$: Las relaciones inducidas $↭_i$ verifican: 1. *Reflexividad*: $\forall (a, b) ∈ A {\times} B\ \Big((a, b) ↭_i (a, b)\Big)$ 2. *Simetría*: $\forall (a, b), (a′, b′) ∈ A {\times} B\ \Big((a, b) ↭_i (a′, b′) \to (a′, b′) ↭_i (a, b)\Big)$ 3. *Transitividad*: $\forall (a, b), (a′, b′), (a′′, b′′) ∈ A {\times} B\ \Big((a, b) ↭_i (a′, b′) \wedge (a′, b′) ↭_i (a′′, b′′) \to (a, b) ↭_i (a′′, b′′)\Big)$ Las relaciones de preferencia inducidas $≼_i$ verifican: 1. *Reflexividad*: $\forall (a, b) ∈ A {\times} B\ \Big((a, b) ≼_i (a, b)\Big)$ 2. *Transitividad*: $\forall (a, b), (a′, b′), (a′′, b′′) ∈ A {\times} B\ \Big((a, b) ≼_i (a′, b′) \wedge (a′, b′) ≼_i (a′′, b′′) \to (a, b) ≼_i (a′′, b′′)\Big)$ !!!Ejemplo: El dilema del Prisionero Consideremos el Juego del Dilema del Prisionero (las filas corresponden al Jugador 1, y las columnas al Jugador 2): | |SS|TP| |--|--|--| |SS|(−1, −1)| (−3, 0)| |TP|(0, −3)|(−2, −2)| Este juego induce el siguiente modelo multirelacional $M_D$ (las relaciones $↭_i$ dibujadas con líneas onduladas, y las relaciones $≼_i$ dibujadas con líneas rectas):  donde no se representan todas las relaciones, solo las básicas, derivándose el resto por reflexividad y transitividad (la simetría de $↭_i$ sí está indicada en el diagrama por medio de la flecha con doble dirección). Por supuesto, se puede describir un modelo relacional sin utilizar un diagrama. Para ello, basta con enumerar los componentes del modelo: * $W = {(SS, SS), (SS, TP), (TP, SS), (TP, TP)}$ * $↭_1 = \{ \{(SS, SS), (TP, SS)\} , \{(SS, TP), (TP, TP)\} \}$ * $↭_2 = \{ \{(SS, SS), (SS, TP)\} , \{(TP, SS), (TP, TP)\} \}$ * $≼_1 = \{(SS, TP)\} ≺ \{(TP, TP)\} ≺ \{(SS, SS) \} ≺ \{(TP, SS)\}$ * $≼_2 = \{(TP, SS)\} ≺ \{(TP, TP)\} ≺ \{(SS, SS)\} ≺ \{(SS, TP)\}$ Donde debemos tener en cuenta que cada relación debe cerrarse con las propiedades que verifica (reflexividad, trnasitividad, etc.). Podemos dar una generalización de la definición anterior al caso de $n$ jugadores. !!!def:Definición (Modelo relacional del Juego) Sea $G = ⟨N, A = A_1 {\times} {\dots} {\times} A_n, u⟩$ un juego de forma normal, con $A_i$ el conjunto de acciones de cada jugador $i$. Definimos el conjunto de proposiciones atómicas (es decir, propiedades básicas) como $P_G := \bigsqcup_{i∈N} A_i$. El juego $G$ induce un modelo multirrelacional $M_G = ⟨A, \{≼_i\}_{i∈N} , \{↭_i\}_{i∈N} , V⟩$, cuyos componentes se definen: * Cada mundo en $M_G$ es un perfil de acción $(a_1, \dots , a_n) ∈ A$. * Cada $↭_i$, la relación del jugador $i$, se define como: $$(a_1, \dots , a_n) ↭_i (a′_1, \dots , a′_n) \iff \forall j\neq i\ (a_j = a′_j)$$ * Cada relación $≼_i$, la relación de preferencia para el jugador $i$, se define como: $$(a_1, \dots , a_n) ≼_i (a′_1, \dots , a′_n) \iff u_i(a_1, \dots , a_n) ⩽ u_i(a′_1, \dots , a′_n)$$ * La valoración atómica $V$ se define, para cada $x_i ∈ PG$, como: $$V(x_i) := \{(a_1, \dots , a_n) ∈ A\ |\ a_i = x\}$$ !!!warn:Ejercicio Construye el modelo relacional correspondiente al siguiente juego dado en forma normal: | | `L` | `M` | `H` | |----|------|------|------| |`L` |(4, 4)|(2, 5)|(1, 3)| |`M` |(5, 2)|(3, 3)|(2, 1)| |`H` |(3, 1)|(1, 2)|(0, 0)| $\quad$ # Modelos basados en Juegos Una vez que sabemos cómo convertir un juego en forma normal en un modelo relacional, podemos utilizar herramientas de lógica modal para razonar sobre el modelo. Para el lenguaje, el modelo tiene tantas modalidades como relaciones hayamos introducido: !!!def: Definición (Lenguaje $\mathcal{L}_{\{⟨↭_i⟩\}_{i∈N},\{⟨≼_i⟩\}_{i∈N}}$) Sea $G = ⟨N, A = A_1 {\times} {\dots} {\times} A_n, u⟩$ un juego en forma normal. Definamos el conjunto de proposiciones atómicas como $P_G := ⨆_{i∈N} A_i$. Las fórmulas del lenguaje $\mathcal{L}_{\{⟨↭_i⟩\}_{i∈N},\{⟨≼_i⟩\}_{i∈N}}$ vienen dadas por: $$ϕ, ψ ::= p\ |\ ¬ϕ\ |\ ϕ ∨ ψ\ |\ ⟨↭_i⟩ ϕ\ |\ ⟨≼_i⟩ ϕ$$ con $p ∈ P_G$ e $i ∈ N$. Otros símbolos se definen como antes; en particular, tenemos: $$[↭_i] ϕ := ¬ ⟨↭_i⟩ ¬ϕ$$ $$[≼_i] ϕ := ¬ ⟨≼_i⟩ ¬ϕ$$ La interpretación semántica es exctamente la esperada: !!!def:Definición Sea $G = ⟨N, A = A_1 {\times} {\dots} {\times} A_n, u⟩$ un juego en forma normal, y sea $M_G = ⟨A, \{↭_i\}_{i∈N} , \{≼_i\}_{i∈N} , V⟩$ su modelo multirelacional inducido. Al evaluar fórmulas en $\mathcal{L}_{\{⟨↭_i⟩\}_{i∈N},\{⟨≼_i⟩\}_{i∈N}}$: * Las proposiciones atómicas y las conectivas booleanas se evalúan como antes. * Para cada relación $↭_i$: $$(MG, (a_1, \dots , a_n)) ⊩ ⟨↭_i⟩ ϕ \iff \text{ existe } (a′_1, \dots , a′_n)\in A \text{ tal que } \Biggl\{ \begin{array}{l}(a_1, \dots , a_n) ↭_i (a′_1, \dots , a′_n) \\ (M_G, (a′_1, \dots , a′_n)) ⊩ ϕ\end{array}$$ * Para cada relación $≼_i$: $$(MG, (a_1, \dots , a_n)) ⊩ ⟨≼_i⟩ ϕ \iff \text{ existe } (a′_1, \dots , a′_n)\in A \text{ tal que } \Biggl\{ \begin{array}{l}(a_1, \dots , a_n) ≼_i (a′_1, \dots , a′_n) \\ (M_G, (a′_1, \dots , a′_n)) ⊩ ϕ\end{array}$$ # Perspectiva modal de la Solución Dentro de $\mathcal{L}_{\{⟨↭_i⟩\}_{i∈N},\{⟨≼_i⟩\}_{i∈N}}$ es posible caracterizar el concepto de mejor respuesta. Más concretamente: !!!teorema: Teorema Para cada jugador $i$ existe una fórmula $\mathcal{L}_{\{⟨↭_i⟩\}_{i∈N},\{⟨≼_i⟩\}_{i∈N}}$, $BR_i$, que es verdadera en un perfil de acción $\mathbf{a}=(a_1, \dots , a_n)$ del modelo si y sólo si la acción elegida por el jugador $i$ en $\mathbf{a}$, $a_i$, es su mejor respuesta frente a la acción colectiva elegida por los demás jugadores, $\mathbf{a}_{-i}$. Esto es: $$(M_G, \mathbf{a}) ⊩ BR_i \iff a_i ∈ B_i(\mathbf{a}_{-i})$$ !!!demo:Demostración Para cualquier juego en forma normal, $G$, se tiene que: $$(M_G, \mathbf{a}) ⊩ [↭_i] ⟨≼_i⟩(a_1 ∧ \dots ∧ a_n) \iff a_i ∈ B_i(\mathbf{a}_{-i})$$ La fórmula simplemente despliega la definición de mejor respuesta. Es más fácil entenderla en el caso de 2 jugadores, pero la interpretación es exactamente igual para $N$ jugadores: $$(M_G, (a,b)) ⊩ [↭_1] ⟨≼_1⟩(a ∧ b) \iff a ∈ B_1(b)$$ En ese tipo de juegos, la acción $a$ del jugador 1 es (una de) su(s) mejor(es) respuesta(s) frente a la elección $b$ del jugador 2 si y sólo si, para todas las opciones de acción del jugador estando en $(a, b)$ (de ahí el uso de $[↭_1]$, alcanzando todos los perfiles de acción en los que el jugador 1 cambia su propia acción, pero la del jugador 2 sigue siendo la misma) el resultado para el jugador 1 es, como mucho (la parte $⟨≼_1⟩$), tan bueno como la jugada $(a,b)$ (la parte $a ∧ b$). Veamos un análisis más detallado de este resultado para el Dilema del Prisionero que hemos fornalizado antes: !!!Ejemplo:Dilema del Prisionero Consideremos de nuevo el juego del Dilema del Prisionero:  Comencemos por el jugador 1. Queremos encontrar el conjunto de mejores respuestas que tiene contra el jugador 2 cuando éste elige la acción $SS$, es decir, queremos encontrar $B_1(SS)$. Como el jugador 1 tiene dos opciones, $SS$ y $TP$, necesitamos evaluar dos fórmulas: una para cada opción y ver si son mejores respuestas o no: * $(M_D, (SS, SS)) ⊮ [↭_1] ⟨≼_1⟩(SS_2 ∧ SS_1)$ Para que la fórmula completa sea válida en $(SS, SS)$, la subfórmula $⟨≼_1⟩(SS_2 ∧ SS_1)$ debe ser válida en los dos mundos $↭_1$ alcanzables desde $(SS, SS)$, es decir, el propio $(SS, SS)$ y $(TP, SS)$. La subfórmula efectivamente se cumple en el primero (recordemos que $≼_1$ es reflexiva), pero falla en el segundo: desde $(TP, SS)$ no es posible $≼_1$-alcanzar un mundo en el que el jugador 2 elija la acción $SS$ y el jugador 1 elija la acción $SS$. Por tanto, $SS\notin B_1(SS)$. * $(M_D, (TP, SS)) ⊩ [↭_1] ⟨≼_1⟩(SS_2 ∧ TP_1)$ Para que la fórmula sea válida en $(TP, SS)$, la subfórmula $⟨≼_1⟩(SS_2 ∧ TP_1)$ debe ser válida en los dos mundos $↭_1$ alcanzables desde $(TP, SS)$, es decir, $(SS, SS)$ y $(TP, SS)$. La subfórmula se cumple en el primero, pues efectivamente desde $(SS, SS)$ es posible $≼_1$-alcanzar el mundo $(TP, SS)$ en el que $SS_2 ∧ TP_1$ es cierto. También se cumple en el segundo, por la reflexividad de $≼_1$. Por tanto, $TP\in B_1(SS)$. En consecuencia, $B_1(SS) = \{TP\}$. De manera análoga, se puede probar que $B_1(TP) = \{TP\}$. Por simetría del juego respecto a ambos jugadores, obtenemos que $B_2(TP) = B_2(SS) = \{TP\}$. # Mejorando la expresividad Acabamos de ver que la fórmula $[↭_i] ⟨≼_i⟩(a_1 ∧ \dots ∧ a_n)\in \mathcal{L}_{\{⟨↭_i⟩\}_{i∈N},\{⟨≼i⟩\}_{i∈N}}$ caracteriza el hecho de que la acción elegida por el jugador $i$ es una de sus mejores respuestas frente a la elección colectiva de los demás jugadores. Pero aún así, se puede argumentar que la fórmula no es completamente transparente, en el sentido de que no deja claro qué requiere una mejor respuesta. Se pueden encontrar fórmulas más _transparentes_ utilizando lenguajes más potentes. Aquí es donde las herramientas adicionales que hemos presentado en secciones anteriores pueden ser útiles. En primer lugar, utilizaremos el hecho de que, a partir de cada relación $≼_i$ del modelo, podemos definir su versión estricta $≺_i$ (como ya hicimos) y, a continuación, podemos incluir modalidades para cada una de estas nuevas relaciones $≺_i$. Por último, utilizaremos la operación de intersección $∩$ presentada anteriormente. !!!def:Definición En las condiciones anteriores (recordamos que $\mathbf{a}=(a_1, \dots , a_n)$ y $\mathbf{a}′=(a′_1, \dots , a′_n)$) $$(M_G, \mathbf{a}) ⊩ ⟨≺_i⟩ ϕ \iff \exists \mathbf{a}′\in A\ \Big(\mathbf{a} ≺_i \mathbf{a}′\ \wedge\ (M_G, \mathbf{a}′) ⊩ ϕ\Big)$$ Con todas estas herramientas (es decir, dentro del lenguaje $\mathcal{L}_{\{⟨↭_i⟩\}_{i∈N},\{⟨≼i⟩\}_{i∈N},∩}$), se puede encontrar una fórmula más transparente que caracteriza el hecho de que la acción elegida por el jugador $i$ es una de sus mejores respuestas frente a la elección colectiva de los demás jugadores. Lo veremos para el caso de 2 jugadores: !!!teorema:Teorema La fórmula $BR := [↭_1 ∩ ≺_1] ⊥$ satisface: $$(M_G, (a, b)) ⊩ [↭_1 ∩ ≺_1] ⊥ \iff a ∈ B_1(b)$$ !!!demo:Demostración Intuitivamente, es más fácil leer la versión dual equivalente: $$¬ ⟨↭_1 ∩ ≺_1⟩ ⊤$$ que dice que no hay ninguna elección de cambio para el jugador 1 en la que podría haber obtenido un resultado estrictamente mejor. !!!warn: Ejercicio Este ejercicio trata sobre el concepto de dominación. 1. Proporciona una fórmula en $\mathcal{L}_{⟨≺_1⟩,⟨≺_2⟩,⟨↭_1⟩,⟨↭_2⟩}$ que caracterice una estrategia estrictamente dominada para el jugador 1. Más concretamente, proporciona una fórmula, $SD(a′_1)$, en el lenguaje dado tal que, para cualquier juego de 2 jugadores $G$: $$(M_G, (a_1, a_2)) ⊩ SD(a′_1) \iff a_1 \text{ está estrictamente dominado por }a′_1$$ 2. Proporciona una fórmula en $\mathcal{L}_{⟨≼_1⟩,⟨≼_2⟩,⟨≺_1⟩,⟨≺_2⟩,⟨↭_1⟩,⟨↭_2⟩}$ que caracterice una estrategia débilmente dominada para el jugador 1. Más concretamente, proporciona una fórmula, $SD(a′_1)$, en el lenguaje dado tal que, para cualquier juego de 2 jugadores $G$: $$(M_G, (a_1, a_2)) ⊩ SD(a′_1) \iff a_1 \text{ está débilmente dominado por } a′_1$$ ara verificar y validar el comportamiento de sistemas multiagente, asegurando que los agentes interactúen de manera correcta y eficiente según las especificaciones dadas. Esto es crucial para el desarrollo de sistemas multiagente confiables y robustos en diversas áreas de aplicación.