Assortment Planning with Sponsored Products

Technisches Resümee: Sortimentsplanung mit gesponserten Produkten

Problemstellung
Diese Arbeit befasst sich mit dem Problem der Sortimentsplanung im E-Commerce und in Empfehlungssystemen und erweitert dabei den Fokus auf die Einbeziehung von gesponserten Produkten neben herkömmlichen organischen Produkten. Während die bisherige Forschung (z. B. Talluri und Van Ryzin 2004) sich überwiegend auf organische Produkte konzentriert hat, führt der Aufstieg gesponserter Platzierungen (z. B. auf Amazon, Facebook, Google) eine komplexe Optimierungsherausforderung ein. Die Plattform muss eine Menge von $k$ Produkten auswählen und positionieren, um den erwarteten Umsatz zu maximieren, während sie gleichzeitig spezifische, von Werbetreibenden auferlegte Beschränkungen einhält.

Die Kernschwierigkeit liegt darin, die Umsatzziele der Plattform mit den verbindlichen Anforderungen der gesponserten Produkte in Einklang zu bringen. Im Gegensatz zu organischen Produkten, die in beliebigen Positionen platziert werden können, sind gesponserte Produkte oft mit strengen Platzierungsbeschränkungen behaftet, die aus Auktionsmechanismen resultieren (z. B. ein Werbetreibender, der für „Top-$m$“-Positionen oder eine spezifische Slot basierend auf Qualitätswerten bietet). Das Problem wird als kombinatorische Optimierungsaufgabe formuliert, bei der das Ziel darin besteht, eine zulässige Sequenz von Produkten zu finden, die den erwarteten Umsatz unter dem Multinomial Logit (MNL)-Wahlmodell maximiert.

Methodik
Die Autoren modellieren das Konsumentenwahlverhalten mithilfe des MNL-Modells, wobei die Wahrscheinlichkeit, dass ein Konsument Produkt $i$ wählt, von dessen intrinsischem Nutzen an einer spezifischen Position und den Nutzen aller anderen angezeigten Produkte abhängt. Die Umsatzfunktion ist aufgrund des Nenners in der Auswahlwahrscheinlichkeit, der die Summe der Nutzen aller ausgewählten Artikel enthält, nichtlinear.

Die Autoren schlagen einen zweigleisigen algorithmischen Ansatz vor, der je nach den Beschränkungen variiert:

1. Exakte Lösung für Basiskonstraints:
   Wenn die einzige Beschränkung die obligatorische Platzierung gesponserter Produkte ist (jedes gesponserte Produkt $i$ muss einer gültigen Position $t \in R_i$ zugewiesen werden), wird das Problem als Zuweisungsproblem formuliert. Die Autoren zeigen, dass die Beschränkungsmatrix total unimodular ist. Folglich kann das Problem optimal durch die Relaxierung der ganzzahligen Beschränkungen auf eine Lineare Programmierung (LP) gelöst werden, was garantiert eine ganzzahlige Lösung liefert.

2. Approximationsalgorithmus für erweiterte Beschränkungen:
   Das Paper erweitert das Problem um zusätzliche Beschränkungen für die Auswahl organischer Produkte, wie etwa Kapazitätsbeschränkungen (Knapsack-Constraints) (Gesamtkosten $\le C$) oder Partitionsmatroiden-Beschränkungen (Limits für die Anzahl von Artikeln aus spezifischen Gruppen).

   • Dekompositionsstrategie: Die optimale Lösung wird in zwei Teile zerlegt: Umsatz aus gesponserten Produkten und Umsatz aus organischen Produkten. Die Autoren konstruieren zwei Kandidatensortimente:
     • Kandidat I: Optimiert den Umsatz unter Berücksichtigung nur der gesponserten Produkte (unter Vernachlässigung der organischen Produkte).
     • Kandidat II: Minimiert zuerst den Gesamtnutzen (Weight) der gesponserten Produkte, um Nutzen für die organische Auswahl zu „sparen“, und optimiert dann das Sortiment der organischen Produkte unter der gegebenen fixen Auswahl der gesponserten Produkte.
   • Randomisierte Auswahl: Die endgültige Lösung wählt den besseren der beiden Kandidaten. Die theoretische Analyse zeigt, dass, wenn das organische Teilproblem (P.5) innerhalb eines Verhältnisses $\beta$ approximiert werden kann, der Gesamtalgorithmus ein Approximationsverhältnis von $\frac{\beta}{\beta+1}$ erreicht.
   • Submodulare Optimierung: Um das organische Teilproblem (P.5) unter komplexen Beschränkungen zu lösen, transformieren die Autoren das Sequenzierungsproblem in ein Teilmengen-Auswahlsproblem über eine Grundmenge von Produkt-Positions-Paaren. Sie beweisen, dass die resultierende Nutzenfunktion monoton und submodular ist. Dies ermöglicht die Anwendung modernster Algorithmen zur Submodul-Maximierung:
     • Für Knapsack-Beschränkungen nutzen sie einen Algorithmus, der ein Verhältnis von $\beta = 1/(1+\epsilon)^3$ erreicht.
     • Für Partitionsmatroiden-Beschränkungen nutzen sie einen Algorithmus, der ein Verhältnis von $\beta = 1/(2+\epsilon)$ erreicht.

