juego de congestión

Clase de juegos en 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 actores que necesitan recursos (por ejemplo, conductores o usuarios de la red); cada jugador elige un subconjunto de estos recursos (por ejemplo, una ruta en la red); el retraso en cada recurso está determinado por la cantidad de jugadores que eligen un subconjunto que contiene este recurso. El coste 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 demás, 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 cada 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. Investigaciones posteriores se centraron en cuestiones 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 donde dos jugadores se originan en un punto y necesitan llegar al mismo . Supongamos que el nodo está conectado al nodo a través de dos caminos: - - y - - , donde está un poco más cerca que (es decir, es más probable que lo elija cada jugador), 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}$

Los caminos desde 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 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 jugadores y cuándo van allí es . ${\displaystyle T}$ ${\displaystyle A}$ ${\displaystyle T}$ ${\displaystyle B}$ ${\displaystyle T}$ ${\displaystyle x}$ ${\displaystyle x^{2}}$

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?

La siguiente matriz expresa los costes 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 este jugador (tenga en cuenta que los valores en la tabla son costos, por lo que los jugadores los prefieren). ser más pequeño). En este ejemplo, el equilibrio de Nash es eficiente : los jugadores eligen carriles diferentes y la suma de costos es mínima.

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

Ahora, el único equilibrio puro de Nash es (OAT,OAT): cualquier jugador que cambie a OBT aumenta su coste de 2,6 a 2,8. Todavía existe un equilibrio, pero no es eficiente: la suma de los costos es 5,2, mientras que la suma de los costos 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 conjunto 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. Estos 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 retraso (también llamada función de latencia o función de costo ). Dado un vector de estrategias, el retraso es . Se supone que cada uno es positivo y monótono 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 , reemplazarlo 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 asigne un valor a cada resultado. ^[1] 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 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})}$

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 en , y los elementos a los que se une el jugador (es decir, ) aumentan el potencial en . Este cambio de potencial es precisamente el cambio de retraso 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\in 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 los jugadores menos a uno, 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}}$

La existencia de una función potencial tiene una implicación adicional, llamada propiedad de mejora finita (FIP) . Si comenzamos con cualquier vector de estrategia, elegimos un jugador arbitrariamente y le permitimos cambiar su estrategia a una mejor estrategia para él, y repetimos, entonces la secuencia de mejoras debe ser finita (es decir, la secuencia no circulará). Esto se debe a que cada mejora 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, como . Hay un continuo de jugadores, los jugadores se consideran "infinitesimalmente pequeños" y cada jugador individual tiene un efecto insignificante sobre 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 fraccionalmente sobre su conjunto de estrategias. Es decir, para cada estrategia , denotemos la fracción de jugadores del tipo que utilizan 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 usan 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 estrategias . 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}$

En función de la estrategia, es continua: es continua por supuesto y es una función continua de la estrategia. Luego, según 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 efectivamente un equilibrio de Nash. Supongamos por contradicción que existe un conjunto de equilibrios que minimizan pero que no son de Nash. Entonces, para algún tipo , existe alguna mejora con respecto a la elección actual . Eso es, . La idea ahora es tomar una pequeña cantidad de jugadores que usan la estrategia y moverlos hacia la estrategia . Ahora, para cualquiera , hemos aumentado su carga en , por lo que su término es ahora . Derivando la integral, este cambio es aproximadamente , con 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, 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 determinada carga que transferir. Al igual que en los CG no atómicos, cada jugador puede dividir su carga en cargas fraccionarias que recorren 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 sobre 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]} Muestran 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 monotonicidad 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 ponderados

En un CG ponderado , diferentes jugadores pueden tener diferentes efectos sobre la congestión. Por ejemplo, en una red de carreteras, un camión añade mucho más congestión 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 peso , y la carga sobre el recurso e es . Un caso especial importante es cuando el peso depende solo del jugador ( pesos independientes de los recursos ), 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 CG ponderados en los que cada estrategia es un recurso único ("CG único"), los pesos son independientes de los recursos y todos los jugadores tienen el mismo conjunto de estrategias. Se prueba lo siguiente:

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

