Juego de congestión

Clases de juegos en la teoría de juegos

Los juegos de congestión (CG) son una clase de juegos en la teoría de juegos . Representan situaciones que ocurren comúnmente en carreteras, redes de comunicación , mercados oligopólicos y hábitats naturales . Hay un conjunto de recursos (por ejemplo, carreteras o enlaces de comunicación); hay varios jugadores que necesitan recursos (por ejemplo, conductores o usuarios de la red); cada jugador elige un subconjunto de estos recursos (por ejemplo, un camino en la red); el retraso en cada recurso está determinado por el número de jugadores que eligen un subconjunto que contiene este recurso. El costo de cada jugador es la suma de los retrasos entre todos los recursos que elige. Naturalmente, cada jugador quiere minimizar su propio retraso; sin embargo, las elecciones de cada jugador imponen una externalidad negativa a los otros jugadores, lo que puede conducir a resultados ineficientes.

La investigación de los juegos de congestión fue iniciada por el economista estadounidense Robert W. Rosenthal en 1973. ^[1] Demostró que todo juego de congestión tiene un equilibrio de Nash en estrategias puras (también conocido como equilibrio de Nash puro , PNE). Durante la prueba, de hecho demostró que todo juego de congestión es un juego potencial exacto . Más tarde, Monderer y Shapley ^[2] demostraron un resultado inverso: cualquier juego con una función potencial exacta es equivalente a algún juego de congestión. Las investigaciones posteriores se centraron en preguntas como:

• ¿La existencia de equilibrio, así como la existencia de una función potencial, se extiende a modelos más generales de juegos de congestión?
• ¿Cuál es la ineficiencia cuantitativa de los juegos de congestión ?
• ¿Cuál es la complejidad computacional de encontrar un equilibrio?

Ejemplo

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

Considere una red de tráfico en la que dos jugadores se originan en el punto y necesitan llegar al punto . Suponga que un nodo está conectado a otro nodo a través de dos caminos: - - y - - , donde está un poco más cerca que (es decir, es más probable que cada jugador lo elija), como en la imagen de la derecha. ${\displaystyle O}$ ${\displaystyle T}$ ${\displaystyle O}$ ${\displaystyle T}$ ${\displaystyle O}$ ${\displaystyle A}$ ${\displaystyle T}$ ${\displaystyle O}$ ${\displaystyle B}$ ${\displaystyle T}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$

Las carreteras de ambos puntos de conexión se congestionan fácilmente, lo que significa que cuantos más jugadores pasan por un punto, mayor es el retraso de cada jugador, por lo que el hecho de que ambos jugadores pasen por el mismo punto de conexión provoca un retraso adicional. Formalmente, el retraso en cada uno de los puntos de conexión y cuando los jugadores pasan por ellos es de . ${\displaystyle T}$ ${\displaystyle A}$ ${\displaystyle T}$ ${\displaystyle B}$ ${\displaystyle T}$ ${\displaystyle x}$ ${\displaystyle x^{2}}$

Un buen resultado en este juego sería que los dos jugadores se "coordinen" y pasen por diferentes puntos de conexión. ¿Es posible lograr un resultado así?

La siguiente matriz expresa los costos de los jugadores en términos de retrasos en función de sus elecciones:

Los equilibrios de Nash puros en este juego son (OAT,OBT) y (OBT,OAT): cualquier cambio unilateral por parte de uno de los jugadores aumenta el costo de ese jugador (nótese que los valores en la tabla son costos, por lo que los jugadores prefieren que sean menores). En este ejemplo, el equilibrio de Nash es eficiente : los jugadores eligen carriles diferentes y la suma de los costos es mínima.

Por el contrario, supongamos que el retraso en cada uno de los jugadores y cuando van allí es . Entonces la matriz de costos es: ${\displaystyle A}$ ${\displaystyle T}$ ${\displaystyle B}$ ${\displaystyle T}$ ${\displaystyle x}$ ${\displaystyle 0.8x}$

Ahora bien, el único equilibrio de Nash puro es (OAT, OAT): cualquier jugador que cambie a OBT aumenta su coste de 2,6 a 2,8. Sigue existiendo un equilibrio, pero no es eficiente: la suma de costes es 5,2, mientras que la suma de costes en (OAT, OBT) y (OBT, OAT) es 4,6.

Resultado básico

Notación

La definición básica de un CG tiene los siguientes componentes.

• Un conjunto base de elementos congestionables (también llamados recursos o factores ). En el ejemplo anterior, es el conjunto de carreteras ( , , y ). ${\displaystyle E}$ ${\displaystyle E}$ ${\displaystyle O}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle T}$ ${\displaystyle O}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle T}$
• Un grupo de jugadores. En el ejemplo anterior . ${\displaystyle n}$ ${\displaystyle n=2}$
• Un conjunto finito de estrategias para cada jugador, donde cada estrategia es un subconjunto de . ${\displaystyle S_{i}}$ ${\displaystyle P\in S_{i}}$ ${\displaystyle E}$
  • En el ejemplo anterior, ambos jugadores tienen el mismo conjunto de estrategias: . Los CG en los que todos los jugadores tienen el mismo conjunto de estrategias se denominan CG simétricos . En general, diferentes jugadores pueden tener diferentes conjuntos, por ejemplo, si cada jugador tiene una fuente diferente y/o un objetivo diferente. Dichos CG se denominan CG asimétricos . ${\displaystyle S_{1}=S_{2}=\{\{OA,AT\},\{OB,BT\}\}}$
  • En general, una estrategia puede ser cualquier subconjunto de . Los CG en los que una estrategia solo puede ser una ruta en un gráfico determinado (como en el ejemplo anterior) se denominan CG de red . Los CG en los que una estrategia solo puede ser un único recurso se denominan CG singleton . ${\displaystyle E}$
