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 una 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 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 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 ).
Definición matemática
Considere un juego , definido por un conjunto de jugadores , conjuntos de estrategias para cada jugador y utilidades (dónde 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) utilidad mínima (equidad u objetivo igualitario) ..., o cualquier función que sea significativa para el juego particular que se está analizando y que sea deseable maximizar.
Podemos definir un subconjunto ser 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 el 'peor equilibrio' y la solución óptima 'centralizada':
Si, en lugar de un 'bienestar' que queremos 'maximizar', la función medir la eficiencia es una 'función de costo' que queremos 'minimizar' (por ejemplo, retraso en una red) usamos (siguiendo la convención en algoritmos de aproximación):
Una noción relacionada es la del precio de estabilidad ( PoS ), que mide la relación entre el 'mejor equilibrio' y la solución óptima 'centralizada':
o en el caso de funciones de costos:
Lo sabemos por la definición. Se espera que la pérdida de eficiencia debido a las limitaciones teóricas del juego se encuentre en algún lugar entre 'PoS' y 'PoA'.
Tanto el PoS como el PoA se han calculado para varios tipos de juegos. A continuación se presentan algunos ejemplos.
El dilema del prisionero
Considere el juego 2x2 llamado dilema del prisionero , dado por la siguiente matriz de costos:
Cooperar | Defecto | |
---|---|---|
Cooperar | 1 , 1 | 7 , 0 |
Defecto | 0 , 7 | 5 , 5 |
y deja que la función de costo sea Ahora, el peor equilibrio de Nash sería cuando ambos jugadores cooperan y el costo resultante es. Sin embargo, el mayor bienestar social se da cuando ambos faltan, en cuyo caso el costo es. Por lo tanto, el PoA de este juego será.
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 trabajos . Existenjugadores y cada uno de ellos tiene un trabajo que ejecutar. Pueden elegir uno demáquinas para ejecutar el trabajo. The Price of Anarchy compara la situación en la que la selección de máquinas se guía / dirige de forma centralizada con la situación en la que cada jugador elige la máquina que hará que su trabajo se ejecute más rápido.
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 sonDefinir la carga en la máquina ser - estar:
El costo para el jugador es es decir, la carga de la máquina que eligieron. Consideramos la función de costo igualitario, aquí llamado el Makingpan .
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 lograr un rendimiento promedio de 1.5, mientras que cualquier PoA de estrategia pura en este entorno es ). Primero debemos argumentar que existen equilibrios de Nash puros.
Reclamo . Para cada juego de programación de trabajos, existe al menos un equilibrio de Nash de estrategia pura.
Prueba . Nos gustaría tener un perfil de acción socialmente óptimo.. Esto significaría simplemente un perfil de acción cuyo alcance es mínimo. Sin embargo, esto no será suficiente. Puede haber varios perfiles de acción de este tipo que conduzcan a una variedad de distribuciones de cargas diferentes (todas con la misma carga máxima). Entre estos, nos restringimos aún más a uno que tenga una segunda carga más grande como mínimo. Nuevamente, esto da como resultado un conjunto de posibles distribuciones de carga, y repetimos hasta quela 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 .
Afirmamos que se trata de un equilibrio de Nash de estrategia pura. Razonando por contradicción, suponga que algún jugador podría mejorar estrictamente moviéndose de la máquina a máquina . Esto significa que el aumento de carga de la máquina después de la mudanza es aún menor que la carga de la máquina antes de la mudanza. 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 el la carga más grande (o de rango superior) en la distribución. Esto, sin embargo, viola la supuesta minimidad lexicográfica de. QED
Reclamo . Para cada juego de programación de trabajos, el PoA puro es como máximo.
Prueba . Es fácil establecer el límite superior del bienestar obtenido en cualquier equilibrio de Nash de estrategia mixta por
Considere, para mayor claridad de exposición, cualquier perfil de acción de estrategia pura. : claramente
Dado que lo anterior también es válido para el óptimo social, comparar las proporciones y prueba la afirmación. QED
Enrutamiento egoísta
La paradoja de Braess
Considere una red de carreteras en la que un número fijo de conductores necesita moverse de una fuente común a un destino común; Supongamos que cada conductor elige su ruta de manera egoísta y que el tiempo para atravesar una carretera depende linealmente del número de conductores que eligen esa carretera.
Podemos formalizar esta configuración como un problema de enrutamiento en un gráfico conectado y dirigido , en el que queremos enviar una unidad de flujo desde un nodo fuente a un nodo de destino (imagine que el flujo se compone de las decisiones de viaje de los diferentes conductores). En particular, deje que el flujo sea una función asignar a cada arista un número real no negativo y considerar el conjunto de funciones lineales que mapean el flujo que atraviesa cada borde a la latencia para atravesar el borde. Definamos también el bienestar social de un flujo. como
Considere el ejemplo de la figura: si la carretera discontinua no está disponible, el equilibrio de Nash de estrategia mixta ocurre 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 se necesitan 1,5 unidades. de tiempo a cada conductor para ir de a . Con la esperanza de mejorar el rendimiento de la red, un legislador podría decidir poner a disposición de los conductores el borde punteado de baja latencia: en este caso, el único equilibrio de Nash se produciría cuando todos los conductores utilicen la nueva carretera, por lo que el costo social sería aumentar a 2 y ahora le tomaría 2 unidades de tiempo a cada jugador para pasar de a .
De ahí el resultado poco común de negar el acceso a la vía más rápida mediante el control central para beneficiar al público en algunos casos.
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) . Dejar, y ser 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 una cesión de un número real, no negativo a cada camino ir desde a , con la restricción de que
El flujo que atraviesa un borde específico de Se define como
Para ser concisos, escribimos Cuándo son claras por el contexto.
Definición (flujo de equilibrio de Nash) . Un flujoes un flujo de equilibrio de Nash si y de a
Esta definición está estrechamente relacionada con lo que dijimos sobre el apoyo de los equilibrios de Nash de estrategia mixta en juegos de forma normal.
Definición (Bienestar condicional de un flujo) . Dejar y ser dos flujos en asociado con los mismos conjuntos y . En lo que sigue, eliminaremos el subíndice para aclarar la notación. Suponga corregir las latencias inducidas poren el gráfico: el bienestar condicional de con respecto a Se define como
Hecho 1 . Dado un flujo de equilibrio de Nash y cualquier otro flujo , .
Prueba (por contradicción) . Asumir que. Por definición,
- .
Desde y están asociados con los mismos conjuntos , lo sabemos
Por lo tanto, debe haber un par y dos caminos de a tal que , , y
En otras palabras, el flujo puede lograr un bienestar menor que solo si hay dos caminos desde a teniendo diferentes costos, y si desvía algún flujo de de la ruta de mayor costo a la ruta de menor costo. Esta situación es claramente incompatible con el supuesto de quees un flujo de equilibrio de Nash. QED
Tenga en cuenta que el Hecho 1 no asume ninguna estructura particular en el conjunto .
Hecho 2 . Dados dos números reales cualesquiera y , .
Prueba . Esta es otra forma de expresar la verdadera desigualdad.. QED
Teorema . El PoA puro de cualquier problema de enrutamiento generalizado con latencias lineales es .
Prueba . Tenga en cuenta que este teorema equivale a decir que para cada flujo de equilibrio de Nash, , dónde es cualquier otro flujo. Por definición,
Al usar Fact 2, tenemos que
desde
Podemos concluir que y pruebe la tesis utilizando el Hecho 1. QED
Nótese que en la demostración hemos hecho un uso extensivo del supuesto de que las funciones en son lineales. En realidad, se mantiene un hecho más general.
Teorema . Dado un problema de enrutamiento generalizado con gráfico y funciones de latencia polinomial de grado con coeficientes no negativos, el PoA puro es .
Tenga en cuenta que el PoA puede crecer con . Considere el ejemplo que se muestra en la siguiente figura, donde asumimos flujo unitario: los flujos de equilibrio de Nash tienen bienestar social 1; sin embargo, el mejor bienestar se logra cuando, en ese caso
Esta cantidad tiende a cero cuando tiende al infinito.
Ver también
- Tragedia de los comunes
- Juego de ubicación de instalaciones competitivo : un juego con un pequeño precio de anarquía.
- El precio de la anarquía en las subastas
Referencias
- ^ a b Koutsoupias, Elias; Papadimitriou, Christos (mayo de 2009). "Equilibrios en el peor de los casos" . Revisión de Ciencias de la Computación . 3 (2): 65–69. Archivado desde el original el 13 de marzo de 2016 . Consultado el 12 de septiembre de 2010 .
- ^ M. Goemans, V. Mirrokni, A. Vetta, Sink equilibria and convergence , FOCS 05
- ^ P. Dubey. Ineficiencia de los equilibrios de Nash. Matemáticas. Operat. Res., 11 (1): 1–8, 1986
- 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 algorítmica de juegos (PDF) . Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-87282-0..
- Tim Roughgarden (2005). Enrutamiento egoísta y el precio de la anarquía . Prensa del MIT . ISBN 0-262-18243-2.Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )
Otras lecturas
- Fabio Cunial, Precio de la anarquía