Juego potencial

Game class in game theory

En teoría de juegos , se dice que un juego es un juego potencial si el incentivo de todos los jugadores para cambiar su estrategia se puede expresar utilizando una única función global llamada función potencial . El concepto se originó en un artículo de 1996 de Dov Monderer y Lloyd Shapley . ^[1]

Desde entonces se han estudiado las propiedades de varios tipos de juegos potenciales. Los juegos pueden ser juegos potenciales ordinales o cardinales . En los juegos cardinales, la diferencia en los pagos individuales para cada jugador al cambiar individualmente su estrategia, en igualdad de condiciones, tiene que tener el mismo valor que la diferencia de valores para la función potencial. En los juegos ordinales sólo los signos de las diferencias tienen que ser iguales.

La función potencial es una herramienta útil para analizar las propiedades de equilibrio de los juegos, ya que los incentivos de todos los jugadores se asignan a una función y el conjunto de equilibrios de Nash puros se puede encontrar localizando los óptimos locales de la función potencial. La convergencia y la convergencia en tiempo finito de un juego iterado hacia un equilibrio de Nash también se pueden entender estudiando la función potencial.

Los juegos potenciales pueden estudiarse como juegos repetidos con estado, de modo que cada ronda jugada tenga una consecuencia directa en el estado del juego en la siguiente ronda. ^[2] Este enfoque tiene aplicaciones en el control distribuido, como la asignación de recursos distribuidos, donde los jugadores sin un mecanismo de correlación central pueden cooperar para lograr una distribución de recursos globalmente óptima.

Definición

Sea el número de jugadores, el conjunto de perfiles de acción sobre los conjuntos de acción de cada jugador y la función de pago para el jugador . ${\displaystyle N}$ ${\displaystyle A}$ ${\displaystyle A_{i}}$ ${\displaystyle u_{i}:A\to \mathbb {R} }$ ${\displaystyle 1\leq i\leq N}$

Dado un juego , decimos que es un juego potencial con una función potencial exacta (ponderada, ordinal, ordinal generalizada, mejor respuesta) si es una función potencial exacta (ponderada, ordinal, ordinal generalizada, mejor respuesta, respectivamente) para . Aquí se llama ${\displaystyle G=(N,A=A_{1}\times \ldots \times A_{N},u:A\rightarrow \mathbb {R} ^{N})}$ ${\displaystyle G}$ ${\displaystyle \Phi :A\rightarrow \mathbb {R} }$ ${\displaystyle G}$ ${\displaystyle \Phi }$

