Cálculo de equilibrios de Nash de estrategia pura en juegos finitos

Question

Estoy intentando calcular los equilibrios de Nash (de estrategia pura) de algunas subastas discretas.

En concreto, definamos la estrategia de cada jugador como una función que relaciona todas las valoraciones que pueda tener con su oferta (es decir, la "función de oferta"). Supongamos que la valoración de cada jugador se extrae de un conjunto finito y que su oferta debe pertenecer a este mismo conjunto (finito). Me interesa encontrar el conjunto de funciones de oferta, una para cada jugador, de manera que la función de oferta de cada jugador sea óptima dadas las funciones de oferta de todos los demás jugadores.

Si facilita las cosas, podemos suponer que las valoraciones son simétricas (es decir, que la valoración de cada jugador está generada por la misma distribución de probabilidad) y que sólo hay dos jugadores. Sin embargo, lo ideal sería proceder sin estas simplificaciones. Me interesa calcular el equilibrio para las subastas de primer precio cerrado y de todo pago (en esta última, se paga la puja aunque se pierda; en la primera, no).

He considerado la posibilidad de escribir el juego de subasta discreta en forma normal y encontrar los equilibrios utilizando un software como Gambit. Sin embargo, esto parece complicado, ya que el espacio de estrategias es muy grande. Por ejemplo, si un jugador elige ofertas de $ \{1,...,10\} $ y extrae los valores de $ \{1,...,10\} $ entonces ya tienen $10^{10}$ estrategias puras.

¿Alguien tiene alguna idea sobre cómo proceder en este caso?

Answer 1

Si $10^{10}$ Las estrategias puras son demasiado grandes para Gambit, probablemente también lo serán para cualquier otro software. En los comentarios, he sugerido que primero se calculen los pagos esperados de cada jugador en un programa separado, como Matlab/R/Excel, y luego se exporte la matriz resultante a Gambit, donde se pueden calcular los BNE. De esta manera, puede ahorrar algunos recursos para Gambit en la conversión del juego en su forma normal bayesiana.

Si te parece bien significativamente reduciendo la dimensión de su problema, entonces puede confiar únicamente en Gambit (o, Explorador de la Teoría del Juego (GTE) que ahora forma parte del proyecto Gambit). En el siguiente ejemplo realizado en GTE, he supuesto que el licitador $i$ Los espacios de valoración y estrategia de la empresa son binarios: $V_i=S_i=\{0,1\}$ para $i=1,2$ . Se supone que los valores están distribuidos uniformemente.

En primer lugar, se entra en el juego en su forma extensa. En la figura siguiente, las cuatro ramas de la parte superior corresponden a las elecciones de la Naturaleza que determinan las valoraciones. De izquierda a derecha, las ramas representan los perfiles de valoración $(v_1,v_2)=(0,0)$ , $(0,1)$ , $(1,0)$ , $(1,1)$ respectivamente, cada una de las cuales ocurre con probabilidad $1/4$ .

Cuando termine de introducir el juego de forma extensiva, pulse la pestaña "Disposición de la matriz" para ver la forma normal bayesiana (calculada automáticamente). Hay un botón de engranaje en la parte superior que calculará la BNE del juego.

El resultado es el siguiente. En este caso, el resultado fue devuelto en segundos (en parte gracias a la dimensión relativamente pequeña del problema). Se encontró el único BNE, en el que cada jugador puja cero independientemente de su valor.

Por supuesto, puede intentar aumentar el tamaño del espacio de valor/estrategia. Este método también le permitiría especificar distribuciones asimétricas de los valores de los postores. Sin embargo, GTE sólo resuelve partidas de dos jugadores. Pero Gambit parece ser capaz de resolver partidas con más de dos jugadores.