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 necesito llegar al punto . Suponga que ese nodo está conectado al nodo a través de puntos de conexión y , dónde está un poco más cerca que (es decir es más probable que sea elegido por 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 el retraso de cada jugador, por lo que hacer que ambos jugadores pasen por el mismo punto de conexión provoca un retraso 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?
Definición
Los juegos de congestión discreta son juegos con los siguientes componentes.
- Un conjunto básico de elementos congestionables. ;
- jugadores;
- Un conjunto finito de estrategias para cada jugador, donde cada estrategia es un subconjunto de ;
- Para cada elemento y un vector de estrategias , Una carga ;
- Para cada elemento , una función de retardo ;
- Dada una estrategia , jugador retraso de experiencias . Suponga que cada es positivo y monótono en aumento.
Ejemplo
Considere el siguiente gráfico dirigido donde cada jugador tiene dos estrategias disponibles: pasar por o pasando por - 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:
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/b/b2/Congestion-diagram.svg/300px-Congestion-diagram.svg.png)
p2 p1 | A | B |
---|---|---|
A | (5,5) | (2,3) |
B | (3,2) | (6,6) |
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 la asistencia social, sino más bien 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.
Considere el caso cuando el jugador cambia de a . Los elementos que están en ambas estrategias no se ven afectados, elementos que el jugador deja (es decir,) Disminuir el potencial por , y los elementos que el jugador une (es decir, ) aumentar el potencial por . Este cambio de potencial es precisamente el cambio de retraso para el jugador., entonces es de hecho una función potencial.
Ahora observe que cualquier mínimo de es un equilibrio de Nash puro. Arreglando a todos menos a un jugador, cualquier mejora en la estrategia de ese jugador corresponde a una disminución, que no puede suceder como mínimo. Ahora que hay un número finito de configuraciones y cada es monótono, existe un equilibrio.
Juegos de congestión continua
Los juegos de congestión continua son el caso límite, ya que . En esta configuración, consideramos a los jugadores como "infinitesimalmente pequeños". Mantenemosun conjunto finito de elementos congestionables. En lugar de reconocer 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 son inconexos. Como antes, suponga que elson monótonas y positivas, pero agregue la suposición de que también son continuas . Finalmente, permitimos que los jugadores de un tipo se distribuyan fraccionalmente sobre su conjunto de estrategias. Es decir, para, dejar denotar la fracción de jugadores en el tipo usando estrategia . Asumir que.
Existencia de equilibrios en el caso continuo
Tenga en cuenta que las estrategias ahora son colecciones de perfiles de estrategia . 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 por la estándar.
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.
El último paso es demostrar que un mínimo de es de hecho un equilibrio de Nash. Suponga por contradicción que existe una colección de que minimizan pero no son un equilibrio de Nash. Entonces para algún tipo, existe alguna mejora sobre la elección actual . Es decir,. La idea ahora es tomar una pequeña cantidad de jugadores que usan estrategia y muévelos a la estrategia . Ahora para cualquier, hemos aumentado su carga en , por lo que su término en es ahora . Diferenciando la integral, este cambio es aproximadamente, con error . El análisis equivalente del cambio se mantiene cuando miramos los bordes en.
Por lo tanto, el cambio de potencial es aproximadamente , que es menor que cero. Esto es una contradicción, como entoncesno fue minimizado. Por lo tanto, un mínimo de debe ser un equilibrio de Nash.
Calidad de las soluciones y precio de la anarquía
Dado que existen equilibrios de Nash en 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 todos , .
Ahora si el retraso es liso, 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.
Ver también
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 [1] están algo relacionados con los juegos de congestión.
- ^ Kukushkin, NS; Men'Shikov, IS; Men'Shikova, OR; Morozov, VV (1990). "Juegos de asignación de recursos". Modelado y Matemática Computacional . 1 (4): 433. doi : 10.1007 / BF01128293 .