Assortment Planning with Sponsored Products

Résumé Technique : Planification de l'Assortiment avec Produits Sponsorisés

Énoncé du Problème
Cet article traite du problème de la planification de l'assortiment dans le commerce électronique et les systèmes de recommandation, en étendant spécifiquement la portée pour inclure les produits sponsorisés aux côtés des produits organiques traditionnels. Alors que les recherches antérieures (par exemple, Talluri et Van Ryzin 2004) se sont principalement concentrées sur les produits organiques, l'essor des placements sponsorisés (par exemple, sur Amazon, Facebook, Google) introduit un défi d'optimisation complexe. La plateforme doit sélectionner et positionner un ensemble de $k$ produits afin de maximiser les revenus attendus tout en respectant des contraintes spécifiques imposées par les annonceurs.

La difficulté principale réside dans l'équilibre entre les objectifs de revenus de la plateforme et les exigences obligatoires des produits sponsorisés. Contrairement aux produits organiques, qui peuvent être placés dans des positions arbitraires, les produits sponsorisés s'accompagnent souvent de contraintes de placement strictes dérivées de mécanismes d'enchères (par exemple, un annonceur misant pour les positions "top-$m$" ou un créneau spécifique basé sur des scores de qualité). Le problème est formulé comme une tâche d'optimisation combinatoire où l'objectif est de trouver une séquence de produits réalisable qui maximise le revenu attendu sous le modèle de choix Multinomial Logit (MNL).

Méthodologie
Les auteurs modélisent le comportement de choix des consommateurs à l'aide du modèle MNL, où la probabilité qu'un consommateur sélectionne le produit $i$ dépend de son utilité intrinsèque à une position spécifique et des utilités de tous les autres produits affichés. La fonction de revenu est non linéaire en raison du dénominateur dans la probabilité de choix, qui inclut la somme des utilités de tous les articles sélectionnés.

Le papier propose une approche algorithmique à deux volets selon les contraintes :

1. Solution Exacte pour les Contraintes de Base :
   Lorsque la seule contrainte est le placement obligatoire des produits sponsorisés (chaque produit sponsorisé $i$ doit être assigné à une position valide $t \in R_i$), le problème est formulé comme un problème d'assignation. Les auteurs démontrent que la matrice de contrainte est totalement unimodulaire. Par conséquent, le problème peut être résolu de manière optimale en relaxant les contraintes entières vers une formulation de Programmation Linéaire (LP), ce qui garantit l'obtention d'une solution entière.

2. Algorithme d'Approximation pour les Contraintes Étendues :
   L'article étend le problème pour inclure des contraintes supplémentaires sur la sélection des produits organiques, telles que des contraintes de capacité (sac à dos) (coût total $\le C$) ou des contraintes de matroid de partition (limites sur le nombre d'articles provenant de groupes spécifiques).

   • Stratégie de Décomposition : La solution optimale est décomposée en deux parties : le revenu des produits sponsorisés et le revenu des produits organiques. Les auteurs construisent deux assortiments candidats :
     • Candidat I : Optimise le revenu en considérant uniquement les produits sponsorisés (en ignorant les produits organiques).
     • Candidat II : Minimise d'abord le poids total (utilité) des produits sponsorisés pour "économiser" de l'utilité pour la sélection organique, puis optimise l'assortiment des produits organiques étant donné la sélection fixe des produits sponsorisés.
   • Sélection Aléatoire : La solution finale sélectionne le meilleur des deux candidats. L'analyse théorique montre que si le sous-problème organique (P.5) peut être approximé avec un ratio $\beta$, l'algorithme global atteint un ratio d'approximation de $\frac{\beta}{\beta+1}$.
   • Optimisation Sous-modulaire : Pour résoudre le sous-problème organique (P.5) sous des contraintes complexes, les auteurs transforment le problème de séquençage en un problème de sélection d'un sous-ensemble sur un ensemble de base de paires produit-position. Ils prouvent que la fonction d'utilité résultante est monotone et sous-modulaire. Cela permet l'application d'algorithmes de maximisation sous-modulaire de pointe :
     • Pour les contraintes de sac à dos (knapsack), ils utilisent un algorithme atteignant un ratio de $\beta = 1/(1+\epsilon)^3$.
     • Pour les contraintes de matroid de partition, ils utilisent un algorithme atteignant un ratio de $\beta = 1/(2+\epsilon)$.

Principales Contributions

• Formulation du Problème : Le papier définit formellement le problème de planification de l'assortiment en présence de produits sponsorisés avec des contraintes de position spécifiques, une lacune identifiée dans la littérature existante qui suppose souvent que tous les produits sont organiques ou ignore l'intégration des sponsorisés.
• Garanties Théoriques : Contrairement aux travaux précédents qui reposent sur des heuristiques d'apprentissage profond sans bornes théoriques (par exemple, Liao et al. 2022), cet article fournit des garanties d'approximation rigoureuses.
• Cadre Algorithmique : Les auteurs développent un cadre qui comble le fossé entre la maximisation des revenus de la plateforme et les contraintes des annonceurs. Ils prouvent que le problème de base est soluble en temps polynomial via la LP et fournissent un algorithme d'approximation à facteur constant pour la variante plus complexe impliquant des contraintes de capacité ou de diversité sur les produits organiques.
• Preuve de Sous-modularité : Une contribution technique significative est la preuve que la fonction d'utilité transformée pour la sélection de produits organiques est sous-modulaire, permettant l'utilisation d'algorithmes d'approximation efficaces pour les contraintes NP-difficiles.

Résultats
Le papier établit les résultats théoriques suivants :

• Pour le problème de base (contraintes de produits sponsorisés uniquement), une solution optimale peut être calculée efficacement.
• Pour le problème étendu (contraintes de produits sponsorisés + contraintes de capacité/matroid des produits organiques), l'algorithme proposé atteint un ratio d'approximation de :
  • $\frac{1}{(1+\epsilon)^3 + 1}$ pour les contraintes de sac à dos.
  • $\frac{1}{(2+\epsilon) + 1}$ pour les contraintes de matroid de partition.
  • (Note : le papier dérive le ratio final comme étant $\frac{\beta}{\beta+1}$ où $\beta$ est le ratio d'approximation du sous-problème).

Signification et Revendications
Les auteurs affirment que cette recherche répond à une lacune critique dans la littérature de la planification de l'assortiment en modélisant explicitement l'intégration des produits sponsorisés. La signification du travail réside dans la fourniture de garanties théoriques pour des solutions qui équilibrent les objectifs souvent conflictuels des plateformes (maximisation des revenus) et des annonceurs (exigences de placement spécifiques). Le papier affirme que son approche offre aux entreprises une méthode pour intégrer les produits sponsorisés de manière transparente sans compromettre les stratégies globales de revenus ou l'expérience utilisateur, en s'appuyant sur des limites mathématiques prouvables plutôt que sur des performances heuristiques. Le travail est présenté comme une étape fondamentale pour la recherche future dans ce domaine évolutif des systèmes de recommandation du commerce électronique.