El precio de la estabilidad

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 9 de marzo de 2022; las comprobaciones requieren 16 ediciones .

El precio de la estabilidad ( precio inglés de estabilidad , PoS) para el juego es la relación entre el valor óptimo de la función objetivo en uno de sus estados de equilibrio y el resultado óptimo. El precio de la estabilidad tiene sentido para los juegos que tienen un mayor poder o condiciones de juego que afectan la posición de los jugadores de alguna manera y pueden ayudarlos a converger al equilibrio de Nash . Al medir la efectividad del equilibrio de Nash en cualquier juego, tiene sentido considerar el precio de la anarquía ( Eng. Price of Anarchy , PoA).

Ejemplos

PoS se puede expresar de la siguiente manera:

PoS={\frac {N}{S)),\PoS\geqslant 0.

Aquí , es el valor del mejor equilibrio de Nash y es el valor de la solución óptima. ${\ estilo de texto N}$ ${\ estilo de texto S}$

En el juego del dilema del prisionero a continuación , los jugadores no siempre cooperarán entre sí, incluso si es lo mejor para ellos, ya que solo hay un equilibrio ( , ), tenemos . ${\ estilo de texto B}$ ${\ estilo de texto R}$ $PoS=PoA={\tfrac {1}{2))$

El dilema del prisionero

	${\ estilo de texto L}$	${\ estilo de texto R}$
${\ estilo de texto T}$	(2.2)	(0.3)
${\ estilo de texto B}$	(3.0)	(1.1)

Este ejemplo es una versión del juego de la batalla de los sexos . Tiene dos puntos de equilibrio, ( , ) y ( , ) con valores 3 y 15, respectivamente. El valor óptimo es 15. Entonces , while . ${\ estilo de texto T}$ ${\ estilo de texto L}$ ${\ estilo de texto B}$ ${\ estilo de texto R}$ $Punto de venta=1$ $PoA={\tfrac {1}{5}}$

Batalla de los sexos

	${\ estilo de texto L}$	${\ estilo de texto R}$
${\ estilo de texto T}$	(2.1)	(0.0)
${\ estilo de texto B}$	(0.0)	(5.10)

Antecedentes e hitos

El precio de la estabilidad fue estudiado por primera vez por A. Shultzan y N. Mozes, y el término mismo apareció en los trabajos de E. Anshelevich. Demostraron que el equilibrio de Nash siempre existe en estrategias puras, y el costo de estabilidad de este juego no excede el número armónico n-ésimo en gráficos dirigidos. Para gráficos no dirigidos, Anshelevich et al., presentaron un límite de estabilidad duro de 4/3 para el caso de una fuente y dos jugadores. Yen Lee demostró que para tales gráficos con diferentes destinos para todos los jugadores, con los que todos los jugadores deben tener una conexión, el precio de un flujo de juego estable para construir una red Shapley es donde está la cantidad de jugadores. Por otro lado, el costo de la anarquía para el juego es de aproximadamente . $O(\log n/\log \log n),$ $norte$ $norte$

Juegos de creación de redes

Condiciones de juego

Los juegos de creación de redes tienen una razón natural para el precio de la estabilidad. En estos juegos, el precio de la anarquía puede ser mucho menor que el precio de la estabilidad.

Un ejemplo del siguiente juego:

$norte$ jugadores;
El objetivo de cada jugador es conectar vértices y en un gráfico dirigido ; $i$ $si}$ $t_{yo}$ $G=(V,E)$
Las estrategias para el jugador son todas las rutas de a en el gráfico ; $Pi}$ $si}$ $t_{yo}$ $GRAMO$
Cada arco tiene un precio ; $c_{yo}$
"Distribución justa de precios": si los jugadores eligen un arco , el precio se distribuye por igual entre ellos; $nordeste}$ $mi$ $d_{e}(n_{e})={\frac {c_{e}}{n_{e}}}$
El precio por el jugador es ; $C_{i}(S)=\sum_{e\in P_{i}}{\frac {c_{e}}{n_{e}}}$
El costo social es igual a la suma de los precios para los jugadores: . $SC(S)=\sum_{i}C_{i}(S)=\sum_{e\in S}n_{e}{\frac {c_{e}}{n_{e}} }=\sum_{e\in S}c_{e}$

