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, considere el sistema de transporte de una ciudad y muchos agentes que intentan ir desde una ubicación inicial a un destino. Aquí, la eficiencia significa el tiempo promedio que tarda un agente en llegar al destino. En la solución "centralizada", una autoridad central puede decirle a cada agente qué camino tomar para minimizar el tiempo promedio 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 promedio de viaje en los dos casos.

Por lo general, 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 sabores de equilibrio de Nash conducen a variaciones de la noción de Precio de Anarquía como Precio Puro de Anarquía (para equilibrios deterministas), Precio Mixto de Anarquía (para equilibrios aleatorios) y Precio de Anarquía Bayes-Nash (para juegos con información incompleta). Los 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 de la "ratio de aproximación" en un algoritmo de aproximación o la "ratio competitiva" en un algoritmo en línea . Esto se encuentra en el contexto de la tendencia actual de analizar juegos utilizando lentes algorítmicos ( teoría de juegos algorítmicos ).

Definición matemática

Consideremos un juego , definido por un conjunto de jugadores , conjuntos de estrategias para cada jugador y utilidades (donde también se denomina 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 o 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 coste' que queremos 'minimizar' (por ejemplo, el retraso en una red) utilizamos (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)}}}$

Un concepto relacionado es el de 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 costo:

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

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

Ejemplos

El dilema del prisionero

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

y sea la función de costo 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 ocurre cuando ambos cooperan, en cuyo caso el costo es . Por lo 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 de tareas . Hay jugadores y cada uno de ellos tiene una tarea que ejecutar. Pueden elegir una de las máquinas para ejecutarla. El precio de la anarquía compara la situación en la que la selección de máquinas está guiada/dirigida de forma centralizada con la situación en la que cada jugador elige la máquina que hará que su tarea 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. Por lo tanto, las estrategias de cada jugador son: Defina la carga de 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 costo para el jugador es , por ejemplo, la carga de la máquina que eligió. Consideramos la función de costo igualitaria , aquí denominada makespan . ${\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: p. ej., cuando , , , y , las estrategias mixtas alcanzan un makespan promedio de 1,5, mientras que cualquier PoA de estrategia pura en este contexto 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}$

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

Demostración . Nos gustaría tomar un perfil de acción socialmente óptimo . Esto significaría simplemente un perfil de acción cuyo makespan sea mínimo. Sin embargo, esto no será suficiente. Puede haber varios de estos perfiles de acción que conduzcan a una variedad de distribuciones de cargas diferentes (todas con la misma carga máxima). Entre estos, nos limitamos aún más a uno que tenga una segunda carga más grande mínima. Nuevamente, esto da como resultado un conjunto de posibles distribuciones de carga, y repetimos hasta la carga n-ésima 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 se trata de un equilibrio de Nash de estrategia pura. Razonando por contradicción, supongamos que algún jugador podría mejorar estrictamente moviéndose de una máquina a otra . Esto significa que la carga incrementada 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 ha reducido la carga más grande (o de mayor rango) en la distribución. Esto, sin embargo, viola la minimalidad lexicográfica asumida de . QED ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle j}$ ${\displaystyle j}$ ${\displaystyle j}$ ${\displaystyle a}$

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

Demostración . Es fácil limitar superiormente el 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, al comparar las proporciones se demuestra 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 en la que 4000 conductores desean viajar desde el punto Inicio hasta el Fin. El tiempo de viaje en minutos en la carretera Inicio-A es el número de viajeros (T) dividido por 100, y en Inicio-B es una constante de 45 minutos (lo mismo con las carreteras de enfrente). Si la carretera discontinua no existe (por lo que la red de tráfico tiene 4 carreteras en total), el tiempo necesario para conducir la ruta Inicio-A-Fin con conductores sería . El tiempo necesario para conducir la ruta Inicio-B-Fin con conductores sería . Como hay 4000 conductores, el hecho de que se puede utilizar para derivar el hecho de que cuando el sistema está en equilibrio. Por lo tanto, cada ruta tarda 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 ruta 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 la carretera está abierta y un conductor intenta ir por Inicio–A–B–Fin. Para su sorpresa, descubre que su tiempo es de minutos, lo que supone un ahorro de casi 25 minutos. Pronto, más de los 4000 conductores están probando esta nueva ruta. El tiempo empleado aumenta de 40,01 y sigue aumentando. Cuando el número de conductores que intentan la nueva ruta llega a 2500, con 1500 todavía en la ruta Inicio–B–Fin, su tiempo será de minutos, lo que no supone ninguna mejora respecto de la ruta original. Mientras tanto, esos 1500 conductores han sido reducidos a minutos, un aumento de 20 minutos. Están obligados a cambiar a la nueva ruta también por A, por lo que ahora tarda minutos. Nadie tiene ningún incentivo para viajar por A–Fin o Inicio–B porque cualquier conductor que las pruebe tardará 85 minutos. De esta forma, la apertura de la ruta transversal desencadena un cambio irreversible en la misma por parte de todos, con un coste para todos de 80 minutos en lugar de los 65 originales. Si todos los conductores aceptaran no utilizar la ruta A–B, o si se cerrara esa ruta, todos los conductores se beneficiarían con 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) . Sea , y como se definieron anteriormente, y supongamos que queremos enrutar las cantidades a través de cada par distinto de nodos en . Un flujo se define como una asignación de un número real no negativo a cada ruta que va desde a , 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 se define como ${\displaystyle G}$

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

