Ubicación de la instalación (juego competitivo)

El juego de ubicación de instalaciones competitivas es un tipo de juego competitivo en el que los proveedores de servicios seleccionan ubicaciones para ubicar 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, la conexión eléctrica.
Hay varios productores que pueden suministrar este servicio, por ejemplo, las compañías eléctricas.
Cada productor puede construir sus instalaciones (por ejemplo, una central eléctrica) en uno de varios lugares.
Para cada par de consumidor (C) y ubicación (L), existe un costo fijo de dar servicio a C desde L (por ejemplo, dependiendo de la distancia entre la central eléctrica y la casa del consumidor). Este costo se denota Cost[C,L].

El juego es un juego secuencial con tres pasos:

Cada productor selecciona una ubicación para ubicar sus instalaciones.
Cada productor fija un precio para cada usuario ( se permite la discriminación de precios , ya que existe un coste diferente por atender a distintos consumidores).
Cada consumidor selecciona una instalación a la que conectarse.

Cada consumidor tiene un cierto valor privado por aceptar el servicio.

Para cada par consumidor-productor:

La ganancia del consumidor por conectarse a la instalación 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 coste del servicio.

Equilibrio

Analizamos el juego utilizando inducción hacia atrás .

El paso 3 es sencillo: cada consumidor simplemente selecciona la instalación más barata.

El paso 2 también es bastante simple. Supongamos que un productor P tiene su instalación en la ubicación L. Entonces, el precio que cobra al consumidor C debe ser al menos Cost[C,L]. Supongamos que las ubicaciones están ordenadas en orden creciente del costo, es decir, las ubicaciones son L1, L2, ... de modo que Cost[C,L1]<Cost[C,L2]<... Entonces, el productor cuya instalación está en la ubicación L1 siempre puede ganar al consumidor ofreciéndole el precio Cost[C,L2]. Esto se debe a que el productor cuya instalación está en L2 no puede ofrecer un precio más bajo. Por lo tanto, en el paso 2 cada productor fija el precio al consumidor C de acuerdo con el costo del siguiente productor más barato.

El paso 1 -el paso de ubicación de la instalación- es más difícil de analizar (por eso el juego lleva este nombre). Es posible demostrar 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 de Nash puro y todo el juego tiene un equilibrio perfecto en subjuegos puro .

Además, todo resultado de máximo bienestar es también un resultado de máximo potencial, por lo que también debe ser un equilibrio de Nash. Esto significa que el precio de la estabilidad es 1.

El juego de la ubicación de las instalaciones puede tener otros equilibrios de Nash puros, en los que el bienestar social no sea 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 al equilibrio. Consideremos 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 2 veces el óptimo. Este último resultado es cierto en una clase mucho más general de juegos, llamados juegos de utilidad. ^[3]^[4] $O(n\cdot \ln(1/\epsilon ))$ $1/2-\épsilon$

Véase también

Referencias

^ Vetta, A. (2002). "Equilibrios de Nash en sociedades competitivas, con aplicaciones a la localización de instalaciones, el enrutamiento del tráfico y las subastas". 43.° Simposio anual IEEE sobre fundamentos de la informática, 2002. Actas . pág. 416. doi :10.1109/SFCS.2002.1181966. ISBN . 0-7695-1822-2.
^ abc Eva Tardos y Tom Wexler, "Network Formation Games". Capítulo 19 en Vazirani, Vijay V. ; Nisan, Noam ; Roughgarden, Tim ; Tardos, Éva (2007). Teoría de juegos algorítmicos (PDF) . Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-87282-0.
^ Mirrokni, Vahab S.; Vetta, Adrian (2004). "Cuestiones de convergencia en juegos competitivos". Aproximación, aleatorización y optimización combinatoria. Algoritmos y técnicas . Apuntes de clase en informática. Vol. 3122. pág. 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 sumideros y convergencia". 46.º Simposio anual IEEE sobre fundamentos de la informática (FOCS'05) . pág. 142. doi :10.1109/SFCS.2005.68. ISBN 0-7695-2468-0.