Precio de la estabilidad

En teoría de juegos , el precio de estabilidad (PoS) de un juego es la relación entre el mejor valor de la función objetivo de uno de sus equilibrios y el de un resultado óptimo. El PoS es relevante para juegos en los que existe alguna autoridad objetiva que puede influir un poco en los jugadores y tal vez ayudarlos a converger hacia un buen equilibrio de Nash . Cuando medimos qué tan eficiente es un equilibrio de Nash en un juego específico, a menudo también hablamos del precio de la anarquía (PoA), que es la relación entre el peor valor de la función objetivo de uno de sus equilibrios y el de un resultado óptimo.

Ejemplos

Otra forma de expresar PoS es:

${\displaystyle {\text{PoS}}={\frac {\text{value of best Nash equilibrium}}{\text{value of optimal solution}}},\ {\text{PoS}}\geq 0.}$

En particular, si la solución óptima es un equilibrio de Nash, entonces el PoS es 1.

En el siguiente juego del dilema del prisionero , dado que existe un equilibrio único, tenemos PoS = PoA = 1/2. ${\displaystyle (B,R)}$

En este ejemplo, que es una versión del juego de batalla de sexos , hay dos puntos de equilibrio, y , con valores 3 y 15, respectivamente. El valor óptimo es 15. Por tanto, PoS = 1 mientras que PoA = 1/5. ${\displaystyle (T,L)}$ ${\displaystyle (B,R)}$

Antecedentes e hitos

El precio de la estabilidad fue estudiado por primera vez por A. Schulz y N. Stier-Moses, mientras que el término fue acuñado por E. Anshelevich et al. Schulz y Stier-Moses se centraron en los equilibrios en un juego de rutas egoísta en el que los bordes tienen capacidades. Anshelevich et al. estudió juegos de diseño de redes y demostró que siempre existe un equilibrio de Nash de estrategia pura y que el precio de la estabilidad de este juego es como máximo el enésimo número armónico en gráficos dirigidos. Para los gráficos no dirigidos, Anshelevich y otros presentaron un límite estricto del precio de la estabilidad de 4/3 para el caso de una sola fuente y dos jugadores. Jian Li ha demostrado que para gráficos no dirigidos con un destino distinguido al que todos los jugadores deben conectarse, el precio de la estabilidad del juego de diseño de redes Shapely es el número de jugadores. Por otro lado, el precio de la anarquía se trata en este juego. ${\displaystyle O(\log n/\log \log n)}$ ${\displaystyle n}$ ${\displaystyle n}$

Juegos de diseño de redes.

Configuración

Los juegos de diseño de redes tienen una motivación muy natural para el Precio de la Estabilidad. En estos juegos, el precio de la anarquía puede ser mucho peor que el precio de la estabilidad.

Considere el siguiente juego.

• ${\displaystyle n}$jugadores;
• Cada jugador pretende conectarse en un gráfico dirigido ; ${\displaystyle i}$ ${\displaystyle s_{i}}$ ${\displaystyle t_{i}}$ ${\displaystyle G=(V,E)}$
• Las estrategias para un jugador son todos caminos de hacia adentro ; ${\displaystyle P_{i}}$ ${\displaystyle s_{i}}$ ${\displaystyle t_{i}}$ ${\displaystyle G}$
• Cada arista tiene un coste ; ${\displaystyle c_{i}}$
• 'Asignación justa de costos': cuando los jugadores eligen ventaja , el costo se divide equitativamente entre ellos; ${\displaystyle n_{e}}$ ${\displaystyle e}$ ${\displaystyle \textstyle d_{e}(n_{e})={\frac {c_{e}}{n_{e}}}}$
• El costo del jugador es ${\displaystyle \textstyle C_{i}(S)=\sum _{e\in P_{i}}{\frac {c_{e}}{n_{e}}}}$
• El coste social es la suma de los costes del jugador: . ${\displaystyle \textstyle SC(S)=\sum _{i}C_{i}(S)=\sum _{e\in S}n_{e}{\frac {c_{e}}{n_{e}}}=\sum _{e\in S}c_{e}}$

Un juego de diseño de redes con Price of Anarchy ${\displaystyle \Omega (n)}$

El precio de la anarquía

El precio de la anarquía puede ser ... Considere el siguiente juego de diseño de redes. ${\displaystyle \Omega (n)}$

Juego El precio patológico de la estabilidad

Considere dos equilibrios diferentes en este juego. Si todos comparten la ventaja, el costo social es . De hecho, este equilibrio es óptimo. Tenga en cuenta, sin embargo, que todos los que comparten la ventaja también son un equilibrio de Nash. Cada agente tiene un costo en equilibrio y cambiar al otro extremo aumenta su costo a . ${\displaystyle 1+\varepsilon }$ ${\displaystyle 1+\varepsilon }$ ${\displaystyle n}$ ${\displaystyle 1}$ ${\displaystyle 1+\varepsilon }$

