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 hay alguna autoridad objetiva que puede influir un poco en los jugadores y quizás ayudarlos a converger hacia un buen equilibrio de Nash . Al medir la eficiencia de un equilibrio de Nash en un juego específico, a menudo también hablamos del precio de la anarquía (PoA).
En el siguiente juego del dilema del prisionero , dado que hay un único equilibrio , tenemos PoS = PoA = 1/2.
En este ejemplo, que es una versión del juego de la batalla de los sexos, hay dos puntos de equilibrio, y , con valores de 3 y 15, respectivamente. El valor óptimo es 15. Por lo tanto, PoS = 1 mientras que PoA = 1/5.
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 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 número armónico n en gráficos dirigidos. Para gráficos no dirigidos, Anshelevich y otros presentaron un límite estricto en el precio de la estabilidad de 4/3 para 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 dondees el número de jugadores. Por otro lado, el precio de la anarquía está en este juego.
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.
El precio de la anarquía puede ser . Considere el siguiente juego de diseño de redes.
