Juego potencial

Clase de juego en la teoría de juegos

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 puede expresarse mediante una única función global denominada 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 ordinales o cardinales . En los juegos cardinales, la diferencia en los pagos individuales que obtiene cada jugador al cambiar individualmente su estrategia, en igualdad de condiciones, tiene que tener el mismo valor que la diferencia en los valores de la función potencial. En los juegos ordinales, solo 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 al localizar 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 comprender mediante el estudio de la función potencial.

Los juegos potenciales pueden estudiarse como juegos repetidos con estado de modo que cada ronda jugada tiene 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 distribuida de recursos, 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 acciones 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 en es igual al cambio en la utilidad del jugador multiplicado por un peso específico positivo del jugador. Cada factor de potencia exacto es un factor de potencia ponderado con w _i = 1 para todos los 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 ser diferente. Cada factor de potencia ponderado es un factor de potencia 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 opuesto no es necesariamente cierto). Todo factor de potencia ordinal es un factor de potencia 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 está la mejor acción para el jugador dado ? ${\displaystyle b_{i}(a_{-i})}$ ${\displaystyle i}$ ${\displaystyle a_{-i}}$

Obsérvese que, si bien existen funciones de utilidad, una para cada jugador, solo hay una función potencial. Por lo tanto, 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 algún sentido) hacia un equilibrio de Nash. ${\displaystyle N}$

Un ejemplo sencillo

En un juego de 2 jugadores y 2 acciones con externalidades, los pagos de cada jugador 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 del jugador i, a _j es la acción del oponente y w es una externalidad positiva por 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 a ₂ ) = 2 b ₁ + 2 w a ₂ = Δ u ₁ .

La solución para el jugador 2 es equivalente. Utilizando los 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ásticamente 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 la dirección opuesta: cada juego con una función de potencial exacta es un juego de congestión .

Juegos potenciales y caminos de mejora

Una ruta de mejora (también llamada dinámica de Nash ) es una secuencia de vectores de estrategia, en la que cada vector se obtiene a partir del vector anterior por un solo jugador que 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 cada ruta de mejora debe ser finita. Esta propiedad se llama propiedad de mejora finita (FIP) . Acabamos de demostrar que cada juego finito de potencial ordinal generalizado tiene la FIP. Lo opuesto también es cierto: cada juego finito tiene la FIP tiene una función de potencial ordinal generalizado. ^{[4] [ aclaración necesaria ]} El estado terminal en cada ruta de mejora finita es un equilibrio de Nash, por lo que la 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 solo 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 a partir del vector anterior mediante un único jugador que cambia su estrategia a una estrategia de mejor respuesta. La propiedad de que cada camino de mejor respuesta es finito se denomina propiedad de mejor respuesta finita (FBRP) . La FBRP es más débil que la 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 la FIP, ya que tienen que calcular una mejor respuesta.

Una propiedad aún más débil es la aciclicidad débil (WA) . ^[5] Esto significa que, para cualquier vector de estrategia inicial, existe un camino finito 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 algunos caminos de mejora pueden ser cíclicos), pero es suficiente para la existencia de un equilibrio de Nash de estrategia pura. Esto implica que un equilibrio de Nash puede calcularse casi con seguridad mediante un proceso distribuido estocástico, en el que en cada punto se elige un jugador al azar, y este jugador elige una mejor estrategia al azar. ^[4]

Véase también

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

Referencias

1. Monderer, Dov; Shapley, Lloyd (1996). "Juegos potenciales". Juegos y comportamiento económico . 14 : 124–143. doi :10.1006/game.1996.0044.
2. Marden, J., (2012) Juegos de potencial 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 (1996-03-01). "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/game.1996.0027. ISSN  0899-8256.
5. Young, H. Peyton (1993). "La evolución de las convenciones". Econometrica . 61 (1): 57–84. doi :10.2307/2951778. ISSN  0012-9682. JSTOR  2951778.
6. Voorneveld, Mark; Norde, Henk (1997-05-01). "Una caracterización de los juegos de potencial ordinal". Juegos y comportamiento económico . 19 (2): 235–242. doi :10.1006/game.1997.0554. ISSN  0899-8256. S2CID  122795041.

Enlaces externos

• Notas de la clase 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 sobre la inevitabilidad de la colusión Capítulo 8, El mundo de las donas y el archipiélago del duopolio, Surfing Economics.