Cómo calcular TODOS los equilibrios de Nash en un ejemplo de matriz de 3x3

Question

Estoy tratando de entender cómo calcular todos los equilibrios de Nash en un juego de 2 jugadores, pero fracaso cuando hay más de 2 opciones posibles para jugar. ¿Podría alguien explicarme cómo calcular una matriz como esta (sin ordenador) \begin {matriz} 1,1 & 10,0 & -10,1 \\ 0,10 & 1,1 & 10,1 \\ 1,-10 & 1,10 & 1,1 \end {matriz}

Lo he intentado con el concepto de apoyo, pero no lo consigo...

Answer 1

Un equilibrio de Nash es un perfil de estrategias $(s_1,s_2)$ tal que las estrategias son las mejores respuestas entre sí, es decir, ningún jugador puede hacerlo estrictamente mejor desviándose. Esto nos ayuda a encontrar los equilibrios de Nash (de estrategia pura).

Para empezar, encontramos la mejor respuesta para el jugador 1 para cada una de las estrategias que el jugador 2 puede jugar. Lo demostraré subrayando las mejores respuestas: \begin {matriz} & A &B&C \\ A& \underline {1},1 & \underline {10},0 & -10,1 \\ B&0,10 & 1,1 & \underline {10},1 \\ C& \underline {1},-10 & 1,10 & 1,1 \end {matriz} El jugador 1 es el jugador de la fila, el jugador 2 es el jugador de la columna. Si 2 juega la columna A, la mejor respuesta del jugador 2 es jugar la fila $A$ o $C$ que le da 1 en lugar de 0 como recompensa. Del mismo modo, la mejor respuesta a la columna $B$ es la fila $A$ y a la columna $C$ es la fila $B$ .

Ahora hacemos lo mismo para el jugador 2 subrayando las mejores respuestas del jugador de la columna: \begin {matriz} & A &B&C \\ A& \underline {1}, \underline {1} & \underline {10},0 & -10, \underline {1} \\ B&0, \underline {10} & 1,1 & \underline {10},1 \\ C& \underline {1},-10 & 1, \underline {10} & 1,1 \end {matriz} Así, si el jugador 1 juega la fila $A$ entonces el jugador 2 responde mejor con la columna $A$ o columna $C$ , dándole 1 en lugar de 0. También encontramos las mejores respuestas para la fila $B$ y $C$ .

Ahora bien, un equilibrio de Nash de estrategia pura es una casilla en la que ambos pagos están subrayados, es decir, en la que ambas estrategias son las mejores respuestas entre sí. En el ejemplo, el único equilibrio de estrategia pura es $(A,A)$ . En todas las demás casillas, al menos uno de los jugadores tiene un incentivo para desviarse (porque le da una mayor recompensa).

EDITAR : ¿Cómo calcular los equilibrios de estrategias mixtas en juegos discretos?

En un equilibrio de estrategia Nash mixta, cada uno de los jugadores debe ser indiferente entre cualquiera de las estrategias puras jugadas con probabilidad positiva. Si este no fuera el caso, entonces hay una desviación rentable (jugar la estrategia pura con mayor retribución con mayor probabilidad).

Consideremos al jugador 2. Juega con la columna $A$ con probabilidad $p$ , $B$ con probabilidad $q$ y $C$ con probabilidad $1-p-q$ . Tenemos que encontrar $p,q$ tal que el jugador 1 es indiferente entre sus estrategias puras $A,B,C$ . Es indiferente entre la fila $A$ (lado izquierdo) y la fila $B$ (lado derecho) si $p,q$ son tales que $$p+10q-10(1-q-p)=q+10(1-p-q).$$ Es indiferente entre $B$ y $C$ si $$q+10(1-p-q)=p+q+1-q-p=1.$$ Sólo hay que resolver la primera condición para $q$ en función de $p$ , sustituto $q$ en la segunda condición y tienes $p$ . Inserción de $p$ de nuevo en la primera te da $q$ .

Ahora hacemos lo mismo con las estrategias para el jugador 1 tal que el jugador 2 es indiferente. El jugador 1 juega $A$ con probabilidad $x$ , $B$ con probabilidad $y$ y $C$ con probabilidad $1-x-y$ . Las dos condiciones que siguen son \begin {ecuación} 1x+10y-10(1-x-y)=x+10(1-x-y) \\ x+10(1-x-y)=1 \end {Ecuación} Resuelve esto de nuevo para encontrar $x,y$ . Este es un equilibrio de estrategia mixta, porque ninguno de los dos jugadores tiene una desviación rentable. Recordemos que hemos construido el perfil $(x,y;p,q)$ tal que el otro jugador es indiferente entre sus estrategias puras. Por lo tanto, no importa cómo se desvíe unilateralmente el otro jugador, su recompensa esperada será idéntica a la del equilibrio $(x,y;p,q)$ . En general, según las soluciones $x,y,p,q$ puede haber infinitos equilibrios de Nash, o ninguno. Cuantas más estrategias puras haya, más tedioso será calcular los equilibrios de estrategia mixta, ya que resolvemos para $N-1$ variables para cada jugador ( $N$ siendo el número de estrategias puras del otro jugador).

Answer 2

Creo que por fin he entendido cómo obtener todos los equilibrios por el concepto de soporte.

Dada la matriz de pagos A para el jugador 1 y B para el jugador 2. Que un punto $(x,y)=(x_1,x_2,x_3,y_1,y_2,y_3)$ es un equilibrio de Nash con supp $x =I$ y apoyar $y =J$ (lo que significa que $x_i>0$ para $i \in I$ y $x_i=0$ para $i \not\in I$ ) equivale a

$1) \forall i,k \in I : (Ay)_i = (Ay)_k \\ 2) \forall i \in I,\forall k \not\in I : (Ay)_k ≤ (Ay)_i \\ 3) \forall j,l \in J : (Bx)_j = (Bx)_l \\ 4) \forall j \in J,\forall l \not\in J : (Bx)_l ≤ (Bx)_j$

Así que para obtener todos los equilibrios de Nash, tengo que comprobar todas las combinaciones de soporte que son posibles, si todas las igualdades y desigualdades se mantienen. En caso afirmativo, las ecuaciones dicen para qué puntos o intervalos hay equilibrios de Nash. En el ejemplo anterior las ecuaciones de Nameless son las ecuaciones para el caso $I=\{1,2,3\}=J$ . En total hay que comprobar 49 sistemas de ecuaciones, lo que supone mucho trabajo...

Gracias por tu respuesta Nameless, me ha ayudado mucho a entender el principio fundamental.

Answer 3

@user106371. Tu respuesta es exactamente cierta. Asignar probabilidades a cada estrategia y resolver el sistema de ecuaciones no es una solución completa, sólo un caso. Con el fin de calcular el número de sistemas de ecuaciones deben ser resueltos, puede utilizar la siguiente fórmula:

$$\sum_{k=1}^m \sum_{p=1}^n \binom{m}{k} \binom{n}{p}$$

donde $m$ y $n$ son el número de estrategias de los jugadores.