Juego potencial - Potential game

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 .

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 de cambiar individualmente la estrategia de uno, en igualdad de condiciones, debe tener el mismo valor que la diferencia de valores para 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 mapean en 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 pueden entenderse mediante el estudio de la función potencial.

Los juegos potenciales se pueden estudiar como juegos repetidos con estado de modo que cada ronda jugada tenga una consecuencia directa sobre el estado del juego en la siguiente ronda. 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 óptima a nivel mundial.

Definición

Definiremos alguna notación requerida para la 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 sea ​​la función de pago. ${\ Displaystyle N}$${\ Displaystyle A}$${\ Displaystyle A_ {i}}$${\ Displaystyle u}$

Un juego es: ${\ Displaystyle G = (N, A = A_ {1} \ times \ ldots \ times A_ {N}, u: A \ rightarrow \ mathbb {R} ^ {N})}$

• un juego potencial exacto si hay una función tal que ,${\ Displaystyle \ Phi: A \ rightarrow \ mathbb {R}}$${\ 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 pasa 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 ''}$

• un juego potencial ponderado si hay una función y un vector tal que ,${\ Displaystyle \ Phi: A \ rightarrow \ mathbb {R}}$${\ 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}))}$

• un juego potencial ordinal si hay una función tal que ,${\ Displaystyle \ Phi: A \ rightarrow \ mathbb {R}}$${\ 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}$

• un juego potencial ordinal generalizado si hay una función tal que ,${\ Displaystyle \ Phi: A \ rightarrow \ mathbb {R}}$${\ 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 \ Flecha derecha \ Phi (a' _ {i}, a _ {- i}) - \ Phi (a '' _ {i}, a _ {- i})> 0}$

• un potencial de juego de mejor respuesta si hay una función tal que ,${\ Displaystyle \ Phi: A \ rightarrow \ mathbb {R}}$${\ 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})}$

donde es la mejor acción para el jugador dada . ${\ Displaystyle b_ {i} (a _ {- i})}$${\ Displaystyle i}$${\ Displaystyle a _ {- i}}$

Un simple ejemplo

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 de 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 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 de potencial es ΔP = P (+1, a ₂ ) - P (–1, a ₂ ) = ( b ₁ + b ₂ a ₂ + w a ₂ ) - (- b ₁ + b ₂ a ₂ - w un ₂ ) = 2 b ₁ + 2 w un ₂ = Δ u ₁ .

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ásticamente estable es (+1, +1) , el máximo global de la función potencial.

+1 –1 +1 + b 1 + w , + b 2 + w + b 1 - w , - b 2 - w –1 - b 1 - w , + b 2 - w - b 1 + w , - b 2 + w Fig.1: Ejemplo de juego potencial

+1 –1 +1 5, 2 –1, –2 –1 –5, –4 1, 4 Fig.2: Batalla de sexos (recompensas)

+1 –1 +1 4 0 –1 –6 2 Fig.3: Batalla de sexos (potenciales)

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)]}$

Ver también

• Juego de congestión
• Econofísica

Referencias

enlaces externos

• Notas de la conferencia de Yishay Mansour sobre juegos de potencial y congestión
• Sección 19 en: Vazirani, Vijay V .; Nisan, Noam ; Roughgarden, 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, Donut world and the duopololy archipiélago , Surfing Economics .