• Para cada elemento y un vector de estrategias , la carga se define como . ${\displaystyle e\in E}$ ${\displaystyle (P_{1},P_{2},\ldots ,P_{n})}$ ${\displaystyle x_{e}=\#\{i:e\in P_{i}\}}$
• Para cada elemento existe una función de retardo (también llamada función de latencia o función de costo ). Dado un vector de estrategias, el retardo en es . Se supone que cada una es positiva y monótona creciente . ${\displaystyle e\in E}$ ${\displaystyle d_{e}:\mathbb {N} \longrightarrow \mathbb {R} }$ ${\displaystyle e}$ ${\displaystyle d_{e}(x_{e})}$ ${\displaystyle d_{e}}$
• Dada una estrategia , el jugador experimenta un retraso ; cada jugador quiere minimizar su retraso. ${\displaystyle P_{i}}$ ${\displaystyle i}$ ${\displaystyle \textstyle \sum _{e\in P_{i}}d_{e}(x_{e})}$
• Un equilibrio de Nash es un vector de estrategias tal que, para cada jugador , reemplazar con una estrategia diferente no disminuiría el retraso experimentado por . ${\displaystyle (P_{1},P_{2},\ldots ,P_{n})}$ ${\displaystyle i}$ ${\displaystyle P_{i}}$ ${\displaystyle Q_{i}}$ ${\displaystyle i}$

Existencia de equilibrios de Nash

Todo CG tiene un equilibrio de Nash en estrategias puras . Esto se puede demostrar construyendo una función potencial que asigna un valor a cada resultado. ^[1] Además, esta construcción también mostrará que la mejor respuesta iterada encuentra un equilibrio de Nash. Defina . Nótese que esta función no es el bienestar 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 retraso 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})}$

Consideremos 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 abandona (es decir, ) disminuyen el potencial en , y los elementos a los que se une el jugador (es decir, ) aumentan el potencial en . Este cambio en el potencial es precisamente el cambio en el retraso para el jugador , por lo que es, de hecho, 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\in Q_{i}-P_{i}}$ ${\displaystyle d_{e}(x_{e}+1)}$ ${\displaystyle i}$ ${\displaystyle \Phi }$

Observemos ahora que cualquier mínimo de es un equilibrio de Nash puro. Si se fijan todos los jugadores menos uno, cualquier mejora en la estrategia de ese jugador corresponde a una disminución de , lo que no puede ocurrir en un 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}}$

La existencia de una función potencial tiene una implicación adicional, llamada propiedad de mejora finita (FIP) . Si empezamos con cualquier vector de estrategia, elegimos un jugador arbitrariamente y dejamos que cambie su estrategia por una mejor para él, y repetimos, entonces la secuencia de mejoras debe ser finita (es decir, la secuencia no será cíclica). Esto se debe a que cada una de esas mejoras aumenta estrictamente el potencial.

Extensiones

A continuación presentamos varias extensiones y variaciones del modelo CG básico.

Juegos de congestión no atómica

Un CG no atómico (también conocido como continuo ) es el límite de un CG estándar con n jugadores, ya que . Hay un continuo de jugadores, los jugadores se consideran "infinitesimalmente pequeños" y cada jugador individual tiene un efecto insignificante en la congestión. Milchtaich, ^[3] Friedman ^[4] y Blonsky estudiaron los CG no atómicos . ^{[5] [6]} ${\displaystyle n\rightarrow \infty }$

• Mantenemos un conjunto finito de elementos congestionables. ${\displaystyle E}$
• 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. ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle i}$ ${\displaystyle r_{i}}$
• Cada agente del tipo i elige una estrategia del conjunto de estrategias . ${\displaystyle S_{i}}$
• Como antes, las funciones de retardo son monótonas y positivas, pero ahora agregamos el supuesto de que también son continuas . ${\displaystyle d_{e}}$
• Permitimos que los jugadores de un tipo se distribuyan fraccionariamente en su conjunto de estrategias. Es decir, para cada estrategia , denotemos la fracción de jugadores del tipo que usan la estrategia . Por definición, . ${\displaystyle P\in S_{i}}$ ${\displaystyle f_{P}}$ ${\displaystyle i}$ ${\displaystyle P}$ ${\displaystyle \textstyle \sum _{P\in S_{i}}f_{P}=r_{i}}$
• Para cada elemento , la carga se define como la suma de fracciones de jugadores que utilizan e , es decir, . ${\displaystyle e\in E}$ ${\displaystyle x_{e}=\sum _{P\ni e}f_{P}}$

Existencia de equilibrios en CG no atómicos

Las estrategias son ahora 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 . Ahora definimos la función potencial como , reemplazando la integral discreta por 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}$

Como función de la estrategia, es continua: es continua por supuesto, 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 demostrar que un mínimo de es de hecho un equilibrio de Nash. Supongamos por contradicción que existe una colección de que se 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 la estrategia y moverlos a la estrategia . Ahora, para cualquier , hemos aumentado su carga en , por lo que su término en ahora es . Diferenciando la integral, este cambio es aproximadamente , con un error . El análisis equivalente del cambio se cumple cuando observamos los bordes en . ${\displaystyle \Phi }$ ${\displaystyle f_{P}}$ ${\displaystyle \Phi }$ ${\displaystyle i}$ ${\displaystyle Q\in S_{i}}$ ${\displaystyle P}$ ${\displaystyle \textstyle \sum _{e\in Q}d_{e}(x_{e})<\sum _{e\in P}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 }$

Juegos de congestión divisibles

En un CG divisible, como en un CG atómico, hay un número finito de jugadores, cada uno de los cuales tiene una cierta carga para transferir. Al igual que en los CG no atómicos, cada jugador puede dividir su carga en cargas fraccionarias que pasan por diferentes caminos, como una empresa de transporte que elige un conjunto de caminos para el transporte masivo. A diferencia de los CG no atómicos, cada jugador tiene un efecto no despreciable en la congestión.

Los CG divisibles fueron analizados por primera vez por Ariel Orda, Raphael Rom y Nachum Shimkin en 1993, en el contexto de las redes de comunicación. ^{[7] [8]} Demuestran que, para una red simple con dos nodos y múltiples enlaces paralelos, el equilibrio de Nash es único en condiciones de convexidad razonables y tiene algunas propiedades de monotonía interesantes. Para topologías de red generales, se requieren condiciones más complejas para garantizar la unicidad del equilibrio de Nash.

Juegos de congestión ponderada

