El precio de la anarquía

El precio de la anarquía ( en inglés Price of Anarchy , PoA ) [1] es un concepto en economía y teoría de juegos que mide cuánto se degrada la eficiencia de un sistema debido al comportamiento egoísta de sus agentes.

Discusión informal

El costo de la anarquía es un concepto general que se puede extender a diferentes sistemas y conceptos de eficiencia. Por ejemplo, considere un sistema de transporte en una ciudad donde muchos agentes intentan viajar desde algún punto de inicio hasta algún punto final. Sea eficiencia en este caso el tiempo promedio en que el agente llega al destino. En una solución "centralizada", la autoridad central puede decirle a cada agente qué ruta debe tomar el agente para minimizar el tiempo promedio de viaje. En la versión "descentralizada", cada agente elige la ruta a su discreción. El precio de la anarquía refleja la relación de los tiempos de viaje promedio para estos dos casos.

Por lo general, el sistema se modela como un juego y la eficiencia es una función del resultado del juego (por ejemplo, latencia máxima de la red, congestión del tráfico, beneficio social en las subastas, etc.). Se pueden usar varios conceptos de equilibrio para modelar el comportamiento egoísta de los agentes, y entre ellos, el concepto más general es el equilibrio de Nash . Diferentes variaciones del equilibrio de Nash conducen a variaciones en el concepto de costo de la anarquía, como el costo de la anarquía pura (para equilibrios deterministas), el costo de la anarquía mixta (para equilibrios aleatorios) y el costo de la anarquía de Bayes-Nash (para juegos con información incompleta). Conceptos distintos al equilibrio de Nash conducen a opciones como el precio de la inmersión [2] .

El término "precio de la anarquía" fue utilizado por primera vez por Elias Koutsoupias y Christos Papadimitriou [1] , pero la idea de medir la ineficiencia del equilibrio es más antigua [3] . El concepto en su forma actual pretendía ser análogo al "factor de aproximación" en un algoritmo de aproximación o al "nivel de competitividad" en un algoritmo en línea . El término está en línea con la tendencia moderna de análisis de juegos utilizando lentes algorítmicos ( Teoría de juegos algorítmicos ).

Definición matemática

Considere un juego definido por un conjunto de jugadores , conjuntos de estrategias para cada jugador y una función de utilidad (que también se denomina conjunto de resultados). Podemos definir una medida de la efectividad de cada resultado, que llamaremos función de beneficio . Los candidatos naturales incluyen la suma de las utilidades de los jugadores (utilidades objetivo), la utilidad mínima (equidad o igualitarismo objetivo) ..., o cualquier función que tenga sentido para el juego particular que se analiza y que deba maximizarse. ${\ estilo de visualización G = (N, S, u)}$ $norte$ $Si}$ $u_{i}:S\rightarrow \mathbb {R}$ ${\displaystyle S=S_{1}\times ...\times S_{n))$ $Welf:S\rightarrow \mathbb {R}$ $Welf(s)=\sum _{i\in N}u_{i}(s),$ $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 costo de la anarquía se define entonces como la relación entre la solución "centralizada" óptima y el "peor equilibrio": $Equil\subseteq S$

$PoA={\frac {\max _{s\in S}Bienestar(s)}{\min _{s\in Equil}Bienestar(es)))$

Si, en lugar del "bien" que queremos maximizar, la función de medida de la eficiencia es la "función de costo" que queremos minimizar (como los retrasos en la red), usamos (siguiendo las convenciones adoptadas en los algoritmos de aproximación): $Costo:S\rightarrow \mathbb {R}$

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

Un concepto relacionado es el Precio de la Estabilidad ( PoS ) , que mide la relación entre el "mejor equilibrio" y la solución óptimamente "centralizada":

$PoS={\frac {\max _{s\in S}Bienestar(s)}{\max _{s\in Equil}Bienestar(es)))$

o en el caso de funciones de costo:

$PoS={\frac {\min_{s\in Equil}Coste(s)}{\min_{s\in S}Costo(s)))$

Lo sabemos por definición. Se espera que la pérdida de eficiencia debida a las restricciones de la teoría de juegos se encuentre entre PoS y PoA. $1\leqslant PoS\leqslant PoA$