CG de red ponderados

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

En particular, decimos que un determinado gráfico G garantiza una determinada propiedad si cada red ponderada CG en la que la red subyacente es G tiene esa propiedad. Milchtaich ^[14] caracterizó redes que garantizan la existencia de PNE, así como la propiedad de mejora finita, con la condición adicional de que un jugador con menor peso tenga 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 uno o dos de un solo borde. redes. ^{: Thm.2}
• Un gráfico G garantiza la existencia de un PNE 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é integrada en G. ^{: Thm.3}

En el caso especial en el que a cada jugador se le permite utilizar cualquier estrategia ("bordes públicos"), existen más redes que garantizan la existencia de PNE; una caracterización completa de tales 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 eficiente en el sentido de Pareto, si y solo tres "redes prohibidas" simples no están integradas en G.
• Un gráfico G garantiza que la paradoja de Braess no ocurre, si y solo se trata de un gráfico serie-paralelo .

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

• Un gráfico G garantiza que los costes PNE son únicos 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 G contiene una red integrada 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 eficiente en el sentido de Pareto .

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 determinada 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] prueban que la clase de funciones lineales garantiza la existencia de un potencial exacto y, por 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 tanto, la existencia de PNE.
• Harks, Klimm y Mohring ^[21] demuestran que una clase de funciones garantiza la existencia de un potencial exacto, si y sólo si contiene sólo 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 sólo si (1) contiene sólo funciones afines, o (2) contiene sólo funciones exponenciales de la forma , donde es el mismo 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 sólo si todas las funciones que contiene 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 sólo si (1) contiene sólo funciones afines, o (2) contiene sólo funciones exponenciales. funciones del formulario , donde es el mismo para todos los recursos. Esta caracterización sigue siendo válida cuando se limita a juegos de tres jugadores. Para juegos de dos jugadores, una clase de funciones garantiza la existencia de PNE si y sólo si todas las funciones que contiene tienen 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 ponderada. ^{[23] [24] [25]}

Funciones de costos específicas del jugador

El modelo CG básico se puede ampliar permitiendo que la función de retardo de cada recurso dependa del jugador. Entonces, para cada recurso e y jugador i , hay una función de retraso . 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 del jugador en CG singleton (juegos multitudinarios)

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

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

Este caso especial de CG también se denomina juego de multitud . ^{[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 multitudinario, 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 iff para cada jugador i, para todos 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 del 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 retardo:

• ${\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)}$

El siguiente es un camino de mejora cíclica: . Esto muestra 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 de 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] : Thm.1} Por tanto, existe un PNE.
• Con sólo dos jugadores, cada propiedad finita de mejor respuesta se cumple. Por tanto, existe una PNE.

Cuando hay tres o más actores, 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 la mayoría de los pasos. Además, todo CG es débilmente acíclico : para cualquier vector de estrategia inicial, al menos una ruta de mejor respuesta que comienza en este vector tiene una longitud máxima de , que termina en un equilibrio. ^{[9] : Thm.3} ${\displaystyle {n+1 \choose 2}}$ ${\displaystyle r{n+1 \choose 2}}$

Cada juego de aglomeración tiene solución secuencial . ^[26] Esto significa que, para cada orden de los jugadores, el juego secuencial en el que cada jugador, a su vez, elige una estrategia tiene un equilibrio perfecto en subjuegos en el que las acciones de los jugadores son un ENP en el juego simultáneo original. Cada juego de crowding tiene al menos un PNE fuerte ; ^[28] cada PNE fuerte de un juego de aglomeración puede alcanzarse como un equilibrio perfecto en subjuegos de una versión secuencial del juego. ^[26]

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

Funciones de costos separables

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