En un CG ponderado , diferentes jugadores pueden tener diferentes efectos en la congestión. Por ejemplo, en una red de carreteras, un camión agrega congestión mucho más que una motocicleta . En general, el peso de un jugador puede depender del recurso ( pesos específicos del recurso ): para cada jugador i y recurso e , hay un peso y la carga en el recurso e es . Un caso especial importante es cuando el peso depende solo del jugador ( pesos independientes del recurso ), es decir, cada jugador i tiene un peso y . ${\displaystyle w_{i,e}}$ ${\displaystyle x_{e}=\sum _{i:e\in P_{i}}w_{i,e}}$ ${\displaystyle w_{i}}$ ${\displaystyle x_{e}=\sum _{i:e\in P_{i}}w_{i}}$

CG singleton ponderados con ponderaciones independientes de los recursos

Milchtaich ^[9] consideró el caso especial de los CG ponderados en los que cada estrategia es un único recurso ("CG singleton"), los pesos son independientes de los recursos y todos los jugadores tienen el mismo conjunto de estrategias. Se demuestra lo siguiente:

• Si todos los jugadores tienen las mismas funciones de retardo, entonces el juego tiene la propiedad de mejora finita (y por lo tanto tiene un PNE).
• Si sólo hay dos estrategias (y arbitrariamente muchos jugadores con funciones de retardo posiblemente diferentes), entonces el juego tiene la propiedad de mejora finita (y, por lo tanto, tiene una PNE).
• Si solo hay dos jugadores (con funciones de retardo posiblemente diferentes), entonces el juego tiene la propiedad de mejor respuesta finita (y, por lo tanto, tiene una PNE).
• Si hay tres o más estrategias y tres o más jugadores con diferentes funciones de retardo, es posible que no exista una PNE.

CG de red ponderados

Milchtaich consideró el caso especial de CG ponderados en el que cada estrategia es un camino en un grafo no dirigido dado ("CG de red"). Demostró que cada juego finito puede representarse como un juego de congestión de red ponderado, con funciones de costo no decrecientes (pero no necesariamente negativas). ^{[10] Esto implica que no todos esos juegos tienen una PNE. Libman y Orda, [11]} así como Goemans Mirrokni y Vetta ^[12] dan ejemplos concretos de CG ponderados sin PNE . Esto plantea la pregunta de qué condiciones garantizan la existencia de PNE. ^[13]

En particular, decimos que un cierto grafo G garantiza una cierta propiedad si cada red ponderada CG en la que la red subyacente es G tiene esa propiedad. Milchtaich ^[14] caracterizó las redes que garantizan la existencia de PNE, así como la propiedad de mejora finita, con la condición adicional de que un jugador con un peso menor tiene débilmente más estrategias permitidas (formalmente, implica ). Demostró que: ${\displaystyle w_{i}<w_{j}}$ ${\displaystyle |S_{i}|\geq |S_{j}|}$

• Un gráfico G garantiza la propiedad de mejora finita si y solo si G es homeomorfo a una red paralela (un gráfico formado por una o más redes de un solo borde conectadas en paralelo ) o a una red paralela conectada en serie con una o dos redes de un solo borde. ^{: Teoría 2}
• Un grafo G garantiza la existencia de un PNE si y solo si G es homeomorfo a una conexión en serie de una o más redes de un conjunto de seis "redes permitidas"; una condición equivalente es que ninguna red de un conjunto de seis "redes prohibidas" esté incrustada en G. : ^{Teoría 3}

En el caso especial en el que a cada jugador se le permite utilizar cualquier estrategia ("bordes públicos"), hay más redes que garantizan la existencia de PNE; una caracterización completa de dichas redes se plantea como un problema abierto. ^[14]

Mlichtaich ^[15] analiza el efecto de la topología de la red en la eficiencia de PNE:

• Un gráfico G garantiza que cada PNE es Pareto-eficiente, siempre y cuando tres "redes prohibidas" simples no estén integradas en G.
• Un gráfico G garantiza que la paradoja de Braess no ocurre, siempre y cuando sea un gráfico serie-paralelo .

Milchtaich ^[16] analiza el efecto de la topología de la red en la unicidad de los costos de PNE:

• Un gráfico G garantiza que los costos de PNE son únicos si y solo si G es una conexión en serie de una o más redes de varios tipos simples.
• Un gráfico G no garantiza que los costos de PNE sean únicos si y solo si G contiene una red incorporada de un tipo simple particular.

Holzman y Law-Yone ^[17] también caracterizan las redes que garantizan que cada CG atómico tenga un PNE fuerte , un PNE único o un PNE Pareto-eficiente .

Richman y Shimkin ^[18] caracterizan las redes que garantizan que cada CG divisible tenga un PNE único.

CG ponderados generales

Decimos que una clase C de funciones garantiza una cierta propiedad si cada CG ponderado en el que todas las funciones de retardo son elementos de C tiene esa propiedad.

• Fotakis, Kontogiannis y Spirakis ^[19] demuestran que la clase de funciones lineales garantiza la existencia de un potencial exacto y, por lo tanto, la existencia de PNE.
• Panagopoulou y Spirakis ^[20] demuestran que la clase de funciones exponenciales garantiza la existencia de un potencial ponderado y, por lo tanto, la existencia de PNE.
• Harks, Klimm y Mohring ^[21] prueban que una clase de funciones garantiza la existencia de un potencial exacto, si y solo si contiene solo funciones afines . Esta caracterización sigue siendo válida cuando se restringe a juegos de dos jugadores, juegos de tres recursos, juegos singleton, juegos con estrategias simétricas o juegos con pesos integrales. Además, una clase de funciones garantiza la existencia de un potencial ponderado, si y solo si (1) contiene solo funciones afines, o (2) contiene solo funciones exponenciales de la forma , donde es la misma para todos los recursos. Esta caracterización sigue siendo válida cuando se restringe a juegos de cuatro jugadores, juegos de cuatro recursos, juegos singleton, juegos con estrategias simétricas o juegos con pesos integrales. Para juegos de dos jugadores, una clase de funciones garantiza la existencia de un potencial ponderado, si y solo si todas las funciones en ella son de la forma , donde es una función monótona (la misma para todos los recursos). ${\displaystyle a_{e}\cdot \exp {(\phi \cdot x_{e})}+b_{e}}$ ${\displaystyle \phi }$ ${\displaystyle a_{e}\cdot f(x_{e})+b_{e}}$ ${\displaystyle f}$
• Harks y Klimm ^[22] prueban un resultado similar para la existencia de PNE: prueban que una clase de funciones garantiza la existencia de PNE si y solo si (1) contiene solo funciones afines, o (2) contiene solo funciones exponenciales de la forma , donde es la misma para todos los recursos. Esta caracterización sigue siendo válida cuando se restringe a juegos de tres jugadores. Para juegos de dos jugadores, una clase de funciones garantiza la existencia de PNE si y solo si todas las funciones en ella son de la forma , donde es una función monótona (la misma para todos los recursos). ${\displaystyle a_{e}\cdot \exp {(\phi \cdot x_{e})}+b_{e}}$ ${\displaystyle \phi }$ ${\displaystyle a_{e}\cdot f(x_{e})+b_{e}}$ ${\displaystyle f}$

