El precio de la anarquía

El Precio de la Anarquía ( PoA ) ^[1] es un concepto en economía y teoría de juegos que mide cómo se degrada la eficiencia de un sistema debido al comportamiento egoísta de sus agentes. Es una noción general que puede extenderse a diversos sistemas y nociones de eficiencia. Por ejemplo, consideremos el sistema de transporte de una ciudad y muchos agentes que intentan ir desde un lugar inicial a un destino. Aquí, eficiencia significa el tiempo promedio que tarda un agente en llegar al destino. En la solución "centralizada", una autoridad central puede indicar a cada agente qué camino tomar para minimizar el tiempo medio de viaje. En la versión 'descentralizada', cada agente elige su propio camino. El Precio de la Anarquía mide la relación entre el tiempo medio de viaje en los dos casos.

Generalmente el sistema se modela como un juego y la eficiencia es alguna función de los resultados (por ejemplo, retraso máximo en una red, congestión en un sistema de transporte, bienestar social en una subasta, etc.). Se pueden utilizar diferentes conceptos de equilibrio para modelar el comportamiento egoísta de los agentes, entre los cuales el más común es el equilibrio de Nash . Diferentes tipos de equilibrio de Nash conducen a variaciones de la noción de Precio de la Anarquía como Precio de la Anarquía Puro (para equilibrios deterministas), Precio de la Anarquía Mixto (para equilibrios aleatorios) y Precio de la Anarquía de Bayes-Nash (para juegos con información incompleta) . Conceptos de solución distintos del equilibrio de Nash conducen a variaciones como el precio de hundimiento . ^[2]

El término Precio de la Anarquía fue utilizado por primera vez por Elias Koutsoupias y Christos Papadimitriou , ^{[1] [3]} pero la idea de medir la ineficiencia del equilibrio es más antigua. ^[4] El concepto en su forma actual fue diseñado para ser el análogo del 'índice de aproximación' en un algoritmo de aproximación o el 'índice competitivo' en un algoritmo en línea . Esto es en el contexto de la tendencia actual de analizar juegos utilizando lentes algorítmicas ( teoría algorítmica de juegos ).

Definición matemática

Consideremos un juego , definido por un conjunto de jugadores , conjuntos de estrategias para cada jugador y utilidades ( también llamado conjunto de resultados). Podemos definir una medida de eficiencia de cada resultado que llamamos función de bienestar . Los candidatos naturales incluyen la suma de las utilidades de los jugadores (objetivo utilitario), la utilidad mínima (objetivo de equidad u igualitario) ..., o cualquier función que sea significativa para el juego particular que se analiza y que sea deseable maximizar. ${\displaystyle G=(N,S,u)}$ ${\displaystyle N}$ ${\displaystyle S_{i}}$ ${\displaystyle u_{i}:S\rightarrow \mathbb {R} }$ ${\displaystyle S=S_{1}\times ...\times S_{n}}$ ${\displaystyle \operatorname {Welf} :S\rightarrow \mathbb {R} }$ ${\displaystyle \operatorname {Welf} (s)=\sum _{i\in N}u_{i}(s),}$ ${\displaystyle \operatorname {Welf} (s)=\min _{i\in N}u_{i}(s),}$

Podemos definir un subconjunto como el conjunto de estrategias en equilibrio (por ejemplo, el conjunto de equilibrios de Nash ). El precio de la anarquía se define entonces como la relación entre la solución "centralizada" óptima y el "peor equilibrio": ${\displaystyle Equil\subseteq S}$

${\displaystyle PoA={\frac {\max _{s\in S}\operatorname {Welf} (s)}{\min _{s\in Equil}\operatorname {Welf} (s)}}}$

Si, en lugar de un 'bienestar' que queremos 'maximizar', la función que mide la eficiencia es una 'función de costos' que queremos 'minimizar' (por ejemplo, retraso en una red), usamos (siguiendo la convención en algoritmos de aproximación) : ${\displaystyle \operatorname {Cost} :S\rightarrow \mathbb {R} }$

