Assortment Planning with Sponsored Products

Sintesi Tecnica: Pianificazione dell'Assortimento con Prodotti Sponsorizzati

Enunciato del Problema
Questo articolo affronta il problema della pianificazione dell'assortimento nell'e-commerce e nei sistemi di raccomandazione, estendendo specificamente l'ambito per includere i prodotti sponsorizzati insieme ai tradizionali prodotti organici. Mentre la ricerca precedente (ad es. Talluri e Van Ryzin 2004) si è concentrata prevalentemente sui prodotti organici, l'ascesa dei posizionamenti sponsorizzati (ad es. su Amazon, Facebook, Google) introduce una complessa sfida di ottimizzazione. La piattaforma deve selezionare e posizionare un insieme di $k$ prodotti per massimizzare il ricavo atteso, rispettando al contempo specifici vincoli imposti dagli inserzionisti.

La difficoltà principale risiede nel bilanciare gli obiettivi di ricavo della piattaforma con i requisiti obbligatori dei prodotti sponsorizzati. A differenza dei prodotti organici, che possono essere collocati in posizioni arbitrarie, i prodotti sponsorizzati spesso comportano vincoli di posizionamento rigidi derivanti da meccanismi d'asta (ad es. un inserzionista che offre per le posizioni "top-$m$" o una specifica posizione basata su punteggi di qualità). Il problema è formulato come un compito di ottimizzazione combinatoria in cui l'obiettivo è trovare una sequenza di prodotti fattibile che massimizzi il ricavo atteso sotto il modello di scelta Multinomial Logit (MNL).

Metodologia
Gli autori modellano il comportamento di scelta del consumatore utilizzando il modello MNL, dove la probabilità che un consumatore selezioni il prodotto $i$ dipende dalla sua utilità intrinseca in una specifica posizione e dalle utilità di tutti gli altri prodotti visualizzati. La funzione di ricavo è non lineare a causa del denominatore nella probabilità di scelta, che include la somma delle utilità di tutti gli articoli selezionati.

Il documento propone un approccio algoritmico a due fronti a seconda dei vincoli:

1. Soluzione Esatta per Vincoli di Base:
   Quando l'unico vincolo è il posizionamento obbligatorio dei prodotti sponsorizzati (ogni prodotto sponsorizzato $i$ deve essere assegnato a una posizione valida $t \in R_i$), il problema viene formulato come un problema di assegnazione. Gli autori dimostrano che la matrice dei vincoli è totalmente unimodulare. Di conseguenza, il problema può essere risolto in modo ottimale rilassando i vincoli interi a una formulazione di Programmazione Lineare (LP), che garantisce di ottenere una soluzione intera.

2. Algoritmo di Approssimazione per Vincoli Estesi:
   Il documento estende il problema includendo ulteriori vincoli sulla selezione dei prodotti organici, come i vincoli di capacità (knapsack) (costo totale $\le C$) o i vincoli di partizione matroid (limiti sul numero di articoli da gruppi specifici).

   • Strategia di Decomposizione: La soluzione ottimale è decomposta in due parti: il ricavo dai prodotti sponsorizzati e il ricavo dai prodotti organici. Gli autori costruiscono due assortimenti candidati:
     • Candidato I: Ottimizza il ricavo considerando solo i prodotti sponsorizzati (ignorando quelli organici).
     • Candidato II: Minimizza prima il peso totale (utilità) dei prodotti sponsorizzati per "risparmiare" utilità per la selezione organica, poi ottimizza l'assortimento dei prodotti organici data la selezione fissa degli sponsorizzati.
   • Selezione Casuale: La soluzione finale seleziona il migliore tra i due candidati. L'analisi teorica mostra che se il sottoproblema organico (P.5) può essere approssimato con un rapporto $\beta$, l'algoritmo complessivo raggiunge un rapporto di approssimazione $\frac{\beta}{\beta+1}$.
   • Ottimizzazione Submodulare: Per risolvere il sottoproblema organico (P.5) sotto vincoli complessi, gli autori trasformano il problema di sequenziamento in un problema di selezione di un sottoinsieme su un insieme fondamentale di coppie prodotto-posizione. Dimostrano che la funzione di utilità risultante è monotona e submodulare. Ciò consente l'applicazione di algoritmi di massimizzazione submodulare all'avanguardia:
     • Per i vincoli knapsack, utilizzano un algoritmo che raggiunge un rapporto $\beta = 1/(1+\epsilon)^3$.
     • Per i vincoli di partizione matroid, utilizzano un algoritmo che raggiunge un rapporto $\beta = 1/(2+\epsilon)$.

Contributi Chiave

• Formulazione del Problema: Il documento definisce formalmente il problema della pianificazione dell'assortimento in presenza di prodotti sponsorizzati con vincoli di posizione specifici, un vuoto identificato nella letteratura esistente che spesso assume che tutti i prodotti siano organici o ignora l'integrazione degli sponsorizzati.
• Garanzie Teoriche: A differenza di lavori precedenti che si affidano ad euristiche di deep learning senza limiti teorici (ad es. Liao et al. 2022), questo articolo fornisce rigorose garanzie di approssimazione.
• Framework Algoritmico: Gli autori sviluppano un framework che colma il divario tra la massimizzazione del ricavo della piattaforma e i vincoli degli inserzionisti. Dimostrano che il problema di base è risolvibile in tempo polinomiale tramite LP e forniscono un algoritmo di approssimazione a fattore costante per la variante più complessa che coinvolge vincoli di capacità o di diversità sui prodotti organici.
• Dimostrazione della Submodularità: Un contributo tecnico significativo è la dimostrazione che la funzione di utilità trasformata per la selezione dei prodotti organici è submodulare, consentendo l'uso di algoritmi di approssimazione efficienti per vincoli NP-hard.

Risultati
Il documento stabilisce i seguenti risultati teorici:

• Per il problema di base (solo vincoli sponsorizzati), una soluzione ottimale può essere calcolata efficientemente.
• Per il problema esteso (vincoli sponsorizzati + vincoli di capacità/matroid organici), l'algoritmo proposto raggiunge un rapporto di approssimazione di:
  • $\frac{1}{(1+\epsilon)^3 + 1}$ per i vincoli knapsack.
  • $\frac{1}{(2+\epsilon) + 1}$ per i vincoli di partizione matroid.
  • (Nota: il documento deriva il rapporto finale come $\frac{\beta}{\beta+1}$ dove $\beta$ è il rapporto di approssimazione del sottoproblema).

Significato e Rivendicazioni
Gli autori affermano che questa ricerca affronta una lacuna critica nella letteratura sulla pianificazione dell'assortimento, modellando esplicitamente l'integrazione dei prodotti sponsorizzati. La significatività del lavoro risiede nel fornire garanzie teoriche per soluzioni che bilanciano gli obiettivi spesso conflittuali delle piattaforme (massimizzazione del ricavo) e degli inserzionisti (requisiti di posizionamento specifici). Il documento asserisce che il suo approccio offre alle imprese un metodo per integrare i prodotti sponsorizzati in modo fluido senza compromettere le strategie di ricavo complessive o l'esperienza dell'utente, basandosi su limiti matematici dimostrabili piuttosto che sulle prestazioni euristiche. Il lavoro è presentato come un passo fondamentale per la ricerca futura in questo ambito in evoluzione dei sistemi di raccomandazione dell'e-commerce.