Para ser más breves, escribimos cuando el contexto lo deja claro. ${\displaystyle f_{e}}$ ${\displaystyle \Gamma ,R}$

Definición (Flujo de equilibrio de Nash) Un flujo es un flujo de equilibrio de Nash si y solo 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 apoyo a los equilibrios de Nash de estrategia mixta en juegos de forma normal.

Definición (bienestar condicional de un flujo) . Sean y dos flujos en asociados con los mismos conjuntos y . En lo que sigue, eliminaremos el subíndice para que la notación sea más clara. Supongamos que se fijan 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^{*})}$

Demostración (por contradicción) . Supóngase 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 el de los demás sólo si existen dos caminos que van desde el de los demás con costos diferentes y si se desvía parte del flujo del camino de mayor costo al 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}$

Nótese que el hecho 1 no supone ninguna estructura particular en el conjunto . ${\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}$

Demostración . Esta es otra forma de expresar la desigualdad verdadera . 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}$

Demostración . Nótese que este teorema es equivalente a decir que para cada flujo de equilibrio de Nash , , donde es 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}.}$

Usando 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 usando el Hecho 1. QED ${\displaystyle w^{f}(f^{*})\leq w(f^{*})+w(f)/4}$

Nótese 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 latencia polinómicas y gráficas de grado con coeficientes no negativos, el PoA puro es . ${\displaystyle G}$ ${\displaystyle d}$ ${\displaystyle \leq d+1}$

Nótese que el PoA puede crecer con . Considere el ejemplo que se muestra en la siguiente figura, donde suponemos un flujo unitario: los flujos de equilibrio de Nash tienen un bienestar social de 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 a infinito. ${\displaystyle d}$

Resultados adicionales

Los límites superiores de PoA se pueden obtener si se demuestra que el juego satisface una desigualdad denominada 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)}$

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

Para los juegos de reparto de costos con funciones de costos cóncavas, la regla óptima de reparto de costos que optimiza el precio de la anarquía, seguido por el precio de la estabilidad , es precisamente la regla de reparto de costos del valor de Shapley. ^[6] (Una declaración simétrica es igualmente válida para los juegos de reparto de utilidad 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 perseguirían en un resultado óptimo del sistema. ^[7]

Véase también

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

Referencias

1. Koutsoupias, Elias; Papadimitriou, Christos (mayo de 2009). "Worst-case Equilibria". Computer Science Review . 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, Christine; Ligett, Katrina; Pruhs, Kirk; Roth, Aaron (2008), Monien, Burkhard; Schroeder, Ulf-Peter (eds.), "El precio de la anarquía estocástica", Algorithmic Game Theory , 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, consultado el 29 de diciembre de 2023
4. P. Dubey. Ineficiencia de los equilibrios de Nash. Math. Operat. 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, Matthew; Marden, Jason R. (julio de 2018). "Compensaciones de diseño en juegos cóncavos de costos compartidos". IEEE Transactions on Automatic Control . 63 (7): 2242–2247. doi :10.1109/tac.2017.2765299. ISSN  0018-9286. S2CID  45923961.
7. Seaton, Joshua H.; Brown, Philip N. (2023). "Sobre la fragilidad intrínseca del precio de la anarquía". IEEE Control Systems Letters . 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. ; Nisan, Noam ; Roughgarden, Tim ; Tardos, Éva (2007). Teoría de juegos algorítmica (PDF) . Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-87282-0..
• Tim Roughgarden (2005). El derrotero egoísta y el precio de la anarquía . MIT Press . ISBN 0-262-18243-2.

Lectura adicional

• Fabio Cunial, El precio de la anarquía