La identificación de los equilibrios de Nash en amplia forma de juego

Question

Hay una forma sistemática de identificar todos (pura estrategia) los equilibrios de Nash (no sólo el subgame perfecto) en una amplia forma de juego? En el siguiente Participante v Residente ejemplo, hay tres NEs, dos de los cuales ($(DE,F),(OA F)$) no son subgame perfecto. Lo que he estado haciendo es convertir el extenso formulario de forma normal, y luego encontrar NEs allí. Mientras confiable, este método consume mucho tiempo, y se complica a medida que el número de acciones/jugadores aumenta. Por ejemplo, sospecho que sería mucho más fácil detectar NEs en una de cuatro jugadores extensa juego (cada uno con dos acción, dicen) que en su forma normal equivalente.

Me interesaría saber si hay algún procedimiento que podemos utilizar para encontrar puro NEs de una manera razonablemente sencilla extensa forma de juego.

Answer 1

Hasta donde yo sé, No.

Aunque no estoy seguro de por qué usted quiere encontrar no subgame perfecto equilibrios de Nash en una amplia forma de juego, estoy seguro de que usted necesita para convertir a la forma normal de hacerlo. Amplia forma de una secuencia de juego lleva más de información de forma normal, específicamente el que se mueve no existen dentro de la secuencia. En una forma normal de la representación de la secuencia de juego tienes que demostrar todo lo posible mover disponibles para todos los jugadores, incluso los movimientos que no existen. Así que, básicamente, al convertir un juego secuencial de gran forma a forma normal, se convierte en otro juego donde usted, a continuación, busque los equilibrios de Nash.

Si usted está haciendo una partida de dos jugadores, donde cada jugador recibe una mudanza, usted puede hacerlo en su cabeza sólo mirar el juego del árbol, pero si el juego es más complejo, tendría que hacerlo paso por paso, convirtiéndolo en una forma normal.

Answer 2

Me parece que el "algoritmo" de abajo muy útiles y fáciles de seguir. Funciona bien para el común de los dos jugadores extenso formulario de juegos (que no tome una página completa para dibujar). También funciona bien en juegos con más de dos jugadores y un nivel suficientemente simple estructura de información (por ejemplo, información perfecta).

La idea es que el primer conjetura de una estrategia para el primer jugador (jugador 1). A continuación nos encontramos con la mejor de las respuestas del jugador subsiguiente(s). Por último, hemos de comprobar si la inicialmente estaba considerando la estrategia para el jugador 1 es una mejor respuesta a los otros jugadores mejores respuestas (a ella). Si es así, tenemos un perfil de las condiciones mutuamente mejores estrategias de responder, por tanto, la NE; si no lo es, entonces no tenemos ninguna NE con la inicialmente supuesta estrategia del jugador 1.

---

Algoritmo para la búsqueda de NE en un 2-jugador extensa forma de juego

Para cada uno de jugador 1 es pura estrategia $s_1$, haga lo siguiente:

1. Encontrar el jugador 2 es la mejor respuesta(s) a $s_1$. Deje que el conjunto de la del jugador 2 mejores respuestas se $B_2(s_1)$
2. Por cada $s_2\en B_2(s_1)$,
   • Si $s_1$ es una mejor respuesta a los $s_2$, registro $(s_1,s_2)$ como NE
   • Si $s_1$ no es una mejor respuesta a los $s_2$, entonces no hay NE

---

Ejemplo con la entrada en el mercado de juego

El participante tiene cuatro pura estrategias: $\{DE,OA,SI,IA\}$.

• Considerar $DE$
  1. Residente de la mejor respuesta es de$F$ o $A$
  2. Participante mejores respuestas:
     • Si el residente desempeña $F$, $A$ es una mejor respuesta $\a$ $(DE,F)$ es NE
     • Si el residente desempeña $A$, $SI$ es la mejor respuesta $\a$ no NE
• Considerar $OA$
  1. Residente de la mejor respuesta es de$F$ o $A$
  2. Participante mejores respuestas:
     • Si el residente desempeña $F$, $OA$ es una mejor respuesta $\a$ $(OA F)$ es NE
     • Si el residente desempeña $A$, $SI$ es la mejor respuesta $\a$ no NE
• Considerar $SI$
  1. Residente de la mejor respuesta es $Una$
  2. Participante mejores respuestas a $A$ es $SI$ $\a$ $(SI,A)$ es NE
• Considerar $IA$
  1. Residente de la mejor respuesta es $Una$
  2. Participante mejores respuestas a $A$ es $SI$, no $IA$, $\a$ no NE

Por lo tanto, todos tres NEs se encuentran.

---

Para un ejemplo con un simple 3-juego de un jugador, ver mi respuesta en el MSE.

El mismo procedimiento también puede utilizarse para encontrar el perfecto equilibrio Bayesiano en amplia forma de juegos.