Ambos valores, PoS y PoA, se calcularon para diferentes tipos de juegos. A continuación se dan algunos ejemplos.

El dilema del prisionero

Considere un juego de 2x2 llamado Prisoner 's Dilemma, dado por la siguiente matriz de costos:

	Cooperar	traicionar
Cooperar	1 ; una	7 ; 0
traicionar	0 ; 7	5 ; 5

y deja que la función de precio sea Ahora el precio mínimo será cuando ambos jugadores cooperen y el precio resultante será . Sin embargo , el equilibrio de Nash se observa solo cuando ambos traicionan, en cuyo caso el precio es . Entonces el valor del PoA de este juego será igual a . $C(s_{1},s_{2})=u_{1}(s_{1},s_{2})+u_{2}(s_{1},s_{2}).$ ${\ estilo de visualización 1 + 1 = 2}$ ${\ estilo de visualización 5+5=10}$ ${\ estilo de visualización 10/2 = 5}$

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

Distribución del trabajo

Un ejemplo más natural es uno de los problemas de programación de trabajos . Hay jugadores y cada uno de ellos tiene un trabajo por hacer. Pueden elegir una de las máquinas para hacer el trabajo. El costo de la anarquía compara una situación en la que la elección de las máquinas se determina centralmente y una situación en la que cada jugador elige un automóvil de tal manera que complete su trabajo más rápido. $norte$ $METRO$

Cada máquina tiene una velocidad Cada trabajo tiene un peso El jugador elige una máquina para realizar su trabajo. Así, las estrategias de cada jugador serán Definir la carga en la máquina como: $s_{1},\ldots,s_{M}>0.$ $w_{1},\ldots,w_{N}>0.$ $A_{i}=\{1,2,\ldots,M\}.$ $j$

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

El precio para el jugador es igual , es decir, es igual a la carga de la máquina que elige el jugador. Consideraremos la función de precio igualitario , que aquí se denomina período de procesamiento. $i$ $c_{i}(a)=L_{a_{i}}(a),$ ${\mbox{MS}}(a)=\max _{j}L_{j}(a)$

Consideraremos dos conceptos de equilibrio: la estrategia de Nash pura y la estrategia de Nash mixta . Es claro que un PoA mixto es un PoA puro, ya que cualquier equilibrio de Nash puro es también un equilibrio de Nash mixto (la desigualdad puede resultar estricta, por cuando,ejemplo ). Lo primero que tenemos que hacer es mostrar la existencia de un equilibrio de Nash puro. $\geqslant$ $N=2$ ${\ estilo de visualización w_{1}=w_{2}=1}$ $METRO=2$ ${\ estilo de visualización s_{1}=s_{2}=1}$ ${\ estilo de visualización \ sigma _ {1} = \ sigma _ {2} = (1/2, 1/2)}$ ${\ estilo de visualización \ leqslant 4/3}$

Declaración _ Para cualquier juego de distribución de puestos, existe al menos una estrategia pura de equilibrio de Nash.

prueba _ Necesitamos obtener un conjunto socialmente óptimo de estrategias . Esto puede significar simplemente un conjunto de estrategias para las cuales el tiempo de procesamiento es mínimo. Sin embargo, esto no es suficiente. Puede haber varios conjuntos de estrategias que den como resultado varias distribuciones de carga diferentes (todas con la misma carga máxima). Además, nos limitaremos al hecho de que hay una segunda carga más baja. Nuevamente, esto conduce a muchas distribuciones de carga posibles, y repetimos el proceso hasta que obtengamos la mejor carga (es decir, la más pequeña), donde solo puede haber una distribución de carga (la única hasta una permutación). Esto también se puede llamar el vector lexicográficamente más pequeño de descargas ordenadas. $un^{*}$ $METRO$

Afirmamos que se trata de un equilibrio de Nash en estrategia pura. Probaremos por contradicción. Supongamos que algún jugador puede mejorar su rendimiento moviéndose de una máquina a otra . Esto significa que la carga de la máquina aumentada después de la transición sigue siendo menor que la carga de la máquina antes de la transición. Dado que la carga en la máquina debería disminuir como resultado de la transición y ninguna otra máquina se ve afectada, lo que significa que la nueva configuración garantiza una reducción en la -ésima carga más grande en la distribución. Esto, sin embargo, viola el supuesto de minimalidad lexicográfica . QED $i$ $j$ $k$ $k$ $j$ $j$ $j$ $a$