• Funciones de costo multiplicativamente separables : , 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 sólo 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 recursos, la configuración con funciones de retraso específicas de recursos se puede reducir a la configuración con una función de retraso universal. Los juegos con funciones de costos separables ocurren en el equilibrio de carga, ^[30] colas M/M/1 , ^[31] y selección de hábitat . ^[32] Se sabe lo siguiente acerca de 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 se aplica si los costos base son independientes de los recursos ( para cada recurso e ). ^{[30] [34]} La prueba se basa en una función potencial valorada por un vector. 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. Cada vez que un jugador se desvía hacia un recurso con un coste menor para él, el vector de costes 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 las ponderaciones son independientes del jugador (de manera equivalente: el CG no está ponderado y las funciones de retardo son específicas de los recursos), entonces tiene el FIP y, por lo tanto, tiene un PNE. ^{[35] [29]} Si las funciones de costos son separables aditivamente, entonces el juego incluso tiene una función potencial exacta. El resultado se mantiene incluso si las funciones de costos no aumentan monótonamente con la carga. Si las funciones de costos no son separables aditivamente, entonces la FIP puede no cumplirse y puede que no haya una función potencial, pero aún existe una PNE. ^{[9] : Thm.2}
• Si las ponderaciones son independientes de los recursos, entonces existe un PNE en los siguientes casos:
  • Cuando hay como máximo tres jugadores, existe un PNE, ^{[36] : Cor.3} , aunque la propiedad de mejora de la mejor respuesta podría no cumplirse. Por el contrario, hay un CG con costos separables y ponderaciones independientes de los recursos con ocho actores en el que no existe ninguna ENP. ^{[33] : Thm.3}
  • Cuando las funciones de costos son separables aditivamente con funciones lineales de costos variables, el CG tiene un potencial ponderado, por lo tanto tiene el FIP y, por lo tanto, tiene un PNE. ^{[36] : Thm.6}
  • Cuando las funciones de costos son separables de forma aditiva 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 un PNE. Sin embargo, es posible que no tenga la propiedad de mejora finita. ^[37] Para más de tres actores, la existencia del PNE está abierta.

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

CG en red con costos específicos para cada jugador

Milchtaich consideró el caso especial de los CG con costes específicos para cada jugador, en los que cada estrategia es un camino en un gráfico determinado ("CG de red"). Demostró que todo juego finito puede representarse como un juego de congestión de red (no ponderado) con costos específicos para el jugador, con funciones de costos no decrecientes (pero no necesariamente negativas). ^[10] Una caracterización completa de las redes que garantizan la existencia de PNE en dichos GC se plantea como un problema abierto. ^[14]

Calcular un equilibrio de Nash puro

Calcular un equilibrio en CG no ponderados