${\displaystyle PoA={\frac {\max _{s\in Equil}\operatorname {Cost} (s)}{\min _{s\in S}\operatorname {Cost} (s)}}}$

Una noción relacionada es la del Precio de Estabilidad ( PoS ), que mide la relación entre la solución "centralizada" óptima y el "mejor equilibrio":

${\displaystyle PoS={\frac {\max _{s\in S}\operatorname {Welf} (s)}{\max _{s\in Equil}\operatorname {Welf} (s)}}}$

o en el caso de funciones de costos:

${\displaystyle PoS={\frac {\min _{s\in Equil}\operatorname {Cost} (s)}{\min _{s\in S}\operatorname {Cost} (s)}}}$

Lo sabemos por la definición. Se espera que la pérdida de eficiencia debido a las restricciones de la teoría de juegos esté en algún punto entre 'PoS' y 'PoA'. ${\displaystyle 1\leq PoS\leq PoA}$

Ejemplos

El dilema del prisionero

Considere el juego 2x2 llamado dilema del prisionero , dado por la siguiente matriz de costos:

y sea la función de costos. Ahora, el peor (y único) equilibrio de Nash sería cuando ambos jugadores desertan y el costo resultante es . Sin embargo, el mayor bienestar social se produce cuando ambos cooperan, en cuyo caso el costo es . Por tanto, el PoA de este juego será . ${\displaystyle C(s_{1},s_{2})=u_{1}(s_{1},s_{2})+u_{2}(s_{1},s_{2}).}$ ${\displaystyle C_{equil}=5+5=10}$ ${\displaystyle C_{min}=1+1=2}$ ${\displaystyle C_{equil}/C_{min}=10/2=5}$

Dado que el juego tiene un equilibrio de Nash único, el PoS es igual al PoA y también es 5.

programación de trabajos

Un ejemplo más natural es el de la programación del trabajo . Hay jugadores y cada uno de ellos tiene un trabajo que ejecutar. Pueden elegir una de las máquinas para ejecutar el trabajo. El precio de la anarquía compara la situación en la que la selección de máquinas está guiada/dirigida centralmente con la situación en la que cada jugador elige la máquina que hará que su trabajo se ejecute más rápido. ${\displaystyle N}$ ${\displaystyle M}$

Cada máquina tiene una velocidad. Cada trabajo tiene un peso. Un jugador elige una máquina para ejecutar su trabajo. Entonces, las estrategias de cada jugador son Definir la carga en la máquina como: ${\displaystyle s_{1},\ldots ,s_{M}>0.}$ ${\displaystyle w_{1},\ldots ,w_{N}>0.}$ ${\displaystyle A_{i}=\{1,2,\ldots ,M\}.}$ ${\displaystyle j}$

${\displaystyle L_{j}(a)={\frac {\sum _{i:a_{i}=j}w_{i}}{s_{j}}}.}$

El coste para el jugador es , por ejemplo, la carga de la máquina que eligió. Consideramos la función de costos igualitarios , aquí llamada makepan . ${\displaystyle i}$ ${\displaystyle c_{i}(a)=L_{a_{i}}(a),}$ ${\displaystyle {\mbox{MS}}(a)=\max _{j}L_{j}(a)}$

Consideramos dos conceptos de equilibrio: Nash puro y Nash mixto . Debe quedar claro que PoA mixto ≥ PoA puro, porque cualquier equilibrio de Nash puro es también un equilibrio de Nash mixto (esta desigualdad puede ser estricta: por ejemplo, cuando , , y , las estrategias mixtas alcanzan un makespan promedio de 1,5, mientras que cualquier equilibrio de Nash puro La estrategia PoA en este entorno es ). Primero debemos argumentar que existen equilibrios de Nash puros. ${\displaystyle N=2}$ ${\displaystyle w_{1}=w_{2}=1}$ ${\displaystyle M=2}$ ${\displaystyle s_{1}=s_{2}=1}$ ${\displaystyle \sigma _{1}=\sigma _{2}=(1/2,1/2)}$ ${\displaystyle \leq 4/3}$

