Assortment Planning with Sponsored Products

Resumen Técnico: Planificación de Surtido con Productos Patrocinados

Planteamiento del Problema
Este artículo aborda el problema de la planificación de surtidos en el comercio electrónico y los sistemas de recomendación, extendiendo específicamente su alcance para incluir productos patrocinados junto con los productos orgánicos tradicionales. Mientras que la investigación previa (por ejemplo, Talluri y Van Ryzin 2004) se ha centrado predominantemente en productos orgánicos, el auge de las colocaciones patrocinadas (por ejemplo, en Amazon, Facebook, Google) introduce un desafío de optimización complejo. La plataforma debe seleccionar y posicionar un conjunto de $k$ productos para maximizar los ingresos esperados cumpliendo con restricciones específicas impuestas por los anunciantes.

La dificultad central radica en equilibrar los objetivos de ingresos de la plataforma con los requisitos obligatorios de los productos patrocinados. A diferencia de los productos orgánicos, que pueden colocarse en posiciones arbitrarias, los productos patrocinados suelen conllevar restricciones de colocación estrictas derivadas de mecanismos de subasta (por ejemplo, un anunciante pujando por posiciones "top-$m$" o un slot específico basado en puntuaciones de calidad). El problema se formula como una tarea de optimización combinatoria donde el objetivo es encontrar una secuencia factible de productos que maximice el ingreso esperado bajo el modelo de elección de Logit Multinomial (MNL).

Metodología
Los autores modelan el comportamiento de elección del consumidor utilizando el modelo MNL, donde la probabilidad de que un consumidor seleccione el producto $i$ depende de su utilidad intrínseca en una posición específica y de las utilidades de todos los demás productos mostrados. La función de ingresos es no lineal debido al denominador en la probabilidad de elección, que incluye la suma de las utilidades de todos los artículos seleccionados.

El artículo propone un enfoque algorítmico de dos vertientes dependiendo de las restricciones:

1. Solución Exacta para Restricciones Básicas:
   Cuando la única restricción es la colocación obligatoria de productos patrocinados (cada producto patrocinado $i$ debe asignarse a una posición válida $t \in R_i$), el problema se formula como un problema de asignación. Los autores demuestran que la matriz de restricciones es totalmente unimodular. En consecuencia, el problema puede resolverse de forma óptima mediante la relajación de las restricciones enteras a una formulación de Programación Lineal (LP), lo que garantiza la obtención de una solución entera.

2. Algoritmo de Aproximación para Restricciones Extendidas:
   El artículo extiende el problema para incluir restricciones adicionales sobre la selección de productos orgánicos, tales como restricciones de capacidad (mochila/knapsack) (costo total $\le C$) o restricciones de matroide de partición (límites en el número de elementos de grupos específicos).

   • Estrategia de Descomposición: La solución óptima se descompone en dos partes: ingresos de productos patrocinados e ingresos de productos orgánicos. Los autores construyen dos surtidos candidatos:
     • Candidato I: Optimiza los ingresos considerando solo productos patrocinados (ignorando los orgánicos).
     • Candidido II: Primero minimiza el peso total (utilidad) de los productos patrocinados para "ahorrar" utilidad para la selección orgánica, y luego optimiza el surtido de productos orgánicos dada la selección fija de patrocinados.
   • Selección Aleatorizada: La solución final selecciona el mejor de los dos candidatos. El análisis teórico muestra que si el subproblema orgánico (P.5) puede aproximarse con un ratio $\beta$, el algoritmo general logra un ratio de aproximación de $\frac{\beta}{\beta+1}$.
   • Optimización Submodular: Para resolver el subproblema orgánico (P.5) bajo restricciones complejas, los autores transforman el problema de secuenciación en un problema de selección de subconjuntos sobre un conjunto base de pares producto-posición. Demuestran que la función de utilidad resultante es monótona y submodular. Esto permite la aplicación de algoritmos de maximización submodular de vanguardia:
     • Para restricciones de mochila (knapsack), utilizan un algoritmo que logra un ratio $\beta = 1/(1+\epsilon)^3$.
     • Para restricciones de matroide de partición, utilizan un algoritmo que logra un ratio $\beta = 1/(2+\epsilon)$.

Contribuciones Clave

• Formulación del Problema: El artículo define formalmente el problema de planificación de surtidos en presencia de productos patrocinados con restricciones de posición específicas, un vacío identificado en la literatura existente que a menudo asume que todos los productos son orgánicos o ignora la integración de los patrocinados.
• Garantías Teóricas: A diferencia de trabajos previos que dependen de heurísticas de aprendizaje profundo sin límites teóricos (por ejemplo, Liao et al. 2022), este artículo proporciona garantías de aproximación rigurosas.
• Marco Algorítmico: Los autores desarrollan un marco que cierra la brecha entre la maximización de ingresos de la plataforma y las restricciones de los anunciantes. Demuestran que el problema básico es soluble en tiempo polinomial vía LP y proporcionan un algoritmo de aproximación de factor constante para la variante más compleja que involucra restricciones de capacidad o diversidad en los productos orgánicos.
• Prueba de Submodularidad: Una contribución técnica significativa es la prueba de que la función de utilidad transformada para la selección de productos orgánicos es submodular, lo que permite el uso de algoritmos de aproximación eficientes para restricciones NP-duras.

Resultados
El artículo establece los siguientes resultados teóricos:

• Para el problema básico (solo restricciones de patrocinados), se puede calcular un solución óptima de manera eficiente.
• Para el problema extendido (restricciones de patrocinados + restricciones de capacidad/matroide de productos orgánicos), el algoritmo propuesto logra un ratio de aproximación de:
  • $\frac{1}{(1+\epsilon)^3 + 1}$ para restricciones de mochila.
  • $\frac{1}{(2+\epsilon) + 1}$ para restricciones de matroide de partición.
  • (Nota: El artículo deriva el ratio final como $\frac{\beta}{\beta+1}$ donde $\beta$ es el ratio de aproximación del subproblema).

Significancia y Reivindicaciones
Los autores afirman que esta investigación aborda una brecha crítica en la literatura de planificación de surtidos al modelar explícitamente la integración de productos patrocinados. La significancia del trabajo reside en proporcionar garantías teóricas para soluciones que equilibran los objetivos, a menudo conflictivos, de las plataformas (maximización de ingresos) y los anunciantes (requisitos de colocación específicos). El artículo sostiene que su enfoque ofrece a las empresas un método para integrar productos patrocinados de manera fluida sin comprometer las estrategias de ingresos generales ni la experiencia del usuario, fundamentado en límites matemáticos demostrables en lugar de un rendimiento heurístico. El trabajo se presenta como un paso fundacional para futuras investigaciones en este ámbito evolutivo de los sistemas de recomendación de comercio electrónico.