Ubicación de las instalaciones (juego competitivo)

El juego competitivo de localización de instalaciones es un tipo de juego competitivo en el que los proveedores de servicios seleccionan ubicaciones para colocar sus instalaciones con el fin de maximizar sus beneficios. ^{[ 1 ]}^{[ 2 ]}^{: 502–506} El juego tiene los siguientes componentes:

Existen varios consumidores que necesitan un determinado servicio, por ejemplo, la conexión eléctrica.
Existen varios proveedores que pueden ofrecer 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 para abastecer a C desde L (por ejemplo, dependiendo de la distancia entre la central eléctrica y la casa del consumidor). Este costo se denota como Costo[C,L].

El juego es un juego secuencial con tres pasos:

Cada productor selecciona un lugar 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 para atender a distintos consumidores).
Cada consumidor selecciona una instalación a la que conectarse.

Cada consumidor tiene un valor privado determinado al 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 atender al consumidor;
El bienestar social de esta pareja es la suma de las ganancias, es decir, el valor para el consumidor menos el costo del servicio.

Equilibrio

Analizamos el juego utilizando la 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 sencillo. Supongamos que un productor P tiene su planta en la ubicación L. Entonces, el precio que cobra al consumidor C debe ser al menos Costo[C,L]. Supongamos que las ubicaciones están ordenadas en orden creciente de costo, es decir, las ubicaciones son L1, L2, ... de manera que Costo[C,L1]<Costo[C,L2]<... Entonces, el productor cuya planta está en la ubicación L1 siempre puede ganar al consumidor ofreciéndole el precio Costo[C,L2]. Esto se debe a que el productor cuya planta está en L2 no puede ofrecer un precio más bajo. Por lo tanto, en el paso 2, cada productor fija el precio para el 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 recibe su nombre de este paso). 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 al beneficio del productor). ^{[ 2 ]}^{: 503–504} Por lo tanto, este paso tiene un equilibrio de Nash puro , y el juego completo tiene un equilibrio perfecto de subjuegos puro .

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

El juego de localización de instalaciones 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 dichos 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 $O(n\cdot \ln(1/\epsilon ))$ , entonces el bienestar social después de la secuencia es al menos $1/2-\epsilon$ veces el óptimo. Este último resultado es cierto en una clase de juegos mucho más general, llamados juegos de utilidad . ^{[ 3 ]}^{[ 4 ]}

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 del IEEE sobre Fundamentos de la Informática, 2002. Actas . pág. 416. doi : 10.1109/SFCS.2002.1181966 . ISBN 0-7695-1822-2.
1 2 3 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 de juegos algorítmica (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 . Notas de clase en informática. Vol. 3122. p. 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 IEEE sobre Fundamentos de la Informática (FOCS'05) . pág. 142. doi : 10.1109/SFCS.2005.68 . ISBN 0-7695-2468-0.

[vetta-1] 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 del IEEE sobre Fundamentos de la Informática, 2002. Actas . pág. 416. doi : 10.1109/SFCS.2002.1181966 . ISBN 0-7695-1822-2.

[agt-2] 1 2 3 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 de juegos algorítmica (PDF) . Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-87282-0.

[3] Mirrokni, Vahab S.; Vetta, Adrian (2004). "Problemas de convergencia en juegos competitivos". Aproximación, aleatorización y optimización combinatoria. Algoritmos y técnicas . Notas de clase en informática. Vol. 3122. p. 183. doi : 10.1007/978-3-540-27821-4_17 . ISBN 978-3-540-22894-3.

[4] Goemans, M.; Mirrokni, V.; Vetta, A. (2005). "Equilibrios de sumidero 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.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

Equilibrio

Véase también

Referencias

Articulos relacionados