Afirmar . Para cada juego de programación de trabajos, existe al menos un equilibrio de Nash de estrategia pura.

Prueba . Nos gustaría adoptar un perfil de acción socialmente óptimo . Esto significaría simplemente un perfil de acción cuyo período de acción sea mínimo. Sin embargo, esto no será suficiente. Puede haber varios perfiles de acción que conduzcan a una variedad de distribuciones de carga diferentes (todas con la misma carga máxima). Entre estos, nos limitamos aún más a uno que tenga al menos la segunda carga más grande. Nuevamente, esto da como resultado un conjunto de posibles distribuciones de carga, y repetimos hasta la carga más grande (es decir, la más pequeña), donde solo puede haber una distribución de cargas (única hasta la permutación). Esto también se llamaría el vector de carga ordenado más pequeño lexicográfico . ${\displaystyle a^{*}}$ ${\displaystyle M}$

Afirmamos que éste es un equilibrio de Nash de estrategia pura. Razonando por contradicción, supongamos que algún jugador podría mejorar estrictamente pasando de una máquina a otra . Esto significa que la carga aumentada de la máquina después del movimiento es aún menor que la carga de la máquina antes del movimiento. Como la carga de la máquina debe disminuir como resultado del movimiento y ninguna otra máquina se ve afectada, esto significa que se garantiza que la nueva configuración habrá reducido la carga más grande (o de mayor rango) en la distribución. Esto, sin embargo, viola la supuesta minimalidad lexicográfica de . QED ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle j}$ ${\displaystyle j}$ ${\displaystyle j}$ ${\displaystyle a}$

Afirmar . Para cada juego de programación de trabajos, el PoA puro es como máximo . ${\displaystyle M}$

Prueba . Es fácil elevar el límite superior del bienestar obtenido en cualquier equilibrio de Nash de estrategia mixta mediante ${\displaystyle \sigma }$

${\displaystyle w(\sigma )\leq {\frac {\sum _{i}{w_{i}}}{\max _{j}{s_{j}}}}.}$

Consideremos, para mayor claridad de exposición, cualquier perfil de acción de estrategia pura : claramente ${\displaystyle a}$

${\displaystyle w(a)\geq {\frac {\sum _{i}{w_{i}}}{\sum _{j}{s_{j}}}}\geq {\frac {\sum _{i}{w_{i}}}{M\cdot \max _{j}{s_{j}}}}.}$

Dado que lo anterior también es válido para el óptimo social, comparar las proporciones prueba la afirmación. QED ${\displaystyle w(\sigma )}$ ${\displaystyle w(a)}$

Ruta egoísta

La paradoja de Braess

Considere una red de carreteras como la que se muestra en el diagrama adyacente por la que 4000 conductores desean viajar desde el principio hasta el final. El tiempo de viaje en minutos en la carretera Inicio-A es el número de viajeros (T) dividido por 100, y en la carretera Inicio-B es una constante de 45 minutos (lo mismo ocurre con las carreteras frente a ellas). Si la carretera discontinua no existe (por lo que la red de tráfico tiene 4 carreteras en total), el tiempo necesario para recorrer la ruta Inicio-A-Fin con conductores sería . El tiempo necesario para recorrer la ruta Inicio-B-Fin con conductores sería . Como hay 4000 impulsores, el hecho de que se puede utilizar para derivar el hecho de que cuando el sistema está en equilibrio. Por tanto, cada ruta tarda unos minutos. Si cualquiera de las rutas tomara menos tiempo, no sería un equilibrio de Nash: un conductor racional cambiaría de la ruta más larga a la más corta. ${\displaystyle a}$ ${\displaystyle {\tfrac {a}{100}}+45}$ ${\displaystyle b}$ ${\displaystyle {\tfrac {b}{100}}+45}$ ${\displaystyle a+b=4000}$ ${\displaystyle a=b=2000}$ ${\displaystyle {\tfrac {2000}{100}}+45=65}$

