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 egoísmocomportamiento de sus agentes en el peor de los casos. 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 de una ubicación inicial a un destino. Dejemos que la eficiencia en este caso signifique 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 medio 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, ...). 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 la anarquía como precio puro de la anarquía (para equilibrios deterministas), precio mixto de anarquía (para equilibrios aleatorios) y precio de anarquía de Bayes-Nash (para juegos con información incompleta) . Los conceptos de solución distintos al equilibrio de Nash conducen a variaciones como laPrecio del hundimiento . [2]
El término Price of Anarchy fue utilizado por primera vez por Elias Koutsoupias y Christos Papadimitriou , [1] [ verificación fallida ] pero la idea de medir la ineficiencia del equilibrio es más antigua. [3] El concepto en su forma actual fue diseñado para ser el análogo de la "razón de aproximación" en un algoritmo de aproximación o la "razón competitiva" en un algoritmo en línea . Esto está en el contexto de la tendencia actual de analizar juegos usando lentes algorítmicos ( teoría algorítmica de juegos ).