Precio de la estabilidad

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${\displaystyle i}$tiene como objetivo conectar${\displaystyle s_{i}}$a${\displaystyle t_{i}}$en un grafo dirigido${\displaystyle G=(V,E)}$;
• Las estrategias${\displaystyle P_{i}}$para un jugador todos los caminos desde${\displaystyle s_{i}}$a${\displaystyle t_{i}}$en${\displaystyle G}$;
• Cada borde tiene un costo${\displaystyle c_{i}}$;
• 'Asignación justa de costos': Cuando${\displaystyle n_{e}}$Los jugadores eligen la ventaja${\displaystyle e}$el costo${\displaystyle \textstyle d_{e}(n_{e})={\frac {c_{e}}{n_{e}}}}$se divide a partes iguales entre ellos;
• El coste 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}}$.

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

Consideremos dos equilibrios diferentes en este juego. Si todos comparten el${\displaystyle 1+\varepsilon }$borde, el costo social es${\displaystyle 1+\varepsilon }$Este equilibrio es, de hecho, óptimo. Sin embargo, tenga en cuenta que todos los que comparten el${\displaystyle n}$borde también es un equilibrio de Nash. Cada agente tiene costo${\displaystyle 1}$en equilibrio, y cambiar al otro borde aumenta su costo a${\displaystyle 1+\varepsilon }$.

Aquí tenemos un juego patológico con el mismo espíritu, pero para el Precio de la Estabilidad. Consideremos${\displaystyle n}$jugadores, cada uno originario de${\displaystyle s_{i}}$y tratando de conectar con${\displaystyle t}$El coste de las aristas sin etiquetar se considera igual a 0.

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

Nótese 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] Supongamos que existen constantes${\displaystyle A}$y${\displaystyle B}$ de tal manera que para cada estrategia${\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${\displaystyle NE}$de${\displaystyle \Phi }$es un equilibrio de Nash, por lo tanto

${\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 en 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${\displaystyle A=1}$y el cálculo anterior da como resultado${\displaystyle B=H_{n}}$, por lo que podemos invocar el teorema para obtener una cota superior del precio de la estabilidad.