Otros resultados

Hay muchos otros artículos sobre juegos de congestión ponderados. ^{[23] [24] [25]}

Funciones de costes específicas del jugador

El modelo básico de CG se puede ampliar permitiendo que la función de retardo de cada recurso dependa del jugador. Por lo tanto, para cada recurso e y jugador i , existe una función de retardo . Dada una estrategia , el jugador experimenta un retraso . ${\displaystyle d_{i,e}}$ ${\displaystyle P_{i}}$ ${\displaystyle i}$ ${\displaystyle \textstyle \sum _{e\in P_{i}}d_{i,e}(x_{e})}$

Costos específicos de cada jugador en CG de un solo jugador (juegos con aglomeración)

Milchtaich ^[9] introdujo y estudió los CG con costos específicos del jugador en el siguiente caso especial:

• Cada jugador elige un único recurso (tales juegos se llaman CG singleton );
• Todos los jugadores tienen el mismo conjunto de estrategias.

Este caso especial de CG también se denomina juego de hacinamiento . ^{[26] [27]} Representa un escenario en el que varias personas eligen simultáneamente un lugar al que ir (por ejemplo, una habitación, un asentamiento, un restaurante), y su recompensa está determinada tanto por el lugar como por el número de otros jugadores que eligen el mismo lugar.

En un juego de hacinamiento, dada una estrategia , el jugador experimenta un retraso . Si el jugador cambia a una estrategia diferente , su retraso sería ; por lo tanto, un vector de estrategia es un PNE si y solo si para cada jugador i, para todos los e , f . ${\displaystyle P_{i}=\{e\}}$ ${\displaystyle i}$ ${\displaystyle d_{i,e}(x_{e})}$ ${\displaystyle f}$ ${\displaystyle d_{i,f}(x_{f}+1)}$ ${\displaystyle d_{i,e}(x_{e})\leq d_{i,f}(x_{f}+1)}$

En general, los CG con retrasos específicos de cada jugador podrían no admitir una función potencial . Por ejemplo, supongamos que hay tres recursos x, y, z y dos jugadores A y B con las siguientes funciones de retraso:

• ${\displaystyle d_{A,x}(1)<d_{A,y}(0)<d_{A,y}(2)<d_{A,z}(0)<d_{A,z}(2)<d_{A,x}(2)}$
• ${\displaystyle d_{B,y}(1)<d_{B,x}(0)<d_{B,x}(2)<d_{B,z}(0)<d_{B,z}(2)<d_{B,y}(2)}$

La siguiente es una ruta de mejora cíclica: . Esto demuestra que la propiedad de mejora finita no se cumple, por lo que el juego no puede tener una función potencial (ni siquiera una función potencial ordinal generalizada). Sin embargo: ${\displaystyle (z,y)\to (y,y)\to (y,z)\to (x,z)\to (x,x)\to (z,x)\to (z,y)}$

• Con sólo dos recursos, se cumple la propiedad de mejora finita. ^{[9] : Teoría 1} Por lo tanto, existe una PNE.
• Con sólo dos jugadores, se cumplen todas las propiedades finitas de mejor respuesta. Por lo tanto, existe una PNE.

Cuando hay tres o más jugadores, incluso los caminos de mejor respuesta pueden ser cíclicos. Sin embargo, cada CG todavía tiene un PNE. ^{[9] : Thm.2} La prueba es constructiva y muestra un algoritmo que encuentra un equilibrio de Nash en como máximo pasos. Además, cada CG es débilmente acíclico : para cualquier vector de estrategia inicial, al menos un camino de mejor respuesta que comienza en este vector tiene una longitud de como máximo , que termina en un equilibrio. ^{[9] : Thm.3} ${\displaystyle {n+1 \choose 2}}$ ${\displaystyle r{n+1 \choose 2}}$

Todo juego de hacinamiento es solucionable secuencialmente . ^[26] Esto significa que, para cada orden de los jugadores, el juego secuencial en el que cada jugador elige por turno una estrategia tiene un equilibrio perfecto en subjuegos en el que las acciones de los jugadores son una PNE en el juego simultáneo original. Todo juego de hacinamiento tiene al menos una PNE fuerte ; ^[28] cada PNE fuerte de un juego de hacinamiento puede alcanzarse como un equilibrio perfecto en subjuegos de una versión secuencial del juego. ^[26]

En general, un juego de congestión puede tener muchas PNE diferentes. Por ejemplo, supongamos que hay n jugadores y n recursos, y que el efecto negativo de la congestión en el resultado es mucho mayor que el valor positivo de los recursos. Entonces hay n! PNE diferentes: cada emparejamiento uno a uno de jugadores con recursos es una PNE, ya que ningún jugador se movería a un recurso ocupado por otro jugador. Sin embargo, si un juego de congestión se replica m veces, entonces el conjunto de PNE converge a un único punto cuando m tiende a infinito. Además, en un juego de congestión "grande" (no atómico), hay genéricamente una PNE única. Esta PNE tiene una propiedad interesante de teoría de grafos. Sea G un grafo bipartito con jugadores en un lado y recursos en el otro, donde cada jugador es adyacente a todos los recursos que sus copias eligen en la PNE única. Entonces G no contiene ciclos. ^[27]

Funciones de costos separables

Un caso especial de las funciones de retardo específicas del jugador es que se pueden separar en un factor específico del jugador y un factor general. Hay dos subcasos:

