Juego potencial

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 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 ordinales o cardinales . En los juegos cardinales, la diferencia en las ganancias individuales de cada jugador al cambiar su estrategia, manteniendo todo lo demás constante, debe 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 deben 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 representan mediante una única 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 comprender estudiando 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.

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

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

• ${\displaystyle \Phi }$se denomina 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 el jugador${\displaystyle i}$cambia de acción${\displaystyle a'}$pasar a la acción${\displaystyle a''}$, el cambio en el potencial${\displaystyle \Phi }$equivale al cambio en la utilidad de ese jugador.

• ${\displaystyle \Phi }$Se denomina función potencial ponderada si existe un vector${\displaystyle w\in \mathbb {R} _{++}^{N}}$de tal manera que${\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${\displaystyle \Phi }$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 }$se denomina 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 en${\displaystyle \Phi }$es igual al signo del cambio en la utilidad del jugador, mientras que la magnitud del cambio puede ser diferente. Cada PF ponderado es un PF ordinal.

• ${\displaystyle \Phi }$se denomina 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 su utilidad aumenta, entonces su potencial también aumenta (pero lo contrario no es necesariamente cierto). Todo PF ordinal es un PF ordinal generalizado.

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

${\displaystyle \arg \max _{a_{i}\in A_{i}}u_{i}(a_{i},a_{-i})=\arg \max _{a_{i}\in A_{i}}\Phi (a_{i},a_{-i})}$. Es decir: para cada jugador i , maximizar la función de potencial común conduce al mismo resultado que maximizar su propia utilidad.

• ${\displaystyle \Phi }$se denomina función pseudopotencial ^{[ 3 ]} si ${\displaystyle \forall i\in N,\ \forall {a_{-i}\in A_{-i}}}$,

${\displaystyle \arg \max _{a_{i}\in A_{i}}u_{i}(a_{i},a_{-i})\supseteq \arg \max _{a_{i}\in A_{i}}\Phi (a_{i},a_{-i})}$. Es decir: para cada jugador i , maximizar la función de potencial común conduce a alguna respuesta óptima.

Tenga en cuenta que, si bien hay${\displaystyle N}$Con funciones de utilidad, una para cada jugador, solo existe una función potencial. Por lo tanto, desde la perspectiva 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 suelen converger (en cierto modo) a un equilibrio de Nash.

En un juego de dos jugadores y dos acciones con externalidades, las ganancias de cada jugador vienen dadas 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 derivada de elegir la misma acción. Las opciones de acción son +1 y −1 , como se muestra 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 se mueve de − 1 a +1, la diferencia de pago es Δ u ₁ = u ₁ (+1, a ₂ ) – u ₁ (–1, a ₂ ) = 2 b ₁ + 2 w a ₂ .

El cambio en el 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. Usando 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 son también 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)]}$

Los juegos de potencial exacto son equivalentes a los juegos de congestión : Rosenthal ^{[ 4 ]} demostró que todo juego de congestión tiene un potencial exacto; Monderer y Shapley ^{[ 1 ]} demostraron la dirección opuesta: todo juego con una función de potencial exacto es un juego de congestión .

La clase de juegos potenciales ordinales es mucho más grande. Fabrikant, Papadimitriou y Talwar ^{[ 5 ] : El teorema 6} demostró que, para cada problema en la clase de complejidad PLS (esencialmente, cada problema de búsqueda local), existe un juego potencial ordinal con un número polinomial de jugadores, tal que el conjunto de equilibrios de Nash puros es igual al conjunto de óptimos locales.

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 mediante un único jugador que cambia su estrategia a una estrategia que aumenta estrictamente su utilidad. Si un juego tiene una función potencial ordinal generalizada${\displaystyle \Phi }$, entonces${\displaystyle \Phi }$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 todo juego finito de potencial ordinal generalizado tiene la FIP. Lo contrario también es cierto: todo juego finito con FIP admite una función de potencial ordinal generalizado. ^{[ 6 ]} El estado final 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.

Una ruta de mejor respuesta es un caso especial de ruta de mejora, en la 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 ruta de mejor respuesta sea finita se denomina propiedad de mejor respuesta finita (FBRP) . La FBRP es más débil que la FIP, pero 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 para 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 (AD) . ^{[ 7 ]} Significa que, para cualquier vector de estrategia inicial, existe una trayectoria de mejor respuesta finita que comienza en ese vector. La aciclicidad débil no es suficiente para la existencia de una función potencial (ya que algunas trayectorias de mejora pueden ser cíclicas), pero sí lo es 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 estocástico distribuido, en el que en cada punto se elige un jugador al azar, y este jugador elige una mejor estrategia al azar. ^{[ 6 ]}

Dubey, Haimanko y Zapechelnyuk ^{[ 3 ] : Thm.1} prueban:

• Cualquier juego de sustitutos estratégicos débiles o complementos estratégicos con agregación es un juego pseudopotencial.
• Todo juego pseudopotencial tiene un equilibrio de Nash de estrategia pura.

Abraham Neyman ^{[ 8 ]} estudió juegos potenciales en los que (a) el potencial es una función suave y cóncava , (b) los conjuntos de estrategias son convexos, (c) las utilidades están acotadas. Demuestra que, en tales juegos, cualquier equilibrio correlacionado es una mezcla de perfiles de estrategias puras que maximizan el potencial.

Si, además, (d) los conjuntos de estrategias son compactos, (e) el potencial es una función estrictamente cóncava, entonces el equilibrio correlacionado es único.

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

• Apuntes de 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 rosquillas y el archipiélago del duopolio , Surfing Economics .