El precio de la anarquía

El precio de la anarquía puede ser . Un ejemplo del siguiente juego de creación de redes. $\ omega (n)$

Hay 2 saldos diferentes en este juego. Si todos comparten el arco , entonces el costo social es . Además, este equilibrio es óptimo. Sin embargo, la división por todos los arcos también es un equilibrio de Nash. Cualquier agente tiene un precio en la estrategia de equilibrio, y cambiarlo a otro arco eleva su precio a . $1+\varepsilon$ $1+\varepsilon$ $norte$ $una$ $1+\varepsilon$

El límite inferior del precio de estabilidad

Aquí hay un juego patológico con el mismo comportamiento, pero al precio de la estabilidad. Hay jugadores, cada uno de los cuales comienza en la parte superior e intenta conectarlo a la parte superior . Digamos que los precios de los arcos sin etiqueta son 0. $norte$ $si}$ $t$

La estrategia óptima para todos los jugadores es compartir el arco , lo que resulta en un costo social . Sin embargo, solo hay una estrategia de equilibrio de Nash para este juego. En el caso de la optimización, cada jugador paga y el jugador 1 puede reducir su precio cambiando al arco . Si esto sucede, resulta rentable para el jugador 2 cambiar al arco , y así sucesivamente. Eventualmente, los agentes alcanzarán un equilibrio de Nash pagando su propio arco por separado. Tal distribución tiene un costo social , donde es el número armónico th , que es igual a . Aunque este valor no tiene límite, el costo de la estabilidad es exponencialmente mejor que el costo de la anarquía en este juego. $1+\varepsilon$ $1+\varepsilon$ $\textstyle {\frac {1+\varepsilon}{n))$ ${\tfrac{1}{n))$ ${\ estilo de visualización {\ tfrac {1} {n-1}}}$ $1+{\tfrac {1}{2}}+\cdots +{\tfrac {1}{n}}=H_{n}$ $H_n$ $norte$ ${\ estilo de visualización \ Theta (\ log n)}$

Límite superior del precio de estabilidad

Por definición, los juegos de construcción de redes son juegos de desbordamiento , por lo que permiten una función potencial . $\Phi =\sum_{e}\sum_{i=1}^{n_{e}}{\frac {c_{e}}{i}}$

Teorema. [Teorema 19.13 del libro 1] Suponga que hay constantes y tales que para cualquier estrategia $A$ $B$ $S$

A\cdot SC(S)\leqslant \Phi (S)\leqslant B\cdot SC(S).

Entonces el precio de la estabilidad es menor. $LICENCIADO EN LETRAS$

Prueba. El mínimo global de la función es un equilibrio de Nash, de modo que ${\ estilo de visualización NE}$ $\Fi$

SC(NE)\leqslant 1/A\cdot \Phi (NE)\leqslant 1/A\cdot \Phi (OPT)\leqslant B/A\cdot SC(OPT).

El precio social se definió como la suma de los precios sobre los arcos, de modo que

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

Trivialmente obtenemos y los cálculos anteriores dan , por lo que podemos invocar el teorema para el límite superior del costo de estabilidad. $A=1$ $B=H_{n}$

Véase también

La distribución de objetos (juego competitivo) es un juego sin el precio de la estabilidad.

Notas

Literatura

Vijay V. Vazirani, Noam Nisan, Tim Roughgarden, Eva Tardos. Teoría de juegos algorítmicos . - Cambridge, Reino Unido: Cambridge University Press, 2007. - ISBN 0-521-87282-0 .
L. Agussurja, H. C. Lau. El precio de la estabilidad en los juegos de programación egoísta // Inteligencia web y sistemas de agentes: una revista internacional. - 2009. - T. 9 , núm. 4 .
Jian Li. Un límite superior en el precio de la estabilidad para juegos de diseño de red Shapely no dirigidos // Cartas de procesamiento de información. - 2009. - T. 109 , núm. 15 _ - S. 876-878 . $O(\log n/\log \log n)$

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