La prueba de la existencia de PNE es constructiva: muestra un algoritmo finito (un camino 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 polinómico maximizando el potencial, mediante la reducción a mínimos. flujo de costos . El algoritmo se puede adaptar a CG no atómicos: bajo ciertos supuestos de suavidad, un equilibrio de Nash en un juego de este tipo se puede aproximar en un 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 .
• Todo problema de la clase PLS puede presentarse como un juego cuyos equilibrios puros se garantizan 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 aproximación de factor constante PNE. En particular:

• Con funciones de retardo lineal, la relación de aproximación es 2+ε y el tiempo de ejecución es polinómico en el número de reproductores, 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 polinomial de PNE es PLS completo.

Calcular 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 lineal, encuentra un PNE en tiempo pseudopolinomial (polinomio en el número de jugadores n y la suma de los pesos de los jugadores W ). Su algoritmo es un algoritmo codicioso de mejor respuesta : 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 tiempo polinómico 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 un PNE. Milchtaich ^[14] demuestra que decidir si una determinada red ponderada CG tiene un PNE es NP-difícil incluso en los siguientes casos:

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

La prueba es por reducción del problema de caminos disjuntos de borde dirigido. ^[40]

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

• Con funciones de retardo lineal, la relación de aproximación es y el tiempo de ejecución es polinomio en el número de reproductores, 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 probar sus resultados, muestran 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 mostrar que cada CG ponderado tiene un PNE aproximado ( d !). Su algoritmo identifica una secuencia corta de movimientos de mejor respuesta, que conduce a un PNE tan aproximado.

Resumen de clasificaciones de juegos de congestión.

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

• Número y capacidad de división de los jugadores: CG atómico , CG divisible o CG no atómico ;
• Peso de los jugadores: CG no ponderado o CG ponderado (con ponderaciones independientes de los recursos o ponderaciones específicas de los recursos );
• Funciones de costos para diferentes jugadores que usan el mismo recurso: idénticas o específicas de cada jugador (con funciones de costos 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 ).

Ver también

• Dado que todo 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 algo relacionados con los juegos de congestión.
• Información incompleta : Facchini, van Megen, Borm y Tijs ^[35] extienden el modelo de Rosenthal a un entorno con información incompleta . Demuestran que los juegos bayesianos relacionados son juegos potenciales y, por 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 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 alimentos, 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 la 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/juego.1996.0044. ISSN  0899-8256.
3. Milchtaich, Igal (1996). "Modelos de competencia con congestión". El naturalista americano . 147 (5): 760–783. doi :10.1086/285878. ISSN  0003-0147. JSTOR  2463089. S2CID  55004212.
4. Friedman, Eric J. (1 de septiembre de 1996). "Dinámica y racionalidad en juegos ordenados de externalidades". Juegos y comportamiento económico . 16 (1): 65–76. doi : 10.1006/juego.1996.0074. ISSN  0899-8256.
5. Blonski, Matías (1 de agosto de 1999). "Juegos anónimos con acciones binarias". Juegos y comportamiento económico . 28 (2): 171–180. doi : 10.1006/juego.1998.0699. ISSN  0899-8256.
6. Jardín áspero, Tim; Tardos, Éva (1 de mayo de 2004). "Limitar la ineficiencia de los equilibrios en juegos de congestión no atómicas". 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. (1 de octubre de 1993). "Enrutamiento competitivo en redes de comunicación multiusuario". Transacciones IEEE/ACM en redes . 1 (5): 510–521. doi : 10.1109/90.251910. ISSN  1558-2566. S2CID  1184436.
8. Jardín áspero, Tim; Schoppmann, Florian (1 de marzo de 2015). "La suavidad local y el precio de la anarquía en los juegos de congestión divisibles". Revista de teoría económica . Informática y Teoría Económica. 156 : 317–342. doi :10.1016/j.jet.2014.04.005. ISSN  0022-0531.
9. Milchtaich, Igal (1 de marzo de 1996). "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/juego.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). "Hundimiento de equilibrios y convergencia". 46.º Simposio anual del IEEE sobre fundamentos de la informática (FOCS'05) . págs. 142-151. doi :10.1109/SFCS.2005.68. ISBN 0-7695-2468-0. S2CID  17850062.
13. Milchtaich, Igal (2006). "El problema de la existencia del equilibrio en los juegos de congestión de redes finitas". En Spirakis, Paul; Mavronicolas, Marios; Kontogiannis, Spyros (eds.). Internet y economía de redes . Apuntes de conferencias sobre 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 (1 de octubre de 1997). "Fuerte equilibrio en los juegos de congestión". Juegos y comportamiento económico . 21 (1): 85-101. doi : 10.1006/juego.1997.0592. ISSN  0899-8256.
18. Richman, Orán; Shimkin, Nahum (1 de febrero de 2007). "Singularidad topológica del equilibrio de Nash para el 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 e indivisibles". Informática 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. Escucha, Tobías; Klimm, Max; Möhring, Rolf H. (1 de julio de 2011). "Caracterización de la existencia de funciones potenciales en juegos de congestión ponderada". Teoría de los Sistemas Computacionales . 49 (1): 46–70. doi :10.1007/s00224-011-9315-x. ISSN  1433-0490. S2CID  912932.
22. Escucha, Tobías; Klimm, Max (1 de agosto de 2012). "Sobre la existencia de equilibrios puros de Nash en juegos de congestión ponderada". Matemáticas de la Investigación de Operaciones . 37 (3): 419–436. doi :10.1287/moor.1120.0543. ISSN  0364-765X.
23. Kollias, Konstantinos; Jardín áspero, Tim (2011). "Restauración del equilibrio puro en los juegos de congestión ponderada". En Aceto, Luca; Henzinger, Mónica; Sgall, Jiří (eds.). Autómatas, Lenguajes y Programación . Apuntes de conferencias sobre 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 puros de Nash en juegos de congestión ponderados y específicos de jugadores". Informática Teórica . Internet y economía de 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 (1 de diciembre de 1998). "Los juegos de multitud se pueden resolver secuencialmente". 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 grandes juegos multitudinarios". 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 Bretón, 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 Bretón, Michel; Weber, Shlomo (1 de octubre de 1997). "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/juego.1997.0542. ISSN  0899-8256.
30. Even-Dar, Eyal; Kesselman, Alex; Mansour, Yishay (2003). "Tiempo de convergencia para los equilibrios de Nash". En Baeten, José CM; Lenstra, Jan Karel; Parrow, Joaquín; Woeginger, Gerhard J. (eds.). Autómatas, Lenguajes y Programación . Apuntes de conferencias sobre 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. Marrón, Joel S. (1990). "La selección de hábitat como 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 ponderados 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. Fabricante, 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 ACM sobre teoría de la informática . ESTOC '04. Nueva York, NY, EE.UU.: Asociación de Maquinaria de Computación. págs. 604–612. doi :10.1145/1007352.1007445. ISBN 978-1-58113-852-8. S2CID  1037326.
35. Facchini, Giovanni; van Megen, Freek; Borm, Pedro; Tijs, Stef (1 de marzo de 1997). "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 conferencias sobre 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, Martín; 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 conferencias sobre informática. vol. 4051. Berlín, Heidelberg: Springer. págs. 501–512. doi :10.1007/11786986_44. ISBN 978-3-540-35905-0.
38. Fabricante, 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 ACM sobre teoría de la informática . ESTOC '04. Nueva York, NY, EE.UU.: Asociación de Maquinaria de Computación. págs. 604–612. doi :10.1145/1007352.1007445. ISBN 978-1-58113-852-8. S2CID  1037326.
39. Caragiannis, Ioannis; Fanelli, Ángel; Gravin, Nick; Skopalik, Alejandro (1 de octubre de 2011). "Cálculo eficiente de equilibrios de Nash puros aproximados en juegos de congestión". 2011 52º Simposio Anual del IEEE sobre Fundamentos de la Informática . págs. 532–541. arXiv : 1104.2690 . doi :10.1109/FOCS.2011.50. ISBN 978-0-7695-4571-4. S2CID  14879292.
40. Fortuna, Steven; Hopcroft, John; Wyllie, James (1 de febrero de 1980). "El problema del homeomorfismo del subgrafo dirigido". Informática Teórica . 10 (2): 111–121. doi : 10.1016/0304-3975(80)90009-2 . ISSN  0304-3975.
41. Caragiannis, Ioannis; Fanelli, Ángel; Gravin, Nick; Skopalik, Alejandro (27 de marzo de 2015). "Equilibrios de Nash puros aproximados en juegos de congestión ponderados: existencia, computación eficiente y estructura". Transacciones ACM sobre Economía y Computación . 3 (1): 2:1–2:32. doi :10.1145/2614687. ISSN  2167-8375. S2CID  5581666.
42. Kukushkin, NS; Men'Shikov, IS; Men'Shikova, OR; Morózov, VV (1990). "Juegos de asignación de recursos". Matemática Computacional 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 conferencias sobre 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

• Apuntes de conferencias de Yishay Mansour sobre juegos de potencial y congestión
• Apuntes de conferencias 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.