Límite inferior del precio de la estabilidad

En cambio, aquí hay un juego patológico en el mismo espíritu para el Precio de la Estabilidad. Considere los jugadores, cada uno de los cuales se origina e intenta conectarse a . El costo de los bordes sin etiquetar se considera 0. ${\displaystyle n}$ ${\displaystyle s_{i}}$ ${\displaystyle t}$

La estrategia óptima es que todos compartan la ventaja, generando un costo social total . Sin embargo, hay un Nash único para este juego. Tenga en cuenta que cuando está en el punto óptimo, cada jugador paga y el jugador 1 puede reducir su costo cambiando al borde. Una vez que esto haya sucedido, al jugador 2 le interesará cambiar al borde, y así sucesivamente. Con el tiempo, los agentes alcanzarán el equilibrio de Nash de pagar por su propia ventaja. Esta asignación tiene costo social , donde está el número armónico ^th , que es . Aunque no tiene límites, el precio de la estabilidad es exponencialmente mejor que el precio de la anarquía en este juego. ${\displaystyle 1+\varepsilon }$ ${\displaystyle 1+\varepsilon }$ ${\displaystyle \textstyle {\frac {1+\varepsilon }{n}}}$ ${\displaystyle \textstyle {\frac {1}{n}}}$ ${\displaystyle \textstyle {\frac {1}{n-1}}}$ ${\displaystyle \textstyle 1+{\frac {1}{2}}+\cdots +{\frac {1}{n}}=H_{n}}$ ${\displaystyle H_{n}}$ ${\displaystyle n}$ ${\displaystyle \Theta (\log n)}$

Límite superior del precio de la estabilidad

Tenga en cuenta que, por diseño, los juegos de diseño de redes son juegos de congestión. Por tanto, admiten una función potencial . ${\displaystyle \textstyle \Phi =\sum _{e}\sum _{i=1}^{n_{e}}{\frac {c_{e}}{i}}}$

Teorema. [Teorema 19.13 de la referencia 1] Supongamos que existen constantes tales que para cada estrategia , ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle S}$

${\displaystyle A\cdot SC(S)\leq \Phi (S)\leq B\cdot SC(S).}$

Entonces el precio de la estabilidad es menor que ${\displaystyle B/A}$

Prueba. El mínimo global de es un equilibrio de Nash, por lo que ${\displaystyle NE}$ ${\displaystyle \Phi }$

${\displaystyle SC(NE)\leq 1/A\cdot \Phi (NE)\leq 1/A\cdot \Phi (OPT)\leq B/A\cdot SC(OPT).}$

Ahora recuerde que el costo social se definió como la suma de los costos sobre los bordes, por lo que

${\displaystyle \Phi (S)=\sum _{e\in S}\sum _{i=1}^{n_{e}}{\frac {c_{e}}{i}}=\sum _{e\in S}c_{e}H_{n_{e}}\leq \sum _{e\in S}c_{e}H_{n}=H_{n}\cdot SC(S).}$

Tenemos trivialmente , y el cálculo anterior da , por lo que podemos invocar el teorema para determinar un límite superior del precio de la estabilidad. ${\displaystyle A=1}$ ${\displaystyle B=H_{n}}$

Ver también

• El precio de la anarquía
• Juego competitivo de ubicación de instalaciones : un juego sin precio de estabilidad.

Referencias

1. AS Schulz, NE Stier-Moses. Sobre el comportamiento de los equilibrios de usuarios en las redes de tráfico . Actas del 14º Simposio anual ACM-SIAM sobre algoritmos discretos (SODA), 2003.
2. E. Anshelevich, E. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, T. Roughgarden. "El precio de la estabilidad para el diseño de redes con una asignación justa de costos" . SIAM Journal on Computing, 38:4, 1602-1623, 2008. La versión de la conferencia apareció en FOCS 2004.
3. Vazirani, Vijay V .; Nisán, Noam ; Jardín rugoso, Tim ; Tardos, Éva (2007). Teoría algorítmica de juegos (PDF) . Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-87282-0.
4. L. Agussurja y HC Lau. El precio de la estabilidad en los juegos de programación egoístas . Inteligencia web y sistemas de agentes: una revista internacional, 9:4, 2009.
5. Jian Li. Un límite superior en el precio de la estabilidad para los juegos de diseño de redes Shapely no dirigidos. Cartas de procesamiento de información 109 (15), 876-878, 2009. ${\displaystyle O(\log n/\log \log n)}$