Ahora supongamos que la línea discontinua A–B es una carretera con un tiempo de viaje extremadamente corto de aproximadamente 0 minutos. Supongamos que se abre la carretera y un conductor intenta Iniciar-A-B-Fin. Para su sorpresa descubre que su tiempo son minutos, un ahorro de casi 25 minutos. Pronto, más de los 4.000 conductores intentarán esta nueva ruta. El tiempo empleado sube desde 40.01 y sigue subiendo. Cuando el número de conductores que prueban la nueva ruta llegue a 2500, con 1500 todavía en la ruta Inicio-B-Fin, su tiempo será de minutos, lo que no representa ninguna mejora con respecto a la ruta original. Mientras tanto, esos 1.500 conductores se han reducido a minutos, un aumento de 20 minutos. También están obligados a cambiar a la nueva ruta por la A, por lo que ahora les llevará unos minutos. Nadie tiene ningún incentivo para viajar por A-End o Start-B porque cualquier conductor que los pruebe tardará 85 minutos. Por lo tanto, la apertura de la ruta transversal provoca un cambio irreversible en ella por parte de todos, lo que les cuesta a todos 80 minutos en lugar de los 65 originales. Si todos los conductores aceptaran no usar la ruta A-B, o si esa ruta se cerrara, cada El conductor se beneficiaría de una reducción de 15 minutos en el tiempo de viaje. ${\displaystyle {\tfrac {2000}{100}}+{\tfrac {2001}{100}}=40.01}$ ${\displaystyle {\tfrac {2500}{100}}+{\tfrac {4000}{100}}=65}$ ${\displaystyle 45+{\tfrac {4000}{100}}=85}$ ${\displaystyle {\tfrac {4000}{100}}+{\tfrac {4000}{100}}=80}$

Problema de enrutamiento generalizado

El problema de enrutamiento introducido en la paradoja de Braess se puede generalizar a muchos flujos diferentes que atraviesan el mismo gráfico al mismo tiempo.

Definición (Flujo generalizado) . Sean , y como se definió anteriormente, y supongamos que queremos enrutar las cantidades a través de cada par distinto de nodos en . Un flujo se define como la asignación de un número real no negativo a cada camino que va desde hasta , con la restricción de que ${\displaystyle G=(V,E)}$ ${\displaystyle L}$ ${\displaystyle w}$ ${\displaystyle R=\{r_{1},r_{2},\dots ,r_{k},\;|\;r_{i}>0\}}$ ${\displaystyle \Gamma =\{(s_{1},t_{1}),(s_{2},t_{2}),\dots ,(s_{k},t_{k})\}\subseteq (V\times V)}$ ${\displaystyle f_{\Gamma ,R}}$ ${\displaystyle p\mapsto \Re }$ ${\displaystyle p}$ ${\displaystyle s_{i}}$ ${\displaystyle t_{i}}$ ${\displaystyle \in \Gamma }$

${\displaystyle \sum _{p:\,s_{i}\rightarrow t_{i}}{f_{p}}=r_{i}\;\;\forall (s_{i},t_{i})\in \Gamma .}$

El flujo que atraviesa un borde específico de se define como ${\displaystyle G}$

${\displaystyle f_{e,\Gamma ,R}=\sum _{p:\,e\in p}{f_{p}}.}$

Para ser concisos, escribimos cuando están claros por el contexto. ${\displaystyle f_{e}}$ ${\displaystyle \Gamma ,R}$

