El precio de la estabilidad

En teoría de juegos , el precio de la 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 los 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 la eficiencia de 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 de dilema del prisionero , como hay un único equilibrio, tenemos PoS = PoA = 1/2. ${\displaystyle (B,R)}$

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

Antecedentes y 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 enrutamiento egoísta en el que las aristas tienen capacidades. Anshelevich et al. estudiaron juegos de diseño de redes y demostraron 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 n-ésimo número armónico en grafos dirigidos. Para grafos no dirigidos, Anshelevich y otros presentaron un límite estricto para el precio de la estabilidad de 4/3 para un caso de una sola fuente y dos jugadores. Jian Li ha demostrado que para grafos 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 donde es el número de jugadores. Por otro lado, el precio de la anarquía es aproximadamente 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.

Consideremos el siguiente juego.

• ${\displaystyle n}$jugadores;
• Cada jugador tiene como objetivo conectarse a 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 a en ; ${\displaystyle P_{i}}$ ${\displaystyle s_{i}}$ ${\displaystyle t_{i}}$ ${\displaystyle G}$
• Cada arista tiene un costo ; ${\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 ... Consideremos el siguiente juego de diseño de redes. ${\displaystyle \Omega (n)}$

Juego del precio patológico de la estabilidad

Consideremos dos equilibrios diferentes en este juego. Si todos comparten la ventaja, el costo social es . Este equilibrio es, en efecto, óptimo. Obsérvese, sin embargo, que el hecho de que todos compartan la ventaja también es un equilibrio de Nash. Cada agente tiene un costo en el equilibrio, y cambiar al otro lado 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í tenemos un juego patológico con el mismo espíritu para el precio de la estabilidad. Consideremos a los jugadores, cada uno de los cuales se origina en e intenta conectarse con . 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, lo que produce un costo social total . Sin embargo, existe un Nash único para este juego. Nótese que cuando se encuentra en el óptimo, cada jugador paga , y el jugador 1 puede disminuir su costo cambiando a la ventaja. Una vez que esto haya sucedido, será en interés del jugador 2 cambiar a la ventaja, y así sucesivamente. Finalmente, los agentes alcanzarán el equilibrio de Nash de pagar por su propia ventaja. Esta asignación tiene un costo social , donde es el número armónico ⁿ ° , que es . Aunque no está acotado, 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 lo 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] Supóngase que existen constantes y 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}$

Demostración. 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 recordemos 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).}$

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

Véase también

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

Referencias

1. AS Schulz, NE Stier-Moses. Sobre el desempeño de los equilibrios de usuario en 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 asignación justa de costos . SIAM Journal on Computing, 38:4, 1602-1623, 2008. La versión de 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ísta . Web Intelligence and Agent Systems: An International Journal, 9:4, 2009.
5. Jian Li. Un límite superior para el precio de la estabilidad en juegos de diseño de redes Shapely no dirigidos. Information Processing Letters 109 (15), 876-878, 2009. ${\displaystyle O(\log n/\log \log n)}$