Declaración _ Para cualquier juego de distribución de trabajo, el PoA de estrategia pura no excede . $METRO$

prueba _ Es fácil acotar desde arriba el bien obtenido como cualquier estrategia mixta de equilibrio de Nash , mediante la fórmula $\sigma$

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

Considere para mayor claridad cualquier conjunto de estrategias puras , entonces está claro que $a$

w(a)\geqslant {\frac {\sum_{i}{w_{i)}}{\sum_{j}{s_{j)}))\geqslant {\frac {\sum _ {i}{w_{i}}}{M\cdot\max _{j}{s_{j}}}}.

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

Enrutamiento egoísta

Paradoja de Braes

Considere una red de carreteras en la que debe viajar un número fijo de conductores desde un punto de inicio común hasta un punto final común. Suponga que cada conductor elige una ruta de manera egoísta y que el tiempo de viaje depende linealmente del número de conductores que eligen la ruta.

Podemos formalizar estas condiciones como un problema de selección de rutas en un grafo conexo dirigido en el que queremos enviar una unidad de flujo desde un nodo fuente a un nodo sumidero (imaginemos que el flujo consta de las rutas elegidas de diferentes conductores). En particular, deje que el flujo sea una función que asigna un número real no negativo a cada borde y considere un conjunto de funciones lineales que asignan el flujo a través del borde al retraso del borde. Definamos también el bien social del flujo como $G=(V,E)$ $s \ en V$ $t\en V$ $f:E\mapsto\Re$ $L=\{l_{e}(f_{e})=a\cdot f_{e}+b\;|\;e\in E,\;a\geqslant 0,\;b\geqslant 0 \}$ $F$ ${\displaystyle w(f)=\sum _{e}{f_{e}\cdot l_{e}(f_{e)))))$

Considere el ejemplo de la figura: si no se dispone de un camino punteado, se obtiene un equilibrio de Nash en estrategias mixtas cuando cada jugador elige la ruta superior y la ruta inferior con la misma probabilidad. Este equilibrio tiene un costo social de 1.5 y toma 1.5 unidades de tiempo para que cada conductor pase de a . Con la esperanza de mejorar el paso por la red, el legislador puede decidir abrir una vía punteada a los conductores con poco retraso. En este caso, el equilibrio de Nash solo puede ocurrir si algún conductor usa la nueva carretera, por lo que el costo social aumenta en 2 y ahora le toma 2 unidades de tiempo a cada conductor viajar de a . $s$ $t$ $s$ $t$

Por lo tanto, se obtiene un resultado inusual: la prohibición legislativa del uso de una carretera más rápida en algunos casos puede tener un resultado positivo.

Problema de enrutamiento generalizado

El problema de enrutamiento presentado en la paradoja de Braes se puede generalizar a muchos flujos diferentes en el mismo gráfico al mismo tiempo.

Definición (Flujo Generalizado) . Deje que , y se defina de la misma manera que arriba, y suponga que deseamos pasar valores a través de cada par diferente de nodos en . El flujo se define como la distribución de números reales no negativos a cada camino que pasa de a , con restricciones $G=(V,E)$ $L$ $w$ ${\displaystyle R=\{r_{1},r_{2},\dots,r_{k},\;|\;r_{i}>0\))$ $\Gamma =\{(s_{1},t_{1}),(s_{2},t_{2}),\dots ,(s_{k},t_{k})\}\subseteq (V\veces V)$ ${\ Displaystyle f_ {\ Gamma, R}}$ $p\mapsto\Re$ $pags$ $si}$ $t_{yo}$ ${\ estilo de visualización \ en \ Gamma}$

\sum_{p:\,s_{i}\rightarrow t_{i}}{f_{p}}=r_{i}\;\;\forall (s_{i},t_{i}) \en \gamma.

El flujo que pasa a través de un borde de gráfico particular se define como $GRAMO$

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

Por brevedad, escribiremos si está claro por el contexto. $f_{e}$ ${\ estilo de visualización \ gamma, R}$