Definición (flujo de equilibrio de Nash) . Un flujo es un flujo de equilibrio de Nash si y desde hasta ${\displaystyle f_{\Gamma ,R}}$ ${\displaystyle \forall (s_{i},t_{i})\in \Gamma }$ ${\displaystyle \forall p,q}$ ${\displaystyle s_{i}}$ ${\displaystyle t_{i}}$

${\displaystyle f_{p}>0\Rightarrow \sum _{e\in p}{l_{e}(f_{e})}\leq \sum _{e\in q}{l_{e}(f_{e})}.}$

Esta definición está estrechamente relacionada con lo que dijimos sobre el soporte de los equilibrios de Nash de estrategias mixtas en juegos de forma normal.

Definición (Bienestar condicional de un flujo) . Sean y dos flujos asociados con los mismos conjuntos y . A continuación eliminaremos el subíndice para aclarar la notación. Supongamos que fijamos las latencias inducidas por en el gráfico: el bienestar condicional de con respecto a se define como ${\displaystyle f_{\Gamma ,R}}$ ${\displaystyle f_{\Gamma ,R}^{*}}$ ${\displaystyle G}$ ${\displaystyle \Gamma }$ ${\displaystyle R}$ ${\displaystyle f}$ ${\displaystyle f^{*}}$ ${\displaystyle f}$

${\displaystyle w^{f}(f^{*})=\sum _{e\in E}{f_{e}^{*}\cdot l_{e}(f_{e})}}$

Hecho 1 . Dado un flujo de equilibrio de Nash y cualquier otro flujo , . ${\displaystyle f}$ ${\displaystyle f^{*}}$ ${\displaystyle w(f)=w^{f}(f)\leq w^{f}(f^{*})}$

Prueba (Por contradicción) . Asumir que . Por definición, ${\displaystyle w^{f}(f^{*})<w^{f}(f)}$

${\displaystyle \sum _{i=1}^{k}\sum _{p:s_{i}\rightarrow t_{i}}f_{p}^{*}\cdot \sum _{e\in p}l_{e}(f_{e})<\sum _{i=1}^{k}\sum _{p:s_{i}\rightarrow t_{i}}f_{p}\cdot \sum _{e\in p}l_{e}(f_{e})}$.

Dado que y están asociados con los mismos conjuntos , sabemos que ${\displaystyle f}$ ${\displaystyle f^{*}}$ ${\displaystyle \Gamma ,R}$

${\displaystyle \sum _{p:s_{i}\rightarrow t_{i}}f_{p}=\sum _{p:s_{i}\rightarrow t_{i}}f_{p}^{*}=r_{i}\;\;\forall i.}$

Por lo tanto, debe haber un par y dos caminos desde a tales que , y ${\displaystyle (s_{i},t_{i})}$ ${\displaystyle p,q}$ ${\displaystyle s_{i}}$ ${\displaystyle t_{i}}$ ${\displaystyle f_{p}^{*}>f_{p}}$ ${\displaystyle f_{q}^{*}<f_{q}}$

${\displaystyle \sum _{e\in p}l_{e}(f_{e})<\sum _{e\in q}l_{e}(f_{e}).}$

En otras palabras, el flujo puede lograr un bienestar menor que sólo si hay dos caminos para llegar a tener costos diferentes, y si desvía parte del flujo de la ruta de mayor costo a la de menor costo. Esta situación es claramente incompatible con el supuesto de que se trata de un flujo de equilibrio de Nash. QED ${\displaystyle f^{*}}$ ${\displaystyle f}$ ${\displaystyle s_{i}}$ ${\displaystyle t_{i}}$ ${\displaystyle f^{*}}$ ${\displaystyle f}$ ${\displaystyle f}$

Tenga en cuenta que el hecho 1 no asume ninguna estructura particular en el set . ${\displaystyle L}$

Hecho 2 . Dados dos números reales cualesquiera y , . ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x\cdot y\leq x^{2}+y^{2}/4}$