• una función potencial exacta si , ${\displaystyle \forall i,\forall {a_{-i}\in A_{-i}},\ \forall {a'_{i},\ a''_{i}\in A_{i}}}$

${\displaystyle \Phi (a'_{i},a_{-i})-\Phi (a''_{i},a_{-i})=u_{i}(a'_{i},a_{-i})-u_{i}(a''_{i},a_{-i})}$

Es decir: cuando un jugador cambia de una acción a otra , el cambio en el potencial es igual al cambio en la utilidad de ese jugador. ${\displaystyle i}$ ${\displaystyle a'}$ ${\displaystyle a''}$ ${\displaystyle \Phi }$

• una función potencial ponderada si existe un vector tal que , ${\displaystyle w\in \mathbb {R} _{++}^{N}}$ ${\displaystyle \forall i,\forall {a_{-i}\in A_{-i}},\ \forall {a'_{i},\ a''_{i}\in A_{i}}}$

${\displaystyle \Phi (a'_{i},a_{-i})-\Phi (a''_{i},a_{-i})=w_{i}(u_{i}(a'_{i},a_{-i})-u_{i}(a''_{i},a_{-i}))}$Es decir: cuando un jugador cambia de acción, el cambio es igual al cambio en la utilidad del jugador, multiplicado por un peso positivo específico del jugador. Cada PF exacto es un PF ponderado con w _i = 1 para todo i . ${\displaystyle \Phi }$

• una función potencial ordinal si , ${\displaystyle \forall i,\forall {a_{-i}\in A_{-i}},\ \forall {a'_{i},\ a''_{i}\in A_{i}}}$

${\displaystyle u_{i}(a'_{i},a_{-i})-u_{i}(a''_{i},a_{-i})>0\Leftrightarrow \Phi (a'_{i},a_{-i})-\Phi (a''_{i},a_{-i})>0}$Es decir: cuando un jugador cambia de acción, el signo del cambio es igual al signo del cambio en la utilidad del jugador, mientras que la magnitud del cambio puede diferir. Cada PF ponderado es un PF ordinal. ${\displaystyle \Phi }$

• una función potencial ordinal generalizada si , ${\displaystyle \forall i,\forall {a_{-i}\in A_{-i}},\ \forall {a'_{i},\ a''_{i}\in A_{i}}}$

${\displaystyle u_{i}(a'_{i},a_{-i})-u_{i}(a''_{i},a_{-i})>0\Rightarrow \Phi (a'_{i},a_{-i})-\Phi (a''_{i},a_{-i})>0}$Es decir: cuando un jugador cambia de acción, si la utilidad del jugador aumenta, entonces el potencial aumenta (pero lo contrario no es necesariamente cierto). Cada PF ordinal es un PF ordinal generalizado.

• una función potencial de mejor respuesta si , ${\displaystyle \forall i\in N,\ \forall {a_{-i}\in A_{-i}}}$

${\displaystyle b_{i}(a_{-i})=\arg \max _{a_{i}\in A_{i}}\Phi (a_{i},a_{-i})}$¿Dónde se da la mejor acción para el jugador ? ${\displaystyle b_{i}(a_{-i})}$ ${\displaystyle i}$ ${\displaystyle a_{-i}}$

Tenga en cuenta que si bien existen funciones de utilidad, una para cada jugador, solo hay una función potencial. Así, a través de la lente de las funciones potenciales, los jugadores se vuelven intercambiables (en el sentido de una de las definiciones anteriores). Debido a esta simetría del juego, los algoritmos descentralizados basados ​​en la función potencial compartida a menudo conducen a la convergencia (en cierto sentido) a un equilibrio de Nash. ${\displaystyle N}$

Un ejemplo sencillo

En un juego de 2 jugadores y 2 acciones con externalidades, los pagos de los jugadores individuales están dados por la función u _i ( a _i , a _j ) = b _i a _i + w a _i a _j , donde a _i es la acción de los jugadores i , a _j es la acción del oponente y w es una externalidad positiva al elegir la misma acción. Las opciones de acción son +1 y −1, como se ve en la matriz de pagos de la Figura 1.

Este juego tiene una función potencial P( a ₁ , a ₂ ) = b ₁ a ₁ + b ₂ a ₂ + w a ₁ a ₂ .

Si el jugador 1 pasa de −1 a +1, la diferencia de pago es Δ u ₁ = u ₁ (+1, a ₂ ) – u ₁ (–1, a ₂ ) = 2 b ₁ + 2 w a ₂ .

El cambio de potencial es ΔP = P(+1, a ₂ ) – P(–1, a ₂ ) = ( b ₁ + b ₂ a ₂ + w a ₂ ) – (– b ₁ + b ₂ a ₂ – w una ₂ ) = 2 segundo ₁ + 2 w una ₂ = Δ tu ₁ .

La solución para el jugador 2 es equivalente. Usando valores numéricos b ₁  = 2 , b ₂  = −1 , w  = 3 , este ejemplo se transforma en una simple batalla de sexos , como se muestra en la Figura 2. El juego tiene dos equilibrios de Nash puros, (+1, +1) y (-1, -1) . Estos también son los máximos locales de la función potencial (Figura 3). El único equilibrio estocástico estable es (+1, +1) , el máximo global de la función potencial.

Un juego de 2 jugadores y 2 acciones no puede ser un juego potencial a menos que

${\displaystyle [u_{1}(+1,-1)+u_{1}(-1,+1)]-[u_{1}(+1,+1)+u_{1}(-1,-1)]=[u_{2}(+1,-1)+u_{2}(-1,+1)]-[u_{2}(+1,+1)+u_{2}(-1,-1)]}$

Juegos potenciales y juegos de congestión.

Los juegos de potencial exacto son equivalentes a los juegos de congestión : Rosenthal ^[3] demostró que cada juego de congestión tiene un potencial exacto; Monderer y Shapley ^[1] demostraron lo contrario: todo juego con una función potencial exacta es un juego de congestión .

Posibles juegos y caminos de mejora.

Un camino de mejora (también llamado dinámica de Nash ) es una secuencia de vectores de estrategia, en la que cada vector se obtiene del vector anterior cuando un solo jugador cambia su estrategia a una estrategia que aumenta estrictamente su utilidad. Si un juego tiene una función de potencial ordinal generalizado , entonces es estrictamente creciente en cada ruta de mejora, por lo que cada ruta de mejora es acíclica. Si, además, el juego tiene un número finito de estrategias, entonces todo camino de mejora debe ser finito. Esta propiedad se llama propiedad de mejora finita (FIP) . Acabamos de demostrar que todo juego finito de potencial ordinal generalizado tiene el FIP. Lo contrario también es cierto: cada juego finito tiene el FIP con una función de potencial ordinal generalizado. ^{[4] [ se necesita aclaración ]} El estado terminal en cada camino de mejora finito es un equilibrio de Nash, por lo que FIP implica la existencia de un equilibrio de Nash de estrategia pura. Además, implica que un equilibrio de Nash puede calcularse mediante un proceso distribuido, en el que cada agente sólo tiene que mejorar su propia estrategia. ${\displaystyle \Phi }$ ${\displaystyle \Phi }$

Un camino de mejor respuesta es un caso especial de un camino de mejora, en el que cada vector se obtiene del vector anterior cuando un solo jugador cambia su estrategia a una estrategia de mejor respuesta. La propiedad de que cada camino de mejor respuesta es finito se llama propiedad de mejor respuesta finita (FBRP) . El FBRP es más débil que el FIP y aún implica la existencia de un equilibrio de Nash de estrategia pura. También implica que un equilibrio de Nash puede calcularse mediante un proceso distribuido, pero la carga computacional de los agentes es mayor que con FIP, ya que tienen que calcular una mejor respuesta.

Una propiedad aún más débil es la aciclicidad débil (WA) . ^[5] Significa que, para cualquier vector de estrategia inicial, existe una ruta finita de mejor respuesta que comienza en ese vector. La aciclicidad débil no es suficiente para la existencia de una función potencial (ya que algunas rutas de mejora pueden ser cíclicas), pero sí es suficiente para la existencia de un equilibrio de Nash de estrategia pura. Implica que un equilibrio de Nash puede calcularse casi con seguridad mediante un proceso estocástico distribuido, en el que en cada punto, se elige un jugador al azar, y este jugador elige al azar la mejor estrategia. ^[4]

Ver también

• juego de congestión
• Econofísica
• Una caracterización de juegos potenciales ordinales. ^[6]

Referencias

1. Monderer, Dov; Shapley, Lloyd (1996). "Juegos potenciales". Juegos y comportamiento económico . 14 : 124-143. doi : 10.1006/juego.1996.0044.
2. Marden, J., (2012) Juegos potenciales basados ​​en el estado http://ecee.colorado.edu/marden/files/state-based-games.pdf
3. Rosenthal, Robert W. (1973), "Una clase de juegos que poseen equilibrios de Nash de estrategia pura", International Journal of Game Theory , 2 : 65–67, doi :10.1007/BF01737559, MR  0319584, S2CID  121904640.
4. Milchtaich, Igal (1 de marzo de 1996). "Juegos de congestión con funciones de pago específicas para el jugador". Juegos y comportamiento económico . 13 (1): 111-124. doi : 10.1006/juego.1996.0027. ISSN  0899-8256.
5. Joven, H. Peyton (1993). "La evolución de las convenciones". Econométrica . 61 (1): 57–84. doi :10.2307/2951778. ISSN  0012-9682. JSTOR  2951778.
6. Voorneveld, Mark; Norde, Henk (1 de mayo de 1997). "Una caracterización de los juegos de potenciales ordinales". Juegos y comportamiento económico . 19 (2): 235–242. doi : 10.1006/juego.1997.0554. ISSN  0899-8256. S2CID  122795041.

enlaces externos

• Apuntes de conferencias de Yishay Mansour sobre juegos de potencial y congestión
• Sección 19 en: Vazirani, Vijay V .; Nisán, Noam ; Jardín rugoso, Tim ; Tardos, Éva (2007). Teoría algorítmica de juegos (PDF) . Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-87282-0.
• Exposición no técnica de Huw Dixon de la inevitabilidad de la colusión Capítulo 8, El mundo Donut y el archipiélago del duopolio, Surfing Economics.