• Funciones de costo separables multiplicativamente : , donde es una constante que representa el costo base del recurso e para el jugador i , y d es una función de retraso general (la misma para todos los recursos). ${\displaystyle d_{i,e}(x_{e})=a_{i,e}\cdot d(x_{e})}$ ${\displaystyle a_{i,e}}$
• Funciones de costo aditivamente separables : ^[29] , donde es una constante que representa el costo fijo del recurso e para el jugador i, y d es una función de retraso general (la misma para todos los recursos). ${\displaystyle d_{i,e}(x_{e})=a_{i,e}+d(x_{e})}$ ${\displaystyle a_{i,e}}$

Cuando solo se consideran estrategias puras, estas dos nociones son equivalentes, ya que el logaritmo de un producto es una suma. Además, cuando los jugadores pueden tener pesos específicos de los recursos, la configuración con funciones de demora específicas de los recursos se puede reducir a la configuración con una función de demora universal. Los juegos con funciones de costo separables ocurren en equilibrio de carga, ^[30] colas M/M/1 , ^[31] y selección de hábitat . ^[32] Se sabe lo siguiente sobre los CG singleton ponderados con costos separables: ^[33]

• Si los costos base son independientes del jugador ( para cada jugador i ), entonces el CG tiene el FIP, por lo tanto tiene un PNE. Lo mismo ocurre si los costos base son independientes de los recursos ( para cada recurso e ). ^{[30] [34]} La prueba se basa en una función potencial con valores vectoriales. Para cada estado del juego, el potencial es un vector de tamaño n que contiene los costos de todos los jugadores, ordenados de mayor a menor. Siempre que un jugador se desvía hacia un recurso con un costo menor para él, el vector de costos se vuelve más pequeño en el orden leximin . ${\displaystyle a_{i,e}}$ ${\displaystyle a_{i,e}=a_{e}}$ ${\displaystyle a_{i,e}=a_{i}}$
• Si los pesos son independientes del jugador (equivalentemente: el CG no está ponderado y las funciones de retardo son específicas de los recursos), entonces tiene el FIP, por lo tanto tiene un PNE. ^{[35] [29]} Si las funciones de costo son aditivamente separables, entonces el juego incluso tiene una función potencial exacta. El resultado se mantiene incluso si las funciones de costo no aumentan monótonamente con la carga. Si las funciones de costo no son aditivamente separables, entonces el FIP puede no mantenerse, y puede que no haya una función potencial, pero aún existe un PNE. ^{[9] : Teoría 2}
• Si los pesos son independientes de los recursos, entonces existe una PNE en los siguientes casos:
  • Cuando hay como máximo tres jugadores, existe una PNE, ^{[36] : Cor.3} aunque la propiedad de mejora de mejor respuesta podría no cumplirse. Por el contrario, hay un CG con costos separables y pesos independientes de los recursos con ocho jugadores en el que no existe una PNE. ^{[33] : Thm.3}
  • Cuando las funciones de costo son aditivamente separables con funciones de costo variable lineales, el CG tiene un potencial ponderado, por lo tanto tiene el FIP, por lo tanto tiene un PNE. ^{[36] : Thm.6}
  • Cuando las funciones de costo son aditivamente separables con una función de costo variable logarítmica, y hay como máximo tres jugadores, el CG tiene la propiedad de mejora de mejor respuesta, por lo tanto tiene una PNE. Sin embargo, podría no tener la propiedad de mejora finita. ^[37] Para más de tres jugadores, la existencia de PNE está abierta.

Cada CG singleton ponderado con preferencias específicas del jugador separables es isomorfo a un CG de red ponderada con preferencias independientes del jugador. ^{[33] [2]}

CG de red con costos específicos para cada jugador

Milchtaich consideró el caso especial de los CG con costos específicos de los jugadores, en el que cada estrategia es una ruta en un grafo dado ("CG de red"). Demostró que cada juego finito puede representarse como un juego de congestión de red (no ponderado) con costos específicos de los jugadores, con funciones de costos no decrecientes (pero no necesariamente negativas). ^[10] Se plantea como un problema abierto una caracterización completa de las redes que garantizan la existencia de PNE en tales CG. ^[14]

Cálculo de un equilibrio de Nash puro

Cálculo de un equilibrio en CG no ponderados

La prueba de la existencia de PNE es constructiva: muestra un algoritmo finito (una ruta de mejora) que siempre encuentra un PNE. Esto plantea la pregunta de cuántos pasos se requieren para encontrar este PNE. Fabrikant, Papadimitriou y Talwar ^[38] demostraron:

• Si todas las estrategias son caminos en una red ("CG de red"), y todos los jugadores tienen el mismo conjunto de estrategias ("CG simétrico"), entonces se puede calcular un PNE en tiempo polinomial maximizando el potencial, a través de la reducción al flujo de costo mínimo . El algoritmo se puede adaptar a CG no atómicos: bajo ciertas suposiciones de suavidad, un equilibrio de Nash en un juego de este tipo se puede aproximar en tiempo fuertemente polinomial.
• Si las estrategias pueden ser subconjuntos generales, o los jugadores pueden tener diferentes conjuntos de estrategias ("CG asimétrico"), entonces calcular un PNE es PLS-completo . Esto implica que hay ejemplos con caminos de mejora exponencialmente largos. También implica que encontrar un equilibrio de Nash alcanzable desde un estado específico es PSPACE-completo .
• Cada problema de la clase PLS puede presentarse como un juego cuyos equilibrios puros están garantizados mediante un argumento de función potencial.

Even-Dar, Kesselman y Mansour ^[30] analizan el número de pasos necesarios para la convergencia al equilibrio en un entorno de equilibrio de carga.

Caragiannis, Fanelli, Gravin y Skopalik ^[39] presentan un algoritmo que calcula una PNE de aproximación de factor constante. En particular:

• Con funciones de retardo lineal, la relación de aproximación es 2+ε, y el tiempo de ejecución es polinomial en el número de repeticiones de reproducción, el número de recursos y 1/ε.
• Cuando las funciones de retardo son polinomios de grado d , la relación de aproximación es d ^{O( d )} .

