Assortment Planning with Sponsored Products

Resumo Técnico: Planejamento de Sortimento com Produtos Patrocinados

Definição do Problema
Este artigo aborda o problema de planejamento de sortimento no e-commerce e em sistemas de recomendação, estendendo especificamente o escopo para incluir produtos patrocinados ao lado de produtos orgânicos tradicionais. Embora pesquisas anteriores (por exemplo, Talluri e Van Ryzin 2004) tenham se concentrado predominantemente em produtos orgânicos, a ascensão de posicionamentos patrocinados (ex: Amazon, Facebook, Google) introduz um desafio de otimização complexo. A plataforma deve selecionar e posicionar um conjunto de $k$ produtos para maximizar a receita esperada, aderindo a restrições específicas impostas pelos anunciantes.

A dificuldade central reside em equilibrar os objetivos de receita da plataforma com os requisitos obrigatórios dos produtos patrocinados. Diferente dos produtos orgânicos, que podem ser colocados em posições arbitrárias, os produtos patrocinados frequentemente trazem restrições de posicionamento rigorosas derivadas de mecanismos de leilão (ex: um anunciante dando lances por as "$m$ melhores" posições ou uma vaga específica baseada em pontuações de qualidade). O problema é formulado como uma tarefa de otimização combinatória onde o objetivo é encontrar uma sequência viável de produtos que maximize a receita esperada sob o modelo de escolha Logit Multinomial (MNL).

Metodologia
Os autores modelam o comportamento de escolha do consumidor usando o modelo MNL, onde a probabilidade de um consumidor selecionar o produto $i$ depende de sua utilidade intrínseca em uma posição específica e das utilidades de todos os outros produtos exibidos. A função de receita é não linear devido ao denominador na probabilidade de escolha, que inclui a soma das utilidades de todos os itens selecionados.

O artigo propõe uma abordagem algorítmica de duas frentes, dependendo das restrições:

1. Solução Exata para Restrições Básicas:
   Quando a única restrição é o posicionamento obrigatório de produtos patrocinados (cada produto patrocinado $i$ deve ser atribuído a uma posição válida $t \in R_i$), o problema é formulado como um problema de atribuição. Os autores demonstram que a matriz de restrição é totalmente unimodular. Consequentemente, o problema pode ser resolvido de forma ótima relaxando as restrições inteiras para uma formulação de Programação Linear (LP), o que garante a obtenção de uma solução inteira.

2. Algoritmo de Aproximação para Restrições Estendidas:
   O artigo estende o problema para incluir restrições adicionais na seleção de produtos orgânicos, tais como restrições de capacidade (knapsack) (custo total $\le C$) ou restrições de matroide de partição (limites no número de itens de grupos específicos).

   • Estratégia de Decomposição: A solução ótima é decomposta em duas partes: receita de produtos patrocinados e receita de produtos orgânicos. Os autores constroem dois sortimentos candidatos:
     • Candidato I: Otimiza a receita considerando apenas produtos patrocinados (ignorando os orgânicos).
     • Candidato II: Primeiro minimiza o peso total (utilidade) dos produtos patrocinados para "economizar" utilidade para a seleção orgânica, e então otimiza o sortimento de produtos orgânicos dada a seleção fixa de patrocinados.
   • Seleção Aleatória: A solução final seleciona o melhor dos dois candidatos. A análise teórica mostra que, se o subproblema orgânico (P.5) puder ser aproximado dentro de uma razão $\beta$, o algoritmo geral alcança uma razão de aproximação de $\frac{\beta}{\beta+1}$.
   • Otimização Submodular: Para resolver o subproblema orgânico (P.5) sob restrições complexas, os autores transformam o problema de sequenciamento em um problema de seleção de subconjuntos sobre um conjunto base de pares produto-posição. Eles provam que a função de utilidade resultante é monótona e submodular. Isso permite a aplicação de algoritmos de maximização submodular de última geração:
     • Para restrições de knapsack, utilizam um algoritmo que alcança uma razão de $\beta = 1/(1+\epsilon)^3$.
     • Para restrições de matroide de partição, utilizam um algoritmo que alcança uma razão de $\beta = 1/(2+\epsilon)$.

Principais Contribuições

• Formulação do Problema: O artigo define formalmente o problema de planejamento de sortimento na presença de produtos patrocinados com restrições de posição específicas, uma lacuna identificada na literatura existente que frequentemente assume que todos os produtos são orgânicos ou ignora a integração de patrocinados.
• Garantias Teóricas: Ao contrário de trabalhos anteriores que dependem de heurísticas de aprendizado profundo sem limites teóricos (ex: Liao et al. 2022), este artigo fornece garantias de aproximação rigorosas.
• Estrutura Algorítmica: Os autores desenvolvem uma estrutura que faz a ponte entre a maximização de receita da plataforma e as restrições dos anunciantes. Eles provam que o problema básico é solucionável em tempo polinomial via LP e fornecem um algoritmo de aproximação de fator constante para a variante mais complexa envolvendo restrições de capacidade ou diversidade em produtos orgânicos.
• Prova de Submodularidade: Uma contribuição técnica significativa é a prova de que a função de utilidade transformada para a seleção de produtos orgânicos é submodular, permitendo o uso de algoritmos de aproximação eficientes para restrições NP-difíceis.

Resultos
O artigo estabelece os seguintes resultados teóricos:

• Para o problema básico (apenas restrições de patrocinados), uma solução ótima pode ser computada eficientemente.
• Para o problema estendido (restrições de patrocinados + restrições de capacidade/matroide de produtos orgânicos), o algoritmo proposto alcança uma razão de aproximação de:
  • $\frac{1}{(1+\epsilon)^3 + 1}$ para restrições de knapsack.
  • $\frac{1}{(2+\epsilon) + 1}$ para restrições de matroide de partição.
  • (Nota: O artigo deriva a razão final como $\frac{\beta}{\beta+1}$, onde $\beta$ é a razão de aproximação do subproblema).

Significância e Alegações
Os autores alegam que esta pesquisa aborda uma lacuna crítica na literatura de planejamento de sortimento ao modelar explicitamente a integração de produtos patrocinados. A significância do trabalho reside em fornecer garantias teóricas para soluções que equilibram os objetivos frequentemente conflitantes das plataformas (maximização de receita) e dos anunciantes (requisitos de posicionamento específicos). O artigo afirma que sua abordagem oferece às empresas um método para integrar produtos patrocinados de forma fluida sem comprometer as estratégias gerais de receita ou a experiência do usuário, fundamentado em limites matemáticos comprováveis em vez de desempenho heurístico. O trabalho é apresentado como um passo fundamental para pesquisas futuras neste domínio em evolução dos sistemas de recomendação de e-commerce.