Juego de congestión - Congestion game

Los juegos de congestión son una clase de juegos en teoría de juegos propuestos por primera vez por el economista estadounidense Robert W. Rosenthal en 1973. En un juego de congestión, la recompensa de cada jugador depende de los recursos que elija y del número de jugadores que elijan el mismo recurso. Los juegos de congestión son un caso especial de juegos potenciales . Rosenthal demostró que cualquier juego de congestión es un juego potencial y Monderer y Shapley (1996) demostraron lo contrario: para cualquier juego potencial, existe un juego de congestión con la misma función potencial.

Motivación

Considere una red de tráfico donde dos jugadores se originan en un punto y necesitan llegar al punto . Supongamos que el nodo está conectado al nodo a través de puntos de conexión y dónde está un poco más cerca de ( es decir, es más probable que lo elija cada jugador). Sin embargo, ambos puntos de conexión se congestionan fácilmente, lo que significa que cuanto más jugadores pasan por un punto, mayor es la demora de cada jugador, por lo que hacer que ambos jugadores pasen por el mismo punto de conexión provoca una demora adicional. Un buen resultado en este juego será que los dos jugadores se "coordinen" y pasen por diferentes puntos de conexión. ¿Se puede lograr tal resultado? Y si es así, ¿cuál será el costo para cada jugador? ${\ Displaystyle O}$${\ Displaystyle T}$${\ Displaystyle O}$${\ Displaystyle T}$${\ Displaystyle A}$${\ Displaystyle B}$${\ Displaystyle A}$${\ Displaystyle B}$${\ Displaystyle A}$

Definición

Los juegos de congestión discreta son juegos con los siguientes componentes.

