Online Price Competition under Generalized Linear Demands

Resumen Técnico: Competencia de Precios en Línea bajo Demandas Lineales Generalizadas

Formulación del Problema
El artículo aborda el problema de la competencia de precios secuencial entre $N$ vendedores que operan durante un horizonte de tiempo finito $T$. A diferencia de los entornos monopolísticos tradicionales o de los modelos competitivos previos que asumen una demanda lineal, este trabajo considera un marco de demanda lineal generalizada (de índice único). Para cada vendedor $i$, la demanda esperada se modela como:
$$\lambda_i(p) = \mu_i(\langle \theta_{i,0}, p \rangle) = \mu_i(-\beta_{i,0}p_i + \langle \gamma_{i,0}, p_{-i} \rangle)$$
donde:

• $p$ es el vector de precios establecidos por todos los vendedores simultáneamente.
• $\mu_i$ es una función de enlace conocida y estrictamente creciente (por ejemplo, logística para resultados binarios, identidad para lineales).
• $\theta_{i,0}$ es un vector de parámetros desconocido que contiene la sensibilidad del propio precio del vendedor ($-\beta_{i,0}$) y las sensibilidades de los precios de los competidores ($\gamma_{i,0}$).
• Las observaciones de la demanda $y_i(t)$ siguen una distribución de familia exponencial canónica condicionada en los precios.

Estructura de Información y Restricciones
El entorno se caracteriza por una asimetría de información específica, distinta del Aprendizaje por Refuerzo Multi-Agente (MARL) estándar:

1. Observabilidad Parcial: Cada vendedor observa únicamente su propia demanda realizada (o ingresos) y los precios establecidos por sus rivales. No observan las demandas o ingresos realizados de los competidores.
2. Movimientos Simultáneos: Los vendedores eligen los precios simultáneamente. En consecuencia, un vendedor observa el contexto (precios de los rivales $p_{-i}$) solo después de elegir su propia acción $p_i$, lo que crea una asimetría temporal que imposibilita los análisis de bandidos contextuales estándar donde el contexto se observa antes de la selección de la acción.
3. Sin Coordinación: La política debe ser totalmente descentralizada; los vendedores no pueden coordinar las fases de exploración.

Metodología: PML-GLUCB
Los autores proponen PML-GLUCB (Máxima Verosimilitud Penalizada con Límite de Confianza Superior para Modelos Lineales Generalizados), un algoritmo descentralizado que elimina la necesidad de una fase de exploración coordinada y de carga frontal. El método opera de la siguiente manera:

1. Estimación de Máxima Verosimilitud Penalizada (PMLE): En cada ronda $t$, el vendedor $i$ actualiza su estimación de $\theta_{i,0}$ maximizando una función de log-verosimilitud penalizada basada en los datos históricos $(p(s), y_i(s))_{s < t}$. Para asegurar que el estimador permanezca dentro del espacio de parámetros acotado $\Theta_i$, se aplica un paso de proyección si el PMLE bruto excede el límite de norma.
2. Precios Optimistas (UCB): En lugar de una estrategia pura de "explorar-luego-comprometerse", el algoritmo emplea un enfoque de Límite de Confianza Superior (UCB). El vendedor construye una estimación optimista de la función de ingresos añadiendo un bono de confianza a la función de ingresos estimada. El bono se deriva de una desigualdad de concentración adaptada para el modelo lineal generalizado, utilizando un límite de potencial elíptico adaptado para movimientos simultáneos.
3. Actualización de Mejor Respuesta: El vendedor selecciona el precio $p_i(t)$ que maximiza esta función de ingresos optimista dado los precios observados de los competidores de la ronda anterior (o de la ronda actual, dependiendo del momento específico de actualización en el algoritmo, aunque el texto enfatiza observar $p_{-i}$ después de elegir $p_i$ en el entorno general; el algoritmo utiliza $p(t-1)_{-i}$ para la decisión en $t$).

Contribuciones Clave

1. Aprendizaje sin Exploración de Carga Frontal: El artículo introduce una política que aprende y optimiza simultáneamente sin requerir una fase inicial de precios aleatorios i.i.d. Esto aborda limitaciones prácticas donde "experimentar con los precios" suele ser inviable y evita la dependencia de constantes desconocidas específicas del problema necesarias para determinar la longitud de la exploración en trabajos previos.
2. Generalización de Modelos de Demanda: El marco generaliza estrictamente los modelos de demanda lineal existentes para incluir una amplia clase de modelos de índice único no lineales y monótonos. Unifica el análisis tanto de la demanda binaria (compra/no compra) como de las observaciones de demanda continua bajo un mismo paraguas teórico.
3. Nuevas Herramientas de Concentración: Debido a la naturaleza de movimientos simultáneos del juego, los lemas de potencial elíptico estándar (que asumen un contexto exógeno) no pueden aplicarse directamente. Los autores derivan un nuevo límite de tipo elíptico (Lema C.2) adecuado para entornos donde el contexto (precios de los rivales) es endógeno y se observa con retraso respecto a la acción.

Resultados

• Límite de Regret (Arrepentimiento): Relativo a un referente dinámico (la mejor respuesta a la secuencia de precios de los rivales en retrospectiva), cada vendedor logra un límite de regret de:
  $$\text{Reg}_i(T) = \tilde{O}(N^2 \sqrt{T})$$
  Esto iguala la tasa óptima $\tilde{O}(\sqrt{T})$ conocida para la fijación de precios competitivos lineales, salvo por factores logarítmicos y una dependencia en el número de vendedores $N$.
• Convergencia al Equilibrio: El algoritmo asegura que la desviación cuadrática media del vector de precios respecto al vector de precios del Equilibrio de Nash (NE) decae como:
  $$\frac{1}{T} \sum_{t=1}^T \mathbb{E}[\|p(t) - p^*\|_2^2] = \tilde{O}\left(\frac{N^2}{\sqrt{T}}\right)$$
  Esto indica que el juego con regret óptimo mantiene el mercado cerca del equilibrio de Nash en promedio.
• Complejidad Computacional: El algoritmo es computacionalmente tratable, con una complejidad por ronda de $O(N^2)$ por vendedor (dominada por actualizaciones de matrices y productos vectoriales), lo que lo hace escalable para un $N$ moderado.

Significancia y Reivindicaciones
El artículo afirma que PML-GLUCB es orden-óptimo (óptimo minimax salvo factores logarítmicos) en el entorno lineal generalizado. Al eliminar el requisito de una exploración coordinada, el método se alinea más estrechamente con las condiciones de mercado realistas donde las empresas actúan de forma independiente y no pueden comprometerse previamente a esquemas de exploración. El trabajo cierra la brecha entre el aprendizaje de la demanda teórica y la implementación práctica en entornos competitivos con estructuras de demanda no lineales.

Los autores señalan que, si bien la dependencia de $\sqrt{T}$ es óptima, la dependencia de $N^2$ respecto al número de vendedores sigue siendo una cuestión abierta sobre su ajuste. Además, el artículo reconoce que, aunque la desviación promedio del equilibrio está controlada, la convergencia puntual de la secuencia de precios al NE no está garantizada sin una fase de exploración i.i.d. inicial, lo cual es consistente con la literatura más amplia sobre algoritmos de bandidos adaptativos.