Hay siempre un puro equilibrio de Nash en una selección de recursos de juego?

Question

Denotar $[r]\triangleq\{1,2,\ldots,r\}$.

Considere la posibilidad de un juego con $n$ los jugadores, $[n]$, cada uno tiene $m$ estrategias, $[m]$.

Cada jugador $i$ tiene asociada una función de la rentabilidad, la cual considera sólo su estrategia seleccionada, y el número de jugadores seleccionados de la misma estrategia: $$U_i:[m]\times[n]\a[0,1]$$

Además, la función de utilidad es monótonamente decreciente en el número de jugadores que eligió la misma estrategia, es decir, $$\forall i\in[n],j\in[m],k\in[n-1]:U_i(j,k)\geq U_i(j,k+1)$$

¿Este juego tiene siempre un puro equilibrio de Nash?

Podemos (computacionalmente) se encuentran de manera eficiente?

---

Observe que el caso especial, donde todos los jugadores son simétricas ($\forall (i,j\in[n]: U_i\equiv U_j\equiv U$), el juego se reduce a un potencial exacta juego y por lo tanto está garantizado para tener un puro equilibrio de Nash.

La función potencial para el simétrica caso sería, dada una estrategia perfil de $s$: $$\phi(s) = \sum_{j\in[m]}\sum_{k=1}^{\#_j(s)} U(j,k)$$

Donde $\#_j(s)$ es el número de jugadores en $s$ estrategia de juego $j$.

Answer 1

Sí, siempre hay un puro equilibrio de Nash. Ver:

Yo Milchtaich (1996). La congestión de los juegos con reproductor específico de la rentabilidad de las funciones. Los juegos y el comportamiento económico 13 (1), 111-124.

Usted está interesado en el caso especial de singleton congestión de juegos con reproductor específico de la rentabilidad de las funciones.

Y sí, puede ser calculado en tiempo polinomio. Ver Corolario 7 en:

Heiner Ackermann, Heiko Röglin, Berthold Vöcking (2009). Puro equilibrios de Nash en jugador específico y ponderado de la congestión de los juegos. La Informática Teórica 410 (17), 1552-1563.