Valor de Shapley con gran cantidad de jugadores.

Soy un novato en estadísticas completo, pero estoy buscando algunos consejos generales sobre soluciones alternativas si estoy tratando de calcular el valor de Shapley en juegos con muchos jugadores.

es decir, si tengo 20 jugadores, necesito ejecutar todas las combinaciones (¡n!) que es 2,432,902,008,176,640,000.

¿Existe un método sólido para resolver el problema tomando una muestra de las combinaciones? ¿Qué debo tener en cuenta para que los resultados del uso de una muestra sean lo más precisos posible?

$i$$i$$i$

$X_i$$i$$\mu_i$$i$$\mathbb{E} X_i = \mu_i$$X_i$$\bar{X}_i$$\mu_i$

$K$$0$$K$$m$$X_i$

$$\Pr[ | \bar{X}_i - \mu_i | \geq \epsilon ] \leq 2e^{-2m \epsilon^2 / K^2} .$$

Entonces, para cada , muestreamos permutaciones al azar y calculamos la contribución marginal promedio .$i$$m$$\bar{X}_i$

Por ejemplo, si y queremos una precisión de y una probabilidad de falla de , entonces necesitamos , entonces billones. Por lo tanto, necesitamos muestrear millones de permutaciones para "garantizar" una precisión de , excepto con una minúscula posibilidad de falla .$K=100$$\epsilon = 0.01$$2e^{-50}$$2m\epsilon^2/K^2 = 50$$m = 25K^2/\epsilon^2 = 2.5$$2.5$$0.01$$2e^{-50}$

Como se ha mencionado en los comentarios, hay grandes mejoras para muchos casos especiales.