Definición (Flujo de equilibrio de Nash) . Un flujo es un flujo de equilibrio de Nash si y solo si y de a ${\ Displaystyle f_ {\ Gamma, R}}$ ${\ estilo de visualización \ para todos (s_ {i}, t_ {i}) \ en \ Gamma}$ ${\ estilo de visualización \ para todos p, q}$ $si}$ $t_{yo}$

f_{p}>0\Rightarrow \sum_{e\in p}{l_{e}(f_{e})}\leqslant \sum_{e\in q}{l_{e}(f_ {mi})}.

Esta definición está muy relacionada con lo que hablamos cuando una estrategia mixta mantiene un equilibrio de Nash en juegos en forma normal.

Definición de (Flujo Condicional Bueno) . Sean y dos flujos asociados con los conjuntos y . En lo que sigue, omitiremos el índice para facilitar la notación. Imagine retrasos fijos generados por funciones en un gráfico: el bien condicional con respecto a se define como ${\ Displaystyle f_ {\ Gamma, R}}$ $f_{\Gamma ,R}^{*}$ $GRAMO$ $\Gama$ $R$ $F$ ${\ estilo de visualización f ^ {*}}$ $F$

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

hecho 1 . Si hay un flujo de equilibrio de Nash y cualquier otro flujo , . $F$ ${\ estilo de visualización f ^ {*}}$ $w(f)=w^{f}(f)\leqslant w^{f}(f^{*})$

Prueba (de conversar) . Supongamos que . Por definición, ${\ estilo de visualización w^{f}(f^{*})<w^{f}(f)}$

\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\en p}l_{e}(f_{e})

Como y están relacionados con los mismos conjuntos , sabemos que $F$ ${\ estilo de visualización f ^ {*}}$ ${\ estilo de visualización \ gamma, R}$

\sum_{p:s_{i}\rightarrow t_{i}}f_{p}=\sum_{p:s_{i}\rightarrow t_{i}}f_{p}^{*} =r_{i}\;\;\para todos los i.

Por lo tanto, debe haber un par y dos caminos de a tales que , , y ${\ estilo de visualización (s_ {i}, t_ {i})}$ $pag q$ $si}$ $t_{yo}$ ${\displaystyle f_{p}^{*}>f_{p))$ $f_{q}^{*}<f_{q}$

\sum_{e\in p}l_{e}(f_{e})<\sum_{e\in q}l_{e}(f_{e}).

En otras palabras, un flujo solo puede obtener un beneficio menor que si dos caminos tienen precios diferentes y si redirige algún flujo de un camino de alto costo a un camino de menor costo. Es claro que esta situación es incompatible con el supuesto de que se trata de un flujo de equilibrio de Nash. QED ${\ estilo de visualización f ^ {*}}$ $F$ $si}$ $t_{yo}$ ${\ estilo de visualización f ^ {*}}$ $F$ $F$

Tenga en cuenta que el Hecho 1 no implica ninguna estructura de conjuntos en particular . $L$

hecho 2 . Si se dan dos números reales y , . $X$ $y$ $x\cdot y\leqslant x^{2}+y^{2}/4$

prueba _ Esta es otra forma de expresar la desigualdad correcta . QED ${\ estilo de visualización (xy/2) ^ {2} \ geqslant 0}$

teorema _ El PoA de la estrategia pura para cualquier problema de enrutamiento generalizado con retrasos lineales es igual a . ${\ estilo de visualización (G, L)}$ ${\ estilo de visualización \ leqslant 4/3}$

prueba _ Tenga en cuenta que este teorema es equivalente a decir que todo flujo de equilibrio de Nash , , donde es cualquier otro flujo. Por definición $F$ $w(f)\leqslant (4/3)\cdot \min _{f^{*}}\{w(f^{*})\}$ ${\ estilo de visualización f ^ {*}}$

w^{f}(f^{*})=\sum_{e\in E}f_{e}^{*}(a_{e}\cdot f_{e}+b_{e})

=\sum_e}(a_{e}f_{e}f_{e}^{*})+\sum_{e\in E}f_{e}^{*}b_{e} .

Usando el hecho 2 obtenemos

w^{f}(f^{*})\leqslant \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}

=\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

\leqslant w(f^{*})+{\frac {w(f)}{4)),

