💻 computer science

Assortment Planning with Sponsored Products

This paper addresses the research gap in assortment planning by formulating a combinatorial optimization problem that strategically integrates sponsored products to maximize expected revenue, moving beyond traditional models that only consider organic or non-sponsored items.

Original authors: Shaojie Tang, Shuzhang Cai, Jing Yuan, Kai Han

Published 2026-06-30

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Shaojie Tang, Shuzhang Cai, Jing Yuan, Kai Han

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are running a busy digital marketplace, like a giant online store. Your job is to decide which products to show a customer when they visit your site. This is called Assortment Planning.

In the past, this was like arranging items on a shelf where everything was just "regular" stock. But today, things have changed. Some products are Sponsored Products. Think of these as items that advertisers have paid extra money to have placed in specific, prime spots on your shelf.

The problem the authors tackle is a tricky balancing act: How do you arrange the shelf to make the most money overall, while also making sure the advertisers get the specific spots they paid for?

Here is a breakdown of their solution using simple analogies:

1. The Core Conflict: The "Paid Seats" vs. The "Best Sellers"

Imagine your website has a row of seats (positions) for products.

Organic Products: These are the regular items. You can put them anywhere, and you make a small commission if someone buys them.
Sponsored Products: These are the VIPs. An advertiser says, "I want my product in seat #1, #2, or #3." If you don't put them there, you lose their money. But if you put a boring product in seat #1 just to satisfy an advertiser, you might lose a customer who wanted to see a cool, popular item.

The authors realized that previous research mostly ignored these "VIP seats." They treated all products the same, which doesn't work in the real world.

2. The Strategy: Two Different Approaches

The authors created a mathematical "recipe" (an algorithm) to solve this. They realized that trying to solve the whole puzzle at once is too hard, so they broke it down into two simpler scenarios and then picked the best result.

Scenario A: The "VIP-Only" Plan
First, they asked: "What if we only focused on making the advertisers happy?"

They arranged the sponsored products in their required seats to maximize revenue from those specific deals.
They ignored the regular products for a moment.
Result: A plan that is great for the advertisers but might miss out on selling popular regular items.

Scenario B: The "Regular-First" Plan
Next, they asked: "What if we first put the 'VIPs' in the seats that annoy the system the least, and then fill the rest with the best regular products?"

They found a way to place the sponsored products in their required spots without "crowding out" too much value.
Then, they filled the remaining open spots with the best-selling organic products.
Result: A plan that maximizes sales from regular items while still satisfying the advertisers.

The Final Decision:
The algorithm compares these two plans. It doesn't just pick one; it calculates which one is likely to make more money and picks that one. They proved mathematically that this "pick the best of two worlds" approach is very close to the perfect, impossible-to-calculate solution.

3. The Rules of the Game (Constraints)

The paper also handles extra rules, which they call "constraints."

The Budget Constraint (Knapsack): Imagine you have a limited amount of shelf space or a budget for how many items you can show. You can't just show everything. The algorithm figures out the best mix of items that fits within that "backpack" size.
The Diversity Constraint (Fairness): Imagine you want to make sure you show at least one item from every category (e.g., one camera, one phone, one laptop). The algorithm ensures you don't just show 10 cameras and ignore the phones.

4. Why This Matters

The authors didn't just guess; they built a system with mathematical guarantees.

They proved that their method will always get you a result that is at least a certain percentage (very high) of the perfect possible revenue.
They showed that this works even when the rules get complicated (like having strict limits on how many items from each category you can show).

Summary

Think of this paper as a smart traffic controller for an online store.

Before: The controller only looked at the cars (products) and ignored the emergency vehicles (sponsored ads), causing chaos.
Now: The controller has a new system. It knows exactly where the emergency vehicles must go. It then calculates the best route for the rest of the traffic to ensure the road (the website) is as profitable as possible. It tries two different traffic patterns and picks the one that gets the most cars moving smoothly without blocking the emergency lanes.

The result is a system that helps online stores make more money while keeping their advertisers happy, all without needing a human to manually rearrange the shelves every time a new ad comes in.

Technical Summary: Assortment Planning with Sponsored Products

Problem Statement
This paper addresses the assortment planning problem in e-commerce and recommendation systems, specifically extending the scope to include sponsored products alongside traditional organic products. While prior research (e.g., Talluri and Van Ryzin 2004) has predominantly focused on organic products, the rise of sponsored placements (e.g., on Amazon, Facebook, Google) introduces a complex optimization challenge. The platform must select and position a set of $k$ products to maximize expected revenue while adhering to specific constraints imposed by advertisers.