• Un conjunto básico de elementos congestionables ; ${\ Displaystyle E}$
• ${\ Displaystyle n}$ jugadores;
• Un conjunto finito de estrategias para cada jugador, donde cada estrategia es un subconjunto de ; ${\ Displaystyle S_ {i}}$${\ Displaystyle P \ en S_ {i}}$${\ Displaystyle E}$
• Para cada elemento y un vector de estrategias , una carga ; ${\ Displaystyle e}$${\ Displaystyle (P_ {1}, P_ {2}, \ ldots, P_ {n})}$${\ Displaystyle x_ {e} = \ # \ {i: e \ in P_ {i} \}}$
• Para cada elemento , una función de retardo ; ${\ Displaystyle e}$${\ Displaystyle d_ {e}: \ mathbb {N} \ longrightarrow \ mathbb {R}}$
• Dada una estrategia , el jugador experimenta retrasos . Suponga que cada uno es positivo y monótono en aumento. ${\ Displaystyle P_ {i}}$${\ Displaystyle i}$${\ Displaystyle \ textstyle \ sum _ {e \ in P_ {i}} d_ {e} (x_ {e})}$${\ Displaystyle d_ {e}}$

Ejemplo

Considere el siguiente gráfico dirigido en el que cada jugador tiene dos estrategias disponibles, pasando o pasando , lo que lleva a un total de cuatro posibilidades. La siguiente matriz expresa los costos de los jugadores en términos de retrasos en función de sus elecciones: ${\ Displaystyle A}$${\ Displaystyle B}$

El gráfico dirigido para un juego de congestión simple.

Tanto (A, B) como (B, A) son equilibrios de Nash puros en este juego, ya que cualquier cambio unilateral de uno de los jugadores aumenta el costo de este jugador (tenga en cuenta que los valores en la tabla son costos, por lo que los jugadores prefiera que sean más pequeños).

Existencia de equilibrios de Nash

La existencia de equilibrios de Nash se puede demostrar construyendo una función potencial que asigna un valor a cada resultado. Además, esta construcción también mostrará que la mejor respuesta iterada encuentra un equilibrio de Nash. Definir . Tenga en cuenta que esta función no es el bienestar social , sino una especie de integral discreta. La propiedad crítica de una función potencial para un juego de congestión es que si un jugador cambia de estrategia, el cambio en su demora es igual al cambio en la función potencial. ${\ Displaystyle \ textstyle \ Phi = \ sum _ {e \ in E} \ sum _ {k = 1} ^ {x_ {e}} d_ {e} (k)}$${\ Displaystyle \ textstyle \ sum _ {e \ in E} x_ {e} d_ {e} (x_ {e})}$

Considere el caso en el que el jugador cambia de a . Los elementos que están en ambas estrategias no se ven afectados, los elementos que el jugador deja (es decir ) disminuyen el potencial y los elementos que el jugador se une (es decir ) aumentan el potencial . Este cambio de potencial es precisamente el cambio de retardo para el jugador , por lo que de hecho es una función potencial. ${\ Displaystyle i}$${\ Displaystyle P_ {i}}$${\ Displaystyle Q_ {i}}$${\ Displaystyle e \ in P_ {i} -Q_ {i}}$${\ Displaystyle d_ {e} (x_ {e})}$${\ Displaystyle e \ en Q_ {i} -P_ {i}}$${\ Displaystyle d_ {e} (x_ {e} +1)}$${\ Displaystyle i}$${\ Displaystyle \ Phi}$

Ahora observe que cualquier mínimo de es un equilibrio de Nash puro. Al arreglar a todos menos a un jugador, cualquier mejora en la estrategia de ese jugador corresponde a una disminución , lo que no puede suceder como mínimo. Ahora bien, como hay un número finito de configuraciones y cada una es monótona, existe un equilibrio. ${\ Displaystyle \ Phi}$${\ Displaystyle \ Phi}$${\ Displaystyle d_ {e}}$

Juegos de congestión continua

Los juegos de congestión continua son el caso límite como . En esta configuración, consideramos a los jugadores como "infinitesimalmente pequeños". Mantenemos un conjunto finito de elementos congestionables. En lugar de reconocer a los jugadores, como en el caso discreto, tenemos tipos de jugadores, donde cada tipo está asociado con un número , que representa la tasa de tráfico para ese tipo. Cada tipo elige una estrategia de un conjunto de estrategias , que asumimos que son inconexas. Como antes, suponga que son monótonos y positivos, pero agregue el supuesto de que también son continuos . Finalmente, permitimos que los jugadores de un tipo se distribuyan fraccionalmente sobre su conjunto de estrategias. Es decir, para , denotemos la fracción de jugadores en el tipo que usan la estrategia . Asume eso . ${\ Displaystyle n \ rightarrow \ infty}$${\ Displaystyle E}$${\ Displaystyle n}$${\ Displaystyle n}$ ${\ Displaystyle i}$${\ Displaystyle r_ {i}}$${\ Displaystyle S_ {i}}$${\ Displaystyle d_ {e}}$${\ Displaystyle P \ en S_ {i}}$${\ Displaystyle f_ {P}}$${\ Displaystyle i}$${\ Displaystyle P}$${\ Displaystyle \ textstyle \ sum _ {P \ in S_ {i}} f_ {P} = r_ {i}}$

Existencia de equilibrios en el caso continuo

Tenga en cuenta que las estrategias ahora son colecciones de perfiles de estrategias . Para un conjunto de estrategias de tamaño , la colección de todos los perfiles válidos es un subconjunto compacto de . Como antes, defina la función potencial como , reemplazando la integral discreta con la estándar. ${\ Displaystyle f_ {P}}$${\ Displaystyle S_ {i}}$${\ Displaystyle n}$${\ Displaystyle [0, r_ {i}] ^ {n}}$${\ Displaystyle \ textstyle \ Phi = \ sum _ {e \ in E} \ int _ {0} ^ {x_ {e}} d_ {e} (z) \, dz}$

En función de la estrategia, es continuo: es continuo y es una función continua de la estrategia. Luego, por el teorema del valor extremo , alcanza su mínimo global. ${\ Displaystyle \ Phi}$${\ Displaystyle d_ {e}}$${\ Displaystyle x_ {e}}$${\ Displaystyle \ Phi}$

El paso final es mostrar que un mínimo de es de hecho un equilibrio de Nash. Suponga por contradicción que existe una colección de ese mínimo pero no es un equilibrio de Nash. Luego, para algún tipo , existe alguna mejora con respecto a la elección actual . Es decir, . La idea ahora es tomar una pequeña cantidad de jugadores que usan la estrategia y moverlos a la estrategia . Ahora, para cualquiera , hemos aumentado su carga en , por lo que su plazo es ahora . Diferenciando la integral, este cambio es aproximadamente , con error . El análisis equivalente del cambio se mantiene cuando miramos los bordes hacia adentro . ${\ Displaystyle \ Phi}$${\ Displaystyle f_ {P}}$${\ Displaystyle \ Phi}$${\ Displaystyle i}$${\ displaystyle Q}$${\ Displaystyle P}$${\ Displaystyle \ textstyle \ sum _ {e \ in P} d_ {e} (x_ {e})> \ sum _ {e \ in Q} d_ {e} (x_ {e})}$${\ Displaystyle \ delta <f_ {P}}$${\ Displaystyle P}$${\ displaystyle Q}$${\ Displaystyle x_ {e} \ in Q}$${\ Displaystyle \ delta}$${\ Displaystyle \ Phi}$${\ Displaystyle \ textstyle \ int _ {0} ^ {x_ {e} + \ delta} d_ {e} (z) dz}$${\ Displaystyle \ delta \ cdot d_ {e} (x_ {e})}$${\ Displaystyle \ delta ^ {2}}$${\ Displaystyle P}$

Por lo tanto, el cambio de potencial es aproximadamente , que es menor que cero. Esto es una contradicción, ya que entonces no se minimizó. Por lo tanto, un mínimo de debe ser un equilibrio de Nash. ${\ Displaystyle \ textstyle \ delta (\ sum _ {e \ in Q} d_ {e} (x_ {e}) - \ sum _ {e \ in P} d_ {e} (x_ {e}))}$${\ Displaystyle \ Phi}$${\ Displaystyle \ Phi}$

Calidad de las soluciones y precio de la anarquía

Dado que existen equilibrios de Nash en los juegos de congestión continua, el siguiente tema natural es analizar su calidad. Derivaremos límites en la relación entre el retraso en Nash y el retraso óptimo, también conocido como el precio de la anarquía . Primero, comenzamos con una condición técnica sobre las funciones de retardo.

Definición El retraso es suave si para todo , . ${\ Displaystyle (\ lambda, \ mu)}$${\ Displaystyle x, y> 0}$${\ Displaystyle yd (x) \ leq \ lambda yd (y) + \ mu xd (x)}$

Ahora bien, si la demora es suave, es un equilibrio de Nash y es una asignación óptima, entonces . En otras palabras, el precio de la anarquía es . Vea estas notas de la conferencia para una prueba. ${\ Displaystyle (\ lambda, \ mu)}$${\ Displaystyle f}$${\ displaystyle f ^ {*}}$${\ Displaystyle \ textstyle \ sum _ {e} x_ {e} d_ {e} (x_ {e}) \ leq {\ frac {\ lambda} {1- \ mu}} \ sum _ {e} x_ {e } ^ {*} d_ {e} (x_ {e} ^ {*})}$${\ Displaystyle \ textstyle {\ frac {\ lambda} {1- \ mu}}}$

Ver también

• Juego potencial

Referencias

• 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 .
• Notas de la conferencia de Michal Feldman y Noam Nisan sobre juegos de potencial y congestión
• 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 .

enlaces externos

• Notas de la conferencia de Yishay Mansour sobre juegos de potencial y congestión
• ּ Los juegos de asignación de recursos están relacionados de alguna manera con los juegos de congestión.