Assortment Planning with Sponsored Products

Technische Samenvatting: Assortimentplanning met Gesponsorde Producten

Probleemstelling
Dit artikel behandelt het assortimentplanningprobleem in e-commerce en aanbevelingssystemen, waarbij de reikwijdte specifiek wordt uitgebreid naar de inclusie van gesponsorde producten naast traditionele organische producten. Terwijl eerder onderzoek (bijv. Talluri en Van Ryzin 2004) zich voornamelijk heeft gericht op organische producten, introduceert de opkomst van gesponsorde plaatsingen (bijv. op Amazon, Facebook, Google) een complexe optimalisatieuitdaging. Het platform moet een set van $k$ producten selecteren en positioneren om de verwachte omzet te maximaliseren, terwijl het voldoet aan specifieke beperkingen opgelegd door adverteerders.

De kern van de moeilijkheid ligt in het balanceren van de omzetdoelstellingen van het platform met de verplichte vereisten van gesponsorde producten. In tegenstelling tot organische producten, die in willekeurige posities kunnen worden geplaatst, gaan gesponsorde producten vaak gepaard met strikte plaatsingsbeperkingen afgeleid van veilingmechanismen (bijv. een adverteerder die biedt voor "top-$m$" posities of een specifie�itore op basis van kwaliteitsscores). Het probleem wordt geformuleerd als een combinatorische optimalisatietaak waarbij het doel is om een haalbare sequentie van producten te vinden die de verwachte omzet maximaliseert onder het Multinomial Logit (MNL) keuzemodel.

Methodologie
De auteurs modelleren het consumentengedrag met behulp van het MNL-model, waarbij de waarschijnlijkheid dat een consument product $i$ selecteert afhangt van de intrinsieke bruikbaarheid (utility) op een specifieke positie en de bruikbaarheid van alle andere getoonde producten. De omzetafunctie is niet-lineair vanwege de noemer in de keuzekans, die de som van de bruikbaarheden van alle geselecteerde items bevat.

Het artikel stelt een tweeledige algoritmische aanpak voor, afhankelijk van de beperkingen:

1. Exacte Oplossing voor Basale Beperkingen:
   Wanneer de enige beperking de verplichte plaatsing van gesponsorde producten is (elk gesponsord product $i$ moet worden toegewezen aan een geldige positie $t \in R_i$), wordt het probleem geformuleerd als een toewijzingsprobleem. De auteurs tonen aan dat de beperkingsmatrix totaal unimodulair is. Bijgevolg kan het probleem optimaal worden opgelost door de gehele-getallenbeperkingen te relaxeren naar een Lineair Programmerings (LP) formulering, die gegarandeerd een geheel getal als oplossing oplevert.

2. Benaderingsalgoritme voor Uitgebreide Beperkingen:
   Het artikel breidt het probleem uit door aanvullende beperkingen op de selectie van organische producten op te nemen, zoals capaciteit (knapsack) beperkingen (totale kosten $\le C$) of partitie-matroïde beperkingen (limieten op het aantal items uit specifieke groepen).

   • Decompositiestrategie: De optimale oplossing wordt opgedeeld in twee delen: omzet uit gesponsorde producten en omzet uit organische producten. De auteurs construeren twee kandidaat-assortimenten:
     • Kandidaat I: Optimaliseert de omzet met alleen gesponsorde producten in overweging (organische producten negerend).
     • Kandidaat II: Minimaliseert eerst de totale gewicht (bruikbaarheid) van de gesponsorde producten om bruikbaarheid te "besparen" voor de organische selectie, en optimaliseert vervolgens het assortiment van organische producten gegeven de vaste gesponsorde selectie.
   • Randomized Selectie: De uiteindelijke oplossing selecteert de betere van de twee kandidaten. Theoretische analyse toont aan dat als het organische subprobleem (P.5) binnen een ratio $\beta$ kan worden benaderd, het algemene algoritme een benaderingsratio van $\frac{\beta}{\beta+1}$ bereikt.
   • Submodulaire Optimalisatie: Om het organische subprobleem (P.5) onder complexe beperkingen op te lossen, transformeren de auteurs het sequentiële probleem in een deelverzameling-selectieprobleem over een grondverzameling van product-positie paren. Zij bewijzen dat de resulterende bruikbaarheidsfunctie monotoon en submodulair is. Dit maakt de toepassing van state-of-the-art submodulaire maximalisatie-algoritmen mogelijk:
     • Voor knapsack-beperkingen maken zij gebruik van een algoritme dat een ratio bereikt van $\beta = 1/(1+\epsilon)^3$.
     • Voor partitie-matroïde beperkingen maken zij gebruik van een algoritme dat een ratio bereikt van $\beta = 1/(2+\epsilon)$.

Belangrijkste Bijdragen

• Probleemformulering: Het artikel definieert formeel het assortimentplanningprobleem in de aanwezigheid van gesponsorde producten met positie-specifieke beperkingen, een gat geïdentificeerd in de bestaande literatuur die vaak ervan uitgaat dat alle producten organisch zijn of de integratie van gesponsorde producten negeert.
• Theoretische Garanties: In tegenstelling tot eerder werk dat vertrouwt op deep learning heuristieken zonder theoretische grenzen (bijv. Liao et al. 2022), biedt dit artikel rigoureuze benaderingsgaranties.
• Algoritmisch Kader: De auteurs ontwikkelen een kader dat de kloof overbrugt tussen platformomzetmaximalisatie en adverteerdersbeperkingen. Zij bewijzen dat het basale probleem in polynomiale tijd oplosbaar is via LP en bieden een constante-factor benaderingsalgoritme voor de complexere variant met capaciteits- of diversiteitsbeperkingen op organische producten.
• Submodulariteit Bewijs: Een belangrijke technische bijdrage is het bewijs dat de getransformeerde bruikbaarheidsfunctie voor de selectie van organische producten submodulair is, wat het gebruik van efficiënte benaderingsalgoritmen voor NP-harde beperkingen mogelijk maakt.

Resultaten
Het artikel stelt de volgende theoretische resultaten vast:

• Voor het basale probleem (alleen gesponsorde beperkingen), kan een optimale oplossing efficiënt worden berekend.
• Voor het uitgebreide probleem (gesponsorde beperkingen + organische capaciteits-/matroïde beperkingen), bereikt het voorgestelde algoritme een benaderingsratio van:
  • $\frac{1}{(1+\epsilon)^3 + 1}$ voor knapsack-beperkingen.
  • $\frac{1}{(2+\epsilon) + 1}$ voor partitie-matroïde beperkingen.
  • (Noot: het artikel leidt de uiteindelijke ratio af als $\frac{\beta}{\beta+1}$ waarbij $\beta$ de benaderingsratio van het subprobleem is).

Betekenis en Claims
De auteurs beweren dat dit onderzoek een kritiek gat in de literatuur over assortimentplanning aanpakt door de integratie van gesponsorde producten expliciet te modelleren. De betekenis van het werk ligt in het bieden van theoretische garanties voor oplossingen die de vaak conflicterende doelen van platforms (omzetmaximalisatie) en adverteerders (specifieke plaatsingseisen) in balans brengen. Het artikel stelt dat hun aanpak bedrijven een methode biedt om gesponsorde producten naadloos te integreren zonder de algehele omzetstrategie of gebruikerservaring in gevaar te brengen, gebaseerd op bewijsbare wiskundige grenzen in plaats van heuristische prestaties. Het werk wordt gepresenteerd als een fundamentele stap voor toekomstig onderzoek in dit evoluerende domein van e-commerce aanbevelingssystemen.