The core difficulty lies in balancing the platform's revenue goals with the mandatory requirements of sponsored products. Unlike organic products, which can be placed in arbitrary positions, sponsored products often come with strict placement constraints derived from auction mechanisms (e.g., an advertiser bidding for "top- $m$ " positions or a specific slot based on quality scores). The problem is formulated as a combinatorial optimization task where the objective is to find a feasible sequence of products that maximizes expected revenue under the Multinomial Logit (MNL) choice model.

Methodology
The authors model the consumer choice behavior using the MNL model, where the probability of a consumer selecting product $i$ depends on its intrinsic utility at a specific position and the utilities of all other displayed products. The revenue function is non-linear due to the denominator in the choice probability, which includes the sum of utilities of all selected items.

The paper proposes a two-pronged algorithmic approach depending on the constraints:

Exact Solution for Basic Constraints:
When the only constraints are the mandatory placement of sponsored products (each sponsored product $i$ must be assigned to a valid position $t \in R_i$ ), the problem is formulated as an assignment problem. The authors demonstrate that the constraint matrix is totally unimodular. Consequently, the problem can be solved optimally by relaxing the integer constraints to a Linear Programming (LP) formulation, which is guaranteed to yield an integer solution.
Approximation Algorithm for Extended Constraints:
The paper extends the problem to include additional constraints on the selection of organic products, such as capacity (knapsack) constraints (total cost $\le C$ ) or partition matroid constraints (limits on the number of items from specific groups).
- Decomposition Strategy: The optimal solution is decomposed into two parts: revenue from sponsored products and revenue from organic products. The authors construct two candidate assortments:
  - Candidate I: Optimizes revenue considering only sponsored products (ignoring organic ones).
  - Candidate II: First minimizes the total weight (utility) of the sponsored products to "save" utility for the organic selection, then optimizes the assortment of organic products given the fixed sponsored selection.
- Randomized Selection: The final solution selects the better of the two candidates. Theoretical analysis shows that if the organic sub-problem (P.5) can be approximated within a ratio $\beta$ , the overall algorithm achieves an approximation ratio of $\frac{\beta}{\beta+1}$ .
- Submodular Optimization: To solve the organic sub-problem (P.5) under complex constraints, the authors transform the sequencing problem into a subset selection problem over a ground set of product-position pairs. They prove that the resulting utility function is monotone and submodular. This allows the application of state-of-the-art submodular maximization algorithms:
  - For knapsack constraints, they utilize an algorithm achieving a ratio of $\beta = 1/(1+\epsilon)^3$ .
  - For partition matroid constraints, they utilize an algorithm achieving a ratio of $\beta = 1/(2+\epsilon)$ .

Key Contributions

Problem Formulation: The paper formally defines the assortment planning problem in the presence of sponsored products with position-specific constraints, a gap identified in existing literature which often assumes all products are organic or ignores sponsored integration.
Theoretical Guarantees: Unlike previous works that rely on deep learning heuristics without theoretical bounds (e.g., Liao et al. 2022), this paper provides rigorous approximation guarantees.
Algorithmic Framework: The authors develop a framework that bridges the gap between platform revenue maximization and advertiser constraints. They prove that the basic problem is solvable in polynomial time via LP and provide a constant-factor approximation algorithm for the more complex variant involving capacity or diversity constraints on organic products.
Submodularity Proof: A significant technical contribution is the proof that the transformed utility function for the organic product selection is submodular, enabling the use of efficient approximation algorithms for NP-hard constraints.

Results
The paper establishes the following theoretical results:

For the basic problem (sponsored constraints only), an optimal solution can be computed efficiently.
For the extended problem (sponsored constraints + organic capacity/matroid constraints), the proposed algorithm achieves an approximation ratio of:
- $\frac{1}{(1+\epsilon)^3 + 1}$ for knapsack constraints.
- $\frac{1}{(2+\epsilon) + 1}$ for partition matroid constraints.
- (Note: The paper derives the final ratio as $\frac{\beta}{\beta+1}$ where $\beta$ is the approximation ratio of the sub-problem).

Significance and Claims
The authors claim that this research addresses a critical gap in assortment planning literature by explicitly modeling the integration of sponsored products. The significance of the work lies in providing theoretical guarantees for solutions that balance the often conflicting goals of platforms (revenue maximization) and advertisers (specific placement requirements). The paper asserts that its approach offers businesses a method to integrate sponsored products seamlessly without compromising overall revenue strategies or user experience, grounded in provable mathematical bounds rather than heuristic performance. The work is presented as a foundational step for future research in this evolving domain of e-commerce recommendation systems.