Online Price Competition under Generalized Linear Demands

Resumo Técnico: Competição de Preços Online sob Demandas Lineares Generalizadas

Formulação do Problema
O artigo aborda o problema da competição de preços sequencial entre $N$ vendedores operando ao longo de um horizonte de tempo finito $T$. Diferente dos modelos monopolísticos tradicionais ou modelos competitivos prévios que assumem demanda linear, este trabalho considera um arcabouço de demanda linear generalizada (modelo de índice único). Para cada vendedor $i$, a demanda esperada é modelada 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)$$
onde:

• $p$ é o vetor de preços definidos por todos os vendedores simultaneamente.
• $\mu_i$ é uma função de ligação conhecida e estritamente crescente (ex: logística para resultados binários, identidade para linear).
• $\theta_{i,0}$ é um vetor de parâmetros desconhecidos contendo a sensibilidade do próprio preço do vendedor ($-\beta_{i,0}$) e as sensibilidades aos preços dos concorrentes ($\gamma_{i,0}$).
• As observações de demanda $y_i(t)$ seguem uma distribuição de família exponencial canônica condicionada aos preços.

Estrutura de Informação e Restrições
O cenário é caracterizado por uma assimetria de informação específica, distinta do Aprendizado por Reforço Multiagente (MARL) padrão:

1. Observabilidade Parcial: Cada vendedor observa apenas sua própria demanda realizada (ou receita) e os preços definidos por todos os rivais. Eles não observam as demandas ou receitas realizadas dos concorrentes.
2. Movimentos Simultâneos: Os vendedores escolhem preços simultaneamente. Consequentemente, um vendedor observa o contexto (preços dos rivais $p_{-i}$) apenas após escolher sua própria ação $p_i$, criando uma assimetria de tempo que impede as análises de bandit contextual padrão, onde o contexto é observado antes da seleção da ação.
3. Sem Coordenação: A política deve ser totalmente descentralizada; os vendedores não podem coordenar fases de exploração.

Metodologia: PML-GLUCB
Os autores propõem o PML-GLUCB (Generalized Linear Upper Confidence Bound de Máxima Verossimilhança Penalizada), um algoritmo descentralizado que elimina a necessidade de uma fase de exploração coordenada e front-loaded. O método opera da seguinte forma:

1. Estimativa de Máxima Verossimilhança Penalizada (PMLE): Em cada rodada $t$, o vendedor $i$ atualiza sua estimativa de $\theta_{i,0}$ maximizando uma função de log-verossimilhança penalizada baseada em dados históricos $(p(s), y_i(s))_{s < t}$. Para garantir que o estimador permaneça dentro do espaço de parâmetros limitado $\Theta_i$, uma etapa de projeção é aplicada caso o PMLE bruto exceda o limite de norma.
2. Preço Otimista (UCB): Em vez de uma estratégia pura de "explorar-então-comprometer" (explore-then-commit), o algoritmo emprega uma abordagem de Limite de Confiança Superior (UCB). O vendedor constrói uma estimativa otimista da função de receita adicionando um bônus de confiança à receita estimada. O bônus é derivado de uma desigualdade de concentração adaptada para o modelo linear generalizado, utilizando um limite de potencial elíptico adaptado para movimentos simultâneos.
3. Atualização de Melhor Resposta: O vendedor seleciona o preço $p_i(t)$ que maximiza esta função de receita otimista, dado os preços observados dos concorrentes da rodada anterior (ou da rodada atual, dependendo do tempo de atualização específico no algoritmo, embora o texto enfatize a observação de $p_{-i}$ após a escolha de $p_i$ no cenário geral; o algoritmo utiliza $p(t-1)_{-i}$ para a decisão em $t$).

Principais Contribuições

1. Aprendizado Sem Exploração Front-Loaded: O artigo introduz uma política que aprende e otimiza simultaneamente sem exigir uma fase inicial de precificação aleatória i.i.d. Isso aborda limitações práticas onde "experimentar preços" costuma ser inviável e evita a dependência de constantes desconhecidas específicas do problema necessárias para determinar a duração da exploração em trabalhos anteriores.
2. Generalização de Modelos de Demanda: O arcabouço generaliza estritamente os modelos de demanda linear existentes para incluir uma ampla classe de modelos de índice único não lineares e monótonos. Ele unifica a análise tanto de demanda binária (compra/não-compra) quanto de observações de demanda contínua sob um único guarda-chuva teórico.
3. Novas Ferramentas de Concentração: Devido à natureza de movimentos simultâneos do jogo, os lemas de potencial elíptico padrão (que assumem contexto exógeno) não podem ser aplicados diretamente. Os autores derivam um novo limite do tipo elíptico (Lema C.2) adequado para cenários onde o contexto (preços dos rivais) é endógeno e observado com atraso em relação à ação.

Resultos

• Limite de Regret (Arrependimento): Em relação a um benchmark dinâmico (a melhor resposta à sequência de preços dos rivais em retrospectiva), cada vendedor alcança um limite de regret de:
  $$\text{Reg}_i(T) = \tilde{O}(N^2 \sqrt{T})$$
  Isso corresponde à taxa ótima $\tilde{O}(\sqrt{T})$ conhecida para precificação competitiva linear, exceto pelos fatores logarítmicos e pela dependência do número de vendedores $N$.
• Convergência para o Equilíbrio: O algoritmo garante que o desvio quadrático médio do vetor de preços em relação ao vetor de preço do Equilíbrio de Nash (NE) decai como:
  $$\frac{1}{T} \sum_{t=1}^T \mathbb{E}[\|p(t) - p^*\|_2^2] = \tilde{O}\left(\frac{N^2}{\sqrt{T}}\right)$$
  Isso indica que o jogo com regret-ótimo mantém o mercado próximo ao equilíbrio de Nash, em média.
• Complexidade Computacional: O algoritmo é computacionalmente tratável, com uma complexidade por rodada de $O(N^2)$ por vendedor (dominada por atualizações de matriz e produtos vetoriais), tornando-o escalável para $N$ moderado.

Significância e Alegações
O artigo afirma que o PML-GLUCB é ordem-ótimo (minimax ótimo até fatores logarítmicos) no cenário de modelos lineares generalizados. Ao remover a exigência de exploração coordenada, o método alinha-se mais de perto com condições reais de mercado, onde as empresas atuam de forma independente e não podem pré-comprometer cronogramas de exploração. O trabalho preenche a lacência entre o aprendizado de demanda teórico e a implementação prática em ambientes competitivos com estruturas de demanda não lineares.

Os autores observam que, embora a dependência $\sqrt{T}$ seja ótima, a dependência $N^2$ em relação ao número de vendedores permanece uma questão aberta quanto à sua precisão (tightness). Além disso, o artigo reconhece que, embora o desvio médio do equilíbrio seja controlado, a convergência pontual da sequência de preços para o NE não é garantida sem uma fase inicial de exploração i.i.d., o que é consistente com a literatura mais ampla sobre algoritmos de bandit adaptativos.