Su algoritmo identifica una secuencia corta de movimientos de mejor respuesta que conduce a un equilibrio aproximado. También muestran que, para CG más generales, lograr cualquier aproximación polinómica de PNE es PLS-completo.

Cálculo de un equilibrio en CG de redes ponderadas

Fotakis, Kontogiannis y Spirakis ^[19] presentan un algoritmo que, en cualquier red ponderada CG con funciones de retardo lineales, encuentra un PNE en tiempo pseudopolinomial (polinomial en el número de jugadores n y la suma de los pesos de los jugadores W ). Su algoritmo es un algoritmo de mejor respuesta codicioso : los jugadores ingresan al juego en orden descendente de su peso y eligen la mejor respuesta a las estrategias de los jugadores existentes.

Panagopoulou y Spirakis ^[20] muestran evidencia empírica de que el algoritmo de Fotakis, Kontogiannis y Spirakis de hecho se ejecuta en un polinomio de tiempo en n y log W. También proponen un vector de estrategia inicial que acelera drásticamente este algoritmo.

En general, un CG de red ponderada puede no tener una PNE. Milchtaich ^[14] demuestra que decidir si un CG de red ponderada dada tiene una PNE es NP-hard incluso en los siguientes casos:

• Hay dos jugadores; todos los jugadores pueden utilizar todos los caminos; todas las funciones de costo son no negativas.
• Hay dos jugadores; el CG no está ponderado; los costos son específicos del jugador y no son negativos.

La prueba se realiza mediante reducción a partir del problema de trayectorias dirigidas y disjuntas. ^[40]

Caragiannis, Fanelli, Gravin y Skopalik ^[41] presentan un algoritmo que calcula una aproximación de factor constante PNE en CG ponderados. En particular:

• Con funciones de retardo lineal, la relación de aproximación es y el tiempo de ejecución es polinomial en el número de repeticiones de reproducción, el número de recursos y 1/ε. ${\displaystyle {\frac {3+{\sqrt {5}}}{2}}+O(\epsilon )}$
• Cuando las funciones de retardo son polinomios de grado d , la relación de aproximación es . ${\displaystyle d^{2d+o(d)}}$

Para demostrar sus resultados, demuestran que, aunque los CG ponderados pueden no tener una función potencial, cada CG ponderado puede aproximarse mediante un determinado juego potencial. Esto les permite demostrar que cada CG ponderado tiene una PNE aproximada ( d !). Su algoritmo identifica una secuencia corta de movimientos de mejor respuesta que conduce a dicha PNE aproximada.

Resumen de las clasificaciones de los juegos de congestión

En resumen, los CG se pueden clasificar según varios parámetros:

• Número y divisibilidad de jugadores: CG atómico , CG divisible o CG no atómico ;
• Peso de los jugadores: CG no ponderado o CG ponderado (con pesos independientes de los recursos o pesos específicos de los recursos );
• Funciones de costo para diferentes jugadores que utilizan el mismo recurso: idénticas o específicas del jugador (con funciones de costo separables o no separables ).
• Posibles estrategias: un recurso ( CG singleton ) o ruta en una red ( CG de red ) o cualquier subconjunto ( CG general) .
• Conjuntos de estrategias de diferentes jugadores: diferentes ( CG asimétrico ) o idénticos ( CG simétrico ).

Véase también

• Dado que cada CG tiene un equilibrio de Nash, el siguiente tema natural es analizar su calidad. Esto se hace utilizando el concepto de Precio de la anarquía en los juegos de congestión .
• Los juegos de asignación de recursos ^{[42] [31]} están de alguna manera relacionados con los juegos de congestión.
• Información incompleta : Facchini, van Megen, Borm y Tijs ^[35] extienden el modelo de Rosenthal a un contexto con información incompleta . Demuestran que los juegos bayesianos relacionados son juegos potenciales y, por lo tanto, tienen equilibrios bayesianos-Nash puros .
• Coaliciones : Fotakis, Kontogiannis y Spirakis ^[43] estudian CG en los que los jugadores participan en coaliciones.
• Juegos de congestión en la naturaleza: Milinsky ^[44] describe un experimento en el que un CG natural converge en un equilibrio de Nash. En su experimento, alimentó a seis peces espinosos desde dos extremos de un tanque. La distribución de peces entre los dos extremos era, en promedio, similar a la relación de las tasas de suministro de alimento, de modo que ningún pez individual podía aumentar su tasa de alimentación moviéndose al otro lado. Mlichtaich ^[3] presenta un tratamiento más general de los CG en competencia interespecífica .

Referencias

