El juego competitivo de ubicación de instalaciones es una especie de juego competitivo en el que los proveedores de servicios seleccionan ubicaciones para colocar sus instalaciones con el fin de maximizar sus ganancias. [1] [2] : 502–506 El juego tiene los siguientes componentes:
- Hay varios consumidores que necesitan un determinado servicio, por ejemplo, conexión eléctrica.
- Hay varios productores que pueden suministrar este servicio, por ejemplo, empresas eléctricas.
- Cada productor puede construir su instalación (por ejemplo, una central eléctrica) en una de varias ubicaciones.
- Para cada par de consumidor (C) y ubicación (L), hay un costo fijo de servir C desde L (por ejemplo, dependiendo de la distancia entre la central eléctrica y la casa del consumidor). Este costo se denota Costo [C, L].
El juego es un juego secuencial con tres pasos:
- Cada productor selecciona un lugar para colocar su instalación.
- Cada productor establece un precio para cada usuario ( se permite la discriminación de precios , ya que hay un costo diferente para atender a diferentes consumidores).
- Cada consumidor selecciona una instalación a la que conectarse.
- Cada consumidor tiene un cierto valor privado para aceptar el servicio.
Para cada par consumidor-productor:
- La ganancia del consumidor por conectarse a las instalaciones del productor es su valor menos el precio;
- La ganancia del productor es el precio menos el costo de servir al consumidor;
- El bienestar social de este par es la suma de las ganancias, es decir, el valor del consumidor menos el costo del servicio.
Equilibrio
Analizamos el juego mediante inducción hacia atrás .
El paso 3 es simple: cada consumidor simplemente selecciona la instalación más barata.
El paso 2 también es bastante sencillo. Suponga que un productor P tiene su instalación en la ubicación L. Entonces, el precio que toma del consumidor C debe ser al menos el costo [C, L]. Suponga que las ubicaciones están ordenadas en orden creciente del costo, es decir, las ubicaciones son L1, L2, ... tal que Costo [C, L1]
El paso 1, el paso de ubicación de las instalaciones, es más difícil de analizar (por eso el juego lleva el nombre de este paso). Es posible probar que se trata de un juego potencial (el potencial es el bienestar social total; cuando un nuevo productor entra en el juego, el aumento del bienestar social es exactamente igual a la ganancia del productor). [2] : 503–504 Por lo tanto, este paso tiene un equilibrio puro de Nash , y todo el juego tiene un equilibrio perfecto puro en subjuegos .
Además, cada resultado de bienestar máximo es también un resultado de potencial máximo, por lo que también debe ser un equilibrio de Nash. Esto significa que el precio de la estabilidad es 1.
El juego instalación-ubicación puede tener otros equilibrios de Nash puros, en los que el bienestar social no es máximo. Sin embargo, es posible demostrar que el bienestar social en tales equilibrios es al menos la mitad del óptimo. Por lo tanto, el precio de la anarquía es como máximo 2. [2] : 505–506
Además, es posible demostrar que el precio de la anarquía es como máximo 2 incluso cuando el juego no converge hacia el equilibrio. Considere una secuencia aleatoria de movimientos de mejor respuesta. Si la longitud de la secuencia es, entonces el bienestar social después de la secuencia es al menos veces el óptimo. Este último resultado es cierto en una clase de juegos mucho más general, llamados juegos de utilidad . [3] [4]
Ver también
Referencias
- ^ Vetta, A. (2002). "Equilibrios de Nash en sociedades competitivas, con aplicaciones para ubicación de instalaciones, enrutamiento de tráfico y subastas". El 43º Simposio Anual del IEEE sobre Fundamentos de la Ciencia de la Computación, 2002. Actas . pag. 416. doi : 10.1109 / SFCS.2002.1181966 . ISBN 0-7695-1822-2.
- ^ a b c Eva Tardos y Tom Wexler, "Juegos de formación de redes". Capítulo 19 en Vazirani, Vijay V .; Nisan, Noam ; Roughgarden, Tim ; Tardos, Éva (2007). Teoría algorítmica de juegos (PDF) . Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-87282-0.
- ^ Mirrokni, Vahab S .; Vetta, Adrian (2004). "Problemas de convergencia en juegos competitivos". Aproximación, Aleatorización y Optimización Combinatoria. Algoritmos y Técnicas . Apuntes de conferencias en informática. 3122 . pag. 183. doi : 10.1007 / 978-3-540-27821-4_17 . ISBN 978-3-540-22894-3.
- ^ Goemans, M .; Mirrokni, V .; Vetta, A. (2005). "Equilibrios de sumidero y convergencia". 46º Simposio Anual del IEEE sobre Fundamentos de las Ciencias de la Computación (FOCS'05) . pag. 142. doi : 10.1109 / SFCS.2005.68 . ISBN 0-7695-2468-0.