porque el

(1/4)\cdot w(f)=(1/4)\cdot \sum_{e\in E}f_{e}(a_{e}f_{e}+b_{e})

=(1/4)\cdot \sum_{e\in E}(f_{e})^{2}+\underbrace {(1/4)\cdot \sum_{e\in E} f_{e}b_{e}} _{\geqslant 0}.

Podemos concluir que , y probar el enunciado con la ayuda del Hecho 1. que se requería probar. $w^{f}(f^{*})\leqslant w(f^{*})+w(f)/4$

Tenga en cuenta que en la prueba hicimos un uso extensivo de la suposición de que las funciones en son lineales. De hecho, se sostienen hechos más generales. $L$

teorema _ Dado un problema de enrutamiento generalizado en un gráfico y funciones de retardo de grado polinomial con coeficientes no negativos, PoA es una estrategia pura . $GRAMO$ $d$ ${\ estilo de visualización \ leqslant d+1}$

Tenga en cuenta que PoA puede crecer como . Considere el ejemplo que se muestra en la figura, donde asumimos un flujo unitario: los flujos de equilibrio de Nash tienen un bien social de 1. Sin embargo, el mejor bien se logra cuando , en este caso, $d$ $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))))

\leqslant e^{-{\sqrt {d+1}}}+{\frac {1}{\sqrt {d+1}}}.

El valor se acerca a cero a medida que se acerca al infinito. $d$

Véase también

La tragedia de los recursos compartidos
Colocación de objetos (juego competitivo) es un juego con un pequeño precio de anarquía.
El precio de la anarquía en las subastas

Notas

↑ 1 2 Koutsoupias, Papadimitriou, 2009 , p. 65–69.
↑ Goemans, Mirrokni, Vetta, 2005 , pág. 142-154.
↑ Dubey, 1986 , pág. 1-8.

Literatura

Elias Koutsoupias, Christos Papadimitriou . Equilibrios en el peor de los casos // Revisión de ciencias de la computación. - 2009. - mayo ( vol. 3 , número 2 ). Archivado desde el original el 13 de marzo de 2016.
Vijay V. Vazirani, Noam Nisan, Tim Roughgarden, Eva Tardos. Capítulo 17 Introducción a la Ineficiencia de los Equilibrios // Teoría Algorítmica de Juegos . - Cambridge, Reino Unido: Cambridge University Press, 2007. - ISBN 0-521-87282-0 .
Goemans M., Mirrokni V., Vetta A. Sink equilibrios y convergencia // 46º Simposio Anual IEEE sobre Fundamentos de Ciencias de la Computación (FOCS'05). - IEEE, 2005. - (Actas de la conferencia IEEE). — ISBN 0769524680 .
Dubey P. Ineficiencia de los equilibrios de Nash // Matemáticas. oper. Res.. - 1986. - T. 11 , núm. 1 .
Tim Roughgarden. Enrutamiento egoísta y el precio de la anarquía. - MIT Press , 2005. - ISBN 0-262-18243-2 .

Lectura para leer más

Fabio Cunial, Price of anarchy Archivado el 10 de septiembre de 2008 en Wayback Machine .

Teoría de juego
Conceptos básicos	Conocimiento mutuo y común Jugador Jerarquía de creencias Amplificación irracional Estrategia ( dominancia ) inducción inversa
tipos de juegos	Simultáneo , secuencial y repetitivo No cooperativo y cooperativo Con información completa , incompleta , perfecta e imperfecta En forma normal y extendida Antagonista Diferencial estocástico Batalla de los sexos Cacería de venados
Conceptos de solución	Dominio del riesgo Equilibrio correlacionado El equilibrio de una mano temblorosa equilibrio de Nash Equilibrio perfecto en subjuegos racionalizabilidad Equilibrio secuencial fuerte equilibrio Saldo propio Estrategia evolutivamente estable Epsilon-equilibrio Eficiencia de Pareto Núcleo
Ejemplos de juegos	El dilema del prisionero La faena del bar "El Farol" Modelo Bertrand modelo de Cournot modelo stackelberg Orlyanka La tragedia de los recursos compartidos halcones y palomas
Teoría de juegos epistémicos Diseño del mecanismo División justa