1. 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.
2. Monderer, Dov; Shapley, Lloyd S. (1 de mayo de 1996). "Juegos potenciales". Juegos y comportamiento económico . 14 (1): 124–143. doi :10.1006/game.1996.0044. ISSN  0899-8256.
3. Milchtaich, Igal (1996). "Modelos de congestión de la competencia". The American Naturalist . 147 (5): 760–783. doi :10.1086/285878. ISSN  0003-0147. JSTOR  2463089. S2CID  55004212.
4. Friedman, Eric J. (1996-09-01). "Dinámica y racionalidad en juegos de externalidades ordenadas". Juegos y comportamiento económico . 16 (1): 65–76. doi :10.1006/game.1996.0074. ISSN  0899-8256.
5. Blonski, Matthias (1999-08-01). "Juegos anónimos con acciones binarias". Juegos y comportamiento económico . 28 (2): 171–180. doi :10.1006/game.1998.0699. ISSN  0899-8256.
6. Roughgarden, Tim; Tardos, Éva (1 de mayo de 2004). "Limitar la ineficiencia de los equilibrios en juegos de congestión no atómicos". Juegos y comportamiento económico . 47 (2): 389–403. doi :10.1016/j.geb.2003.06.004. ISSN  0899-8256. S2CID  10778635.
7. Orda, A.; Rom, R.; Shimkin, N. (1993-10-01). "Enrutamiento competitivo en redes de comunicación multiusuario". IEEE/ACM Transactions on Networking . 1 (5): 510–521. doi :10.1109/90.251910. ISSN  1558-2566. S2CID  1184436.
8. Roughgarden, Tim; Schoppmann, Florian (1 de marzo de 2015). "Suavidad local y el precio de la anarquía en juegos de congestión divisibles". Journal of Economic Theory . Ciencias de la computación y teoría económica. 156 : 317–342. doi :10.1016/j.jet.2014.04.005. ISSN  0022-0531.
9. 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.
10. Milchtaich, Igal (1 de noviembre de 2013). "Representación de juegos finitos como juegos de congestión de red". Revista internacional de teoría de juegos . 42 (4): 1085–1096. doi :10.1007/s00182-012-0363-5. ISSN  1432-1270. S2CID  253713700.
11. Libman, Lavy; Orda, Ariel (1 de agosto de 2001). "Compartir recursos atómicos en redes no cooperativas". Sistemas de telecomunicaciones . 17 (4): 385–409. doi :10.1023/A:1016770831869. ISSN  1572-9451.
12. Goemans, M.; Mirrokni, Vahab; Vetta, A. (1 de octubre de 2005). "Equilibrios de sumideros y convergencia". 46.º Simposio anual IEEE sobre fundamentos de la informática (FOCS'05) . págs. 142-151. doi :10.1109/SFCS.2005.68. ISBN . 0-7695-2468-0. Número de identificación  S2C17850062.
13. Milchtaich, Igal (2006). "El problema de la existencia de equilibrio en juegos de congestión de redes finitas". En Spirakis, Paul; Mavronicolas, Marios; Kontogiannis, Spyros (eds.). Internet and Network Economics . Apuntes de clase en informática. Vol. 4286. Berlín, Heidelberg: Springer. págs. 87–98. doi :10.1007/11944874_9. ISBN 978-3-540-68141-0.
14. Milchtaich, Igal (1 de agosto de 2015). "Topología de red y existencia de equilibrio en juegos de congestión de red ponderada". Revista internacional de teoría de juegos . 44 (3): 515–541. doi :10.1007/s00182-014-0443-9. hdl : 10419/95995 . ISSN  1432-1270. S2CID  253723798.
15. Milchtaich, Igal (1 de noviembre de 2006). "Topología de red y eficiencia del equilibrio". Juegos y comportamiento económico . 57 (2): 321–346. doi :10.1016/j.geb.2005.09.005. hdl : 10419/259308 . ISSN  0899-8256.
16. Milchtaich, Igal (1 de febrero de 2005). "Condiciones topológicas para la unicidad del equilibrio en redes". Matemáticas de la investigación de operaciones . 30 (1): 225–244. doi :10.1287/moor.1040.0122. ISSN  0364-765X.
17. Holzman, Ron; Law-Yone, Nissan (1997-10-01). "Equilibrio fuerte en juegos de congestión". Juegos y comportamiento económico . 21 (1): 85–101. doi :10.1006/game.1997.0592. ISSN  0899-8256.
18. Richman, Oran; Shimkin, Nahum (1 de febrero de 2007). "Singularidad topológica del equilibrio de Nash para enrutamiento egoísta con usuarios atómicos". Matemáticas de la investigación de operaciones . 32 (1): 215–232. doi :10.1287/moor.1060.0229. ISSN  0364-765X.
19. Fotakis, Dimitris; Kontogiannis, Spyros; Spirakis, Paul (8 de diciembre de 2005). "Flujos egoístas indivisibles". Ciencias de la computación teórica . Autómatas, lenguajes y programación: algoritmos y complejidad (ICALP-A 2004). 348 (2): 226–239. doi :10.1016/j.tcs.2005.09.024. ISSN  0304-3975.
20. Panagopoulou, Panagiota N.; Spirakis, Paul G. (9 de febrero de 2007). "Algoritmos para equilibrios de Nash puros en juegos de congestión ponderada". Revista ACM de algorítmica experimental . 11 : 2,7–es. doi :10.1145/1187436.1216584. ISSN  1084-6654. S2CID  17903962.
21. Harks, Tobias; Klimm, Max; Möhring, Rolf H. (1 de julio de 2011). "Caracterización de la existencia de funciones potenciales en juegos de congestión ponderados". Teoría de sistemas informáticos . 49 (1): 46–70. doi :10.1007/s00224-011-9315-x. ISSN  1433-0490. S2CID  912932.
22. Harks, Tobias; Klimm, Max (1 de agosto de 2012). "Sobre la existencia de equilibrios de Nash puros en juegos de congestión ponderados". Matemáticas de la investigación de operaciones . 37 (3): 419–436. doi :10.1287/moor.1120.0543. ISSN  0364-765X.
23. Kollias, Konstantinos; Roughgarden, Tim (2011). "Restauración de equilibrios puros en juegos de congestión ponderada". En Aceto, Luca; Henzinger, Monika; Sgall, Jiří (eds.). Autómatas, lenguajes y programación . Apuntes de clase en informática. Vol. 6756. Berlín, Heidelberg: Springer. págs. 539–551. doi :10.1007/978-3-642-22012-8_43. ISBN 978-3-642-22012-8.
24. Ackermann, Heiner; Röglin, Heiko; Vöcking, Berthold (6 de abril de 2009). "Equilibrios de Nash puros en juegos de congestión ponderada y específicos para cada jugador". Ciencias de la Computación Teórica . Economía de Internet y Redes. 410 (17): 1552–1563. doi : 10.1016/j.tcs.2008.12.035 . ISSN  0304-3975.
25. Panagopoulou, Panagiota N.; Spirakis, Paul G. (9 de febrero de 2007). "Algoritmos para equilibrios de Nash puros en juegos de congestión ponderada". Revista ACM de algorítmica experimental . 11 : 2,7–es. doi :10.1145/1187436.1216584. ISSN  1084-6654. S2CID  17903962.
26. Milchtaich, Igal (1998-12-01). "Los juegos de aglomeración se pueden resolver de forma secuencial". Revista internacional de teoría de juegos . 27 (4): 501–509. doi :10.1007/s001820050086. ISSN  1432-1270. S2CID  125221.
27. Milchtaich, Igal (2000). "Singularidad genérica del equilibrio en juegos de gran concentración". Matemáticas de la investigación de operaciones . 25 (3): 349–364. doi :10.1287/moor.25.3.349.12220. ISSN  0364-765X. JSTOR  3690472.
28. Konishi, Hideo; Le Breton, Michel; Weber, Shlomo (1 de enero de 1997). "Equilibrios en un modelo con rivalidad parcial". Revista de teoría económica . 72 (1): 225–237. doi :10.1006/jeth.1996.2203. ISSN  0022-0531.
29. Konishi, Hideo; Le Breton, Michel; Weber, Shlomo (1997-10-01). "Equilibrio de Nash de estrategia pura en un juego de formación de grupos con externalidades positivas". Juegos y comportamiento económico . 21 (1): 161–182. doi :10.1006/game.1997.0542. ISSN  0899-8256.
30. Even-Dar, Eyal; Kesselman, Alex; Mansour, Yishay (2003). "Tiempo de convergencia a equilibrios de Nash". En Baeten, Jos CM; Lenstra, Jan Karel; Parrow, Joachim; Woeginger, Gerhard J. (eds.). Autómatas, lenguajes y programación . Apuntes de clase en informática. Vol. 2719. Berlín, Heidelberg: Springer. págs. 502–513. doi :10.1007/3-540-45061-0_41. ISBN 978-3-540-45061-0.
31. Libman, Lavy; Orda, Ariel (1 de agosto de 2001). "Compartir recursos atómicos en redes no cooperativas". Sistemas de telecomunicaciones . 17 (4): 385–409. doi :10.1023/A:1016770831869. ISSN  1572-9451.
32. Brown, Joel S. (1990). "La selección del hábitat como un juego evolutivo". Evolución . 44 (3): 732–746. doi :10.2307/2409448. ISSN  0014-3820. JSTOR  2409448. PMID  28567976.
33. Milchtaich, Igal (1 de noviembre de 2009). "Juegos de congestión ponderada con preferencias separables". Juegos y comportamiento económico . 67 (2): 750–757. doi :10.1016/j.geb.2009.03.009. hdl : 10419/96071 . ISSN  0899-8256.
34. Fabrikant, Alex; Papadimitriou, Christos; Talwar, Kunal (13 de junio de 2004). "La complejidad de los equilibrios de Nash puros". Actas del trigésimo sexto simposio anual de la ACM sobre teoría de la computación . STOC '04. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 604–612. doi :10.1145/1007352.1007445. ISBN 978-1-58113-852-8.S2CID 1037326  .
35. Facchini, Giovanni; van Megen, Freek; Borm, Peter; Tijs, Stef (1997-03-01). "MODELOS DE CONGESTIÓN Y JUEGOS POTENCIALES BAYESIANOS PONDERADOS". Teoría y decisión . 42 (2): 193–206. doi :10.1023/A:1004991825894. ISSN  1573-7187. S2CID  123623707.
36. Mavronicolas, Marios; Milchtaich, Igal; Monien, Burkhard; Tiemann, Karsten (2007). "Juegos de congestión con constantes específicas del jugador". En Kučera, Luděk; Kučera, Antonín (eds.). Fundamentos matemáticos de la informática 2007. Apuntes de clase en informática. Vol. 4708. Berlín, Heidelberg: Springer. págs. 633–644. doi :10.1007/978-3-540-74456-6_56. ISBN 978-3-540-74456-6.
37. Gairing, Martin; Monien, Burkhard; Tiemann, Karsten (2006). "Enrutamiento de flujo (no) divisible en juegos con funciones de latencia lineal específicas del jugador". En Bugliesi, Michele; Preneel, Bart; Sassone, Vladimiro; Wegener, Ingo (eds.). Autómatas, lenguajes y programación . Apuntes de clase en informática. Vol. 4051. Berlín, Heidelberg: Springer. págs. 501–512. doi :10.1007/11786986_44. ISBN . 978-3-540-35905-0.
38. Fabrikant, Alex; Papadimitriou, Christos; Talwar, Kunal (13 de junio de 2004). "La complejidad de los equilibrios de Nash puros". Actas del trigésimo sexto simposio anual de la ACM sobre teoría de la computación . STOC '04. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 604–612. doi :10.1145/1007352.1007445. ISBN 978-1-58113-852-8.S2CID 1037326  .
39. Caragiannis, Ioannis; Fanelli, Angelo; Gravin, Nick; Skopalik, Alexander (1 de octubre de 2011). "Cálculo eficiente de equilibrios de Nash puros aproximados en juegos de congestión". 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science . págs. 532–541. arXiv : 1104.2690 . doi :10.1109/FOCS.2011.50. ISBN 978-0-7695-4571-4. Número de identificación del sujeto  14879292.
40. Fortune, Steven; Hopcroft, John; Wyllie, James (1980-02-01). "El problema del homeomorfismo del subgrafo dirigido". Ciencias de la Computación Teórica . 10 (2): 111–121. doi : 10.1016/0304-3975(80)90009-2 . ISSN  0304-3975.
41. Caragiannis, Ioannis; Fanelli, Angelo; Gravin, Nick; Skopalik, Alexander (27 de marzo de 2015). "Equilibrios de Nash puros aproximados en juegos de congestión ponderados: existencia, computación eficiente y estructura". ACM Transactions on Economics and Computation . 3 (1): 2:1–2:32. doi :10.1145/2614687. ISSN  2167-8375. S2CID  5581666.
42. Kukushkin, NS; Men'Shikov, IS; Men'Shikova, OR; Morozov, VV (1990). "Juegos de asignación de recursos". Matemáticas computacionales y modelado . 1 (4): 433. doi :10.1007/BF01128293. S2CID  120639586.
43. Fotakis, Dimitris; Kontogiannis, Spyros; Spirakis, Paul (2006). "Juegos de congestión atómica entre coaliciones". En Bugliesi, Michele; Preneel, Bart; Sassone, Vladimiro; Wegener, Ingo (eds.). Autómatas, lenguajes y programación . Apuntes de clase en informática. Vol. 4051. Berlín, Heidelberg: Springer. págs. 572–583. doi :10.1007/11786986_50. ISBN . 978-3-540-35905-0.
44. Milinski, Manfred (26 de abril de 2010). "Una estrategia de alimentación evolutivamente estable en los espinosos". Zeitschrift für Tierpsychologie . 51 (1): 36–40. doi :10.1111/j.1439-0310.1979.tb00669.x.

Enlaces externos

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