Prueba . Esta es otra forma de expresar la verdadera desigualdad . QED ${\displaystyle (x-y/2)^{2}\geq 0}$

Teorema . El PoA puro de cualquier problema de enrutamiento generalizado con latencias lineales es . ${\displaystyle (G,L)}$ ${\displaystyle \leq 4/3}$

Prueba . Tenga en cuenta que este teorema equivale a decir que para cada flujo de equilibrio de Nash , donde está cualquier otro flujo. Por definición, ${\displaystyle f}$ ${\displaystyle w(f)\leq (4/3)\cdot \min _{f^{*}}\{w(f^{*})\}}$ ${\displaystyle f^{*}}$

${\displaystyle w^{f}(f^{*})=\sum _{e\in E}f_{e}^{*}(a_{e}\cdot f_{e}+b_{e})}$

${\displaystyle =\sum _{e}(a_{e}f_{e}f_{e}^{*})+\sum _{e\in E}f_{e}^{*}b_{e}.}$

Al utilizar el hecho 2, tenemos que

${\displaystyle w^{f}(f^{*})\leq \sum _{e\in E}\left(a_{e}\cdot \left((f_{e}^{*})^{2}+(f_{e})^{2}/4\right)\right)+\sum _{e\in E}f_{e}^{*}\cdot b_{e}}$

${\displaystyle =\left(\sum _{e\in E}a_{e}(f_{e}^{*})^{2}+f_{e}^{*}b_{e}\right)+\sum _{e\in E}a_{e}(f_{e})^{2}/4}$

${\displaystyle \leq w(f^{*})+{\frac {w(f)}{4}},}$

desde

${\displaystyle (1/4)\cdot w(f)=(1/4)\cdot \sum _{e\in E}f_{e}(a_{e}f_{e}+b_{e})}$

${\displaystyle =(1/4)\cdot \sum _{e\in E}(f_{e})^{2}+\underbrace {(1/4)\cdot \sum _{e\in E}f_{e}b_{e}} _{\geq 0}.}$

Podemos concluir que y probar la tesis utilizando el hecho 1. QED ${\displaystyle w^{f}(f^{*})\leq w(f^{*})+w(f)/4}$

Tenga en cuenta que en la prueba hemos hecho un uso extensivo del supuesto de que las funciones en son lineales. En realidad, se cumple un hecho más general. ${\displaystyle L}$

Teorema . Dado un problema de enrutamiento generalizado con funciones de grado de latencia polinómica y gráfica con coeficientes no negativos, el PoA puro es . ${\displaystyle G}$ ${\displaystyle d}$ ${\displaystyle \leq d+1}$

Tenga en cuenta que el PoA puede crecer con . Considere el ejemplo que se muestra en la siguiente figura, donde asumimos un flujo unitario: los flujos de equilibrio de Nash tienen bienestar social 1; sin embargo, el mejor bienestar se logra cuando , en cuyo caso ${\displaystyle d}$ ${\displaystyle x=1-1/{\sqrt {d+1}}}$

${\displaystyle w=\left(1-{\frac {1}{\sqrt {d+1}}}\right)^{d}\cdot \left(1-{\frac {1}{\sqrt {d+1}}}\right)+1\cdot {\frac {1}{\sqrt {d+1}}}}$

${\displaystyle =\left(\left(1-{\frac {1}{\sqrt {d+1}}}\right)^{\sqrt {d+1}}\right)^{\sqrt {d+1}}+{\frac {1}{\sqrt {d+1}}}}$

${\displaystyle \leq e^{-{\sqrt {d+1}}}+{\frac {1}{\sqrt {d+1}}}.}$

Esta cantidad tiende a cero cuando tiende al infinito. ${\displaystyle d}$

Otros resultados

Se pueden obtener límites superiores de PoA si se demuestra que el juego satisface la llamada desigualdad de suavidad . Más precisamente, un juego de minimización de costos es ( λ , μ ) suave (con λ ≥ 0 y μ < 1) si la desigualdad