Zentrale Beiträge

• Problemformulierung: Das Paper definiert formal das Sortimentsplanungsproblem in der Präsenz von gesponserten Produkten mit positionsspezifischen Beschränkungen – eine Lücke, die in der bestehenden Literatur identifiziert wurde, da diese oft entweder nur organische Produkte annimmt oder die Integration gesponserter Produkte ignoriert.
• Theoretische Garantien: Im Gegensatz zu früheren Arbeiten, die sich auf Deep-Learning-Heuristiken ohne theoretische Grenzen verlassen (z. B. Liao et al. 2022), liefert dieses Paper rigorose Approximationsgarantien.
• Algorithmischer Rahmen: Die Autoren entwickeln einen Rahmen, der die Lücke zwischen der Umsatzmaximierung der Plattform und den Anforderungen der Werbetreibenden schließt. Sie beweisen, dass das Basisszenario mittels LP in Polynomialzeit lösbar ist, und liefern einen Approximationsalgorithmus mit konstantem Faktor für die komplexere Variante mit Kapazitäts- oder Diversitätsbeschränkungen für organische Produkte.
• Beweis der Submodularität: Ein bedeutender technischer Beitrag ist der Beweis, dass die transformierte Nutzenfunktion für die Auswahl organischer Produkte submodular ist, was die Verwendung effizienter Approximationsalgorithmen für NP-schwere Beschränkungen ermöglicht.

Ergebnisse
Das Paper etabliert die folgenden theoretischen Ergebnisse:

• Für das Basisszenario (nur gesponserte Beschränkungen) kann eine optimale Lösung effizient berechnet werden.
• Für das erweiterte Szenario (gesponserte Beschränkungen + organische Kapazitäts-/Matroidenbeschränkungen) erreicht der vorgeschlagene Algorithmus ein Approximationsverhältnis von:
  • $\frac{1}{(1+\epsilon)^3 + 1}$ für Knapsack-Beschränkungen.
  • $\frac{1}{(2+\epsilon) + 1}$ für Partitionsmatroiden-Beschränkungen.
  • (Hinweis: Das Paper leitet das endgültige Verhältnis als $\frac{\beta}{\beta+1}$ ab, wobei $\beta$ das Approximationsverhältnis des Teilproblems ist).

Bedeutung und Ansprüche
Die Autoren behaupten, dass diese Forschung eine kritische Lücke in der Sortimentsplanungs-Literatur schließt, indem sie die Integration gesponserter Produkte explizit modelliert. Die Bedeutung der Arbeit liegt in der Bereitstellung von theoretischen Garantien für Lösungen, die die oft gegensätzlichen Ziele von Plattformen (Umsatzmaximierung) und Werbetreibenden (spezifische Platzierungsanforderungen) in Einklang bringen. Das Paper postuliert, dass sein Ansatz Unternehmen eine Methode bietet, gesponserte Produkte nahtlos zu integrieren, ohne die allgemeine Umsatzstrategie oder das Nutzererlebnis zu gefährden, gestützt auf beweisbare mathematische Grenzen statt auf heuristische Leistung. Die Arbeit wird als grundlegender Schritt für die zukünftige Forschung in diesem sich entwickelnden Bereich der E-Commerce-Empfehlungssysteme präsentiert.