Precio de la anarquía

El precio de la anarquía (PoA)​ es un concepto de la teoría de juegos que mide cómo la eficiencia de un sistema se degrada debido a la conducta egoísta de sus agentes. Se trata de una noción general que puede ampliarse a los diversos sistemas y a las diferentes nociones de eficiencia. Por ejemplo, considere el sistema de transporte de una ciudad y a los muchos agentes que tratan de pasar de una cierta localización inicial hasta un destino final. Sea la eficiencia en este caso el promedio de tiempo que un agente tarda para llegar a su destino. En la solución «centralizada», una autoridad central puede decirle a cada agente qué camino tomar con el fin de reducir al mínimo el tiempo de viaje promedio. En la versión "descentralizada", cada agente elige su propio camino. El precio de la anarquía mide la relación entre el tiempo de viaje promedio en los dos casos.

Por lo general, el sistema se modela como un juego y la eficiencia es una función de los resultados (por ejemplo retardo máximo en una red, congestión en el sistema de transporte, el bienestar social en una subasta, ...). Diferentes conceptos de equilibrio se pueden utilizar para modelar el comportamiento egoísta de los agentes, entre los cuales el más común es el equilibrio de Nash. Diferentes refinamientos del equilibrio de Nash conducen a variaciones de la noción de precio de la anarquía como: Precio de la Anarquía puro (por equilibrios determinista), Precio de la Anarquía mixto (por azar equilibrios), Precio de la Anarquía Bayes-Nash (para los juegos con información incompleta), ... Otros conceptos, excepto los equilibrios de Nash, conducen a las variaciones del concepto, ya que el precio de hundimiento.​

El término de precio de la anarquía fue utilizado por primera vez por Koutsoupias y Papadimitriou,​ pero la idea de medir la ineficacia de equilibrio es más antigua.​ El concepto en su forma actual fue diseñado para ser el análogo de la "relación de aproximación», en un algoritmo de aproximación o de la "relación de competencia" en un algoritmo en línea . Esto es en el contexto de la tendencia actual de análisis de los juegos que usan lentes algorítmicos ( teoría de juegos algorítmica ).

Definición Formal

Podemos definir un subconjunto $E\subseteq S$ a ser el conjunto de estrategias en equilibrio (por ejemplo, el conjunto de equilibrios de Nash ). El precio de la anarquía se define como la relación entre el "peor equilibrio" y la solución 'centralizado' óptimo:

$PoA={\frac {\max _{s\in S}W(s)}{\min _{s\in E}W(s)}}$

Siguiendo la convención en los algoritmos de aproximación, si la función de la eficiencia de la medida es, en lugar de un "bienestar" queremos "maximizar", una 'función de coste' $C:S\rightarrow R$ queremos 'minimizar' (retardo en una red, por ejemplo) que utilizamos:

$PoA={\frac {\max _{s\in E}C(s)}{\min _{s\in S}C(s)}}$

Un concepto relacionado es el de la estabilidad de precios (punto de venta), que mide la relación entre el "mejor equilibrio" y la solución 'centralizado' óptimo:

$PoS={\frac {\max _{s\in S}W(s)}{\max _{s\in E}W(s)}}$

o en el caso de funciones de coste:

$PoS={\frac {\min _{s\in E}C(s)}{\min _{s\in S}C(s)}}$

Sabemos que $1\leq PoS\leq PoA$ por definición. Se espera que la pérdida en la eficiencia debido a las limitaciones de teoría de juegos está en algún lugar entre el 'punto de venta Pos y PoA.

Ejemplos

Dilema del prisionero

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

	Cooperate	Defect
Cooperate	1, 1	7, 0
Defect	0, 7	5, 5

y sea la función de costos $C(s_{1},s_{2})=u_{1}(s_{1},s_{2})+u_{2}(s_{1},s_{2}).$ Ahora, la función de coste mínimo sería cuando ambos jugadores cooperan y el costo resultante es $1+1=2$, Sin embargo, el único equilibrio de Nash se produce cuando tanto el costo defecto de tal situación es $5+5=10,$ por lo que el precio de la anarquía de este juego será $10/2=5$.

Bibliografía Adicional

• Noam Nisan, Tim Roughgarden, Eva Tardos, and. Vijay Vazirani, ed. (2007). «Introduction to the Inefficiency of Equilibria». Algorithmic Game Theory. Cambridge University Press. ISBN 0-521-87282-0. 
• Tim Roughgarden (2005). Selfish routing and the price of anarchy. MIT Press. ISBN 0-262-18243-2. 

• Datos: Q7242623