${\displaystyle \sum _{i=1}^{n}C_{i}\left(a_{i}^{*},a_{-i}\right)\leq \lambda C\left(a^{*}\right)+\mu C(a)}$

es válido para cualquier resultado a y a *. En este caso, el PoA está limitado superiormente por λ /(1 − μ ). ^[5]

Para los juegos de costos compartidos con funciones de costos cóncavas, la regla de costo compartido óptima que optimiza el precio de la anarquía, seguido del precio de la estabilidad , es precisamente la regla de costo compartido del valor de Shapley. ^[6] (Una afirmación simétrica es igualmente válida para juegos de utilidad compartida con funciones de utilidad convexas). En el diseño de mecanismos , esto significa que el concepto de solución de valor de Shapley es óptimo para estos conjuntos de juegos.

Además, para estos juegos (finitos) se demostró que todo equilibrio que alcanza el límite del PoA es frágil, en el sentido de que los agentes demuestran un estado de indiferencia entre su acción de equilibrio y la acción que llevarían a cabo en un resultado óptimo del sistema. ^[7]

Ver también

• Precio de la anarquía en las subastas
• El precio de la anarquía en los juegos de congestión
• Precio de la estabilidad
• Tragedia de los comunes
• Juego competitivo de ubicación de instalaciones : un juego con un pequeño precio de anarquía.

Referencias

1. Koutsoupias, Elías; Papadimitriou, Christos (mayo de 2009). "Equilibrios en el peor de los casos". Revisión de informática . 3 (2): 65–69. doi :10.1016/j.cosrev.2009.04.003. Archivado desde el original el 13 de marzo de 2016 . Consultado el 12 de septiembre de 2010 .
2. M. Goemans, V. Mirrokni, A. Vetta, Equilibrios y convergencia del sumidero , FOCS 05
3. Chung, Cristina; Ligett, Katrina; Pruhs, Kirk; Roth, Aaron (2008), Monien, Burkhard; Schroeder, Ulf-Peter (eds.), "El precio de la anarquía estocástica", Teoría algorítmica de juegos , vol. 4997, Berlín, Heidelberg: Springer Berlin Heidelberg, págs. 303–314, doi :10.1007/978-3-540-79309-0_27, ISBN 978-3-540-79308-3, recuperado el 29 de diciembre de 2023
4. P. Dubey. Ineficiencia de los equilibrios de Nash. Matemáticas. Operar. Res., 11(1):1–8, 1986
5. Roughgarden, Tim (2 de noviembre de 2015). "Robustez intrínseca del precio de la anarquía". Revista de la ACM . 62 (5): 1–42. doi :10.1145/2806883. ISSN  0004-5411.
6. Phillips, Mateo; Marden, Jason R. (julio de 2018). "Compensaciones de diseño en juegos cóncavos de costos compartidos". Transacciones IEEE sobre control automático . 63 (7): 2242–2247. doi :10.1109/tac.2017.2765299. ISSN  0018-9286. S2CID  45923961.
7. Seaton, Josué H.; Marrón, Philip N. (2023). "Sobre la fragilidad intrínseca del precio de la anarquía". Cartas de sistemas de control IEEE . 7 : 3573–3578. doi :10.1109/LCSYS.2023.3335315. ISSN  2475-1456.

• Tim Roughgarden y Eva Tardos, "Introducción a la ineficiencia de los equilibrios". Capítulo 17 en Vazirani, Vijay V .; Nisán, Noam ; Jardín áspero, Tim ; Tardos, Éva (2007). Teoría algorítmica de juegos (PDF) . Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-87282-0..
• Tim Roughgarden (2005). "La ruta egoísta y el precio de la anarquía" . Prensa del MIT . ISBN 0-262-18243-2.

Otras lecturas

• Fabio Cunial, El precio de la anarquía